Abstract
In this work we explore the fundamental structure-adaptiveness of state of the art randomized first order algorithms on regularized empirical risk minimization tasks, where the solution has intrinsic low-dimensional structure (such as sparsity and low-rank). Such structure is often enforced by non-smooth regularization or constraints. We start by establishing the fast linear convergence rate of the SAGA algorithm on non-strongly-convex objectives with convex constraints, via an argument of cone-restricted strong convexity. Then for the composite minimization task with a coordinate-wise separable convex regularization term, we propose and analyse a two stage accelerated coordinate descend algorithm (Two-Stage APCG). We provide the convergence analysis showing that the proposed method has a global convergence in general and enjoys a local accelerated linear convergence rate with respect to the low-dimensional structure of the solution. Then based on this convergence result, we proposed an adaptive variant of the two-stage APCG method which does not need to foreknow the restricted strong convexity beforehand, but estimate it on the fly. In numerical experiments we compare the adaptive two-stage APCG with various state of the art variance-reduced stochastic gradient methods on sparse regression tasks, and demonstrate the effectiveness of our approach.
Introduction
Modern machine learning frequently involves solving "composite minimization" problems, such as Lasso regression, where the goal is to minimize a loss function plus a regularizer that enforces a specific structure, like sparsity. Standard optimization theory suggests that linear convergence is only guaranteed if the objective function is globally strongly convex. However, in high-dimensional settings where the number of features ($d$) significantly exceeds the number of samples ($n$), global strong convexity is rarely present.
This paper addresses the gap by leveraging Restricted Strong Convexity (RSC). RSC implies that while a function may not be globally strongly convex, it behaves as such in directions pointing toward the structured solution. While researchers have long recognized that RSC can lead to faster convergence, most existing accelerated algorithms require prior knowledge of the RSC parameters—a requirement that is often impossible to meet in practice.
Geometric Intuition: Structure as a Proxy for Stability
The core insight of this research is that non-smooth regularizers (like the $L_1$ norm) do more than just produce sparse solutions; they effectively restrict the optimization search space into a low-dimensional cone where the problem becomes significantly more stable.
As shown in the figure above, the geometry of the constraint set $\mathcal{K}$ or the regularizer creates a cone $\mathcal{C}_{x^*}$ around the optimal solution $x^*$. Within this cone, the objective function exhibits the stability necessary for accelerated convergence.
Methodology: Two-Stage APCG and Adaptive Estimation
The authors propose a novel framework to exploit this local stability through three key developments:
- SAGA Analysis: They prove that SAGA, a popular variance-reduced gradient method, automatically adapts to RSC in constrained problems, achieving linear convergence without manual intervention.
- Two-Stage APCG: They introduce a two-stage approach for coordinate descent. Stage 1 utilizes a version of APCG designed for non-strongly convex functions to reach the "neighborhood" of the solution. Stage 2 then switches to an accelerated linear rate by exploiting local RSC once the algorithm has identified the low-dimensional structure of the solution.
- Adaptive Estimation: To make the algorithm practical, the authors developed a heuristic to estimate the RSC parameter ($\mu_c$) on the fly. By monitoring the "composite gradient map," the algorithm dynamically adjusts its estimate: if progress slows, it decreases $\mu_c$; if progress is rapid, it increases the estimate to further accelerate.
Experimental Results
The proposed adaptive algorithm was evaluated on sparse regression (Lasso) tasks using several real-world datasets: YearPredictionMSD, REGED (genomics), Madelon (synthetic), and MARTI2.
The experiments yielded several key insights:
- Superior Speed: On the REGED and Million Song datasets, the Adaptive Two-Stage APCG significantly outperformed state-of-the-art methods, including SVRG and Katyusha, which is often considered the gold standard for accelerated stochastic gradients.
- Phase Transition: A clear "phase transition" was observed. When the regularization parameter $\lambda$ is large (resulting in high sparsity), the proposed method is drastically faster. As $\lambda$ decreases and the solution becomes less sparse, the advantage diminishes, eventually matching standard accelerated methods.
- Robustness: The adaptive heuristic successfully estimated the hidden $\mu_c$ across different datasets without manual tuning, demonstrating that structure-adaptiveness can be effectively automated.
Conclusion and Future Work
This work demonstrates that stochastic optimization algorithms can be made "structure-adaptive," allowing them to achieve accelerated linear convergence even without global strong convexity. While the current focus is on coordinate-wise separable regularizers (like $L_1$), future research could extend these principles to more complex structures, such as nuclear norms for low-rank matrices. Additionally, developing a more rigorous, provably adaptive scheme for the stochastic case remains a valuable goal for the field.
Summary updated