Universal Conditional Gradient Sliding for Convex Optimization

DOI10.1137/21M1406234MaRDI QIDQ6071883zbMATH OpenFDO

Authors Yuyuan Ouyang, Trevor Squires

Publication date 29 November 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.11026

zbMATH Keywords

conditional gradient methodconditional gradient slidingconvex optimizationfirst-order methoduniversal gradient method

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Convex programming (90C25)

Abstract: In this paper, we present a first-order projection-free method, namely, the universal conditional gradient sliding (UCGS) method, for solving $varepsilon$-approximate solutions to convex differentiable optimization problems. For objective functions with H"older continuous gradients, we show that UCGS is able to terminate with $varepsilon$-solutions with at most $O((M_u{D}_X^{1+u}/varepsilon{)}^{2/(1+3u)})$ gradient evaluations and $O((M_u{D}_X^{1+u}/varepsilon{)}^{4/(1+3u)})$ linear objective optimizations, where $uin(0,1]$ and $M_u>0$ are the exponent and constant of the H"older condition. Furthermore, UCGS is able to perform such computations without requiring any specific knowledge of the smoothness information $u$ and $M_u$. In the weakly smooth case when $uin(0,1)$, both complexity results improve the current state-of-the-art $O((M_u{D}_X^{1+u}/varepsilon{)}^{1/u})$ results on first-order projection-free method achieved by the conditional gradient method. Within the class of sliding-type algorithms, to the best of our knowledge, this is the first time a sliding-type algorithm is able to improve not only the gradient complexity but also the overall complexity for computing an approximate solution. In the smooth case when $u=1$, UCGS matches the state-of-the-art complexity result but adds more features allowing for practical implementation.

Recommendations

• Conditional gradient sliding for convex optimization
• Projection-free accelerated method for convex optimization
• Universal intermediate gradient method for convex problems with inexact oracle
• Universal gradient methods for convex optimization problems
• Gradient sliding for composite optimization

Cites work

• Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
• Complexity bounds for primal-dual methods minimizing the model of objective function
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• Conditional gradient sliding for convex optimization
• Conditional gradient type methods for composite nonlinear and stochastic optimization
• Convex optimization: algorithms and complexity
• Fast bundle-level methods for unconstrained and ball-constrained convex optimization
• First-order and stochastic optimization methods for machine learning
• First-order methods in optimization
• First-order methods of smooth convex optimization with inexact oracle
• Gradient sliding for composite optimization
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 3293978 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Lectures on convex optimization
• New analysis and results for the Frank-Wolfe method
• On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Universal gradient methods for convex optimization problems

This page was built for publication: Universal Conditional Gradient Sliding for Convex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071883)