New analysis and results for the Frank-Wolfe method

DOI10.1007/s10107-014-0841-6zbMath1342.90101arXiv1307.0873OpenAlexW2076095618MaRDI QIDQ5962717

Robert M. Freund, Paul Grigas

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

computational guaranteesconditional gradient methodduality/bound gapsFrank-Wolfe methodstep-size rules

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

Related Items

Technical Note—Dynamic Data-Driven Estimation of Nonparametric Choice Models, Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators, Inexact variable metric method for convex-constrained optimization problems, A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm, Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning, New results on subgradient methods for strongly convex optimization problems with a unified analysis, Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications, Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets, On the global convergence of an inexact quasi-Newton conditional gradient method for constrained nonlinear systems, Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier, An adaptive partial linearization method for optimization problems on product sets, Universal Conditional Gradient Sliding for Convex Optimization, Near-optimal coresets of kernel density estimates, Affine Invariant Convergence Rates of the Conditional Gradient Method, A unified analysis of stochastic gradient‐free Frank–Wolfe methods, Asymptotic linear convergence of fully-corrective generalized conditional gradient methods, No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization, Robust matrix estimations meet Frank-Wolfe algorithm, Perturbed Fenchel duality and first-order methods, A generalized Frank-Wolfe method with ``dual averaging for strongly convex composite optimization, First-order methods for convex optimization, Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems, An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion, A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization, Filtering with State-Observation Examples via Kernel Monte Carlo Filter, On the Convergence of a Greedy Algorithm for the Solution of the Problem for the Construction of Monotone Regression, Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, Frank-Wolfe and friends: a journey into projection-free first-order optimization methods, Conditional gradient method without line-search, Simplified versions of the conditional gradient method, Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints, Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization, Complexity bounds for primal-dual methods minimizing the model of objective function, Alternating conditional gradient method for convex feasibility problems, Conditional Gradient Sliding for Convex Optimization, Robust Analysis in Stochastic Simulation: Computation and Performance Guarantees, Gradient Projection and Conditional Gradient Methods for Constrained Nonconvex Minimization, Unnamed Item, Scalable Robust Matrix Recovery: Frank--Wolfe Meets Proximal Methods, Generalized Conditional Gradient for Sparse Estimation, Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces, Restarting Frank-Wolfe: faster rates under Hölderian error bounds, Duality gap estimates for a class of greedy optimization algorithms in Banach spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual subgradient methods for convex problems
• Smooth minimization of non-smooth functions
• First-order methods of smooth convex optimization with inexact oracle
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• A new perspective on boosting in linear regression via subgradient optimization and relatives
• The gap function of a convex program
• Conditional gradient algorithms with open loop step size rules
• Introductory lectures on convex optimization. A basic course.
• Optimizing over the Growing Spectrahedron
• Smooth Optimization with Approximate Gradient
• Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
• Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
• Rounding of Polytopes in the Real Number Model of Computation
• Sparse Approximate Solutions to Semidefinite Programs