Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach

Kimon Antonakopoulos, Elena Veronica Belmega, Panayotis MertikopoulosICLR 2020 · OpenReview

Abstract: Standard optimization algorithms often fail when gradients "blow up" near the boundaries of a problem. This paper introduces a Riemannian geometry framework that redefines Lipschitz continuity, allowing researchers to achieve optimal convergence rates even for highly singular loss functions, such as those found in Poisson imaging and quantum tomography.

The Problem with Bounded Gradients

In the world of machine learning and signal processing, first-order methods like Stochastic Gradient Descent (SGD) and Mirror Descent are foundational. However, their theoretical guarantees usually rest on a restrictive assumption: Lipschitz continuity. This condition requires the "steepness" or gradient of the loss function to be bounded by a global constant.

In many real-world applications—such as Support Vector Machines (SVMs), Poisson inverse problems in medical imaging, or quantum tomography—this assumption is fundamentally violated. As the optimization process approaches the edge of the feasible region (for instance, where a pixel value drops to zero), the gradient can shoot off to infinity. When this "speed limit" of the gradient is broken, standard algorithms can oscillate wildly or fail to converge entirely. The authors of this paper seek a robust way to apply the power of online and stochastic optimization to these "singular" landscapes.

The Riemannian Solution: Taming Singularities

The authors’ core innovation is moving away from fixed, global norms (like the standard Euclidean norm) and adopting a framework based on Riemannian geometry.

Instead of measuring the change in a function against a straight-line Euclidean distance, the authors introduce Riemann–Lipschitz (RL) Continuity. They measure change against a Riemannian distance by choosing a metric tensor that "stretches" space near the singularities. Consequently, a function that appears singular and unbounded in Euclidean space becomes "smooth" and RL continuous in Riemannian space.

To make this practical, the paper provides a principled rule of thumb for metric selection: if a gradient blows up at a certain rate, the optimizer should choose a Riemannian metric that grows at a matching rate to cancel out the singularity. The authors then adapt the concept of Bregman divergences to work in harmony with these position-dependent metrics, effectively re-tooling classic algorithms like Follow the Regularized Leader (FTRL) and Online Mirror Descent (OMD) to operate within this new Riemannian framework.

Key Insights: Geometry, Harmony, and Convergence

Several powerful theoretical insights emerge from this geometric approach:

  • Geometry as a Compensator: The difficulty of an optimization problem does not lie solely in the function itself, but in the relationship between the function and the space it inhabits. By altering the geometry of the space, the function can be tamed.
  • The Three-Way Harmony: Successful optimization requires a careful alignment between the loss landscape, the Riemannian metric, and the regularizer. When these three elements are tailored to one another, optimal performance is recovered.
  • Last-Iterate Convergence: Unlike many studies that only prove ergodic convergence (convergence for the average of all guesses), this paper provides conditions—specifically, a "weak secant inequality"—under which the very last guess of the algorithm is guaranteed to be correct, even in certain non-convex settings.

Experimental Validation: Poisson Imaging

The paper validates its theoretical findings using Poisson inverse problems, a broad class of challenges common in tomography and imaging. Using the standard "Lena" test image contaminated with Poisson noise, the authors used their algorithm to reconstruct the original image.

The results are striking. The authors proved that their Riemannian FTRL and OMD achieve an $O(\sqrt{T})$ regret bound, the theoretical "gold standard" for online optimization, despite the functions being non-Lipschitz. In numerical experiments on Poisson denoising, their Riemannian Mirror Descent (RMD) outperformed the standard Lucy-Richardson algorithm by an astonishing 7 orders of magnitude in terms of loss. Furthermore, RMD outperformed the recent Composite Mirror Prox (CMP) method by 3 orders of magnitude, producing significantly sharper and more accurate image reconstructions.

Limitations and Future Directions

While the framework is highly effective, the authors note a few limitations. First, metric discovery is not yet fully automated; while the paper provides a heuristic for choosing a metric based on the singularity, it does not offer a way to "learn" the best Riemannian metric for an arbitrary, unknown loss function. Second, the current work focuses on manifolds that are topologically simple (subsets of $\mathbb{R}^d$) but not "flat" in the Riemannian sense, leaving more complex, non-Euclidean topologies (like spheres or tori) unexplored. Finally, the algorithms currently rely on a constant step-size policy ($\alpha/\sqrt{T}$). Integrating this Riemannian context with adaptive step-size methods, such as AdaGrad, remains a promising open challenge for future research.

Summary updated

Abstract

Motivated by applications to machine learning and imaging science, we study a class of online and stochastic optimization problems with loss functions that are not Lipschitz continuous; in particular, the loss functions encountered by the optimizer could exhibit gradient singularities or be singular themselves. Drawing on tools and techniques from Riemannian geometry, we examine a Riemann–Lipschitz (RL) continuity condition which is tailored to the singularity landscape of the problem’s loss functions. In this way, we are able to tackle cases beyond the Lipschitz framework provided by a global norm, and we derive optimal regret bounds and last iterate convergence results through the use of regularized learning methods (such as online mirror descent). These results are subsequently validated in a class of stochastic Poisson inverse problems that arise in imaging science.
BibTeX
@inproceedings{antonakopoulos2020online,
  author = {Kimon Antonakopoulos and Elena Veronica Belmega and Panayotis Mertikopoulos},
  title = {{Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=0KS7JdYJ-UD},
}
Figure