LMO Methods

LMO: Linear Minimization Oracle

Latest papers

15 papers5 papers in the last four weeks, up 67% on the four weeks before. 0.0% of all new papers.

An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles
Oct 27, 2026Julien Weibel, Pierre Gaillard, Wouter Koolen +1Online Convex Optimization LMO Methods
Inria, D.I. ´Ecole Normale Sup´erieure, CNRS PSL Research University · Centrum Wiskunde & Informatica, Amsterdam and Twente University, Enschede · Universit´e Grenoble Alpes, Inria, CNRS Grenoble INP, LJK
Understanding Practical Optimization in Machine Learning
Oct 26, 2026Egor ShulginNonconvex Stochastic Optimization LMO Methods
King Abdullah University of Science and Technology Thuwal, Kingdom of Saudi Arabia
Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates
Oct 9, 2026El Mahdi Chayti, Alireza Mirrokni, Martin JaggiLMO Methods Multi-Objective Optimization
Machine Learning and Optimization Laboratory (MLO), EPFL
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
Oct 9, 2026Sebastian PokuttaLMO Methods Oracle Complexity
Zuse Institute Berlin and TU Berlin
Optimizing Large Language Models with Chained LMOs
Oct 7, 2026Sungyoon Kim, Kaan Ozkara, Youngsuk ParkLMO Methods Deep Learning Optimization
Department of Electrical Engineering, Stanford University · Amazon Annapurna Labs
Lower Bounds for Linear-Oracle Online Learning
Sep 29, 2026Mohit SinhaOnline Convex Optimization Information-Theoretic Lower Bounds
Local LMO is Secretly a Projection Method!
Sep 27, 2026Peter Richtárik, Ammar MahranLMO Methods Constrained Optimization
King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
Sep 23, 2026Vaneet AggarwalOnline Convex Optimization LMO Methods
Purdue University West Lafayette, Indiana, USA
OmniOpt: Taxonomy, Geometry, and Benchmarking of Modern Optimizers
Jul 4, 2026Siyuan Li, Jiabao Pan, Yumou Liu +9LMO Methods Deep Learning Optimization
Shanghai Artificial Intelligence Laboratory · Westlake University · Shanghai University +4
From SGD to Muon: Adaptive Optimization via Schatten-p Norms
May 19, 2026Thomas Massena, Corentin Friedrich, Mathieu SerrurierLMO Methods Neural Network Optimization
DTIPG - SNCF, IRIT · IRIT
Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
May 18, 2026Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin +1LMO Methods Momentum Methods
KAUST
Accelerating LMO-Based Optimization via Implicit Gradient Transport
May 7, 2026Won-Jun Jang, Si-Hyeon LeeLMO Methods Muon Optimizer
School of Electrical Engineering · Korea Advanced Institute of Science and Technology (KAIST) · Daejeon, South Korea
Deriving Hyperparameter Scaling Laws via Modern Optimization Theory
Mar 16, 2026Egor Shulgin, Dimitri von Rütte, Tianyue H. Zhang +3LMO Methods Scaling Laws
King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia · ETH Zürich, Zürich, Switzerland · Mila, Quebec AI Institute & Université de Montréal, Quebec, Canada +1
Ky Fan Norms and Beyond: Dual Norms and Combinations for Matrix Optimization
Dec 10, 2025Alexey Kravatskiy, Ivan Kozyrev, Nikolai Kozlov +3LMO Methods Deep Learning Optimization
MIRIAI · Russia · MIPT, INM RAS +3
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

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

An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles

Julien Weibel, Pierre Gaillard, Wouter Koolen, Adrien Taylor

Inria, D.I. ´Ecole Normale Sup´erieure, CNRS PSL Research University · Centrum Wiskunde & Informatica, Amsterdam and Twente University, Enschede · Universit´e Grenoble Alpes, Inria, CNRS Grenoble INP, LJK

Online Convex Optimization LMO Methods Minimax Regret

Open paper AskPDF arXiv

This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as

T^{3/4}

(where

T

is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as

T^{3/4}

. We answer that question, proving a universal worst-case regret lower bound

Ω(T^{3/4} m^{-1/4})

for any projection-free algorithm that makes at most

m

linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound

O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \})