# A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2017.

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

- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2502.07774/) (2025)
- [Optimistic and Adaptive Lagrangian Hedging](https://mlsanity.com/paper/2101.09603/) (2021)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Optimistic Optimisation of Composite Objective with Exponentiated Update](https://mlsanity.com/paper/2208.04065/) (2022)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Generalized Implicit Follow-The-Regularized-Leader](https://mlsanity.com/paper/2306.00201/) (2023)
- [Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees](https://mlsanity.com/paper/2502.12678/) (2025)
- [Optimistic Meta-Gradients](https://mlsanity.com/paper/2301.03236/) (2023)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game](https://mlsanity.com/paper/2203.05920/) (2022)
- [Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes](https://mlsanity.com/paper/2405.02188/) (2024)
- [Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces](https://mlsanity.com/paper/2502.14790/) (2025)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

Recently, much work has been done on extending the scope of online learning and incremental stochastic optimization algorithms. In this paper we contribute to this effort in two ways: First, based on a new regret decomposition and a generalization of Bregman divergences, we provide a self-contained, modular analysis of the two workhorses of online learning: (general) adaptive versions of Mirror Descent (MD) and the Follow-the-Regularized-Leader (FTRL) algorithms. The analysis is done with extra care so as not to introduce assumptions not needed in the proofs and allows to combine, in a straightforward way, different algorithmic ideas (e.g., adaptivity, optimism, implicit updates) and learning settings (e.g., strongly convex or composite objectives). This way we are able to reprove, extend and refine a large body of the literature, while keeping the proofs concise. The second contribution is a byproduct of this careful analysis: We present algorithms with improved variational bounds for smooth, composite objectives, including a new family of optimistic MD algorithms with only one projection step per round. Furthermore, we provide a simple extension of adaptive regret bounds to practically relevant non-convex problem settings with essentially no extra effort.