# Online Learning with Inexact Proximal Online Gradient Descent Algorithms

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2018.

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

- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Online Weak-form Sparse Identification of Partial Differential Equations](https://mlsanity.com/paper/2203.03979/) (2022)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [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)
- [Continuous Online Learning and New Insights to Online Imitation Learning](https://mlsanity.com/paper/1912.01261/) (2019)
- [Learning equilibria with personalized incentives in a class of nonmonotone games](https://mlsanity.com/paper/2111.03854/) (2021)
- [Predictor-corrector algorithms for stochastic optimization under gradual distribution shift](https://mlsanity.com/paper/2205.13575/) (2022)
- [Personalized incentives as feedback design in generalized Nash equilibrium problems](https://mlsanity.com/paper/2203.12948/) (2022)
- [Regret Analysis of Online Gradient Descent-based Iterative Learning Control with Model Mismatch](https://mlsanity.com/paper/2204.04722/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Optimized Gradient Tracking for Decentralized Online Learning](https://mlsanity.com/paper/2306.06375/) (2023)
- [Online Distributed Learning with Quantized Finite-Time Coordination](https://mlsanity.com/paper/2307.06620/) (2023)
- [Fusing Multiple Algorithms for Heterogeneous Online Learning](https://mlsanity.com/paper/2312.05432/) (2023)
- [WEEP: A Differentiable Nonconvex Sparse Regularizer via Weakly-Convex Envelope](https://mlsanity.com/paper/2507.20447/) (2025)
- [The Hidden Cost of Approximation in Online Mirror Descent](https://mlsanity.com/paper/2511.22283/) (2025)
- [Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization](https://mlsanity.com/paper/2205.09571/) (2022)
- [Online Non-Stationary Stochastic Quasar-Convex Optimization](https://mlsanity.com/paper/2407.03601/) (2024)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Online Learning via Learned Latent Bayesian Tracking](https://mlsanity.com/paper/2609.31559/) (2026)
- [ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations](https://mlsanity.com/paper/2609.33993/) (2026)

## Abstract (arXiv)

We consider non-differentiable dynamic optimization problems such as those arising in robotics and subspace tracking. Given the computational constraints and the time-varying nature of the problem, a low-complexity algorithm is desirable, while the accuracy of the solution may only increase slowly over time. We put forth the proximal online gradient descent (OGD) algorithm for tracking the optimum of a composite objective function comprising of a differentiable loss function and a non-differentiable regularizer. An online learning framework is considered and the gradient of the loss function is allowed to be erroneous. Both, the gradient error as well as the dynamics of the function optimum or target are adversarial and the performance of the inexact proximal OGD is characterized in terms of its dynamic regret, expressed in terms of the cumulative error and path length of the target. The proposed inexact proximal OGD is generalized for application to large-scale problems where the loss function has a finite sum structure. In such cases, evaluation of the full gradient may not be viable and a variance reduced version is proposed that allows the component functions to be sub-sampled. The efficacy of the proposed algorithms is tested on the problem of formation control in robotics and on the dynamic foreground-background separation problem in video.