mlsanityData to 14 Oct 2026

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

arXiv 1903.08110 ↗First posted 19 Mar 2019cs.LG math.OC stat.MLcited by 32

Not on the map. Why?

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'.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 8; 2023: 5; 2024: 3; 2025: 7; 2026: 7.

32 papers.

Sort:

By area:

  1. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  2. 2021An Online Learning Approach to Interpolation and Extrapolation in Domain Generalizationcited by 30
  3. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 15
  4. 2022Optimistic No-regret Algorithms for Discrete Cachingcited by 10
  5. 2022Online Low Rank Matrix Completioncited by 9
  6. 2022Building Robust Ensembles via Margin Boostingcited by 8
  7. 2022Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Gamescited by 8
  8. 2023Non-Convex Bilevel Optimization with Time-Varying Objective Functionscited by 8
  9. 2021Zeroth-order non-convex learning via hierarchical dual averagingcited by 6
  10. 2022Online Convex Optimization with Unbounded Memorycited by 6
  11. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  12. 2024Locally Differentially Private Online Federated Learning With Correlated Noisecited by 6
20 more
  1. 2023Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Makingcited by 5
  2. 2025Online Decision-Focused Learningcited by 4
  3. 2022Distributed Online Non-convex Optimization with Composite Regretcited by 2
  4. 2025Efficient Controllable Diffusion via Optimal Classifier Guidancecited by 2
  5. 2024Optimistic Safety for Online Convex Optimization with Unknown Linear Constraintscited by 1
  6. 2025Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraintscited by 1
  7. 2026Computing Equilibrium beyond Unilateral Deviationcited by 1
  8. 2026Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithmscited by 1
  9. 2023Online (Non-)Convex Learning via Tempered Optimismcited by 0
  10. 2023Solving Robust MDPs through No-Regret Dynamicscited by 0
  11. 2023Online Non-convex Optimization with Long-term Non-convex Constraintscited by 0
  12. 2025Event-Driven Online Vertical Federated Learningcited by 0
  13. 2025Online Ensemble Transformer for Accurate Cloud Workload Forecasting in Predictive Auto-Scalingcited by 0
  14. 2025Conformal Online Learning of Deep Koopman Linear Embeddingscited by 0
  15. 2025BOCO: Bayesian Online Contextual Optimization for Decision-Focused Online Learningcited by 0
  16. 2026Online Sharp-Calibrated Bayesian Optimizationcited by 0
  17. 2026Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedbackcited by 0
  18. 2026From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimizationcited by 0
  19. 2026Online Optimization of Difference-of-Convex Compositions with Smooth Mappingscited by 0
  20. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0