Online Convex Optimization

Overview

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

CardsList

73 papers16 papers in the last four weeks, up 78% on the four weeks before. 0.1% of all new papers.

  1. Adversarially Batched Online Learning

    Nov 12, 2026Mingda Qiao, Kerui WuBatched BanditsOnline Convex Optimization

  2. KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

    Nov 9, 2026Zhaoye Pan, Tao Li, Yunjie Guo +1Online Convex OptimizationDistributed Optimization

  3. Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence

    Nov 5, 2026Mohammed Abdullah, George Iosifidis, Salah Eddine Elayoubi +1Online Convex OptimizationDynamic Regret Minimization

  4. Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

    Nov 5, 2026Linzhe He, Sifan Yang, Wei Jiang +1Competitive AnalysisOnline Convex Optimization

  5. Tilted Convexity and an Exact Offline-Online Separation

    Nov 2, 2026Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn +1Online Convex Optimization

  6. When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

    Nov 2, 2026Ridham PatelDynamic Regret MinimizationOnline Convex Optimization

  7. Conic-Lifting for Learning-rate-free Convex Optimization

    Oct 29, 2026Julien Grand-Clément, Joon Kwon, Francesco OrabonaParameter-Free Online LearningOnline Convex Optimization

  8. Strongly Adaptive Online Learning Achieves Uniform Discounted Regret

    Oct 29, 2026Sifan Yang, Wenhao Yang, Lijun ZhangOnline Convex Optimization

  9. Optimal Regret for Communication-Efficient Decentralized Online Learning

    Oct 28, 2026Sifan Yang, Wenhao Yang, Wei Jiang +2Decentralized OptimizationOnline Convex Optimization

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

    Oct 27, 2026Julien Weibel, Pierre Gaillard, Wouter Koolen +1Online Convex OptimizationLMO Methods

  11. Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on ℓp\ell_p Balls

    Oct 26, 2026Jack J. MayoOnline LPRegret Minimization

  12. Strongly Adaptive Online Learning with Time-Varying Movement Costs

    Oct 23, 2026Andrew Jacobsen, Emmanuel Esposito, Hao Qiu +1Online Convex OptimizationDynamic Regret Minimization

  13. Universal Online Convex Optimization With Delayed Feedback

    Oct 20, 2026Hao Qiu, Andrew Jacobsen, Emmanuel Esposito +1Online Convex Optimization

  14. Decentralized Online Exp-Concave Optimization

    Oct 18, 2026Hao Qiu, Mengxiao Zhang, Yuanyu WanDecentralized OptimizationOnline Convex Optimization

  15. 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 AnalysisOnline Convex Optimization

  16. Tracking a Small Set of Experts in Online Convex Optimization

    Oct 14, 2026Angelos Assos, Anand Brahmbhatt, Elad HazanOnline Convex Optimization

  17. Efficient Preconditioned Optimization Methods with Frequent Directions

    Oct 12, 2026Sifan Yang, Yuanyu Wan, Yibo Wang +1Adaptive Gradient MethodsOnline Convex Optimization

  18. O~(T)\tilde{O}(\sqrt{T}) Regret and Polylogarithmic Constraint Violation for COCO

    Oct 2, 2026Dhruv Sarkar, Abhishek SinhaOnline Convex OptimizationConstrained Optimization

  19. Universal Dynamic Portfolios

    Sep 28, 2026Yu-Jie Zhang, Yu-Xiang Wang, Peng Zhao +1Online Convex OptimizationDynamic Regret Minimization

  20. On the Relation Between Interval Regret and Dynamic Regret

    Sep 28, 2026Yi-Han Wang, Peng Zhao, Zhi-Hua ZhouOnline Convex OptimizationDynamic Regret Minimization

  21. Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

    Sep 24, 2026Naram Mhaisen, George IosifidisOnline Convex OptimizationDynamic Regret Minimization

  22. Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

    Sep 23, 2026Jiameng LyuOnline Convex OptimizationOnline LP

  23. From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

    Sep 17, 2026Yibo Wang, Wenhao Yang, Sifan Yang +3Online Convex OptimizationDynamic Regret Minimization

  24. Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

    Sep 12, 2026Zhanyuan Cai, Emre Sahinoglu, Shahin ShahrampourRiemannian OptimizationDecentralized Optimization