Convergence Rate of Frank-Wolfe for Non-Convex Objectives

Abstract

We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).

6 pages

Cited by in corpus (35)

• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• Noncoherent Joint Transmission Beamforming for Dense Small Cell Networks: Global Optimality, Efficient Solution and Distributed Implementation
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Robust estimation via generalized quasi-gradients
• Stochastic Conditional Gradient++
• Fusion of Head and Full-Body Detectors for Multi-Object Tracking
• One Sample Stochastic Frank-Wolfe
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Continuous DR-submodular Maximization: Structure and Algorithms
• Projection-Free Algorithm for Stochastic Bi-level Optimization
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Linearly Convergent Frank-Wolfe with Backtracking Line-Search
• Joint Discovery of Object States and Manipulation Actions
• A contribution to Optimal Transport on incomparable spaces
• Projection-Free Adaptive Gradients for Large-Scale Optimization
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications
• Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization
• Safe Learning under Uncertain Objectives and Constraints
• A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks
• A Proximal Linearization-based Decentralized Method for Nonconvex Problems with Nonlinear Constraints
• Non-convex Conditional Gradient Sliding
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Three Operator Splitting with a Nonconvex Loss Function
• Scalable Projection-Free Optimization
• Online Graph Dictionary Learning
• Competitive Algorithms for Online Budget-Constrained Continuous DR-Submodular Problems
• Aligning Time Series on Incomparable Spaces