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

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

TL;DR

This paper introduces the first stochastic optimization algorithms with non-asymptotic convergence guarantees for a broad class of non-convex problems, specifically those involving Difference of Convex (DC) functions and non-smooth, non-convex regularizers. By using a stagewise approach (SSDC) that solves a sequence of convex approximations, the authors provide a practical and theoretically sound way to scale complex non-convex optimization to "big data" regimes.

Introduction: The Challenge of Non-Convex Optimization

Many machine learning models rely on non-convex optimization, which is notoriously difficult to solve efficiently. A particularly powerful framework is Difference of Convex (DC) programming, where the objective is written as $f(x) = g(x) - h(x)$ (with $g$ and $h$ being convex). This covers everything from "weakly convex" functions to deep neural network components.

While deterministic algorithms for DC problems have existed since the 1980s, they don't scale well to massive datasets because they require processing all data points at every step. Stochastic Optimization (SO) is the standard for big data, but existing SO methods for DC functions either lacked "non-asymptotic" theory (meaning we didn't know exactly how many iterations were needed to reach a certain accuracy) or were restricted to very specific, smooth cases. Furthermore, handling non-smooth, non-convex regularizers (like the $\ell_0$ norm or SCAD) within a stochastic framework remained a significant challenge.

The Stagewise Stochastic DC (SSDC) Framework

The authors propose the Stagewise Stochastic DC (SSDC) algorithm. The core idea is to break the hard non-convex problem into a series of easier convex subproblems.

  1. Convex Majorants: At each stage $k$, the algorithm constructs a convex "majorant" function that upper-bounds the true objective. It does this by linearizing the "$-h(x)$" part of the DC function.
  2. Inexact Solving: Unlike previous methods that required solving these subproblems to extreme precision (which is expensive), SSDC allows for "inexact" solutions. The accuracy requirement grows slowly over stages, making the early stages very fast.
  3. Flexible Sub-solvers: The framework is modular. Depending on the problem structure, one can use different stochastic solvers for the subproblems:
  4. SSDC-SPG: For general non-smooth cases.
  5. SSDC-AdaGrad: An adaptive version that automatically adjusts to the geometry of the data.
  6. SSDC-SVRG: Uses variance reduction for faster convergence when the functions are smooth.
  7. The Moreau Envelope Trick: To handle general non-smooth, non-convex regularizers $r(x)$ that aren't easily written as $g-h$, the authors use the "Moreau envelope." This mathematical transformation turns a nasty non-convex function into a DC function, allowing it to be solved using the SSDC framework.

Key Insights and Ideas

  • Bridging the Gap: This is the first work to provide non-asymptotic convergence rates for stochastic optimization with general non-convex, non-smooth regularizers.
  • Efficiency through Inexactness: A major "aha" moment is that you don't need to solve the intermediate convex subproblems perfectly. By carefully controlling the "error budget" of each stage, you can maintain global convergence while drastically reducing computation time.
  • Adaptive Theory: The authors showed that their AdaGrad variant is "automatically adaptive" to the Hölder continuity of the function. In plain English: the algorithm figures out how smooth the problem is on the fly and adjusts its speed accordingly, without the user needing to tune complex parameters.
  • Generality: The framework isn't just for DC functions; it's shown to be a "super-set" that covers weakly convex functions and many popular sparse regularizers used in statistics.

Empirical and Theoretical Results

The algorithms were evaluated on several large-scale datasets from the LIBSVM repository, including real-sim ($n=72,309$), rcv1 ($n=20,242$), and Million Songs ($n=463,715$). These datasets were used to test various models, including logistic regression with SCAD penalties, Huber loss with MCP penalties, and non-linear least squares with $\ell_0$ regularization.

Theoretical Complexity: The paper establishes concrete iteration complexities. For example, to find an $\epsilon$-critical point in a non-smooth DC problem, SSDC-SPG requires $O(1/\epsilon^4)$ iterations, which matches the best-known rates for simpler classes of non-convex problems.

Convergence of SSDC-SPG and SSDC-AdaGrad compared to SGD and AdaSPD on standard DC problems.

Empirical Performance: In head-to-head tests against deterministic baselines (like GIST and GPPA) and prior stochastic methods (like SMM and SDCA), the SSDC family consistently converged faster and reached lower objective values, especially on the largest datasets.

Comparison of SSDC algorithms against baselines on logistic regression with SCAD penalty and Huber loss with MCP penalty.

AdaGrad Advantage: As seen in the figures above, SSDC-AdaGrad was particularly effective, often outperforming the standard stochastic proximal gradient method. This confirms that adaptive step sizes are highly beneficial even in the DC optimization context.

Limitations and Future Work

  • First-Order Only: The convergence guarantees are for "stationary points" (places where the gradient is zero). Like most non-convex optimization papers, it does not guarantee finding the global minimum, which remains an open challenge for these complex functions.
  • Proximal Mapping Requirement: The method for general non-convex regularizers relies on having an efficient "proximal mapping" (a specific type of sub-optimization). While many common regularizers have this, it isn't universal.
  • Hyperparameter Tuning: While the theory is robust, the "stagewise" nature introduces parameters (like the number of iterations per stage) that may still require some empirical tuning for peak performance in new applications.

Summary updated

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. Altho...
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 Regularizers with Non-asymptotic Convergence}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=SyNpLo-OWr},
}
Figure