# Online Non-Stationary Stochastic Quasar-Convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 4 Jul 2024.

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

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Online Learning with Inexact Proximal Online Gradient Descent Algorithms](https://mlsanity.com/paper/1806.00202/) (2018)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising](https://mlsanity.com/paper/1305.3011/) (2013)
- [Online Proximal-ADMM For Time-varying Constrained Convex Optimization](https://mlsanity.com/paper/2005.03267/) (2020)
- [Optimizing Star-Convex Functions](https://mlsanity.com/paper/1511.04466/) (2015)
- [Second-order Online Nonconvex Optimization](https://mlsanity.com/paper/2001.10114/) (2020)
- [Accelerated Methods for α-Weakly-Quasi-Convex Problems](https://mlsanity.com/paper/1710.00797/) (2017)
- [An online learning approach to dynamic pricing and capacity sizing in service systems](https://mlsanity.com/paper/2009.02911/) (2020)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2108.03285/) (2021)
- [Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning](https://mlsanity.com/paper/2309.09411/) (2023)

## Abstract (arXiv)

Recent research has shown that quasar-convexity can be found in applications such as identification of linear dynamical systems and generalized linear models. Such observations have in turn spurred exciting developments in design and analysis algorithms that exploit quasar-convexity. In this work, we study the online stochastic quasar-convex optimization problems in a dynamic environment. We establish regret bounds of online gradient descent in terms of cumulative path variation and cumulative gradient variance for losses satisfying quasar-convexity and strong quasar-convexity. We then apply the results to generalized linear models (GLM) when the underlying parameter is time-varying. We establish regret bounds of online gradient descent when applying to GLMs with leaky ReLU activation function, logistic activation function, and ReLU activation function. Numerical results are presented to corroborate our findings.