# Regret minimization in stochastic non-convex learning via a proximal-gradient approach

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

## Key facts

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

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

- [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)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [Future Gradient Descent for Adapting the Temporal Shifting Data Distribution in Online Recommendation Systems](https://mlsanity.com/paper/2209.01143/) (2022)
- [Online Nonconvex Bilevel Optimization with Bregman Divergences](https://mlsanity.com/paper/2409.10470/) (2024)
- [OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression](https://mlsanity.com/paper/2105.13271/) (2021)
- [Online Optimization of Difference-of-Convex Compositions with Smooth Mappings](https://mlsanity.com/paper/2607.19553/) (2026)
- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## Abstract (arXiv)

Motivated by applications in machine learning and operations research, we study regret minimization with stochastic first-order oracle feedback in online constrained, and possibly non-smooth, non-convex problems. In this setting, the minimization of external regret is beyond reach for first-order methods, so we focus on a local regret measure defined via a proximal-gradient mapping. To achieve no (local) regret in this setting, we develop a prox-grad method based on stochastic first-order feedback, and a simpler method for when access to a perfect first-order oracle is possible. Both methods are min-max order-optimal, and we also establish a bound on the number of prox-grad queries these methods require. As an important application of our results, we also obtain a link between online and offline non-convex stochastic optimization manifested as a new prox-grad scheme with complexity guarantees matching those obtained via variance reduction techniques.