# Online Non-Convex Learning: Following the Perturbed Leader is Optimal

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2019.

## Built on by (most cited first, 30 of 32)

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization](https://mlsanity.com/paper/2102.13128/) (2021)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Building Robust Ensembles via Margin Boosting](https://mlsanity.com/paper/2206.03362/) (2022)
- [Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games](https://mlsanity.com/paper/2210.12606/) (2022)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Efficient Controllable Diffusion via Optimal Classifier Guidance](https://mlsanity.com/paper/2505.21666/) (2025)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025)
- [Computing Equilibrium beyond Unilateral Deviation](https://mlsanity.com/paper/2604.28186/) (2026)
- [Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms](https://mlsanity.com/paper/2605.01778/) (2026)
- [Online (Non-)Convex Learning via Tempered Optimism](https://mlsanity.com/paper/2301.07530/) (2023)
- [Solving Robust MDPs through No-Regret Dynamics](https://mlsanity.com/paper/2305.19035/) (2023)
- [Online Non-convex Optimization with Long-term Non-convex Constraints](https://mlsanity.com/paper/2311.02426/) (2023)
- [Event-Driven Online Vertical Federated Learning](https://mlsanity.com/paper/2506.14911/) (2025)
- [Online Ensemble Transformer for Accurate Cloud Workload Forecasting in Predictive Auto-Scaling](https://mlsanity.com/paper/2508.12773/) (2025)
- [Conformal Online Learning of Deep Koopman Linear Embeddings](https://mlsanity.com/paper/2511.12760/) (2025)
- [BOCO: Bayesian Online Contextual Optimization for Decision-Focused Online Learning](https://mlsanity.com/paper/2511.20413/) (2025)
- [Online Sharp-Calibrated Bayesian Optimization](https://mlsanity.com/paper/2605.10572/) (2026)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)
- [From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization](https://mlsanity.com/paper/2606.02948/) (2026)

## Abstract (arXiv)

We study the problem of online learning with non-convex losses, where the learner has access to an offline optimization oracle. We show that the classical Follow the Perturbed Leader (FTPL) algorithm achieves optimal regret rate of O(T-1/2) in this setting. This improves upon the previous best-known regret rate of O(T-1/3) for FTPL. We further show that an optimistic variant of FTPL achieves better regret bounds when the sequence of losses encountered by the learner is `predictable'.