Online Learning With Inexact Proximal Online Gradient Descent Algorithms

Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, Ketan RajawatIEEE TSP 2019 · DOI

Introduction

In modern machine learning and signal processing, the assumption of a static optimal solution is often violated. Real-world applications, such as robotic target tracking or real-time video surveillance, require algorithms capable of following a "moving target"—a time-varying optimum. This paper by Dixit et al. introduces the Inexact Proximal Online Gradient Descent (IP-OGD) framework to address these dynamic optimization challenges, particularly when objective functions are non-smooth and gradients are computationally expensive or noisy.

Problem Formulation

Standard optimization algorithms often struggle with two primary hurdles in dynamic environments:

  1. Non-Smoothness: Many effective regularizers (e.g., $L_1$ norm for sparsity) are non-differentiable, causing standard gradient descent to fail.
  2. Computational Complexity: In large-scale "big data" scenarios, calculating exact gradients at every time step is infeasible. Practitioners often rely on "inexact" or stochastic gradients, which introduce noise that can lead to tracking drift.

The authors address these by measuring Dynamic Regret, which compares the algorithm's performance against the best possible point at every discrete time step, rather than a single fixed optimum.

Methodology

The IP-OGD framework decomposes the problem into a smooth loss function and a non-smooth regularizer.

Key Innovations

  • Proximal Mapping: By utilizing proximal operators, the algorithm efficiently handles non-differentiable penalties, outperforming general subgradient methods in tasks like foreground-background separation.
  • Handling Inexactness: The framework explicitly accounts for gradient error ($e_k$). The authors prove that the algorithm successfully tracks the optimum provided the cumulative error and the target's path length remain bounded.
  • Dynamic Variance Reduction (OP-SVRG): The authors adapt the Stochastic Variance Reduced Gradient (SVRG) method for dynamic settings. By using periodically refreshed "stale" gradient information to correct current noise, the algorithm achieves significant speedups without sacrificing tracking accuracy.

Theoretical Contributions

A central contribution of this work is the derivation of tighter regret bounds for non-differentiable problems under inexact gradients. As shown in the comparison below, the proposed method expands the scope of solvable problems while maintaining competitive regret rates.

Comparison of the proposed IP-OGD framework with existing literature.

Experimental Results

The researchers validated IP-OGD through two primary experiments:

  1. Synthetic Robot Formation: A simulation where a group of robots tracked a leader while their formation morphed from a decagon to a star. The algorithm demonstrated robust tracking despite the changing geometry.
  2. Foreground-Background Separation: Using a standard parking lot surveillance benchmark, the OP-SVRG variant achieved a 4x speedup by using only 25% sampling. Notably, it correctly identified parked cars as part of the background, whereas state-of-the-art methods like ReProCS often left "ghost" artifacts.

Conclusion

The IP-OGD framework provides a robust mathematical foundation for real-time tracking in non-smooth environments. While the variance-reduced version (OP-SVRG) requires specific conditioning ($\mu/L > 0.89$) and additional memory for gradient storage, its sublinear dynamic regret makes it a powerful tool for large-scale online learning. Future work aims to extend these results to distributed settings, such as collaborative drone swarms.

Summary updated

BibTeX
@article{dixit2019online,
  author = {Rishabh Dixit and Amrit Singh Bedi and Ruchi Tripathi and Ketan Rajawat},
  title = {{Online Learning With Inexact Proximal Online Gradient Descent Algorithms}},
  journal = {IEEE Trans. Signal Process.},
  year = {2019},
  doi = {10.1109/tsp.2018.2890368},
}
Figure