Efficient Generalized Conditional Gradient with Gradient Sliding for Composite Optimization

Yiu-ming Cheung, Jian Lou

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:

  1. 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).
  2. 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.

Performance comparison of GCG vs GCG-GS across four biological datasets. GCG-GS consistently reaches lower objective values in less CPU time.

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.

Sensitivity analysis of the number of inner loops (m) on convergence across different datasets.

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

Abstract

Generalized conditional gradient method has regained increasing research interest as an alternative to another popular proximal gradient method for sparse optimization problems. For particular tasks, its low computation cost of linear subproblem evaluation on each iteration leads to superior practical performance. However, the inferior iteration complexity incurs excess number of gradient evaluations, which can counteract the efficiency gained by solving low cost linear subproblem. In this paper, we therefore propose a novel algorithm that requires optimal graduate evaluations as proximal gradient. We also present a refined variant for a type of gauge regularized problem where approximation techniques are allowed to further accelerate linear subproblem computation. Experiments of CUR-like matrix factorization problem with group lasso penalty on four real-world datasets demonstrate the efficiency of the proposed method.
BibTeX
@inproceedings{cheung2015efficient,
  author = {Yiu-ming Cheung and Jian Lou},
  title = {{Efficient Generalized Conditional Gradient with Gradient Sliding for Composite Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure