Frank-Wolfe Algorithms

Latest papers

12 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
Oct 9, 2026Sebastian PokuttaLMO Methods Oracle Complexity
Zuse Institute Berlin and TU Berlin
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
Sep 22, 2026Akbar Rafiey, Yifei Xu, Nikolaos KaraliasSelf-Supervised Learning Combinatorial Optimization
NYU · MIT
Lloyd's $K$ -Means Clustering Algorithm Is Frank-Wolfe in Disguise
Jul 28, 2026Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-JulienClustering Unsupervised Clustering
Department of Mathematics & Statistics and School of Data Science Old Dominion University Norfolk, VA 23529, USA · Information Systems & Analytics Department Miami University Oxford, OH 45056, USA · Canada CIFAR AI Chair Department of Computer Science and Operations Research & Mila Université de Montréal Montréal (QC) Canada
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Query Complexity Oracle Complexity
University of New South Wales · University of California, Berkeley · University of Sydney
BLADE: Scalable Bi-level Adaptive Data Selection for LLM Training
Jun 17, 2026Jiaxing Wang, Deping Xiang, Jin Xu +9Training Data Selection Bilevel Optimization
University of Oxford
Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature
May 7, 2026Satoshi HayakawaConstrained Optimization Kernel Methods
The University of Tokyo
Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming
Apr 2, 2026Qiheng Lu, Nicholas D. SidiropoulosFrank-Wolfe Algorithms Constrained Optimization
University of Virginia Charlottesville, VA 22904, USA
Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Feb 26, 2026Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1Frank-Wolfe Algorithms Stackelberg Games
EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences
$κ$ -Explorer: Minimax Active Model Estimation in MDPs
Feb 23, 2026Xihe Gu, Urbashi Mitra, Tara JavidiFrank-Wolfe Algorithms RL Exploration
Department of Electrical and Computer Engineering, University of California, San Diego · Department of Electrical and Computer Engineering, University of Southern California
RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization
Feb 6, 2026El Mahdi Chayti, Mohamad FakhouriFrank-Wolfe Algorithms Second-Order Optimization
Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland
Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
Nov 4, 2025Dan GarberConstrained Optimization Frank-Wolfe Algorithms
Faculty of Data and Decision Sciences Technion - Israel Institute of Technology
Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin
Jan 30, 2025Fangyuan Xie, Jinghui Yuan, Feiping Nie +1Frank-Wolfe Algorithms Graph Clustering
School of Artificial Intelligence, Optics and Electronics (iOPEN), Northwestern Polytechnical University, Xi’an 710072, P.R. China

Oct 9, 2026J/K move · Enter open · S save

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

Sebastian Pokutta

Zuse Institute Berlin and TU Berlin

LMO Methods Oracle Complexity Frank-Wolfe Algorithms Constrained Optimization Information-Theoretic Lower Bounds Stochastic Optimization

Open paper AskPDF arXiv

Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order

1/T^2

after

T

linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on

T

and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an

Ω(L\operatorname{diam}(S)^2/T^2)

distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We further show that the same error threshold holds with probability at least

3/4

and yields a stopping-time tail bound.