Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization

• URL: http://arxiv.org/abs/2605.25255v1
• Date: Sun, 24 May 2026 21:04:26 GMT
• Title: Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization
• Abstract summary: We develop a novel step constant of the boosted Frank-Wolfe algorithm.<n>We prove that boosting with this step size strategy can be combined with many modern estimators.
• Score: 0.4499833362998487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex problems, with step sizes that require either line search or knowledge of the Lipschitz constant of the gradient. We develop a novel step size strategy that does not depend on the Lipschitz constant of the gradient, which allows us to extend the boosted Frank-Wolfe algorithm to the stochastic setting. We prove that boosting with this step size strategy can be combined with many modern gradient estimators, including SAGA, L-SVRG, SAG, Heavy Ball momentum, and zeroth-order estimators, among others, while retaining the worst-case convergence rates of ordinary stochastic Frank-Wolfe. Our analysis also yields the first convergence rates for boosted Frank-Wolfe on nonconvex and quasar-convex objectives, results which are new even for deterministic problems. Experiments on sparse logistic regression and quantum process tomography show that stochastic boosted Frank-Wolfe achieves faster convergence per gradient oracle call (and on wall-clock) compared to the non-boosted baseline.

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe [11.287482309003334]
  We show that Lion and Muon with weight decay can be viewed as special instances a Frank-Wolfe.<n>We also find that convergence to this gap implies convergence to a KKT point of the original problem under a norm constraint.
  arXiv  Detail & Related papers  (2025-06-04T17:39:03Z)
• Beyond Short Steps in Frank-Wolfe Algorithms [25.808224336342683]
  We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps.<n>We present a new Frank-Wolfe algorithm utilizing an optimistic framework and provide a primal-dual convergence proof.
  arXiv  Detail & Related papers  (2025-01-30T21:52:45Z)
• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. We provide the applications for fast-rate convergence in games and extended adversarial optimization.
  arXiv  Detail & Related papers  (2024-08-17T02:22:08Z)
• Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz [66.22095739795068]
  Sign-based methods have gained attention due to their ability to achieve robust performance despite only using only the sign information for parameter updates. The current convergence analysis of sign-based methods relies on the strong assumptions of first-order acceleration and second-order acceleration. In this paper we analyze their convergence under more realistic assumptions of first- and second-order acceleration.
  arXiv  Detail & Related papers  (2023-10-23T06:48:43Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  The Frank-Wolfe (FW) method is a popular approach for solving optimization problems with structured constraints. We present two new variants of the algorithms for minimization of the finite-sum gradient.
  arXiv  Detail & Related papers  (2023-04-23T20:05:09Z)
• Reducing Discretization Error in the Frank-Wolfe Method [2.806911268410107]
  The Frank-Wolfe algorithm is a popular method in structurally constrained machine learning applications. One major limitation of the method is a slow rate of convergence that is difficult to accelerate due to erratic, zig-zagging step directions. We propose two improvements: a multistep Frank-Wolfe method that directly applies optimized higher-order discretization schemes; and an LMO-averaging scheme with reduced discretization error.
  arXiv  Detail & Related papers  (2023-04-04T00:43:05Z)
• A Multistep Frank-Wolfe Method [2.806911268410107]
  We study the zig-zagging phenomenon in the Frank-Wolfe method as an artifact of discretization. We propose multistep Frank-Wolfe variants where the truncation errors decay as $O(Deltap)$, where $p$ is the method's order.
  arXiv  Detail & Related papers  (2022-10-14T21:12:01Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Boosting Frank-Wolfe by Chasing Gradients [26.042029798821375]
  We propose to speed up the Frank-Wolfe algorithm by better aligning the descent direction with that of the negative gradient via a subroutine. We demonstrate its competitive advantage both per iteration and in CPU time over the state-of-the-art in a series of computational experiments.
  arXiv  Detail & Related papers  (2020-03-13T16:29:02Z)
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization [60.90222082871258]
  We demonstrate how to scalably solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO) over the constraint set. We prove that the number of LMO calls of our method is nearly the same as that of the Frank-Wolfe method in the L-smooth case.
  arXiv  Detail & Related papers  (2020-02-17T15:28:31Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.