Linearization Algorithms for Fully Composite Optimization

Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, Nicolas Flammarion
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3669-3695, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-vladarean23a, title = {Linearization Algorithms for Fully Composite Optimization}, author = {Vladarean, Maria-Luiza and Doikov, Nikita and Jaggi, Martin and Flammarion, Nicolas}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3669--3695}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/vladarean23a/vladarean23a.pdf}, url = {https://proceedings.mlr.press/v195/vladarean23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Linearization Algorithms for Fully Composite Optimization %A Maria-Luiza Vladarean %A Nikita Doikov %A Martin Jaggi %A Nicolas Flammarion %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-vladarean23a %I PMLR %P 3669--3695 %U https://proceedings.mlr.press/v195/vladarean23a.html %V 195 %X 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.
APA
Vladarean, M., Doikov, N., Jaggi, M. & Flammarion, N.. (2023). Linearization Algorithms for Fully Composite Optimization. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3669-3695 Available from https://proceedings.mlr.press/v195/vladarean23a.html.

Related Material