New analysis and results for the Frank-Wolfe method
From MaRDI portal
Publication:5962717
DOI10.1007/S10107-014-0841-6zbMATH Open1342.90101arXiv1307.0873OpenAlexW2076095618MaRDI QIDQ5962717FDOQ5962717
Authors: Robert M. Freund, Paul Grigas 
Publication date: 23 February 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We present new results for the Frank-Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps and the so-called FW gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.
Full work available at URL: https://arxiv.org/abs/1307.0873
Recommendations
conditional gradient methodFrank-Wolfe methodcomputational guaranteesstep-size rulesduality/bound gaps
Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)
Cites Work
- Smooth minimization of non-smooth functions
- Introductory lectures on convex optimization. A basic course.
- Primal-dual subgradient methods for convex problems
- Title not available (Why is that?)
- Smooth Optimization with Approximate Gradient
- First-order methods of smooth convex optimization with inexact oracle
- Rounding of Polytopes in the Real Number Model of Computation
- Conditional gradient algorithms with open loop step size rules
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Sparse Approximate Solutions to Semidefinite Programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The gap function of a convex program
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Title not available (Why is that?)
- A new perspective on boosting in linear regression via subgradient optimization and relatives
- Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
- Optimizing over the growing spectrahedron
Cited In (48)
- Restarting Frank-Wolfe: faster rates under Hölderian error bounds
- Gradient Projection and Conditional Gradient Methods for Constrained Nonconvex Minimization
- Avoiding bad steps in Frank-Wolfe variants
- A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization
- Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems
- First-order methods for convex optimization
- Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Conditional gradient method without line-search
- On the Convergence of a Greedy Algorithm for the Solution of the Problem for the Construction of Monotone Regression
- Robust matrix estimations meet Frank-Wolfe algorithm
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
- Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Statistical computational learning
- 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
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Inexact variable metric method for convex-constrained optimization problems
- Universal Conditional Gradient Sliding for Convex Optimization
- Alternating conditional gradient method for convex feasibility problems
- A generalized Frank-Wolfe method with ``dual averaging for strongly convex composite optimization
- Some comments on Wolfe's ‘away step’
- On the global convergence of an inexact quasi-Newton conditional gradient method for constrained nonlinear systems
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion
- Technical Note—Dynamic Data-Driven Estimation of Nonparametric Choice Models
- Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
- Filtering with State-Observation Examples via Kernel Monte Carlo Filter
- Generalized Conditional Gradient for Sparse Estimation
- Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Duality gap estimates for a class of greedy optimization algorithms in Banach spaces
- An adaptive partial linearization method for optimization problems on product sets
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- Simplified versions of the conditional gradient method
- Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Robust Analysis in Stochastic Simulation: Computation and Performance Guarantees
- Near-optimal coresets of kernel density estimates
- Perturbed Fenchel duality and first-order methods
- Conditional gradient sliding for convex optimization
- Title not available (Why is that?)
- Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
- Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
- 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
This page was built for publication: New analysis and results for the Frank-Wolfe method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962717)
