Stochastic Optimization for DC Functions and Non-smooth Non-convex\n Regularizers with Non-asymptotic Convergence

Yi Xu, Qi Qi, Qihang Lin, Rong Jin, Tianbao Yang

Abstract

Difference of convex (DC) functions cover a broad family of non-convex and possibly non-smooth and non-differentiable functions, and have wide applications in machine learning and statistics. Although deterministic algorithms for DC functions have been extensively studied, stochastic optimization that is more suitable for learning with big data remains under-explored. In this paper, we propose new stochastic optimization algorithms and study their first-order convergence theories for solving a broad family of DC functions. We improve the existing algorithms and theories of stochastic optimization for DC functions from both practical and theoretical perspectives. On the practical side, our algorithm is more user-friendly without requiring a large mini-batch size and more efficient by saving unnecessary computations. On the theoretical side, our convergence analysis does not necessarily require the involved functions to be smooth with Lipschitz continuous gradient. Instead, the convergence rate of the proposed stochastic algorithm is automatically adaptive to the Hölder continuity of the gradient of one component function. Moreover, we extend the proposed stochastic algorithms for DC functions to solve problems with a general non-convex non-differentiable regularizer, which does not necessarily have a DC decomposition but enjoys an efficient proximal mapping. To the best of our knowledge, this is the first work that gives the first non-asymptotic convergence for solving non-convex optimization whose objective has a general non-convex non-differentiable regularizer.

Introduction

In modern machine learning and statistics, objective functions often exhibit complex, non-convex, and non-smooth structures. A particularly flexible framework for these problems is the Difference of Convex (DC) decomposition, where the objective is represented as $f(x) = g(x) - h(x)$, with both $g$ and $h$ being convex functions. This structure encompasses a wide range of applications, from weakly convex functions to robust learning models and deep neural networks with specific activation functions.

While deterministic algorithms for DC problems are well-established, they struggle to scale to the "big data" regime. Existing stochastic DC algorithms often face significant practical hurdles, such as requiring extremely high precision in sub-problem solutions or massive mini-batch sizes to manage gradient variance. Furthermore, most theoretical guarantees rely on strict Lipschitz continuity assumptions that do not always hold in practice. This paper introduces the Stagewise Stochastic DC (SSDC) algorithm to bridge these gaps, providing a framework that is both theoretically robust and practically efficient.

The SSDC Algorithm Framework

The core of the SSDC approach is a "divide and conquer" strategy that transforms the complex DC problem into a sequence of manageable convex sub-problems. The algorithm proceeds through several key steps:

  1. Convex Majorization: At each stage, the algorithm constructs a convex majorant by linearizing the $h(x)$ component and adding a quadratic regularization term to ensure stability.
  2. Stagewise Solving: Rather than solving the entire problem at once, SSDC solves a sequence of these convex sub-problems. Crucially, the required accuracy for these sub-problems increases gradually, allowing for significant computational savings in the early stages of optimization.
  3. Modular Sub-solvers: The framework is designed to be modular, supporting various stochastic "engines" such as Stochastic Proximal Gradient (SPG), AdaGrad (for adaptive learning rates), or SVRG (for finite-sum problems).
  4. Handling General Regularizers: To address non-convex, non-smooth regularizers (like $\ell_0$ or $\ell_p$ norms) that lack an obvious DC decomposition, the authors employ the Moreau envelope. This transformation smooths the regularizer, allowing it to be integrated into the DC framework.

Theoretical Convergence and Complexity

A major contribution of this work is the first non-asymptotic convergence guarantee for problems involving general non-convex, non-smooth regularizers. Unlike previous methods that require massive mini-batches to satisfy theoretical bounds, SSDC remains efficient and user-friendly.

Furthermore, the convergence analysis is adaptive to Hölder continuity. This means the algorithm's performance automatically adjusts to the actual smoothness of the function, rather than relying on a worst-case global Lipschitz constant. The complexity results for various configurations of the SSDC algorithm are summarized below.

Complexity analysis of SSDC variants across different function classes and sub-problem solvers.

Experimental Evaluation

The authors evaluated the SSDC framework on several large-scale datasets, including real-sim, rcv1, and million songs, representing high-dimensional classification and regression challenges. The results demonstrate several key advantages:

  • Efficiency: SSDC-AdaGrad and SSDC-SVRG converged significantly faster than deterministic baselines like GIST and GPPA across all datasets.
  • Stability: The stagewise approach provided much more stable descent compared to standard SGD, particularly when dealing with non-smooth losses such as hinge or absolute loss.
  • State-of-the-Art Performance: In Positive-Unlabeled (PU) learning tasks, SSDC variants outperformed existing specialized algorithms like AdaSPD, achieving lower objective values with fewer gradient computations.

Conclusion

The SSDC algorithm provides a powerful and flexible framework for stochastic DC optimization. By eliminating the need for massive mini-batches and providing the first non-asymptotic convergence rates for general non-convex regularizers, this work makes complex non-smooth optimization more accessible for large-scale machine learning applications. Future work may focus on further improving the dependence on the number of data points ($n$) in variance-reduced variants and extending the Moreau envelope approach to broader deterministic settings.

Summary updated

Abstract

Difference of convex (DC) functions cover a broad family of non-convex and\npossibly non-smooth and non-differentiable functions, and have wide\napplications in machine learning and statistics. Although deterministic\nalgorithms for DC functions have been extensively studied, stochastic\noptimization that is more suitable for learning with big data remains\nunder-explored. In this paper, we propose new stochastic optimization\nalgorithms and study their first-order convergence theories for solving a broad\nfamily of DC functions. We improve the existing algorithms and theories of\nstochastic optimization for DC functions from both practical and theoretical\nperspectives. On the practical side, our algorithm is more user-friendly\nwithout requiring a large mini-batch size and more efficient by saving\nunnecessary computations. On the theoretical side, our convergence analysis\ndoes not necessarily require the involved functions to be smooth with Lipschitz\ncontinuous gradient. Instead, the convergence rate of the proposed stochastic\nalgorithm is automatically adaptive to the H\\"{o}lder continuity of the\ngradient of one component function. Moreover, we extend the proposed stochastic\nalgorithms for DC functions to solve problems with a general non-convex\nnon-differentiable regularizer, which does not necessarily have a DC\ndecomposition but enjoys an efficient proximal mapping. To the best of our\nknowledge, this is the first work that gives the first non-asymptotic\nconvergence for solving non-convex optimization whose objective has a general\nnon-convex non-differentiable regularizer.\n
BibTeX
@inproceedings{xu2019stochastic,
  author = {Yi Xu and Qi Qi and Qihang Lin and Rong Jin and Tianbao Yang},
  title = {{Stochastic Optimization for DC Functions and Non-smooth Non-convex\textbackslash\{\}n Regularizers with Non-asymptotic Convergence}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=SyNpLo-OWr},
}
Figure