Frank-Wolfe Algorithms for (L0, L1)-smooth functions

2025/10/18 by A. A. Vyguzov, Vyguzov, A. A., Fedor Stonyakin +2 · 1 voice · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.2510.16468

openalex publication_date 2025/10/18 · arxiv published 2025/10/18 · openalex created_date 2025/10/22 · arxiv updated 2026/05/20 · openalex updated_date 2026/07/28

Abstract

We propose a new version of the Frank-Wolfe method, called the (L0, L1)-Frank-Wolfe algorithm, developed for optimization problems with (L0, L1)-smooth objectives. We establish that this algorithm achieves superior theoretical convergence rates compared to the classical Frank-Wolfe method. In addition, we introduce a novel adaptive procedure, termed the Adaptive (L0, L1)-Frank-Wolfe algorithm, which dynamically adjusts the smoothness parameters to further improve performance and stability. Comprehensive numerical experiments confirm the theoretical results and demonstrate the clear practical advantages of both proposed algorithms over existing Frank-Wolfe variants.

Citations

• Adaptive Conditional Gradient Descent
• Generalized Gradient Norm Clipping & Non-Euclidean (L₀,L₁)-Smoothness
• Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions
• Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L₀,L₁)-Smoothness
• Optimizing (L₀, L₁)-Smooth Functions by Gradient Methods
• Methods for Convex (L₀,L₁)-Smooth Optimization: Clipping, Acceleration, and Adaptivity
• Adaptive Variant of Frank-Wolfe Method for Relative Smooth Convex Optimization Problems
• Adaptive Variant of the Frank-Wolfe Algorithm for Convex Optimization Problems
• Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees
• Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
• Conditional Gradient Methods
• Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
• Complexity of Linear Minimization and Projection on Some Sets
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• Выпуклая оптимизация

Cited by

• Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients

Discussions

• Have you ever written a paper, and you see a small variation you could easily cover with your analysis etc but you don't do it? But you know if someone else did it right after, you would be upset you [bsky, 3 points, 1 comments]

Related

• The Frank-Wolfe algorithm: a short introduction
• The Frank-Wolfe Algorithm: A Short Introduction
• Adaptive Variant of the Frank-Wolfe Algorithm for Convex Optimization Problems
• Adaptive Variant of Frank-Wolfe Method for Relative Smooth Convex Optimization Problems
• Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions