# Linearization Algorithms for Fully Composite Optimization

arXiv: https://arxiv.org/abs/2302.12808 · HTML: https://mlsanity.com/paper/2302.12808/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 24 Feb 2023.

## Builds on (most cited first, 27 of 27)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Conditional Gradient Methods](https://mlsanity.com/paper/2211.14103/) (2022)
- [Convergence guarantees for a class of non-convex and non-smooth optimization problems](https://mlsanity.com/paper/1804.09629/) (2018)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Non-convex Conditional Gradient Sliding](https://mlsanity.com/paper/1708.04783/) (2017)
- [Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier](https://mlsanity.com/paper/2010.08999/) (2020)
- [Composite Difference-Max Programs for Modern Statistical Estimation Problems](https://mlsanity.com/paper/1803.00205/) (2018)
- [Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization](https://mlsanity.com/paper/2002.07290/) (2020)
- [Boosting Frank-Wolfe by Chasing Gradients](https://mlsanity.com/paper/2003.06369/) (2020)
- [Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/1906.07867/) (2019)
- [A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guarantees](https://mlsanity.com/paper/1708.06714/) (2017)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularization](https://mlsanity.com/paper/1404.3591/) (2014)
- [A study of convex convex-composite functions via infimal convolution with applications](https://mlsanity.com/paper/1907.08318/) (2019)
- [The multiproximal linearization method for convex composite problems](https://mlsanity.com/paper/1712.02623/) (2017)
- [Accelerating Frank-Wolfe via Averaging Step Directions](https://mlsanity.com/paper/2205.11794/) (2022)

## Built on by (most cited first, 2 of 2)

- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)
- [Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe](https://mlsanity.com/paper/2605.15350/) (2026)

## 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.