Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach
Authors: Kimon Antonakopoulos
E. Veronica Belmega
Panayotis Mertikopoulos
Venue:  (2020)
Keywords: Online optimization
stochastic optimization
Poisson inverse problems

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.

Published as a conference paper at ICLR 2020
ONLINE AND STOCHASTIC OPTIMIZATION BEYOND LIPSCHITZ CONTINUITY: A RIEMANNIAN APPROACH
Kimon Antonakopoulos
Inria, Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG 38000 Grenoble, France kimon. aatonakkopollosiimiii..
E. Veronica Belmega
ETIS UMRS051, CY University, ENSEA, CNRS, F-95000, Cergy, France belmega@ensea.ff
Panayotis Mertikopoulos
Inria, Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG
38000 Grenoble, France
panayotis.eertikooolllloess mertiikopouloseingg.. fr
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 tools and techniques from Riemannian geometry, we examine Riemann-Lipschit, (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 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.
INTRODUCTION
The surge of recent breakthroughs in machine learning and artificial intelligence has reaffirmed the prominence of first-order methods in solving large-scale optimization problems. One of the main reasons for this is that the computation of higher-order derivatives of functions with thousands if not millions of variables quickly becomes prohibitive; another is that gradient calculations are typically casier distribute and parallelize, especially in large-scale problems. methods have met with prolific success in many diverse fields, from machine learning and signal processing to wireless communications, nuclear medicine, and many others [10, 34, 37].
view of this, first-order
This success is especially pronounced in the field of online optimization, i.e., when the optimizer faces a sequence of time-varying loss functions f., / = 1.2...., one at time for instance, when drawing different sample points from large training set [11, 35]. In this general framework, first-order methods have proven extremely flexible and robust, and the attained performance guarantees are well known to be optimal [1, 11, 35]. Specifically, if the optimizer faces sequence of G- G-Lipschitz convex losses, the incurred min max regret after T rounds is (GGT and this bound can be achieved by inexpensive first-order methods such online mirror descent and its variants [11, 35, 36, 41].
Nevertheless, in many machine learning problems (support vector machines, Poisson inverse problems, quantum tomography, etc.), the loss landscape is not Lipschitz continuous, the results mentioned above do not apply. Thus, a natural question that emerges the following: Is it possible to apply online optimization tooly and techniques beyond the standard Lipschitz, framework? And, if so, how?

---

Published as a conference paper at ICLR 2020
Our approach and contributions. Our point of departure is the observation that Lipschitz conti- nuity is a property of metric spaces - not normed spaces. Indeed, in convex optimization, Lipschitz continuity is typically stated in terms of global norm (e.g.. the Euclidean norm), but such a norm is de facto independent of the point in space at which it is calculated. Because of this, the standard Lipschitz framework is oblivious to the finer aspects of the problem's loss landscape and, in particular, any singularities that may arise at the boundary of the problem's 's feasible region. On the other hand, in general metric spaces, this is no longer the case: the distance between two points is no longer given by a global norm, so it is much more sensitive to the geometry of the feasible region. For this reason, if the (Riemannian) distance dist(x, x') between two points x and x' becomes larger and larger as the points approach the boundary of the feasible region, condition of the form V(x)- = O(dist(x',x)) may still hold even if becomes singular at the boundary.
We leverage this observation by introducing the notion of Riemann-Lippshitz (RI.) continuity, an extension of "vanilla" Lipschitz continuity to general spaces endowed with a Riemannian metric. We show that this metric can be chosen in principled manner based solely on the singularity landscape of the problem's 's loss functions - i.e., their growth rate at infinity and/or the boundary of the feasible region. Subsequently, using similar mechanism to choose Riemannian regularizer, we provide an optimal ?2 regret guarantee through the use of regularized learning methods namely, "follow the regularized leader" (FTRL) and online mirror descent (OMD).
Our second contribution concerns an extension of this framework to stochastic programming. First, in the context of stochastic convex optimization, show that an online-to-batch conversion yields an O(T-1/2) value convergence rate, Second, motivated by applications to nonconvex stochastic programming (where averaging not a priori beneficial), we also establish the convergence of the method's s last iterate in a class of nonconvex problems satisfying a weak secant inequality. Finally, we supplement our theoretical analysis with numerical experiments in Poisson inverse problems.
Related work. To the best of our knowledge, the first treatment of a similar question was undertaken by Bauschke et al. [3] who focused on deterministic, offline convex programs (ʃ; = f for all z) without Lipschitz smoothness assumption (i.e., Lipschitz continuity of the gradient, as opposed Lipschitz continuity of the objective). To tackle this issue, Bauschke et al. [3] introduced second-orde "Lipschitz-like" condition of the form f & / for some suitable Bregman function h, and they showed that Bregman proximal methods achieve an O(1/T) value convergence rate in offline convex problems with perfect gradient feedback.
Always in the context of deterministic optimization, Bolte et al. [8] extended the results of Bauschke et al. [3] to unconstrained non-convex problems and established trajectory convergence to critical points for functions satisfying the Kurdyka-t.ojasieviin
(KL) inequality. In slightly different vein, Lu et al. [25] considered functions that are also strongly convex relative to the Bregman function defining the Lipschitz-like condition for the gradients, and they showed that mirror descent achieves a geometric convergence rate in this context. Finally, in a very recent preprint, Hanzely et al. [17] examined the rate of convergence of an accelerated variant of mirror descent under the same Lipschitz-like smoothness assumption.
Importantly, all these works concern offine, deterministic optimization problems with perfect gradient feedhack and regularity assumptions that cannot be exploited in an online optimization setting (such as the KL inequality). Beyond offline, deterministic optimization problems, Lu [24] established the ergodic convergence of mirror descent in stochastic non-adversarial convex problems under a "relative continuity" condition of the form f(v]l s G iiff V2D xx)lIxx' xil (with D denoting the divergence of an underlying "reference" Bregman function h). More recently, Hanzely and Richtárik [16] examined the performance of stochastic mirror descent under a combination of relative strong convexity and relative smoothness/ Ceaiiinessssiiispssceee Lipschitz-like conditions, and established series of convergence rate guarantees that mirror the corresponding rates for ordinary (Fuclidean) stochastic gradient descent. Except for trivial cases, these conditions are not related to Riemann-Lipschizz continuity, so there is no overlap in our results our methodology.
Finally, in very recent paper, Bécigneul and Ganea [5] established the convergence of a class of adaptive Riemannian methods in geodesically convex problems (extending in this way classical results for AdaGrad to manifold setting). Importantly, the Riemannian methodology of [5] involves the exponential mapping of the underlying metric and focuses on geodesic convexity, so it concerns an orthogonal class of problems. The only overlap would be in the case of flat Riemannian manifolds:
2

---

Published as a conference paper at ICLR 2020
however, even though the manifolds consider here are topologically simple, they not flat.' In view of this, there is no overlap with the analysis and results of [5].
2 PROBLEM SETUP
We begin by presenting the core online optimization framework that we will consider throughout the rest of our paper. This can be described by the following sequence of events:
1. At each round / = 1,2, the optimizer chooses an action X, from a convex - but not necessarily closed or compact subset X' of ambient normed space V Rd.
The optimizer incurs a loss fi(X;) based on some (unknown) convex loss function fr: X - R.
3. The optimizer updates their action and the process repeats.
Remark 1. For posterity, we note that if X' is not closed, fi (or its derivatives) could become singular do not assume here that admits a smooth
residual point bd(X)) X; in particular, extension to the closure cl(2t) of X' (or even that it is bounded over bounded subsets of X).
In this broad framework, the most widely used figure of merit is the minimization of the agent's regret. Formally, the regret of a policy X, E x2 1,2...., defined as
Reg, (T) = -
- f(x0).
(1)
1=1
for x E X. We then say that the policy X, leads to no regret if Reg, o(T) for all X. In addition convexity, the standard assumption in the literature for the problem's loss functions is Lipschitz continuity, i.c.,
lf(x') f((x) G x!I
(LC)
for some G, 2 0, 1.2..... and for all x, X. Under (LC), if the agent observes at each
stage an element of (x))), straightforward online policies based on gradient descent enjoy bound of the form (7), (()))12), with G2 7-1 Σ G? [11, 35, 41]. particular,
G lim sup Gr < (e.g., if each G-Lipschitz continuous over X'), we have the bound
Reg, (
(2)
which is well known to be min-max optimal in this setting [1].
paper, make clear distinction between V and its dual, and we use Dirac's 's notation (ulx) for the duality pairing between u E V and x E V (not to be confused with the notation (.--) for scalar product V). Also, unless mentioned otherwise, all notions of boundary and interior should be interpreted in the relative (as opposed to topological) sense. We also make the blanket assumption that the subdifferential θf, of f, admits continuous selection f((x) e 0f(() for all x dom of; = (x E X 0ff(x) # Ø).
A note notation. Throughout
3 RIEMANN- CONTINUITY
Despite its generality, (LC) may fail to hold in wide range of problems and applications, ranging from support vector machines to Poisson inverse problems, quantum tomography, etc. [3, 8, 25). The loss functions of these problems exhibit singularities at the boundary of the feasible region, so the standard regret analysis cited above no longer applics. Accordingly, our first step will be to introduce family of local norms ll. X, such that variant of (LC) holds even if the derivatives Of /Ox; of f blow up near the boundary of X.
To achieve this, will employ the notion of Riemannian metric. This is simply position- dependent scalar product on V. i.e., continuous assignment of bilinear pairings (. x E X, satisfying the following conditions for all e V and all X::
For example, the open unit simplex endowed with the Shahshahani metric is isometric to the positive orthant of sphere with the round metric (cf. Section 3). This space has constant positive curvature and the geodesics are portions of great circles, so the analyses very different that case.
3

---

Published as a conference paper at ICLR 2020
1. Symmerry: (2,2),, (2,2)x
2. Positive-defmittenes:: (2, with equality if and only if 0.
More concretely, in the standard basis teil of R2, we define the metric tensor of (: as the matrix g(x) Rddd with components
91y(x)= = (ei, ei
A.=l......
(3)
The norm of z V at E X is then defined as
| (z, 2) Σ = LF
= =
(4)
In this way, Riemannian metric allows us to measure lengths and angles between displacement vectors at each x E X: for illustration, we provide some notable examples below:
Example 1 (Euclidean geometry). The ordinary Euclidean metric on X' = Rd is g(x) = I. This yields the standard expressions Ilall; Σi 27 and (z,z'), = Σ zęZ, both independent of x.
Example 2 (Hyperbolic geometry). The Poincaré metric on the positive orthant X' R
g(x) diag(I/
leading to the local norm || = half-space model for hyperbolic geometry [22]; this will become important later.
Under (5), Rá, can be seen as variant of Poincaré's
Given Riemannian metric X, the length of curve y: [0, 1] - X' is defined as 4,ly] [C (ly00 ds, and the Riemannian distance between x1. E X' is given by disty(x1, x2) inf, Lyly].
(6)
Under this definition, is natural to introduce the following Riemannian variant of (L.C): Definition 1. We say that f: X R is Riemann-lipschit, continuous relative to g if
If(x) - f(x) = G dxsty(x,x') for some and all X X.
Albeit simple to state, (RLC) may difficult to verify because requires the computation of the distance function dist, of - which, in turn, relies on geodesic calculations to identify the shortest possible curve between two points. Nevertheless, if f differentiable, Proposition below provides an alternative characterization of Riemann-
continuity which is easier work with:
Proposition 1. Suppose that f: X - R is differentiable. Then, (RLC) holds if and only if
llgrad f(x)ll S G for all x e X.
(RLC)
Remark 2. In the above, the Riemannian gradient grad f(x) of at x is defined as follows: First, let Z = span[xx : x x'x X3) denote the tangent hull of X. Then, f(x) E Z is defined by the characteristic property
f((: = (grad f(x), 2)x for Ze Z.
Existence and uniqueness of grad f(x) is due to the fact that g(x) is positive-definite - and, hence, invertible [22]. In particular, if X' is full-dimensional (so Z V), we have:
Igrad f(x)); = E (10)
The proof of Proposition 1 requires the introduction of further tools from Riemannian geometry; seeing as these notions are not used anywhere else in our paper, we relegate it to the appendix. Instead, close this section with simple example of singular function which is nonetheless Lipshnn- continuous:
4

---

Published as a conference paper at ICLR 2020
Example 3. Let X' [0, (0)) (so X' is convex but neither open closed) and let f(x)
log(a" x) for some positive vector a E R,,.. we take gi,(x) = 6t/(Xi +... + xa)² we get
l|grad f(ol Σ d; (E xi)
Σ oj
(10)
(a"x)²
(miny az)²
Thus, although f is not Lipschitz continuous in the standard sense, it is Riemann Lipscchtt continuous relative to y: we will revisit this example in our treatment of Poisson inverse problems in Section 6.
More generally, Example suggests the following rule of thumb: if f exhibits a gradient singularity of the form [0, (()(x) some residual point cl(X) X' of X, taking 9i,(x) oij gives O(I). On that account, f is Riemann-Lipscitz continuous, even though its derivative is singular; we find this heuristic particularly appealing because it provides a principled choice of Riemannian metric under which f satisfies (RLC).
l|grad f(x)); ((x)~ [0,
ALGORITHMS
In this section, we present the algorithms that we will study in the sequel: "follow the regularized leader" (FTRL) and online mirror descent (OMD). Both methods have been widely studied in the literature in the context of "vanilla" Lipschitz continuity; however, beyond this basic setting, treating FTRL/OMD in the Riemannian framework of the previous section is an intricate affair that requires several conceptual modifications. For this reason, we take in-depth look into both methods below.?
4.1 REGULARIZATION
We begin with the idea of regularization through suitable penalty function. In Riemannian setting, we adapt this notion as follows:
Definition Let g be a Riemannian metric on X' and let continuous (l.s.c.) convex function with dom h = X.3 We say that h is a Riemannian regularizer on X if:
R be proper lower semi-
1. The subdifferential of h admits continuous selection, i.e., continuous function Vh such that Vh(x) E öh(x) for all x E X = dom oh.
2. h is strongly convex relative to g, i.e.,
h(x') 2 h(x) + (Vh(x)xx - x) [ xII?
(1I)
for some K 0 and all X2, x E X. The Bregman divergence induced by h is then defined for all p X. E X as
D(p. x) = h(p) h(x) - <Vh(x)lp x).
(12)
There are two points worth noting in the above definition. First, the domain of is all of X, but this need not be the case for the subdifferential oh of h: by convex analysis arguments [33, Chap. 26]. have ri X' S A dom dh X. To connect the two, will say that h is Riemann-Legendre regularizer when x = ri X' and D(p, xx,) - whenever x,
Second, strong convexity in (11) is defined relative to the underlying Riemannian metric. If the norm in (11) does not depend on x, we recover the standard definition; however, the dependence of the second-order term in (11) on g can change the landscape significantly. Lemma and Example below provide an illustration of this interplay between g and h:
Lemma 1. A Riemannian regularizer h K-strongly convex relative to g if and only if
D(p, 2 1 xII
(13)
For convenience, we tacitly assume what follows that g(x) > pul for some μ and all e X. Since 0. this can always be achieved without loss of generality hy replacing g by g μl. Following standard convex analysis terminology. "proper" means here that h * 400 while lower semi- continuous refers the property that lim inf, inf,-. h(x) h(xx) for all x, V.
5

---

Published as a conference paper at ICLR 2020
The proof of Lemma follows from rearrangement of (11) so omit it. Instead, present below some examples of Riemannian regularizers:
Example 4. Let X' = [0. IJ", and consider the so-called Burg entropy h(x) = - Σ/= log x,. It is easy to see that h(x) is strongly convex relative to the standard Euclidean norm I|-122. Moreover, have
Pi X2
x(p,))
x)
log
-
(14)
E
and, by Taylor's theorem with Lagrange remainder, we readily get
- x;)
x(p,x) x)
1lp x1|
(15)
X2
where |kall = Ei=1 2//x, denotes the so-called Shahshahani norm on X' (i.e., h is also strongly convex relative to |HHlk). This regularizer has been used extensively in the setting of Poisson inverse problems and plays central role in the analysis of Bauschke al. [3], Hanzely and Richtárik [16], He et al.
[18), and Lu et al. [25]. For completeness, we revisit it in Section 6.
Example 5. Let X' and g be as in Example 3, and let h(x) (1 + A\ E with p²= Σi x/. Then, a tedious (but otherwise straightforward) algebraic calculation gives
(x) pi) x
D(p.x)
1p xII
(16)
ie., J is strongly convex relative to g. By contrast, due to the singularity of g at O, it is easy to check that the Euclidean regularizer h(x) = (1/2) Ed x is not strongly convex relative to g.
4.2 ALGORITHMS AND FEEDBACK STRUCTURE
With these preliminaries in hand, we begin with the FTRL algorithm, which we state here follows:
Σ f(x)+(+++++)))) + /b(x)
X,+1 arg min xEX
(FTRL)
In the above, > O is a step-size parameter whose role is discussed below; as for the existence of the arg min, this is justified by the lower semicontinuity and strong convexity of h together with the fact that dom / = X' (so the minimum cannot be attained in the residual set cl(2') X' of X)).
In terms of feedback, FTRL assumes that the optimizer has access all the loss functions encountered up to given round (except, of course, for the current one). In many cases of practical interest, this assumption too restrictive and, instead, the optimizer only has access to a first-order oracle for each fi. To model this feedback structure, we assume that once X, has been chosen, the optimizer receives an estimate 0, of (((,) satisfying the following hypotheses:
a) Unbiasedness:
E(u, Fi1 f(()))
(17a)
b) Finile mean square:
11 Fi = M/.
(17b)
In the above, Il-ll- denotes the dual norm of Ilx,,,, i.c., the Riemannian norm at the point X, where the oracle was called (we suppress here the index X, and write Il-ll, instead of Il-lxx.. to lighten the notation). In particular, the oracle feedback e, may fail to be bounded in L2 relative to any global norm on V*; such, (17) is considerably weaker than the standard L b.-boundessess assumption for global norms. Finally, in terms of measurability, the expectation in (17) is conditioned on the history F, of X, up to stage I; since e is generated randomly from X,, it is not Fr-eesurable.
To proceed, the main idea of mirror descent is to replace fa(x) in (FTRL) with the first-order surrogate f((x) f(X,) + (V (V((X))xx- X,). In this way, substituting n, for the estimate of V f((,)) received at stage s, we obtain the linearized FTRL scheme
X arg mi Ei + h(x)).
(18)
To rewrite this process in recursive form, introduce the auxiliary (dual) variable
Y *+ Y, yo,
(19)

---

Published as a conference paper at ICLR 2020
so 1111 -y Uy and hence
X,11 arg min(h(x) - (Yeil>>) arg max - -h(x))
(20)
xex
xe.2
Therefore, letting
@ arg (g)l)) - h(x))
(21)
denote the so-called "mirror map" of the method, we obtain the following incarnation the online mirror descent (OMD) algorithm:
Y = Y, - yu
(OMD)
x 2()++).
This version of OMD also known as "dual averaging" [26. 29, 30, 38] or "lazy mirror descent" [35]; for a "greedy" variant, see [6, 27, 28] and references therein.
5 ANALYSIS AND RESULTS
5.1 REGRET ANALYSIS
We begin by stating our main results for the regret minimization properties FTRL and OMD. Throughout this section, make the following blanket assumptions:
1. Both algorithms are initialized at the "prox-center" = arg min h of X and are run with (constant) step-size a//T//2 for some > 0 chosen by the optimizer.
2. The 1-th stage loss function fi: X
convex and satisfies (RLC) with constant G, 3. The optimizer's aggregate loss Σ fi attains its minimum value at some x" E X.
The purpose of the last assumption is avoid cases where the infimum of loss function is not attained within the problem's feasible region (such as e over R.). We then have:
Theorem 1.
Let (Tg(T) = Reg, (T), C2 = T Σ G?.. and M2 = T Σ M?. Then:
a) The FTRL algorithm enjoys the regret bound
xx)
2aG2
Reg(T) <
+
VT.
(22a)
K
b) The OMD algorithm with noisy feedback of the form (17) enjoys the mean regret bound
D(x",xe) xx)
aM
[[Reg(T))
T
VT.
(22b)
2K
In particular, if sup, G, < 0o, sup, M, co, both algorithms guarantee O( VT) regret.
Remark 3. We emphasize here that the O( VT) regret bound above achieved even i if the "Bregman depth" I1 = sup D(x, xe) sup h inf f of X' is infinite." Of course, if H < co and G (or M) is known to the optimizer, (22) can be optimized further by tuning a. When these constants are unknown, achieving optimized constant by means of adaptive step-size policy is an important question, but one which lies beyond the scope of this paper.
unbounded
The main idea behind the proof of Theorem is to relate the Riemannian structure of X' to the Bregman regularization framework underlying (FTRL) and (OMD). A surst link is provided by the Bregman divergence (12); however, because of the primal-dua interplay between X, E X and Y, E V", the Bregman divergence not sufficiently adapted. To overcome this difficulty, we employ the Fenchel coupling between target point e X' and E V" defined here as
d y) = h(p) h (ylp) for all p X, Y"
(23)
"To see this, simply note that D(x, h(x) h(x,) (Vh(x))r- x.) < oa for all x E X' = dom h (recall also that, since x, arg min we have 0 dh(x,)) x, dom @h).
7

---

Published as a conference paper at ICLR 2020
with (1) max Xylx)
h(x)) denoting the convex conjugate of ht As we show in the appendix,
the Fenchel coupling (which is non-negative by virtue of Young's s inequality) enjoys the key property
Y 2K
Φ(p.y - yu) = p(p. (y)l(()) - p)
Iolll
Q91.
(24)
It is precisely this primal-dual inequality which allows us to go heyond the standard Lipschitz framework: compared to (primal-primal) inequalities of similar form for global norms [2. 21, 27, 30, 40), the distinguishing feature of (24) is the advent of the Riemannian norm ||e||x,.. Thanks the intricate connection between g and h, the second-orde term in (24) can be controlled even when the received gradient unbounded relative to any global norm, i.e., even if the objective is singular.
The main obstacle to achieve this is that the underlying Riemannian metric g. the Fenchel coupling ① and the Bregman divergence D) (all state-dependent notions of distance) need not be compatible with one another. That this is indeed the case is owed to Lemma I: tethering the Riemannian norm in (13) to the second argument of the Bregman divergence instead of the first (or any other point in-between) plays crucial role in deriving (24), Any other relation between and h along these lines is not amenable to analyzing (FTRL) or (OMD) in this framework.
5.2 APPLICATIONS TO STOCHASTIC OPTIMIZATION
The second part of our analysis concerns stochastic optimization problems of the form minimize f(x)= = [[F((;
(Opt)
subject to X
with the expectation taken over some model sample space Q. Our first result here is as follows:
Theorem 2. Assume that f is convex and Riemann-Lipschiz continuous in mean square, i.e. sup, F(IVF (x; z M for some M > O. If (OMD) is run for T iterations with constant step-size of the form a/ NT and stochastic gradients e, VF wi) generated by an i.i.d. sequence w. E Ω. we have
Dr + aM² a
BIS(XT) S f f+
(25)
2K
VT
where XT= (1/T) EL X, is the "ergodicc average" of X, and D. inf reargmin D(x', xx)) < co denotes the Bregman distance of the prox-center x, of X to arg min f.
The key novelty in Theorem is that the optimal O1- convergence rate of OMD is maintained even if the stochastic gradients of F become singular at residual points E cl(A') \ &. As with the regret guarantee of Theorem 1, this is achieved by the intricate three-way relation between the landscape of f. the underlying Riemannian metric (which is tailored to the singularity profile of the latter), and the Riemannian regularizer ht The proof of Theorem 2 likewise relies on an online-to- bo-batch conversion of the regret guarantees of (OMD) for the sequence of stochastic gradients F w.) of fi the details can be found in the appendix.
To go beyond the ergodic guarantees of Theorem 2, also analyze below the convergence of the "last iterate" of OMD, i.e., the actual sequence of generated points x,. This is of particular interest for non-convex problems where ergodic convergence results of limited value (because Jensen's 's inequality no longer applies). To obtain global convergence results in this setting, we focus on a class of functions which satisfy weak secant inequality of the form
iVf((V x²) x arg min K
(SI)
for every closed subset KC of X' that is separated by neighborhoods from arg min f. Variants of this condition have been widely studied in the literature and include non-convex functions with complicated ridge structures [9, 13, 19, 20, 23, 31, 39, 40]. this very general setting, we have:
Theorem 3. Assume f satisfies (SI) and is Riemann -iemahr-Lipschitz continuous in L2. Suppose further that arg min f is bounded and (OMD) is run with a sequence of stochastic gradients v, V. w.). a Riemann- Riemann-Legendre regularizer h, and a variable step-size y, such that Σ y, = c0, E yi 00.
Then, with probability 1, X, converges some (possibly random) x" arg f.
8

---

Published as a conference paper at ICLR 2020
Poisson dara
CMP reconstraction
RMD reconstraction
Poisson Minimization
KL giveggeeee
0.100
Lit avanad)
10"
CMP lest averac)
RMDD lets, avarape
100
1000
Figure 1: Reconstruction of the Lena test image from sample contaminated with Poisson noise. Left right: (a) contaminated sample: (b) CMP reconstruction; (c) RMD reconstruction; and (d) Poisson likelihood loss at each iteration. The RMD process provides a sharper definition of image features relative to the CMP algorithm (which is the second-best).
The proof for Theorem 3 hinges combining gquaai-)supermartingee convergence results with the basic inequality (24); we detail the proof in the paper's appendix. Seeing as (SI) holds trivially for (pseudo-Jeonvex functions, we only note here that Theorem 3 complements Theorem 2 in an important way: the convergence of X, implies that of X, so the convergence of E[f(X)) to min follows immediately from Theorem 3; however, the rate of convergence (25) doesn't In practice, the ergodic average converges to interior minimizers faster than the last iterate but lags behind when tracking boundary points and/or in non-convex landscapes; we explore this issue Section below.
NUMERICAL EXPERIMENTS IN POISSON INVERSE PROBLEMS
For the purposes of validation, we proceed with an application of our algorithmic results to broad class of Poisson inverse problems that arise in tomography problems. Referring the reader to the appendix for the details, the objective of interest here is the Poisson likelihood loss (generalized Kullback-Leibler divergence):
TH [r log (Hx))
f(x)
(Hx)) us)
(26)
where u RR is vector of Poisson data observations (e.g., pixel intensities) and RRad is an ill-conditioned matrix representing the data- lata-gathering protocol. Since the generalized KI. objective of (26) exhibits an O(1/x) singularity at the boundary of the orthant, we consider the Poincaré metric g(x) diag(I/xı..... 1/xa) under which the KL divergence is Riemann-Lipschtz continuous (cf. Example 2). Going back to Example 3, a suitable Riemannian regularizer for this metric is h(x)) Σ 1/x;, which is 1-strongly convex relative to g. We then run the induced mirror descent algorithm with an online-to-batch conversion mechanism as described in Section 5.2. For reference purposes, call the resulting process Riemannian mirror descent (RMD).
Subsequently, we ran RMD on a Poisson denoising problem for 384 x 384 test image contaminated with Poisson noise (so d æ 10 in this case). For benchmarking, we also ran fast variant of the widely used Lucy-Richardson (LR) algorithm [7], and the recent composite mirror prox (CMP) method of [18]; all methods were run with stochastic gradients and the same minibatch size. Because of the "dark area" gradient singularities when [Hx]; - O, Euclidean stochastic gradient methods oscillate without converging, so they are not not reported. As we see in Fig. 1, the RMD process provides the sharpest reconstruction of the original. In particular, after an initial warm-up phase, the last iterate of Riemannian mirror descent consistently outperforms the LR algorithm by orders of magnitude, and CMP by 3. We also note that the Poisson likelihood loss decreases faster under the last iterate of RMD relative to the different algorithmic variants that we tested, exactly because the hysteresis effect that is inherent ergodic averaging.
Overall, we note that the introduction of an additional degree of freedom (the choice of Bregman function and that of the local Riemannian norm), makes RMD particularly flexible and powerful paradigm for loss models with singularities. We find these results particularly encouraging for further investigations the interplay between Riemannian geometry and fregman--roxiine methods.

---

Published as a conference paper at ICLR 2020
7 CONCLUDING REMARKS
Owing to its connections with machine learning (support vector machines, Poisson inverse problems, quantum tomography, etc.), venturing beyond Lipschitz continuity is fruitful research direction that has recently generated considerable interest in the literature. Depending on the type of continuity or smoothness encountered (Lipschitz continuity of the objective or Lipschitz continuity of the objective's s gradients), the results can be significantly different, and it is not a priori clear which surrogate smoottness/continutyy condition would be the most appropriate for any given problem. The present paper provides complementary, Riemannian-geonenn be fairly promising for the design of efficient optimization algorithms in this context. The precise characterization of the interplay between the different continuity conditions considered in the literature is an important open issue which we leave for future work.
viewpoint which we feel can
ACKNOWLEDGMENTS
The authors gratefully acknowledge financial support from the French National Research Agency (ANR) under grants ORACLESS (ANR-6-CC33--00-00) and ELIOT ANR--1-CE44000300 as well as the FAPESP 2018/12579-7 project. This work also benefited from financial support by MIAI Grenoble Alpes (Multidisciplinary Institute in Artificial Intelligence).
REFERENCES
[1] Abernethy, Jacob, Peter L. Bartlett, Alexander Rakhlin, Ambuj Tewari. 2008. Optimal strategies and minimax lower bounds for online convex games. COLT '08: Proceedings of the 21 Annual Conference Learning Theory.
[2] Balandat, Maximilian, Walid Krichene, Claire Tomlin, Alexandre Bayen. 2016. Minimizing regret on
reflexive Banach spaces and Nash equilibria in continuous zero-sum games. NIPS '16: Proceedings of the 30th International Conference on Neural Information Processing Systems.
[3] Bauschke, Heinz H., Jérôme Bolte, Mare Teboulle. 2017. A descent lemma heyond Lipschitz gradient continuity: First-order methods revisited and applications. Mathematics of Operations Research 42(2) 330-348.
[4] Bauschke, Heinz H., Patrick Combettes. 2017. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. 2nd ed. Springer, New York, NY, USA.
[5] Bécigneul, Gary, Detavian-Eugee Ganea. 2019. Riemannian adaptive optimization methods. ICLR '19: P Proceedings of the 2019 International Conference on Learning Representations.
[6] Beck, Amir, Mare Teboulle. 2003. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters 31(3) 167-175.
[7] Bertero, Mario, Patrizia Boccacci, Gabriele Desiderå, Giuseppe Vicidomini. 2009. Image deblurring with Poisson data: from cells to galaxies. Inverse Problems 25(12) 123006.
[8] Bolte, Jérôme, Shoham Sabach, Mare Teboulle, Yakov Vaisbourd. 2018. First order methods heyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization 28(3) 2131-2151.
[9] Bottou, Léon. 1998. Online learning and stochastic approximations. On-line learning in neural networks 17(9) 142.
[10] Bubeck, Sébastien. 2015, Convex optimization: Algorithms and complexity. Foundations and Trends in
Machine Learning 8(3-4) 231-358.
[11] Bubeck. Sébastien, Nicolò Cesa-
Cesa-Bianchi, Bianchi. 2012. Regret analysis of stochastic and nonstochastic arme bandit problems. Foundations and Trends in Machine Learning 5(1) 1-122.
[12] Chen, Gong, Marc Teboulle. 1993. Convergence analysis a proximal- like minimization algorithm using Bregman functions. SIAM Journal on Optimization 3(3) 538-543.
[13] Facchinei. Francisco, Jong-Shi Pang. 2003. Diiie--Dimesi Variational Inequalities and Complemen- tarity Problems. Springer Series in Operations Research, Springer.
[14] Ferreira, Orizon P. 2006. Proximal subgradient and characterization of Lipschitz function Riemannian manifolds. Journal of Mathematical Analysis and Applications 313 587-597.
[15] Hall, P., C. C. Heyde. 1980. Martingale Limit Theory and Its Application. Probability and Mathematical Statistics, Academic Press, New York.
[16] Hanzely, Filip, Peter Richtárik. 2018. Fastest rates for stochastic mirror descent methods. https:
//aaxiv.org//// www.o//////////////ee//////////e 07374.
10

---

Published as a conference paper at ICLR 2020
[17] Hanzely, Filip, Peter Richtárik, Lin Xiao. 2018. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. https://arxiv, wwt./bs/////aeeeeoo 03045.
[18] He, Niao, 7aid Harchaoui, Yichen Wang. Le Song. 2016. Fast and simple optimization for Poisson likelihood models.
http:///axxvvv///aaae/ /ttbb///1............ 01264.
[19] Jiang, Houyuan, Huifu Xu. 2008. Stochastic approximation approaches to the stochastic variational inequality problem. IEEE Truns. Autom. Control 53(6) 1462-1475.
[20] Karimi, Hamed, Julie Nutini, Mark Schmidt. 2016. Linear convergence of gradient and croximal-gradies methods under the Polyak--.ojasiewiizz condition. https://arxit orggabs/1600 04636.
[21] Krichene, Walid. 2016. Continuous and discrete dynamics for online learning and convex optimization. Ph.D. thesis, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley.
[22] Lee, John M. 1997. Riemannian Manifolds: an Introduction to Curvature. No. 176 in Graduate Texts in Mathematics, Springer.
[23] Ljung. Lennart. 1978. Strong convergence of a stochastic approximation algorithm. Annals of Statistics 6(3) 680-696. [24] Lu, Haihao. 2017. "Relative-continiit"" for non-iiisciitz non-smooth convex optimization using stochastic (or deterministic) mirror descent. nttps://arxiv> .org ottp///////////////////////////e 04718.
[25] Lu, Haihao, Robert M. Freund, Yurii Nesterov. 2018. Relatively-smooth convex optimization by first-order methods and applications. SIAM Journal on Optimization 28(1) 333-354.
[26] Mertikopoulos, Panayotis, Zhengyuan Zhou. 2019. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming 173(1-2) 465-507.
[27] Nemirovski, Arkadi Semen, Anatoli Juditsky, Guanghui Lan, Alexander Shapiro. 2009. Robust stochastic
approximation approach to stochastic programming. SIAM Journal on Optimization 19(4) 1574-1609,
[28] Nemirovski, Arkadi Semen, David Berkovich Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY.
[29] Nesterov, Yurii. 2007. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming 109(2) 319-344.
[30] Nesterov, Yurii, 2009. Primal-dual subgradient methods for convex problems. Mathematical Programming 120(1) 221-259.
[31] Nevel'son, M. B.. Rafail Z. Khasminskii. 1976. Stochastic Approximation and Recursive Extimation. American Mathematical Society, Providence, RI.
[32] Robbins, Herbert, David Sigmund. 1971. convergence theorem for nonnegative almost supernartingales and some applications. J. S. Rustagi. ed., Optimizing Methods in Statistics. Academic Press, New York,
NY, 233-257.
[33] Rockafellar, Ralph Tyrelll. 1970. Conver Analysis. Princeton University Press, Princeton, NJ.
[34] Scutari, Gesualdo, Francisco Facchinei, Daniel Pérez Palomar. Jong-Shi Pang. 2010. Convex optimization. game theory, and variational inequality theory multiuser communication systems. IEEE Signal Process. Mag. 27(3) 35-49.
[35] Shalev-Shwarde Shai. 2011. Online learning and online convex optimization. Foundations and Trends in Machine Learning 4(2) 107-194.
[36] Shalev-Shwartz. Shai, Yoram Singer. 2007. Convex repeated games and Fenchel duality. Advances in Neural Information Processing Systems 19, MIT Press, 1265-1272.
[37] Sra, Suvrit, Sebastian Nowozin, Stephen J. Wright. 2012. Optimization for Machine Learning. MIT Press, Cambridge, MA, USA.
[38] Xiao, Lin. 2010. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research 11 2543-2596.
[39] Zhang, Hui. Wotao Yin. 2013. Gradient methods for convex minimization: Better rates under weaker conditions. /ttpss:/arxiv.... wwtp://///////////////es /5t//3333.4444..
[40] Zhou, Zhengyuan, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, Peter W. Glynn. 2017. Stochastic mirror descent for variationally coherent optimization problems. NIPS '17 Proceedings of the 31st International Conference Neural Information Processing Systems.
[41] Zinkevich, Martin. 2003. Online convex programming and generalized infinitesimal gradient ascent. ICML '03: Proceedings of the 20th International Conference on Machine Learning. 928-936.
11

---

Published as a conference paper at ICLR 2020
A
CONTINUITY
In this appendix, our main goal is to prove Proposition 1, i... the equivalence between (7) and (RLC) when f is differentiable.
To do so, we first need to introduce the notion of a geodesic, i.e., a length-minimizing curve that attains the infimum inf, L[y] over all piecewise smooth curves joining two points X1. U. That such curve exists and is unique in our setting is a basic fact of Riemannian geometry [22]. Moreover,
given a tangent vector E 2, this leads the definition of the exponential mapping exp: U x 2 U so that
(A.1) where Y2 denotes the unique geodesic emanating from x with initial velocity vector y. = z. We then have exp,,tz)= (1(1) for all and, moreover, for sufficiently small r O, the restriction of exp, to ball of radius r in is a diffeomorphism onto its image U. The largest positive number i, such that the above holds for all < ię is then known as the injectivity radius of LI at x [22].
(x + exp,(z) = (I()),
Our proof of the equivalence between (7) and (RLC) follows a simplified version of the approach of Ferreira [ [14] who, to our knowledge, was the first to diseuss the concept of proximal subgradients in Riemannian manifolds. To that end, fix some x U, let z grad f(x) and consider the ray emanating
from
y(t) = exp, (tz/llll))....
(A.2)
Since y is a geodesic, we readily obtain (x, y()) = / for all sufficiently small t. Also, by construction, we have exp," y(1) = fz/lk=llr- Hence, with f convex, it follows that, for some constant 0 and for sufficiently small positive 5 < iz. have
f(y(t) f(x) 2 (z, exppp) a dist, y(1)).
(A.3)
(A.4)
where used the local topological equivalence of the Riemannian topology and the standard topology of R and the fact that (xp,(r) (f) is diffcomorphism for sufficiently small 5 > 0 and hence, for all ō i,. Thus, if f is also Riemann-Lipschit continuous in the sense of (7), we will also have
Gr f((()) f(x) 2 (z, fz/llelk)) at..
(A.5)
Thus, by isolating the leftmost and rightmost hand sides, dividing by and taking the limit - 0, we get
Ilgrad f(x)], ||z|l, S G.
(A.6)
as to be shown.
To establish the converse, assume that (RLC) holds, fix x, x' E X' pick K > G and a sufficiently small
8 > O, and consider the Riemannian distance majorant w(x) dxst,(x,xx') if dxst)(x,xx) < Ó, and w(x)= K disty(x,,x') e²/(6 when ö < disty x') 28, with dxsty(x,
simple calculation then shows that l|grad w(x)ll. 2 > G. It is also straightforward to show that the minimum of f is attained x',
f(x) f(x) w(x')
$ f(x) + w(x)
s f(x) + K dxst,(x,,x')
(A.7)
Then, by interchanging x and x' above, we obtain If(x) f(x') s K xx,), Since K > G has been chosen arbitrarily, (7) follows.
B PROPERTIES OF MIRROR MAPPINGS AND THE FENCHEL COUPLING
We begin by recalling and clarifying some of the notational conventions used in the paper. First, let V Rd be imite-dimensional real space; then, its dual space will be denoted by y = V*, and write (ylx) for the duality pairing between E y and x e V. Also, if |I-I| is a norm on V, the dual norm on } is defined as ||yl.. = sup((y)x) [|x|| 1).
12

---

Published as a conference paper at ICLR 2020
Given an extended-real- valued convex function f: X - RU we will write dom f= {x V : f(x) < oo) for its effective domain. The subdifferential of f at x E dom f is then defined as åf(x) = (y E f(x') f(x)))())x)>> (ylx' -x 2 0 for all x' ε V) and the domain of subdiffereniiability of ffis dom Of = (x E dom f 0f # Ø). Finally, assuming it exists, the directional derivative of f along 2 V is defined ("xx; = d/d + tz). We will then say that f is differentiable at x E dom/ f if there exists f(x) E y such that (V((x))) = fx; for all vectors of the form z= - x, x' E dom
With these notational conventions at hand, we proceed to prove some auxiliary results and estimates that are used throughout the analysis of Section 5. To recall the basic setup, we assume throughout what follows that h is a Riemannian regularizer in the sense of Definition 2. The convex conjugate h:: y R of is then defined as
h (y) supl h(x)).
(B.1)
xxXx
Since h is K-strongly convex relative g. it is also strongly convex relative to the Euclidean norm (recall here that g(x) > jl). As a result, the supremum in (B.1) is always attained, and h (ÿ) is finite for all y E y [4]. Moreover, by standard results in convex analysis [33, Chap. 26], h² is differentiable on y and its gradient satisfies the identity
Vh (y) arg myx h(x))-
(B.2)
Thus, recalling the definition of the mirror map Q: y - X' (cf.. Section 4):
Q arg max h(x)),
(B.3)
x
we we readily get
Q Vn)
(B.4)
Together with the prox-mapping induced by h, all these notions are related as follows:
Lemma B.1. Let h be Riemannian regularizer on X. Then, for all dom ôh and all y, e V, we have:
a) Q4y) b) x = Q(Vh(x) + = Vh(x) U ah(x*)
ye ah(x).
(B.5a)
(B.5b)
Finally, if xf== = Q(y) and p E X, we have
(Vh(s)(x- - p) S (ylx p)-
(B.6)
Remark. Note that (B.5b) directly implies that öh(x*) # 0. i.c., x* E dom ōh for all V. An immediate consequence of this is that the update rule x= = Q(Vh(x) + o) is well-posed, i.e., it can be iterated in perpetuity.
Proof of Lemma B.I. To prove (B.5a), note that x solves (B.2) if and only if y ōh(x) e 0, i.e., if and only y E ah(x). Eq. (B.5b) then obtained in the same manner.
For the inequality (B.6), it suffices to show it holds for all p e X = dom ah (by continuity). To do so, let
(() = h(x + f(p x)) [h(x) (ylx + 1(p- - x))]-
(B.7)
Since h is strongly convex relative to g and E dh(x) by (B.5a), it follows that Φ(t) 2 0 with equality if and only if = 0. Moreover, note that (0(1) = (Vh(x+ {(p - x)) ylpp - x) is continuous selection of subgradients of d. Given that & and & are both continuous on [0. 11. it follows that & is continuously differentiable and ø' & on [0, 1]. Thus, with & convex and d(1) 2 0 6(0) for all E [0, 1J, conclude that &'(0) = (Vh(x) - glp x) 2 0, from which our claim follows.
As we mentioned earlier, much of our analysis revolves around a "primal-dual" divergence between a target point p E X and dual vector y E y, called the Fenchel coupling. Following [26], this is defined as follows for all p E X.y y E y:
d(p. y) = h(p) hr) - (ylp).
(B.8)
The following lemma illustrates some hasic properties of the Fenchel coupling:
13

---

Published as a conference paper at ICLR 2020
Lemma B.2. Let h be Riemannian regularizer on X with convexity modulus K. Then, for all p X and all y V, we have:
1. (pp D(p, 2(y) if QQ)) X² (but not necessarily otherwise).
2. If Q(y). then ppp y) ||x pll
Proof. For our first claim, let x Q Then, by definition we have:
D(p.y) h(p) - ()10 h(Q())) (ylp) h(p) h(x) (ylp x)..
(B.9)
Since y öh(xx, we have it (x; - x) (ylp- x² whenever x X², thus proving our first claim. For our second claim, working in the previous spirit we get that:
D(p.y) h(p) h(x) (ylp-x)
(B.10)
Thus, we obtain the result by recalling the strong convexity assumption for h with respect to the Riemannian norm ||
We continue with some basic relations connecting the Fenchel coupling relative target point before and after gradient step. The basic ingredient for this is primal-dual analogue of the so-called "three-point identity" for Bregman functions [12]:
Lemma B.3. Let be regularizer X. Fix some p X and let y. E V. Then, letting Q(y). we have
@(p.y") k(p.)) + Oxxx )²+ (y* -lx p).
(B.11)
Proof. By definition, we get:
d(p.y") h(p) + -h'h+")""- k(p.y) h(p) + -
(B.12)
Then, by subtracting the above we get:
(ppyy" d(p. h(p) + h1(y") (y"1p) - h(p) - h hy( + (ylp)
= hh"y²) 11(()) (y" slp)
11')²) (yl2(y)) + h((()) - (y* ylp)
h hh'(²") (ylx) + h(x) - (y* ylp)
=h(x") + (y" ylx) (1'1x) + h(x) (y² -5lp))
<Dxxx")) + (y' -yx--x---- p)
(B.13)
and our proof is complete.
With all this at hand, we have the following key estimate:
Proposition B.1. Let be Riemannian regularizer on X' with convexity modulus K, fix some p E X, let = Q(y) for some E y. Then, for all E Y, we have:
V(p.y + S ((p. (vlx p)
-1101
(B.14)
2K
Proof. By the three-point identity (B.11), we get
d(p.y) <D u) < v).y) (y- (y +01 +
(B.15)
and hence, after rearranging:
@(p.y + 0pp, 9) 41Q + +0.)) (vlQ + 0) p)
((p.y) D (vlx p) + (v1Q(v x)
(B.16)
By Young's inequality [33], we also have
K 11 - - 1 2
(1 x)
2K ||o1l2.
(B.17)
Our claim then follows by the fact that (v 0). o).
x1l2 + xI12 (cf. Lemmas 1 and B.2).
14

---

Published as a conference paper at ICLR 2020
C ANALYSIS OF FTRL
Our goal here is to prove the regret bound (22a) of Theorem 1. The starting point of our analysis is the following basic bound:
Lemma C.1 (35, Lemma 2.3). The sequence of actions generated by (FTRL) satisfies
(T) s h(x) h(X)) + Σ1GO)) -(Xx)))(((x1)))) f(x;,1))
(C.1)
Importantly, the above bound does not require any Lipschitz continuity or strong convexity assump- tions, so it applies our setting "as is". The importance of Riemann Lipschitz continuity lies in the following:
Lemma C.2. f convex and Riemann-Lipschit continuous with constant G, then:
f(x- - f(x) G||K' - xllx for all X X..
(C.2)
Proof. By the convexity of f. we have:
f(x) f(x) (Vf(i)x- x (grad f(x), x)x
x llgrad f(x) - x'Ile
Gl|x x
(C.3)
where the first line follows from the definition of the Riemannian gradient of f, the second one from the Cauchy-Schwartz inequality, and the last from Proposition 1.
With these preliminary results at hand, we obtain the following basic bound for FTRL: Proposition C.I. Suppose that (FTRL) run against a sequence of loss corvex loss functions with assumptions in Section 5. Then, for all E X, we have:
T
Reg, (T) S D(r, xe)
2y
+
G
(C.4)
K
Proof. Our proof is patterned after Shwart- [35], but with an important difference regarding the use of Riemannian norms and Riemann-Lipschitz continuity. To begin, let
F,(x) Σ f(() h(x)
(C.5)
denote the "cumulative" loss faced by the optimizer up to roun r- 1, including the regularization penalty. By the definition of the FTRL policy, X, e arg min F,(x), so (VF,(X,) X,) 2 and, likewise, (V (-F+=1(X=))l>= X,+)) 0 for all x X. Furthermore, since h is K-strongly convex relative to g, F, and F will be (K/y)-strongly convex relative to g.
Putting all this together, we obtain:
K |X X,113 24
F,(X..)) 2 F((X))
(C.6a)
(x,())) 2 ((
+ 1|X, x 2y
(C.6b)
and hence, after summing the above inequalities:
K
K |X Xm.11
fiX,)) fi(x..1) 2
||
Xille
2y
2y
K
2
||X - Xill..
(C.7)
2y
On the other hand, Lemma C.2 gives
f(X,) f((x,1) G,IIX, X,+llxx,
(C.8)
15

---

Published as a conference paper at ICLR 2020
so, combining the last two inequalities, get:
K
|X Xilxx s G,
(C.9)
2y0; 2y
Therefore, plugging this back into (C.8) yields
f(X)) - f(x,+1)
(C.10)
K
and our result obtains from Lemma C.I.
The proof of (22a) then follows by applying Proposition C.I with a step-size of the prescribed form.
D ERGODIC ANALYSIS OF OMD
This appendix is devoted to the proof of our main regret bound for (OMD). We begin by recalling ther recursive definition of the (lazy) OMD method:
Y Y, yu:
(OMD)
X Q(),-)
with Q defined as in Appendix B and oracle feedback subject to the hypotheses (17). We may then write the oracle feedback received by the optimizer at time as 0, Vf((X) U,+1; hence, by the unbiasedness assumption (17a), it follows that E(U Fi] = 0, i... U, is martingale difference sequence (MDS) relative to F;,
Now, applying Proposition B.1 to (OMD), we get:
O(x" Y+) s d(x", Y,) - y(ui,, - + x2
2K
y2
0(x" Y,) + VVXX,( - X,) ylU,olXX, -x))
(D.1)
2K
Hence, after rearranging and telescoping, we obtain
- (V - -X) D(x"xx))
I
7
Reg(T) &
Y
Σ
(D.2)
2K
where, in the last line, used the definition of the Riemannian dual norm ||.||. = lll.,,,, and we set Er11 = (U~ilx* - X,) Our result then follows by taking expectations on both sides.
E LAST-ITERATE ANALYSIS OF OMD
In this last section, we will present the convergence analysis for the last iterate (OMD) to arg min f.
We begin by recalling two important results from probability theory. The first is version of the law of large numbers for martingale difference sequences that are bounded in L [15]:
Theorem E.1. Let Y, = Ei & be a martingale and B, non-decreasing positive sequence such that lim = co. Then,
lim Y, = 0 almost surely 1-000
(E.1)
on the set E B EL? [F c0.
The second is convergence result for quarmsuuperaattnngallss due to Robbins and Sigmund [32]: Lemma E.1. Let (Jiie be nen-decrgginng sequence of a- algebras. Let (a,)aN (6)aa non- negative F,- measurable random variables, (1))NN is an F,- measurable non-negative summable random variable and the following inequality holds:
Eia | F. S a, 0, + 17 almost surely
(E.2)
Then, (ar)IeN converges almost surely towards [0, oo)-valued random variable.
16

---

Published as a conference paper at ICLR 2020
An application of this lemma leads to the following result which is of independent interest:
Proposition E.1. Let X, be the sequence of iterates generated by (OMD) run with a step-size sequence y, such that L Yi and a stochastic oracle as in the statement of Theorems and Then, for all x² arg min f. ((x', .Y)) converges with probability 1.
Proof. Xet E arg min f. Recalling our main estimation:
2i
0(x',Kn) s d(x,, YD y,l,, - x'), + ||ull
(E.3)
2K
and taking conditional expectations both sides, we get due to F,- measurability arguments:
xi
E[O(x', (+1)) s 0(x', Y,) y,(,,/X, - x')x
El IFF.
(E.4)
2K
Since, (2K)-1 Ee 17 Blll |F = M(2K)- E x, co. Thus, by applying the above we get the result.
Having this hand, we can establish the following proposition:
Proposition E.2. Let X, be the sequence of iterates generated by (OMD) with assumptions in
Theorem Then, for all x" E arg min f. the sequence [|X; xx xxlxx, is bounded with probability 1.
Proof. Recalling our main estimation and taking condition expectations on both sides, we get:
x2
- x')x + 2K E[O(x", Y,-1) 1 [F] s o(x", Y,) - -
(E.5)
Hence, by the above corollary, we have that the sequence O(x", Y2) converges with probability 1 for all x* E arg min f. Thus, it is also bounded with probability for all x². We then get
|X - x'1,, s K
0(x", Y)
(E.6)
which concludes our proof.
We continue by showing that X, possesses a subsequence that converges to arg min
Proposition E.3. Let X, be the sequence of iterates generated by (OMD) with assumptions as in Theorem 3. Then, with probability I, there exists a (possibly random) subsequence of X, which converges to arg f.
Proof. Assume to the contrary that, with positive probability, the sequence X, generated by (OMD) admits limit points in arg min f. Conditioning on this event, there exists (nonempty) closed set c X' which is separated by neighborhoods from arg min f and is such that X; C for all suffiently large Then, by relabeling X, if necessary, we can assume without loss of generality that X, C for all f E N. Thus, by Proposition B.I, we get:
22 11:.1
Φ(x", YY,) Oxx, Y,) y,l,lx,- - x²)
2K
x2
= =(x", Y,) XVX((XI x²) - -X 2K
0(x', Y2) ,,((C) +x + 12
2K llul
(E.7)
where in the last line we set 6(C) infk ((x)xx x²)
arg m.n x E CJ (by (SI)), Up1 = Vf()). = - - xx) and B, = Σ Vi- Thus, by telescoping and factorizing we
get:
Σi YsE.u
Σ/= 221lu,ll
Φ(x", Yn.) 0(x'. Yi) 103--B,0 8(C)
(E.8)
B.
2KB,
17

---

Published as a conference paper at ICLR 2020
By the unbiasedness assumption for U, have Els [i] (E[U,+1 [FIII, x²) 0. Moreover, for all x² arg min f, we have
Σ vi BL Fil s
Σ rilix, x' EIU, 1F) Σ 700(" YI [F) < 0o (E.9)
where the last (strict) inequality is obtained due to the finite mean square property, the boundness of O(x", X,) and the fact that Σi=1 Y? co. Thus, we can apply the law large numbers for L²- martingales stated above and conclude that B, E1=1 7-5,-1 converges to almost surely. On the other hand, for the term S 701 Σ' ylll,,1l,,, since Psot is F, J--masuureele for all s 1.2..., have:
Σ Alli rllloulBe.. Fr =, 5, +, 1lo S
B[S :1 [F,
(E.10)
so S, is submartingale with respect to F, Furthermore, by the law of total expectation, we also get:
Σ i=1
E[S EI ml Fill o²
Vi
(E.11)
implying that S, is bounded in L'. Thus, due to Doob's ' submartingale convergence theorem [15], we coclude that S, converges to some (almost surely finite) random variable s. so lim Sue 0 with probability 1.
B.
,,) ..) -o0 contradiction. Going back to our original assumption, this shows that there exists a subsequence of X, which converges to arg min f with probability as claimed.
Now, by letting - (E.8), we get ((x",
With all this at hand, proceed to the proof of our last-iterate convergence result:
Proof of Theorem 3. By the boundedness (and hence compactness) of arg min Proposition E.3 implies that, with probability there exists some E arg min f such that X₂ - for some (possibly random) subsequence X, of X,. By the -iemann-Legendee property of h, it follows that d(x', Y,) D(x*, X, 0 as & co, implying turn that lim, D(x", X,) (by Proposition E.1). Since D(x", X,) 2 KI|X, x" x 2 pl|X, x21 we conclude that X, x", and our proof is complete.
F APPLICATIONS TO POISSON INVERSE PROBLEMS AND NUMERICAL EXPERIMENTS
F.1 DETAILED STATEMENT OF THE PROBLEM
The class of Poisson inverse problems that we consider stem from linear systems of the form
" = Hx+
(F.I)
where
x E Rd is the object under study (a signal, image....
u RT, the observed data (usually m < d).
The kernel matrix H Raadd is representation of the data-gathering protocol and is typically highly ill-conditioned (e.g., a Toeplitz matrix the case of image deconvolution problems).
E R" is the noise affecting the measurements.
When data points are obtained by means of a counting process, measurements can be modeled Poisson random variables of the form "j Pois(Hxx)- Then, up additive constant, the R., will be
log-likelihood of Rd given observation
m
Uxx;))
Σ
Uj u log (Ix))
+ (Hx)) - 11
(F22
18

---

Published as a conference paper at ICLR 2020
Hence, obtaining maximum likelihood estimate for x leads to the archetypal Poisson inverse problem
minimize f(x) = (u, Hx).
(PIP)
subject to E R
where (p. Ip log(p)/q)) + 9j- Pýl denotes the generalized KL divergence on R For an extensive review of Poisson inverse problems, we refer the reader to Bertero et al. [7].
In many cases of practical interest, measurements arrive in distinct batches over time c.g., as sequential optical sections in microscopy and tomography. Morcover, due to the large numbers of pixels/voxels involved (a typical range of values for m is between 106 and 10'), gradients of f are very costly to compute; as such, optimization methods that rely on accurate gradient data are difficult to apply in this setting. Accordingly, natural workaround to this obstacle is exploit the online nature of the measurement process, model (PIP) as an online optimization problem, and then to use an online-to-batch conversion to get candidate solution [35].
On the downside, this online optimization analysis crucially requires the loss functions faced by the optimizer be Lipschitz continuous. However, this assumption does not hold for (PIP): if ff(x) = -uj 1o:loo(u// log(u;/(Hx)) denotes the singular part of the KL divergence for the j-th sample, we readily get
0fj HgHK
(F3)
0x, (Hx))
This shows that the gradient of f, exhibits an ((1xx) singularity at the boundary of R so f cannot be Lipschitz under any global norm on R
As suggested by Example 3, this singularity can be lifted by considering the local norm
|| = (xi xx)² Ed 2ी for all V Rd.
(F:4)
In this case, have
n 11 Ow
Σ
(F:5)
(Hx)
Hyx:}
so fill l is bounded under this modified norm. This is the principal motivation for considering the Riemannian mirror descent method defined with respect to this metric and the regularizer presented in Example 5.
F22 DETAILS ON THE EXPERIMENTS
In the rest of this appendix. we discuss in more detail the algorithms tested in Section 6. The algorithms we considered are
1. The accelerated Lich-Richan algorithm, as presented in [7] and corresponding to OMD with the entropic regularizer h(x) >, x; log x₁.
2. The composite mirror prox (CMP) of He et al. [18], corresponding to OMD with an extra gradient step and the log-barrier (Burg) regularizer h(x) - E,, log x; of Example
3. The Riemannian mirror descent (RMD) algorithm detailed in Section 6, corresponding to the Poincaré-like like regularizer of Example 5.
All algorithms were run with stochastic gradients drawn with the same minibatch size (n = 256) and step-size of the form y; x 1/ Vi (corresponding to the stochastic variant of each algorithm). For comparison purposes, we harvested each algorithm's 's last generated sample ("last iterate") as well as the corresponding ergodic average (defined here as X7 E/ y/X./ Σ/ 7:). Overall, the algorithms' last generated sample provided consistently better results than the ergodic average. The ground truth and the evolution of the Poisson likelihood loss are all reported in Fig. 1.
Remark. We should note here that the method of He et al. [18] can be seen an rextra-gradiemt version of the NoLips algorithm of Bauschke et al. [3] and the "relative stochastic gradient descent" scheme of Hanzely and Richtárik [16] (the difference between the last two being the step-size policy). In our experiments, Burg mirror descent with and without an extra- tatriggradient step behaved similarly, with the extra-gradient version (CMP) performing slightly better. To minimize clutter, and because we are already comparing RMD to CMP above, we do not report this extra set of numerical experiments.
19


Reviews:
[{"review_id": "SklTXJI75B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper generalizes regret analysis results from convex online learning to\nfunctions that are not Lipschitz but Riemann Lipschitz continuous.\n\nExample:\n$f(x) = -\\log(x) + x$ is convex on the convex domain $X = [0, 2]$ but $f$ is\nnot Lipschitz on $D$ since $f(x) \\to \\infty$ as $x \\to 0$.\n\nA possible Riemannian metric that can be used on the domain of such a function\nis the Poincare metric $g(x) = 1 / x^2$.\nThe norm defined by that Riemannian metric is $\\| z \\|^2_x = z^T g(x) z$.\nThis norm can be used to measure infinitesimal distances in $X$.\nThe Riemannian distance $dist(x, x')$ on $X$ that follows from this is defined\nas integrating over the infinitesimal distances on a curve connecting\n$x$ and $x'$ as measured by the norm defined above.\n\nIntuitively, an infinitesimal distance Lipschitz bound can be seen to be\nconstructed by\n$| f(x + \\delta x) - f(x) | \\approx \\| f'(x) \\| \\| \\delta x \\|$ as $\\delta x \\to 0$\nwhich in the case of our example does not exist since $f'(x) \\to \\infty$.\nBut when using a Riemannian metric based norm\n$\\| f'(x) \\| = \\sqrt{ f'(x)^T g^{-1}(x) f'(x) }$\non the right-hand side we have\n$f'(x) = -\\frac{1}{x} + 1$\n$f'(x)^2 = \\frac{1}{x^2} - \\frac{2}{x} + 1$\n$f'(x)^2 g^{-1}(x) = O(1)$\nwith $g(x) = 1 / x^2$.\n\nIn this way it is possible to bound changes of $f(x)$ relative to changes in\n$x$ for functions that are not Lipschitz continuous.\n\nThe authors show how a suitable Riemannian metric can be transformed into\na regularizer usuable in online optimization.\nThey present various rates that appear to be otherwise known for similar\nregularizers.\nMy knowledge of the online learning literature is very limited so I cannot\nmake a qualified statement about these formal analyses in a reasonable amount\nof time.\n\nThe authors also transfer the results from the convex online setting to the\nconvex stochastic setting and the nonconvex setting.\n\nBased on my limited understanding I would recommed to accept the paper.\nThe analysis to me seems both rigorous and useful in practice\n(at least with regard to the formal definitions of Riemannian metrics and\nRiemannian Lipschitz condition for singular functions).\n\nRemarks / Suggestions:\n- With a similar knowledge of the underlying function it would perhaps be\n\tpossible to perform a nonlinear transformation of the input space that\n\tleads to Lipschitz continuous function.\n\tCan something be said about this?\n\n- Definition 2: Write out l.s.c. (lower semi-continuous?) as it does not seem\n\tto be defined everywhere and not every reader is necessarily familiar\n\tenough with convex analysis\n\n- Page 8: Typo: \"Eucldiean stochastic gradient method\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeKfUUoqS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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).\n\nQUESTIONS/SUGGESTIONS:\n1) 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.\n2) 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?\n3) 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.\n\nAFTER REBUTTAL: I thank the authors for addressing my questions.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylZuqdiFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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. \n\nI 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,\n* 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; \n* 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). \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

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)