Online Convex Optimization

Follow this topic Ask about this topic

Online convex optimization studies how to choose actions sequentially as convex losses arrive, measuring performance against the best fixed or changing comparator in hindsight. Common methods include Online Mirror Descent, projected gradient descent, Follow-the-Regularized-Leader, and adaptive or optimistic variants; feedback may be full-information, bandit, delayed, or distributed. Constraints and changing feasible sets add costs such as cumulative violation, movement, communication, and computation, so algorithms often balance these against regret. Current work sharpens guarantees for dynamic comparators and problem-dependent conditions, while a central challenge is achieving optimal regret and feasibility with partial feedback and limited resources.

Latest papers

61 papers12 papers in the last four weeks, up 71% on the four weeks before. 0.1% of all new papers.

Strongly Adaptive Online Learning with Time-Varying Movement Costs
Oct 23, 2026Andrew Jacobsen, Emmanuel Esposito, Hao Qiu +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · National University of Singapore +1
Universal Online Convex Optimization With Delayed Feedback
Oct 20, 2026Hao Qiu, Andrew Jacobsen, Emmanuel Esposito +1Online Convex Optimization
Universitat Pampeu Fabra · University of Iowa
Decentralized Online Exp-Concave Optimization
Oct 18, 2026Hao Qiu, Mengxiao Zhang, Yuanyu WanDecentralized Optimization Online Convex Optimization
National University of Singapore, Singapore · Department of Business Analytics, Tippie College of Business, University of Iowa, USA · School of Software Technology, Zhejiang University, Ningbo, China +1
Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
Oct 17, 2026Lijun Zhang, Linzhe He, Wei Jiang +1Competitive Analysis Online Convex Optimization
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China +1
Tracking a Small Set of Experts in Online Convex Optimization
Oct 14, 2026Angelos Assos, Anand Brahmbhatt, Elad HazanOnline Convex Optimization
Princeton University · Google DeepMind Princeton
Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
Oct 14, 2026Yanyi Li, Wendao Wu, Haihan Zhang +6Dynamic Regret Minimization Online Convex Optimization
Peking University
Efficient Preconditioned Optimization Methods with Frequent Directions
Oct 12, 2026Sifan Yang, Yuanyu Wan, Yibo Wang +1Adaptive Gradient Methods Online Convex Optimization
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China +1
$\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO
Oct 2, 2026Dhruv Sarkar, Abhishek SinhaOnline Convex Optimization Constrained Optimization
MIT Cambridge, USA · Tata Institute of Fundamental Research Mumbai, India
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Sep 30, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University, West Lafayette, IN, USA
Lower Bounds for Linear-Oracle Online Learning
Sep 29, 2026Mohit SinhaOnline Convex Optimization Information-Theoretic Lower Bounds
Universal Dynamic Portfolios
Sep 28, 2026Yu-Jie Zhang, Yu-Xiang Wang, Peng Zhao +1Online Convex Optimization Dynamic Regret Minimization
University of Washington · University of California, San Diego · State Key Laboratory for Novel Software Technology, Nanjing University School of Artificial Intelligence, Nanjing University
On the Relation Between Interval Regret and Dynamic Regret
Sep 28, 2026Yi-Han Wang, Peng Zhao, Zhi-Hua ZhouOnline Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
Sep 24, 2026Naram Mhaisen, George IosifidisOnline Convex Optimization Dynamic Regret Minimization
Faculty of Electrical Engineering, Mathematics and Computer Science TU Delft, Netherlands
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
Sep 23, 2026Vaneet AggarwalOnline Convex Optimization LMO Methods
Purdue University West Lafayette, Indiana, USA
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
Sep 23, 2026Jiameng LyuOnline Convex Optimization Online Resource Allocation
Department of Management Science, School of Management, Fudan University, Shanghai 200433, China
From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
Sep 17, 2026Yibo Wang, Wenhao Yang, Sifan Yang +3Online Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University
Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
Sep 12, 2026Zhanyuan Cai, Emre Sahinoglu, Shahin ShahrampourRiemannian Optimization Decentralized Optimization
Department of Mechanical and Industrial Engineering, Northeastern University, Boston, MA 02115
Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Sep 10, 2026Rahul VazeOnline Convex Optimization Proximal Optimization
Constrained Online Learning with Noisy Constraint Values
Sep 7, 2026Vaneet AggarwalStochastic Optimization Online Convex Optimization
Purdue University
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
Aug 29, 2026Dhruv Sarkar, Aprameyo ChakrabarttyOnline Convex Optimization
Massachusetts Institute of Technology, Cambridge, MA · Purdue University, West Lafayette, IN
Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
Aug 25, 2026Mengxiao ZhangOnline Convex Optimization Minimax Regret
University of Iowa
Optimal Alternating Regret for Online Learning and Games
Aug 25, 2026Yixin Tao, Weiqiang ZhengOnline Convex Optimization Nash Equilibrium Computation
ITCS, Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics · Yale University
Online Convex Optimization with Dueling Feedback
Aug 15, 2026Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar +2Online Convex Optimization Follow-the-Regularized-Leader
Purdue University · IIT Indore · Mila - Quebec AI Institute/McGill University
Distributed Optimization with Streaming Data: A Temporal Weighting Perspective
Aug 10, 2026Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. LarssonOnline Convex Optimization Decentralized Optimization
School of Electrical, Computer and Energy Engineering, Arizona State University · Department of Electrical Engineering (ISY), Linköping University, 58183 Linköping, Sweden
Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws
Aug 3, 2026Zijun Wang, Yuchen Miao, Yifan Hu +1Online Convex Optimization Statistical Learning Theory
Northeastern University, China · Beijing Jiaotong University, China · Xiangtan University, China
Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning
Jul 30, 2026Wentao Zhang, Wentao MoOnline Convex Optimization Real-Time Scheduling
Tsinghua Shenzhen International Graduate School, Tsinghua University Shenzhen, China
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
Jul 28, 2026Wentao ZhangOnline Convex Optimization Constrained Optimization
Tsinghua Shenzhen International Graduate School · Tsinghua University
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
Jul 22, 2026Zhanyuan Cai, Emre Sahinoglu, Shahin ShahrampourOnline Convex Optimization Riemannian Optimization
Department of Mechanical & Industrial Engineering at Northeastern University, Boston, MA 02115, USA
The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
Jul 21, 2026Nived RajaramanOnline Convex Optimization Minimax Regret
Microsoft Research

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

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

Università degli Studi di Milano · Politecnico di Milano · National University of Singapore+1

Online Convex Optimization Dynamic Regret Minimization

Open paper AskPDF arXiv

We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval

[a,b] \subseteq [T]

, achieves a data-dependent regret bound of

\widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right)

, where

D

is the diameter of the decision domain,

P_{[a,b]}

is the path length of the comparator sequence over

[a,b]

g_t

is the gradient of the loss, and

λ_t

is the movement-cost coefficient at round

t

. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.