Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: 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.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: Summary:

The paper generalizes regret analysis results from convex online learning to
functions that are not Lipschitz but Riemann Lipschitz continuous.

Example:
$f(x) = -\log(x) + x$ is convex on the convex domain $X = [0, 2]$ but $f$ is
not Lipschitz on $D$ since $f(x) \to \infty$ as $x \to 0$.

A possible Riemannian metric that can be used on the domain of such a function
is the Poincare metric $g(x) = 1 / x^2$.
The norm defined by that Riemannian metric is $\| z \|^2_x = z^T g(x) z$.
This norm can be used to measure infinitesimal distances in $X$.
The Riemannian distance $dist(x, x')$ on $X$ that follows from this is defined
as integrating over the infinitesimal distances on a curve connecting
$x$ and $x'$ as measured by the norm defined above.

Intuitively, an infinitesimal distance Lipschitz bound can be seen to be
constructed by
$| f(x + \delta x) - f(x) | \approx \| f'(x) \| \| \delta x \|$ as $\delta x \to 0$
which in the case of our example does not exist since $f'(x) \to \infty$.
But when using a Riemannian metric based norm
$\| f'(x) \| = \sqrt{ f'(x)^T g^{-1}(x) f'(x) }$
on the right-hand side we have
$f'(x) = -\frac{1}{x} + 1$
$f'(x)^2 = \frac{1}{x^2} - \frac{2}{x} + 1$
$f'(x)^2 g^{-1}(x) = O(1)$
with $g(x) = 1 / x^2$.

In this way it is possible to bound changes of $f(x)$ relative to changes in
$x$ for functions that are not Lipschitz continuous.

The authors show how a suitable Riemannian metric can be transformed into
a regularizer usuable in online optimization.
They present various rates that appear to be otherwise known for similar
regularizers.
My knowledge of the online learning literature is very limited so I cannot
make a qualified statement about these formal analyses in a reasonable amount
of time.

The authors also transfer the results from the convex online setting to the
convex stochastic setting and the nonconvex setting.

Based on my limited understanding I would recommed to accept the paper.
The analysis to me seems both rigorous and useful in practice
(at least with regard to the formal definitions of Riemannian metrics and
Riemannian Lipschitz condition for singular functions).

Remarks / Suggestions:
- With a similar knowledge of the underlying function it would perhaps be
	possible to perform a nonlinear transformation of the input space that
	leads to Lipschitz continuous function.
	Can something be said about this?

- Definition 2: Write out l.s.c. (lower semi-continuous?) as it does not seem
	to be defined everywhere and not every reader is necessarily familiar
	enough with convex analysis

- Page 8: Typo: "Eucldiean stochastic gradient method

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper investigates online and stochastic convex optimization problems in which the objective function is not Lipschitz continuous. The originality of this study lies in the use of Riemannian geometry. Specifically, the standard condition of Lipschitz continuity is replaced with a more general condition involving Riemannian distances and called Riemann-Lipschitz Continuity (RLC). Based on an appropriate definition of Riemannian regularizer and a generalization of Fenchel coupling to Riemannian geometry, the authors provide $O(\sqrt T)$ regret (resp. risk) bounds for the online (resp. stochastic) mirror descent algorithm, under the Riemann-Lipchitz condition. The performance of the algorithm is validated on Poisson inverse problems.

Overall, this is a dense, yet interesting, paper. I am not an expert in Riemannian geometry but, as far as I could check, the proofs look correct. Notably, the analysis of OMD is relatively standard, once we get a bound (Prop B.1) on the Fenchel coupling, using the Riemannian dual norm. 

I have essentially one main comment. Clearly, the concept of “Riemann-Lipschitz continuity” is different from the notions of “relative continuity” and “relative smoothness” that have been recently proposed in the literature. But it is not clear that the Riemann-Lipschitz condition can tackle convex optimization tasks in which relative continuity and relative smoothness do not hold. In particular, Poisson (linear) inverse problems have already been handled under the relative smoothness condition, using Mirror Descent or Bregman proximal methods (Hanzely and Richtarik, 2018; Hanzely et. al. 2018). Thus,
* from a conceptual viewpoint, it would be interesting to provide some applications in which the RLC condition hold, but the relative smoothness condition does not; 
* from an experimental viewpoint, in Sec. 6, it would be legitimate to compare the present “Riemannian Mirror Descent” algorithm with respect to the APBG method (Hanzely et. al. 2018) and the relSGD method (Hanzely and Richtarik, 2018). 

review_title: Official Blind Review #1

Meta-review: This is a mostly theoretical paper concerning online and stochastic optimization for convex loss functions that are not Lipschitz continuous. The authors propose a method for replacing the Lipschitz continuity condition with a more general Riemann-Lipschitz continuity condition, under which they are able to provide regret bounds for the online mirror descent algorithm, as well as extending to the stochastic setting. They follow up by evaluating their algorithm on Poisson inverse problems. 

The reviewers all agree that this is a well-written paper that makes a clear contribution. To the best of our knowledge, the theory and derivations are correct, and the authors were highly responsive to reviewers’ (minor) comments. I’m therefore happy to recommend acceptance.
Decision: Accept (Spotlight)