# Online non-convex optimization with imperfect feedback

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2020.

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

- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [Learning in nonatomic games, Part I: Finite action spaces and population games](https://mlsanity.com/paper/2107.01595/) (2021)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements](https://mlsanity.com/paper/2107.08011/) (2021)
- [Real-Time Black-Box Optimization for Dynamic Discrete Environments Using Embedded Ising Machines](https://mlsanity.com/paper/2506.16924/) (2025)
- [Gradient and Projection Free Distributed Online Min-Max Resource Optimization](https://mlsanity.com/paper/2112.03896/) (2021)
- [Event-Driven Online Vertical Federated Learning](https://mlsanity.com/paper/2506.14911/) (2025)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)
- [Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses](https://mlsanity.com/paper/2606.19891/) (2026)

## Abstract (arXiv)

We consider the problem of online learning with non-convex losses. In terms of feedback, we assume that the learner observes - or otherwise constructs - an inexact model for the loss function encountered at each stage, and we propose a mixed-strategy learning policy based on dual averaging. In this general context, we derive a series of tight regret minimization guarantees, both for the learner's static (external) regret, as well as the regret incurred against the best dynamic policy in hindsight. Subsequently, we apply this general template to the case where the learner only has access to the actual loss incurred at each stage of the process. This is achieved by means of a kernel-based estimator which generates an inexact model for each round's loss function using only the learner's realized losses as input.