# Online convex optimization and no-regret learning: Algorithms, guarantees and applications

arXiv: https://arxiv.org/abs/1804.04529 · HTML: https://mlsanity.com/paper/1804.04529/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2018.

## Built on by (most cited first, 5 of 5)

- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Prediction techniques for dynamic imaging with online primal-dual methods](https://mlsanity.com/paper/2405.02497/) (2024)
- [Solving reward-collecting problems with UAVs: a comparison of online optimization and Q-learning](https://mlsanity.com/paper/2112.00141/) (2021)
- [Online optimisation for dynamic electrical impedance tomography](https://mlsanity.com/paper/2412.12944/) (2024)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

Spurred by the enthusiasm surrounding the "Big Data" paradigm, the mathematical and algorithmic tools of online optimization have found widespread use in problems where the trade-off between data exploration and exploitation plays a predominant role. This trade-off is of particular importance to several branches and applications of signal processing, such as data mining, statistical inference, multimedia indexing and wireless communications (to name but a few). With this in mind, the aim of this tutorial paper is to provide a gentle introduction to online optimization and learning algorithms that are asymptotically optimal in hindsight - i.e., they approach the performance of a virtual algorithm with unlimited computational power and full knowledge of the future, a property known as no-regret. Particular attention is devoted to identifying the algorithms' theoretical performance guarantees and to establish links with classic optimization paradigms (both static and stochastic). To allow a better understanding of this toolbox, we provide several examples throughout the tutorial ranging from metric learning to wireless resource allocation problems.