Introduction
In modern machine learning, many problems are formulated as composite optimization tasks: $\min F(x) = l(x) + r(x)$. Here, $l(x)$ typically represents a smooth loss function, such as least squares, while $r(x)$ is a non-smooth regularizer like the $\ell_1$ norm or trace norm.
Practitioners often face a dilemma between two primary algorithmic families:
- Proximal Gradient (PG) Methods: These offer optimal convergence rates regarding gradient evaluations. However, each step requires a "Proximal Map," which can be computationally prohibitive for complex regularizers (e.g., requiring a full Singular Value Decomposition).
- Generalized Conditional Gradient (GCG) Methods: These utilize a "Linear Operator" (LO) that is significantly cheaper per iteration. The trade-off is a slower convergence rate, necessitating many more expensive gradient evaluations of the loss function.
This paper introduces GCG-GS, an algorithm designed to bridge this gap by combining the cheap subproblems of GCG with the optimal gradient efficiency of PG.
The GCG-GS Algorithm: Gradient Sliding
The core innovation of GCG-GS is the "Gradient Sliding" technique. Traditionally, optimization algorithms compute a new gradient for every subproblem. GCG-GS decouples these two processes using an outer and inner loop structure.
In the outer loop, the algorithm calculates the gradient of the smooth loss function. This gradient is then passed to an inner loop—a Conditional Gradient-style subroutine—which performs multiple iterations without re-calculating the gradient. This "sliding" mechanism allows the method to achieve $O(1/\sqrt{\epsilon})$ gradient evaluations (matching accelerated PG) while maintaining $O(1/\epsilon)$ linear operator calls (matching GCG).
Refined GCG-GS for Gauge Regularizers
For regularizers that can be expressed as gauge functions (such as norms), the authors provide a refined version of GCG-GS. This version utilizes polar operators and approximation techniques to solve linear subproblems even faster. To ensure stability despite these approximations, the algorithm returns a weighted average of the inner iterates, providing theoretical convergence guarantees even when duality gaps are difficult to compute.
Experimental Evaluation
The authors evaluated GCG-GS on a CUR-like matrix factorization task with a group lasso penalty. Testing was conducted across four biological datasets: SRBCT, Brain Tumor 2, 9 Tumor, and Leukemia.
As shown in the performance plots above, GCG-GS significantly outperforms the state-of-the-art GCG-TUM algorithm. The proposed method requires far fewer gradient evaluations to reach the same objective function value, leading to substantial savings in total CPU time.
Parameter Sensitivity
A critical aspect of GCG-GS is the number of inner iterations ($m$). The authors found that this parameter is remarkably easy to tune. Sensitivity analysis across all four datasets indicates that setting $m=3$ consistently yields superior performance.
Conclusion
GCG-GS effectively decouples gradient complexity from subproblem complexity, offering a robust solution for large-scale composite optimization where gradient computation is expensive. While the current work focuses on general convex problems, the authors suggest that extending these principles to strongly convex cases is a promising avenue for future research. Additionally, the inclusion of heuristic "Improve" steps allows for domain-specific optimizations that can further accelerate convergence in practical applications.
Summary updated