# Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 64 references that are in the map.
- First posted on arXiv 18 Sep 2023.

## Builds on (most cited first, 26 of 26)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Online Learning with Inexact Proximal Online Gradient Descent Algorithms](https://mlsanity.com/paper/1806.00202/) (2018)
- [Statistical Learning with Conditional Value at Risk](https://mlsanity.com/paper/2002.05826/) (2020)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [Online Projected Gradient Descent for Stochastic Optimization with Decision-Dependent Distributions](https://mlsanity.com/paper/2107.09721/) (2021)
- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [Risk-sensitive safety analysis using Conditional Value-at-Risk](https://mlsanity.com/paper/2101.12086/) (2021)
- [Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine](https://mlsanity.com/paper/2010.12865/) (2020)
- [Second-order Online Nonconvex Optimization](https://mlsanity.com/paper/2001.10114/) (2020)
- [Tracking Moving Agents via Inexact Online Gradient Descent Algorithm](https://mlsanity.com/paper/1710.05133/) (2017)
- [Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Lojasiewicz Conditions](https://mlsanity.com/paper/2012.07785/) (2020)
- [Inexact Online Proximal-gradient Method for Time-varying Convex Optimization](https://mlsanity.com/paper/1910.02018/) (2019)
- [Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2108.03285/) (2021)
- [Square distance functions are Polyak-Lojasiewicz and vice-versa](https://mlsanity.com/paper/2301.10332/) (2023)
- [Regularization Helps with Mitigating Poisoning Attacks: Distributionally-Robust Machine Learning Using the Wasserstein Distance](https://mlsanity.com/paper/2001.10655/) (2020)
- [Online Stochastic Convex Optimization: Wasserstein Distance Variation](https://mlsanity.com/paper/2006.01397/) (2020)
- [Applications of Convex Analysis within Mathematics](https://mlsanity.com/paper/1302.1978/) (2013)

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

- [Online Non-Stationary Stochastic Quasar-Convex Optimization](https://mlsanity.com/paper/2407.03601/) (2024)
- [Risk-Averse Learning with Varying Risk Levels](https://mlsanity.com/paper/2512.22986/) (2025)
- [Continuous-time Online Learning via Mean-Field Neural Networks: Regret Analysis in Diffusion Environments](https://mlsanity.com/paper/2604.10958/) (2026)

## Abstract (arXiv)

In this work, we consider a sequence of stochastic optimization problems following a time-varying distribution via the lens of online optimization. Assuming that the loss function satisfies the Polyak-Lojasiewicz condition, we apply online stochastic gradient descent and establish its dynamic regret bound that is composed of cumulative distribution drifts and cumulative gradient biases caused by stochasticity. The distribution metric we adopt here is Wasserstein distance, which is well-defined without the absolute continuity assumption or with a time-varying support set. We also establish a regret bound of online stochastic proximal gradient descent when the objective function is regularized. Moreover, we show that the above framework can be applied to the Conditional Value-at-Risk (CVaR) learning problem. Particularly, we improve an existing proof on the discovery of the PL condition of the CVaR problem, resulting in a regret bound of online stochastic gradient descent.