New analysis and results for the Frank-Wolfe method
From MaRDI portal
Publication:5962717
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 5764862 (Why is no real title available?)
- scientific article; zbMATH DE number 3293978 (Why is no real title available?)
- scientific article; zbMATH DE number 3345848 (Why is no real title available?)
- A new perspective on boosting in linear regression via subgradient optimization and relatives
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient algorithms with open loop step size rules
- Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
- First-order methods of smooth convex optimization with inexact oracle
- Introductory lectures on convex optimization. A basic course.
- Optimizing over the growing spectrahedron
- Primal-dual subgradient methods for convex problems
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Rounding of Polytopes in the Real Number Model of Computation
- Smooth Optimization with Approximate Gradient
- Smooth minimization of non-smooth functions
- Sparse Approximate Solutions to Semidefinite Programs
- The gap function of a convex program
Cited in
(56)- Frank-Wolfe-type methods for a class of nonconvex inequality-constrained problems
- Using Taylor-approximated gradients to improve the Frank-Wolfe method for empirical risk minimization
- Statistical computational learning
- Scalable Frank-Wolfe on generalized self-concordant functions via simple steps
- Duality gap estimates for a class of greedy optimization algorithms in Banach spaces
- Perturbed Fenchel duality and first-order methods
- Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
- Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm
- Alternating conditional gradient method for convex feasibility problems
- A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization
- Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
- Quadratures over graphs via the Frank-Wolfe method and its variant
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- A unified analysis of stochastic gradient‐free Frank–Wolfe methods
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- A generalized Frank-Wolfe method with ``dual averaging for strongly convex composite optimization
- A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- Generalized conditional gradient for sparse estimation
- Inexact variable metric method for convex-constrained optimization problems
- Restarting Frank-Wolfe: faster rates under Hölderian error bounds
- Frank-Wolfe style algorithms for large scale optimization
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- On the Convergence of a Greedy Algorithm for the Solution of the Problem for the Construction of Monotone Regression
- Conditional gradient sliding for convex optimization
- An adaptive partial linearization method for optimization problems on product sets
- On the global convergence of an inexact quasi-Newton conditional gradient method for constrained nonlinear systems
- Frank-Wolfe algorithm from optimization to equilibrium problems
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Technical note -- Dynamic data-driven estimation of nonparametric choice models
- Simplified versions of the conditional gradient method
- Complexity bounds for primal-dual methods minimizing the model of objective function
- scientific article; zbMATH DE number 7064051 (Why is no real title available?)
- Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
- Gradient projection and conditional gradient methods for constrained nonconvex minimization
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Avoiding bad steps in Frank-Wolfe variants
- Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems
- Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Robust analysis in stochastic simulation: computation and performance guarantees
- Near-optimal coresets of kernel density estimates
- Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets
- First-order methods for convex optimization
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- Filtering with state-observation examples via kernel Monte Carlo filter
- Conditional gradient method without line-search
- Robust matrix estimations meet Frank-Wolfe algorithm
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- Frank-Wolfe and friends: a journey into projection-free first-order optimization 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
- Some comments on Wolfe's ‘away step’
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- The Frank-Wolfe algorithm: a short introduction
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Universal Conditional Gradient Sliding for 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)
