Abstract
Stochastic Dual Coordinate Ascent (SDCA) is a cornerstone algorithm for large-scale optimization in machine learning. However, traditional convergence analysis typically requires the objective function to be strongly convex—a condition not met by many popular statistical models such as Lasso, Group Lasso, or non-convex M-estimators like SCAD. In this paper, we demonstrate that SDCA achieves linear convergence under a more relaxed condition known as Restricted Strong Convexity (RSC). We further introduce a dual-free variant of SDCA capable of handling general regularization terms, bridging the gap between efficient optimization and high-dimensional statistical estimation.
Introduction
In modern statistics and machine learning, Empirical Risk Minimization (ERM) is the standard framework for model training. We seek to minimize a loss function combined with a regularizer to ensure model generalizability and sparsity. Stochastic Dual Coordinate Ascent (SDCA) has emerged as a preferred method for these problems due to its scalability and fast convergence properties.
Despite its practical success, SDCA's theoretical guarantees have historically been limited. Standard proofs for linear convergence—where the error decreases geometrically—rely on the assumption of strong convexity. This poses a problem for high-dimensional statistics, where the number of features ($p$) often exceeds the number of samples ($n$). In such regimes, the loss functions for models like Lasso or Logistic Regression with $\ell_1$ penalties are not strongly convex. Consequently, it was previously believed that SDCA might only achieve sublinear convergence rates for these critical applications. This work refutes that notion, proving that SDCA is significantly more efficient in statistical settings than once thought.
Methodology
Restricted Strong Convexity (RSC)
The core of our analysis lies in the Restricted Strong Convexity (RSC) property. Unlike global strong convexity, RSC only requires the objective function to behave like a strongly convex function on a restricted set of directions—specifically, those corresponding to the sparse structures we expect to find in high-dimensional data. By leveraging RSC, we show that SDCA can maintain a linear convergence rate even when the global objective is only convex or even non-convex.
Dual-Free SDCA Formulation
Traditional SDCA requires the derivation of a dual objective, which can be mathematically cumbersome for complex or non-convex regularizers. To address this, we utilize a "dual-free" version of the algorithm. To handle the lack of strong convexity, we employ a stabilization technique: adding a strongly convex quadratic term to the regularization while simultaneously subtracting it from the loss function. This transformation preserves the original problem's global optimum while providing the algorithm with the necessary curvature to maintain high-speed convergence.
Experimental Setup
We validated our theoretical findings through extensive testing on both synthetic and real-world datasets:
- Synthetic Benchmarks: We generated data to test Lasso, Group Lasso, Corrected Lasso (designed for noisy covariates), and the non-convex SCAD regularizer.
- Real-World Data:
- rcv1 & sido0: Benchmarks for sparse classification using Logistic Regression with $\ell_1$ regularization.
- IJCNN1: Used for sparse regression tasks.
- Boston Housing: Utilized for evaluating Group Lasso performance.
Key Insights and Results
Geometric Convergence Rates
Our analysis proves that for models like Lasso and Group Lasso, the objective gap $F(w_k) - F(\hat{w})$ decreases at a linear rate of $O((1-\eta\lambda)^t)$. This was confirmed experimentally, where SDCA demonstrated geometric error reduction consistent with our theoretical bounds.
Robustness to Non-Convexity
One of the most significant findings is SDCA's performance on non-convex problems. By using the dual-free formulation under RSC conditions, SDCA successfully navigates the landscapes of Corrected Lasso and SCAD, reaching global optima with linear efficiency. This suggests that SDCA is a robust choice even for non-convex M-estimators.
The Statistical Limit
We observe that SDCA converges linearly until it reaches the "statistical limit" of the problem—the point where optimization error is smaller than the inherent noise level of the data. Beyond this threshold, further optimization does not improve generalization performance. This highlights that SDCA is optimally suited for statistical tasks where reaching the noise floor is the primary goal.
Comparison with State-of-the-Art
In head-to-head comparisons, SDCA performed as well as or better than other variance-reduced stochastic methods, such as SVRG and SAGA. Furthermore, SDCA showed remarkable independence from the condition number of the data, maintaining efficiency across varying levels of feature correlation and sparsity.
Conclusion and Future Work
This work provides a new theoretical foundation for SDCA in high-dimensional statistics. By proving linear convergence under RSC, we justify the use of SDCA for a much broader class of models than previously supported.
However, some limitations remain. The linear convergence regime depends on having a sufficient sample size ($n \gtrsim s \log p$) to satisfy the RSC condition. Additionally, the dual-free approach requires careful selection of the stabilization parameter $\tilde{\lambda}$. Future research will focus on automated parameter tuning and exploring how other structured data properties can be exploited to further accelerate stochastic optimization algorithms.
Summary updated