Linearization Algorithms for Fully Composite Optimization
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 27 of its 55 references that are in the map. First posted on arXiv 24 Feb 2023.
Builds on
27 of 55 references.
References · 27
- 2021Convex optimizationcited by 2,479
- 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
- 2021Multi-Objective Bayesian Optimization over High-Dimensional Search Spacescited by 87
- 2020Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimizationcited by 60
- 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 59
- 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
- 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
- 2013The Complexity of Large-scale Convex Programming under a Linear Optimization Oraclecited by 27
- 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
- 2017Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrievalcited by 24
- 2021Complexity of Linear Minimization and Projection on Some Setscited by 19
- 2020Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Methodcited by 17
15 more
- 2022Conditional Gradient Methodscited by 16
- 2018Convergence guarantees for a class of non-convex and non-smooth optimization problemscited by 15
- 2018A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programmingcited by 14
- 2017Non-convex Conditional Gradient Slidingcited by 12
- 2020Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barriercited by 11
- 2018Composite Difference-Max Programs for Modern Statistical Estimation Problemscited by 10
- 2020Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimizationcited by 10
- 2020Boosting Frank-Wolfe by Chasing Gradientscited by 9
- 2019Locally Accelerated Conditional Gradientscited by 8
- 2017A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guaranteescited by 5
- 2021Parameter-free Locally Accelerated Conditional Gradientscited by 5
- 2014Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularizationcited by 3
- 2019A study of convex convex-composite functions via infimal convolution with applicationscited by 3
- 2017The multiproximal linearization method for convex composite problemscited by 2
- 2022Accelerating Frank-Wolfe via Averaging Step Directionscited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.