TL;DR
This paper introduces a novel "Two-Stage Accelerated Coordinate Descent" (TS-APCG) algorithm that significantly speeds up optimization for problems with low-dimensional solutions (like sparse or low-rank data). They also propose an adaptive version that automatically tunes itself, removing the need for manual parameter tuning.
What Problem Does This Paper Address?
Many machine learning tasks involve minimizing a complex objective function, often with regularization to encourage desirable properties in the solution (e.g., sparsity for feature selection). While accelerated coordinate descent methods are efficient, they typically assume strong convexity, which doesn't hold for many common regularizers. This paper addresses the challenge of achieving fast, structure-adaptive convergence for these non-strongly convex problems, where the solution's inherent low-dimensional structure (like sparsity) is key. Existing methods often fail to fully exploit this structure, leading to slower convergence.
Methods
The core contribution is the Two-Stage APCG (TS-APCG) algorithm. It operates in two stages:
- Warm-starting: A standard, non-strongly-convex APCG is run for a limited number of iterations to get close to the solution.
- Structure-Exploiting Stage: This stage leverages the "Restricted Strong Convexity" (RSC) framework, which captures the low-dimensional structure of the solution. The algorithm then converges at an accelerated linear rate with respect to this structure.
Two options are presented for the second stage:
- Option 1: Periodically restarts the non-strongly-convex APCG.
- Option 2: Uses a specific momentum parameter and restart strategy.
Crucially, they also introduce an adaptive variant of TS-APCG. This adaptive version estimates the RSC parameter on-the-fly, eliminating the need for prior knowledge or grid search, which is a significant practical advantage.
Datasets
The paper evaluates their methods on the following datasets for Lasso regression:
- MADELON+
- MARTI2
- RCV1
- NEWS20
For the Madelon dataset, they augmented it with 3500 additional random features.
Key Insights and Ideas
- Structure is Power: The paper strongly emphasizes that exploiting the low-dimensional structure of the solution (e.g., sparsity) is not just an academic curiosity but a direct path to significantly faster convergence in optimization.
- Two-Stage Approach: The idea of a "warm-start" phase followed by a structure-aware phase is a clever way to bridge the gap between general optimization and exploiting specific problem properties.
- Adaptive Tuning is Practical: The adaptive variant is a major practical win. Manual tuning of parameters like the Restricted Strong Convexity (RSC) parameter is often difficult or impossible in real-world scenarios. An algorithm that learns this on the fly is much more user-friendly and robust.
- RSC as a Bridge: The Restricted Strong Convexity (RSC) framework is shown to be a powerful tool for analyzing and achieving structure-adaptive convergence rates.
Key Results
- Accelerated Linear Convergence: The TS-APCG algorithm achieves a local accelerated linear convergence rate that scales with the intrinsic dimension (e.g., sparsity) of the solution. This is a significant improvement over standard methods.
- Adaptive Variant Performance: The adaptive TS-APCG demonstrates comparable or superior performance to its non-adaptive counterpart, even outperforming other state-of-the-art methods like Katyusha on several datasets.
- Effectiveness on Sparse Problems: Numerical experiments on Lasso regression (a problem inherently favoring sparse solutions) show that TS-APCG and its adaptive variant significantly outperform the standard non-strongly-convex APCG.
Limitations and Future Work
- Non-Blowout Assumption: Option 2 of the TS-APCG relies on a "non-blowout" assumption for the iterates, which has not been theoretically proven for accelerated coordinate descent. The authors provide it as a relaxed assumption.
- Computational Overhead: The adaptive variant requires calculating a composite gradient map, which introduces some computational overhead compared to the non-adaptive version. However, this overhead is deemed manageable due to the restart period.
- Future Directions: The authors suggest several promising avenues:
- Incorporating importance sampling for better iteration complexity.
- Using screening rules to skip updates for zero-elements in sparse problems.
- Exploring continuation methods for faster initial convergence.
- Investigating the interplay between primal and dual coordinate descent methods for different dataset characteristics.
Summary updated