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.
The paper establishes optimal regret bounds of the order O(\sqrt{T}) for Follow The Regularised Leader (FTRL) and Online Mirror Descent (OMD) for convex loss functions and potentials (a.k.a. Riemannian regularizers) that are, respectively, Lipschitz continuous and strongly convex with respect to a given Riemannian metric. These conditions naturally generalize the classical conditions typically considered in the literature, which are defined with respect to a global norm and, as such, are not well-suited to problems where the loss functions and its gradient present singularities at the boundary of the feasibility region. The authors suggest a principled way to choose both the Riemannian metric and the potential function based on the singularity landscape of the gradient of the loss function. Via standard online-to-batch conversion, the authors also address the offline setting and give O(1/\sqrt{T}) error bounds for ergodic averages in convex problems and for last iterates in non-convex problems satisfying a weak secant inequality. The authors include numerical experiments involving a Poisson inverse problem.
The paper is well-written, with a very clean narrative highlighting the main ideas and results. To the best of my knowledge, the literature review is complete and rightly highlights the fact that most results in the literature on Riemannian mirror descent methods have so far primarily addressed offline deterministic problems with exact oracle gradients. The contribution of this work lies not only in the focus on online and noisy setting but also on establishing natural results upon natural generalizations of well-known conditions in standard (non-Riemannian) settings. The techniques used are extensions of the classical theory and follow quite naturally, with the exception of the non-trivial primal-dual inequality (20).
QUESTIONS/SUGGESTIONS:
1) Can the authors be more explicit about how the (OMD) equations are derived from (16). While this is standard, I feel currently there is a bit of a jump in the narrative—which otherwise is very good.
2) The workhorse behind the established results is the primal-dual inequality (20) which relies on the introduction of the Fenchel coupling. Can the authors be more explicit about the use of this inequality, and what makes the Riemann generalization difficult in general? In particular, can the authors comment on the applicability of this inequality (or similar) to the smooth setting?
3) Typo: sometimes the notation $\mathcal{U}$ seems to be used instead of the notation $\mathcal{X}$. See, for instance, equation (7) in Definition 1 and the definition of the set $\mathcal{Z}$ in Remark 2.
AFTER REBUTTAL: I thank the authors for addressing my questions.