Online Mirror Descent

Follow this topic Ask about this topic

Latest papers 16

5 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

All topics

Prediction with Expert Advice under Heavy-Tailed Losses
Oct 10, 2026Yuki Shibukawa, Shinji ItoMinimax Regret Heavy-Tailed Distributions
The University of Tokyo and RIKEN
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
Oct 1, 2026S. Rasoul EtesamiGame Theory Online Mirror Descent
Department of Industrial and Systems Engineering, Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA 61801
Fast Regularized Policy Mirror Descent with One-Step TD Updates
Sep 30, 2026Qipei Chen, Wenye Li, Yule Sun +1Markov Decision Processes Policy Optimization
School of Mathematical Sciences, Fudan University · School of Data Science, Fudan University
An analysis of Mirror-Descent Soft Actor-Critic
Sep 28, 2026Denis Zorba, Michal ValkoReinforcement Learning Online Mirror Descent
School of Mathematics, University of Edinburgh, United Kingdom · INRIA, Paris, France
PolicyAttention: Softmax Attention Implements Policy Mirror Descent for Closed-Loop Control
Sep 24, 2026Yuhe Sui, Yingzhi Tang, Shufang ChenPolicy Learning Policy Optimization
Quantitative Research Society, Singapore · Nanyang Technological University, Singapore · The Chinese University of Hong Kong, Shenzhen, China +1
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
Sep 8, 2026Ashkan Soleymani, Gabriele Farina, Patrick JailletGame Theory Gradient Descent
MIT
Online Learning of Scale Parameters in Score-Driven Filters
Aug 10, 2026Fabrizio Lillo, Giulia Livieri, Gianluca PalmariDynamic Regret Minimization Online Mirror Descent
Scuola Normale Superiore, Piazza dei Cavalieri 7, Pisa, Italy · Department of Statistics, London School of Economics and Political Science, Columbia House, 69 Aldwych, London, United Kingdom
Bandit PCA with Minimax Optimal Regret
Jul 12, 2026Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa SahaPrincipal Component Analysis Minimax Regret
Georgia Tech · University of Illinois, Chicago
Nonlinear Bandit
Jul 8, 2026Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou +1Multi-Armed Bandits Heavy-Tailed Noise
School of Mathematics, Nanjing University, Nanjing, 210093, China · School of Artificial Intelligence, Nanjing University, National Key Laboratory for Novel Software Technology, Nanjing, 210023, China · School of Mathematics and Physics, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National University
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback
May 12, 2026Benjamin Amoh, Geoffrey G. Parker, Wesley MarreroPredict-Then-Optimize Decision-Focused Learning
Thayer School of Engineering, Dartmouth College
Path-Space Mirror Descent for On-Policy Reinforcement Learning under the Generalized Schrödinger Bridge
Mar 23, 2026Yuehu Gong, Zeyuan Wang, Yulin Chen +3Policy Optimization Continuous Control
School of Data Science, Fudan University · Laboratory for Big Data and Decision, National University of Defense Technology · ShanghaiTech University +2
Block-Norm Geometries for Online Mirror Descent with Sparse Losses
Feb 13, 2026Swati Gupta, Jai Moondra, Mohit SinghOnline Convex Optimization Online Mirror Descent
MIT · CMU · Georgia Tech
A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions
Feb 11, 2026Sanghwa Kim, Junghyun Lee, Se-Young YunMulti-Armed Bandits Online Mirror Descent
Kim Jaechul Graduate School of AI, KAIST
Online Learning: A Modern Introduction Using Convex Optimization
Dec 31, 2019Francesco OrabonaOnline Convex Optimization Follow-the-Regularized-Leader
KAUST

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

Prediction with Expert Advice under Heavy-Tailed Losses

Yuki Shibukawa, Shinji Ito

The University of Tokyo and RIKEN

Minimax Regret Heavy-Tailed Distributions Follow-the-Regularized-Leader Online Mirror Descent

Open paper AskPDF arXiv

We study prediction with expert advice over

T

rounds with

K

experts under heavy-tailed losses whose

(1+ε)

-moment is bounded by

θ>0

for some

ε\in(0,1]

. In this setting, existing algorithms designed for the case

ε=1

can be suboptimal when

ε<1

, suffering an additional polynomial dependence on

K

. We characterize the minimax pseudo-regret rate as

Θ((θT)^{\frac{1}{1+ε}}(\log K)^{\fracε{1+ε}})

and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either

ε

θ

, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither

ε

nor

θ

and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when

ε

and

θ

are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.