Linearization Algorithms for Fully Composite Optimization
This provides new optimization algorithms for a subclass of non-differentiable problems, which is incremental but practically useful for applications where linear minimization oracles can be efficiently implemented.
The paper tackles fully composite optimization problems by developing first-order algorithms that handle differentiable and non-differentiable components separately, linearizing only smooth parts. It introduces generalizations of Frank-Wolfe and Conditional Gradient Sliding methods with global convergence rates for convex and non-convex objectives, and an accelerated method with improved complexity for convex cases.
This paper studies first-order algorithms for solving fully composite optimization problems over convex and compact sets. We leverage the structure of the objective by handling its differentiable and non-differentiable components separately, linearizing only the smooth parts. This provides us with new generalizations of the classical Frank-Wolfe method and the Conditional Gradient Sliding algorithm, that cater to a subclass of non-differentiable problems. Our algorithms rely on a stronger version of the linear minimization oracle, which can be efficiently implemented in several practical applications. We provide the basic version of our method with an affine-invariant analysis and prove global convergence rates for both convex and non-convex objectives. Furthermore, in the convex case, we propose an accelerated method with correspondingly improved complexity. Finally, we provide illustrative experiments to support our theoretical results.