{'fraction_non_alphanumeric': 0.05932553855408098, 'fraction_numerical': 0.009098086394225347, 'mean_word_length': 3.861111111111111, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Logarithmic Regret for Online Gradient Descent Beyond Strong Convexity

Hoffman's classical result gives a bound on the distance of a point from a convex and compact polytope in terms of the magnitude of violation of the constraints. Recently, several results showed that Hoffman's bound can be used to derive strongly-convex-like rates for first-order methods for \textit{offline} convex optimization of curved, though not strongly convex, functions, over polyhedral sets. In this work, we use this classical result for the first time to obtain faster rates for \textit{online convex optimization} over polyhedral sets with curved convex, though not strongly convex, loss functions. We show that under several reasonable assumptions on the data, the standard \textit{Online Gradient Descent} algorithm guarantees logarithmic regret. To the best of our knowledge, the only previous algorithm to achieve logarithmic regret in the considered settings is the \textit{Online Newton Step} algorithm which requires quadratic (in the dimension) memory and at least quadratic runtime per iteration, which greatly limits its applicability to large-scale problems. In particular, our results hold for \textit{semi-adversarial} settings in which the data is a combination of an arbitrary (adversarial) sequence and a stochastic sequence, which might provide reasonable approximation for many real-world sequences, or under a natural assumption that the data is low-rank. We demonstrate via experiments that the regret of OGD is indeed comparable to that of ONS (and even far better) on curved though not strongly-convex losses.


Introduction
The celebrated Online Gradient Descent algorithm (OGD), originally due to [20], is a natural adaptation of the classical projected (sub)gradient descent algorithm for offline convex optimization, to the setting of Online Convex Optimization [5,15]. The benefits of OGD are two folded: (i) in many problems of interest it performs very efficient iterations, which can often be executed in linear time (in the dimension), and (ii) it often guarantees optimal regret rates, mainly in terms of the length of the sequence T , e.g., √ T regret for arbitrary convex loss functions, and log T regret in case all loss functions are strongly-convex [6].
However, there exists a highly-important and wide class of loss functions, known as exp-concave losses [6], for which OGD does not guarantee optimal regret (in terms of T ). For instance, the family of expconcave losses capture important problems such as online linear regression with the square loss and online LASSO, online logistic regression, online portfolio selection, and more. While for exp-concave losses, OGD only guarantees regret that scales like √ T , it is known that an online algorithm known as Online Newton Step (ONS), originally due to [6], guarantees log T regret (see also recent work [12] which gives an improved variant in terms of runtime and regret bound for lowrank data). On the downside, while OGD applies very efficient iterations in terms of runtime and memory requirements (e.g., when computing the gradient vector of the loss function and projecting onto the feasible set is computationally-cheap), ONS requires quadratic memory and to solve a linear system on each iteration (which requires at least quadratic runtime via efficient implementation). ONS also requires to compute a non-Euclidean projection on each iteration to enforce the constraints, which can be considerably more expensive than the Euclidean projection required by OGD (e.g., might require to use an iterative algorithm). Thus, despite the improved regret bound, ONS is often not applicable to large-scale problems. This naturally motivates the following question: Can Online Gradient Descent be shown to enjoy a logarithmic regret bound for classes of loss functions beyond the class of strongly convex losses?
In this paper we take a step forward towards understanding the conditions under-which OGD can guarantee logarithmic regret, hence yielding both an efficient algorithm and an improved convergence rate in such settings. In particular, we focus on an important sub-class of the exp-concave losses: loss functions which can be written as a strongly-convex function applied to a linear transformation of the input variables. Such loss functions include important examples such as the square loss for linear regression, the online portfolio optimization loss, the logistic regression loss, and more. While such losses are not necessarily strongly convex in the entire space, they are strongly convex on a certain subspace, which corresponds to the rowspan of the linear transformation. Our main result shows that when all loss functions are of this form, with linear transformations that satisfy certain consistency conditions, and the feasible set is a convex and compact polytope, the vanilla OGD algorithm, with a suitable choice of learning rate, indeed guarantees logarithmic regret. To the best of our knowledge, this is the first result to establish strongly-convex-like rates for OGD without strong convexity, on an important and wide class of applications.
Technically, at the heart of our result lies a classical result in convex analysis, originally due to Hoffman [8], which roughly speaking, bounds the distance of a point from a convex and compact polytope in terms of the magnitude of violation of the constraints describing the polytope. In case the feasible set is a polytope and the loss function is as described above (i.e., strongly convex applied to linear transformation), it can be shown that Hoffman's bound implies a property known as quadratic growth, which upper bounds the ℓ 2 distance between any feasible point and a feasible optimal solution, in terms of the distance in function values -a property well known to enable faster convergence rates in convex optimization settings (this is often also the main consequence of strong convexity needed in order to achieve fast rates for stronglyconvex optimization).
Indeed, several recent works have used this classical result by Hoffman [8], to achieve fast rates without strong convexity for offline optimization problems, see for instance the recent works [14,18,9,1,19]. Importantly, all of these results consider only stationary settings, in which the objective function is fixed. As we show in the sequel, obtaining such fast rates results in the online convex optimization setting is considerably more challenging since, as opposed to strong convexity which is a property that holds in the entire space, and hence, given a sequence of strongly convex functions, this property holds throughout the sequence, Hoffman's bound on the other-hand, is related to a specific subspace (which corresponds to the row-span of the linear transformation in the losses discussed above), and thus, given a sequence of such losses with different corresponding subspaces, these subspaces need not be, informally speaking, consistent with each other. Hence, a main contribution of this work is to formalize and analyze conditions under which this property could indeed be leveraged towards obtaining fast rates in a non-stationary online setting.
In particular, we show that our logarithmic-regret result holds for sequences which can be expressed as a combination of an arbitrary (adversarial) sequence and a stochastic sequence with certain stationary characteristics, which may potentially serve as reasonable approximation to many real-world data-streams, or when the data enjoys a low-rank structure. We report preliminary experimental results on both synthetic and real-world datasets which indeed show that OGD can outperform the Online Netwon Step method, both in terms of the regret and computational efficiency, on non-strongly convex sequences.

Preliminaries
Throughout this work we use · to denote the Euclidean norm for vectors and the spectral norm (i.e., largest singular value) for matrices. Also, for a compact set P ⊂ R d and a matrix C ∈ R m×d , we use the notation CP := {Cx | x ∈ P}.

Convex optimization preliminaries
Definition 1. Given a convex and compact set K ⊂ R d and a real-valued function f , differentiable over K, In particular, if f is convex, differentiable and G-Lipschitz over a convex and compact K, we have that ∀x, y ∈ K: Definition 2. Given a convex and compact set K ⊂ R d and a real-valued function f which is differentiable over K, we say f is α-strongly convex over K if ∀x, y ∈ K: We recall the first-order optimality condition for convex differentiable functions (see for instance [2]): for any K ⊂ R d , convex and compact, and a realvalued function f , convex and differentiable over K, we have that ∀x ∈ K, x * ∈ arg min y∈K f (y): (x * − x) ⊤ ∇f (x * ) ≤ 0.

Online convex optimization preliminaries
We now briefly recall the setting of Online Convex Optimization (OCO). For a more in-depth introduction we refer the reader to [5,15].
In the OCO problem, a decision maker (DM) is required to iteratively choose points in a fixed convex and compact set K ⊂ R d . On each round t, after the DM makes his choice, i.e., chooses some x t ∈ K, a convex function f t : K → R is revealed, and the DM suffers the loss f t (x t ). This process continues for T rounds, where T is assumed to be known in advanced. The goal is to design an algorithm for choosing the actions of the DM so to minimize a quantity called regret, which is given by It is well known than an algorithm known as Online Gradient Descent, see Algorithm 1 below, can guarantee a O(GD √ T ) bound on the regret, where D is the ℓ 2 diameter of K and G is an ℓ 2 upper bound on the gradients of the functions f 1 , . . . , f T [20], which is in general optimal. It is also known that when all functions f 1 , . . . , f T are α-strongly convex, the same algorithm (though with different learning rate) guarantees O((G 2 /α) log T ) regret [6], which is also optimal under this assumption [7].
x t+1 ← arg min x∈K x − y t+1 2 5: end for 2.3 Hoffman's bound and the quadratic growth property Definition 3. We say a matrix C ∈ R m×d is σ-Hoffman with respect to a convex and compact polytope P ⊂ R d for some σ > 0, if for any vector c ∈ R m such that the set P(C, c) := {x ∈ P | Cx = c} is not empty, it holds that ∀x ∈ P: The following Lemma, originally due to Hoffman [8], shows that a Hoffman parameter bounded away from zero, always exists. Here we give the result in rephrased form. A proof is given in the appendix for completeness.
Lemma 1. Let P := {x ∈ R d | Ax ≤ b} be a compact and convex polytope and let C ∈ R m×d . Given a vector c ∈ R m , define the set P(C, c) := {x ∈ P | Cx = c}.
If P(C, c) = ∅, then there exists σ > 0 such that ∀x ∈ P: dist(x, P(C, c)) 2 ≤ σ −1 Cx − c 2 . Moreover, we have the bound σ ≥ min Q∈M λ min QQ ⊤ , where M is the set of all d × d matrices whose rows are linearly independent rows of the matrix M := (A ⊤ , C ⊤ ) ⊤ , and λ min (·) denotes the smallest non-zero eigenvalue.
Definition 4. . We say a function f : R d → R has the quadratic growth property with parameter κ with respect to a compact and convex set , where X * := arg min y∈K f (y) and f * := min y∈K f (y).
The following lemma, which will be instrumental in the proof of our main result, demonstrates the connection between Hoffman's bound and the quadratic growth property for (possibly stochastic) convex objectives.
Lemma 2 (from Hoffman's bound to quadratic growth). Let P ⊂ R d be a convex and compact polytope. Let D be a distribution over pairs (g(·), C) ∈ (R m → R) × R m×d satisfying: 1. for each pair (g, C) in the support of D, the function g is differentiable, G-Lipschitz, and αstrongly convex over CP.

the function
, and denote by σ the Hoffman constant of C D w.r.t. P. Finally, define X * := arg min y∈P {F (y) : Proof. For any x ∈ P and x * ∈ X * it holds that where (a) follows since each g(·) in the support of D is differentiable and α-strongly convex over CP, (b) follows since F (x) is differentaible over P and hence it's gradient vector is given by , and (c) follows form the first-order optimality condition for F (·). Thus, ∀x * ∈ X * , x ∈ P: Thus, setting c D = C D x * for some x * ∈ X * , directly gives the =⇒ direction of the first part of the lemma To prove the ⇐= direction of the first part of the lemma, let x ∈ P such that C D x = c D . Then we have that Since for each pair (g, C) in the support of D, g is convex and G-Lipschitz over CP, using Eq. (1) we have that meaning x ∈ X * , which completes the proof of the first part of the lemma. The second part of the lemma follows directly form combining the first part of the lemma with Hoffman's bound (Lemma 1) and Eq. (2).

Informal Statement of Results and Examples
We now give an informal statement of our theoretical results, followed by several concrete examples to demonstrate possible applications. We then conclude the section by drawing a connection between our setting and online exp-concave optimization and the Online Newton Step algorithm.

Logarithmic regret for Online Gradient Descent without strong convexity
Suppose that the feasible set P is a convex and compact polytope in R d and suppose all loss functions are of the form f t (x) := g t (C t x), where g t (·) is differentiable and α 1 -strongly convex. Suppose further, that there exists a matrix M ∈ R k×d such that for where the expectation is with respect to possible randomness in the choice of C t . Then, we show there exists a choice of step-sizes {η t } t∈ [T ] such that OGD guarantees O(log T ) regret (treating all other quantities as constants).
We note that while the requirement M ⊤ M E[C ⊤ t C t ] α 2 M ⊤ M seems not standard at first glance, observe that when C t is full-rank, and hence f t (x) is in particular strongly convex, this requirement holds trivially with M = I. Hence, this condition is natural for dealing with loss functions that are strongly convex only on a restricted subspace of R d , requiring them all to be consistent, at least in expectation, with the same subspace. In Subsection 3.2 we discuss several settings of interest in which it is reasonable to assume this requirement holds.

Examples of relevant settings and loss functions
Linear regression and Lasso: Consider the ℓ p linear regression loss function f t (x) : In particular, when p = 2 and the feasible polytope is an ℓ 1 -ball, i.e., P := {x ∈ R d | x 1 ≤ k}, for some k > 0, we get an online version of the famous LASSO problem [17].
For our log-regret result to hold for deterministic data, i.e., deterministic choice of (A 1 , b 1 ) . . . (A t , b T ), it must hold that row-span(A 1 ) = row-span(A 2 ) = · · · = row-span(A T ). This is reasonable if A t ∈ R m×d for a large enough value of m, and the data, i.e., the rows of A 1 , . . . , A T lie in a certain low-dimensional subspace 1 .
A different non-deterministic setting of interest is a "semi-adversarial" model in which A t :=Ã t + N t , where the matricesÃ 1 , . . .Ã T are arbitrary and N t ∼ D i.i.d. for all t ∈ [T ], for some fixed (yet unknown) distribution D. Then, a sufficient condition for our fast OGD rate to hold (in expectation), is that αÃ ⊤ tÃt for all t ∈ [T ], for some α > 0. That is, the data can be faithfully modeled as a deterministic sequence perturbed by a well-conditioned stochastic noise. For instance, such a model underlies the problem of Universal Linear Filtering studied in [13,3].
Finally, if we can treat the data as generated by a stochastic mechanism that on each time t randomly samples A t from a (unknown) distribution D t (note we allow the distribution to change each round), then a sufficient condition for our log-regret result to hold is that there exists a matrix M and α > 0 such that for all t ∈ [T ]: Logistic regression: In online logistic regression, the loss on m data points organized in a matrix A t ∈ R m×d , can be written as f t (x) : Observe f t (x) can be rewritten as f t (x) := g(A t x) with g(y) := m i=1 log (1 + e yi ). It not difficult to verify that for bounded y, g(y) is indeed strongly convex, and hence this problem also falls into our setting. As in the linear regression case, if the feasible set is a polytope (e.g., standard selections are a ℓ 1 or ℓ ∞ ball), then same assumptions on the matrices A 1 , . . . , A T will allow to apply our log-regret result.
Online portfolio selection: In the online portfolio selection problem [5], the loss of a rebalancing portfolio x (a point in the unit simplex) on m consecutive trading rounds is given by f where the rows of A t ∈ R m×d , A t > 0 (entrywise) encodes the asset prices on each round. Similarly to the logistic regression example, we can write f t (x) := g(A t x) with g(y) := − m i=1 log (y i ). Again, it is not hard to verify that if A t ≥ r (entry-wise) for some r > 0, then g(·) is indeed strongly convex over the transformed simplex A t ∆ d : Again, our log-regret result holds under the same assumptions on the data A 1 , . . . , A T , as above.

Connection with exp-concavity and the Online Newton Step algorithm
A real-valued function f , twice-differentiable over a compact set K ⊂ R d , is σ exp-concave on K if and only if ∀x ∈ K : ∇ 2 f (x) σ∇f (x)∇f (x) ⊤ [5].
Thus, if all loss functions are as above, i.e., f t (x) := g t (C t x), and we let G be a uniform upper bound on the ℓ 2 norm of the gradients of g t (·) and C be a uniform upper bound on the spectral norm of the matrices C t , the Online Newton Step (ONS) algorithm [5], guarantees regret bound:

Logarithmic Regret for OGD Without Strong Convexity
In this section we present and prove our main result -a logarithmic regret bound for Online Gradient Descent (Algorithm 1) without strong-convexity. As discussed, our result holds under certain conditions on the data which are captured in the following assumption. In the following Subsection 4.1 we discuss several concrete examples in which this assumption holds.
Assumption 1. Given a convex and compact polytope P ⊂ R d , a distribution D over pairs (g, C) ∈ (R m → R) × R m×d , is said to satisfy Assumption 1 with parameters (M,Ḡ, α 1 , α 2 ) ∈ R k×d × R 3 + w.r.t. P, if it holds that 1. each function g, part of a pair (g, C) in the support of D, is differentiable, α 1 -strongly convex over CP := {Cx | x ∈ P} and G-Lipschitz over CP, for some finite G > 0 We can now state our main theorem, Theorem 1. While the theorem holds under quite general conditions, we refer the reader again to Section 3.2 for discussion of concrete applications.

Theorem 1. [OGD Master
Theorem] Fix a convex and compact polytope P ⊂ R d . Consider a sequence of T distributions D 1 , . . . D T over (R m → R)×R m×d which satisfy Assumption 1 with parameters (C,Ḡ, α 1 , α 2 ) w.r.t. P, whereC is a matrix satisfy- Suppose further thatC is σ-Hoffman w.r.t. P. Let f 1 (x) . . . f T (x) be a sequence of loss functions such that f t (x) = g t (C t x), with (g t , C t ) ∼ D t independently of the functions {f τ } τ ∈[T ]\{t} . Then, applying Algorithm 1 with stepsize η t = 1 α1α2σt , w.r.t. the losses f 1 . . . f T and the polytope P, guarantees that Before we can prove the theorem, we need the following technical lemma which extends Lemma 2 from a single stochastic objective to a sequence of stochastic objectives, and hence plays a key role in our regret analysis .
Lemma 3 (from Hoffman's bound to quadratic growth of a sequence). Let D 1 , . . . , D T be distributions over (R m → R) × R m×d satisfying Assumption 1 with parameters (C,Ḡ, Consider the function F (x) := 1 T T t=1 E (g,C)∼Dt [g(Cx)], and define the set of feasible minimizers: X * := arg min x∈P F (x). Then, it holds that ∀x * , y * ∈ X * , t ∈ [T ]: Moreover, letting σ denote the Hoffman constant ofC w.r.t. the polytope P, we have that ∀x ∈ P, x * ∈ X * : dist(x, Proof. Consider a distribution D over (R m → R) × R m×d , described by the following sampling procedure: pick t ∈ [T ] uniformly at random, and then sample (g, C) ∼ D t . Clearly, it holds that Thus, it follows that X * = arg min x∈P E (g,C)∼D [g(Cx)].
Note that since each distribution D t satisfies Assumption 1, it also satisfies the assumptions of Lemma 2. It can be easily verified that as a consequence, the distribution D also satisfies the assumptions of Lemma 2, and thus there exists a matrixC, satisfyinḡ C ⊤C = E (g,C)∼D [C ⊤ C], such that ∀x * , y * ∈ X * : By the definitions ofC and the distribution D, it holds that where we defineC t to be a matrix satisfyingC ⊤ tC t = E (g,C)∼Dt [C ⊤ C].
Thus, we have that ∀x * , y * ∈ X * : 0 = (x * − y * ) ⊤C⊤C (x * − y * ) which, since eachC ⊤ tC t is positive semidefinite, implies that ∀x * , y * ∈ X * , t ∈ [T ]: Thus, fixing some x * , y * ∈ X * and t ∈ [T ], it holds that where (a) follows via Eq. (1) since each g(·) in the support of D t is convex and G-Lipschitz for some finite G > 0, and (b) follows from Eq. (3). Thus, the first part of the lemma follows.
The second part of the lemma is a straightforward consequence of Lemma 2, when applied to the distribution D, defined above.
Proof of Theorem 1. Let us denote the set of of minimizers in hindsight: Given the sequence of points generated by Algorithm 1 {x t } T t=1 , we define the sequence {x * t } T t=1 as follows: ∀t ≥ 1: x * t := arg min x∈X * x − x t 2 , i.e., x * t is the projection of x t onto the set of optimal plays in hindsight X * .
Let us fix some x * ∈ X * . By an application of Lemma 3, it holds that Thus, to prove the theorem, it suffices to upper bound Let us also define the sequence {r t : . Throughout the rest of the proof we write ∇ t as a short notation for ∇f t (x t ).
As standard in the analysis of Online Gradient Descent, for every t ≥ 1, we have that where the first inequality holds since x t+1 is the orthogonal projection of y t+1 onto P. Rearranging and recalling that f t (x) = g t (C t x) for some g t , C t , we have that Since g t (·) is α 1 -strongly convex, we have By the definition of the sequence {x * t } T t=1 , we have Summing over all T iterations, rearranging and taking expectation on both sides, we have that where we have used the fact that ∀t ∈ [T ] : Note that since for all t, C t is independent of x t , x * t , we have that where we letC t be such thatC ⊤ tC t = E (g,Ct)∼Dt [C ⊤ t C t ]. By Lemma 3 and the assumption of the theorem, it holds that Thus, since the step-size η t is monotonically nonincreasing with t, we have that ∀t ≥ 2: Combining Eq. (4), (5), (6), and plugging-in our choice of step-size η t = 1 α1α2σt , we conclude that (1 + ln T ).

Applications of Theorem 1
Deterministic data: In case g 1 , . . . g T : R m → R are arbitrary α 1 -strongly convex and differentiable functions over R m , then a sufficient condition on the matrices C 1 , . . . , C T for applying the result of Theorem 1 is that there exists a positive constant α 2 such that or in a different formulation: row-span(C 1 ) = row-span(C 2 ) = · · · = row-span(C T ).
A simple application of Theorem 1 upper-bounds the regret by α1α2σD 2 Semi-adversarial data: A way to circumvent the limitation of condition (7), is to consider slightly "easier" data. In particular if we let {g t (·)} t∈[T ] be as in the deterministic case, but we assume that the matrices C 1 , . . . , C T are perturbed realizations of some underlying deterministic sequenceC 1 , . . . ,C T . That is, we letC t be arbitrary, but the observed matrix C t is a perturbed version given by C t =C t + N t , where N t ∼ D, where D is a fixed unknown distribution. Then, the condition in (7)   (1 + ln T ), where σ is the Hoffman constant of the expected matrix , w.r.t. the polytope P. As mentioned in Section 3.2, such a setting underlies for instance the Universal Linear Filtering problem studied in [13,3].
Shifting stochastic data: Assuming (g t (·), C t ) is sampled out of a distribution D t (possibly changing from round to round), under assumptions on g t (·) as above, a sufficient condition on the stochastic matrices C t for applying the result of Theorem 1 is that there exists some α 2 > 0 such that for all , in which case we get the same bound as in the "semiadversarial" case with σ being the Hoffman constant of 1 T T t=1 E C∼Dt [C ⊤ C] w.r.t. P.

Experiments
In this section we provide empirical evidence for the performance of Online Gradient Descent on curved, though not strongly convex, losses. Since the computational advantage of OGD over competing methods is clear, we focus on demonstrating convergence in terms of the average loss. We consider the LASSO optimization problem, i.e., the loss function on each round t is f t (x) := 1 2 a ⊤ t x − b t 2 and the feasible polytope is an ℓ 1 ball. In all experiments we compare OGD with Online Newton Step (ONS).
Synthetic data: We compare OGD and ONS in an online stochastic setting. We fix the dimension to d = 100 and generate a random PSD matrix M ∈ R d×d with rank = 50 and with decaying eigenvalues given by λ i = 10 · 0.8 i−1 for all i ∈ [50]. We set a t = v ⊤ t M for a random unit vector v t , and b t := a ⊤ t w * + 0.1n t , where w * is a fixed sparse vector chosen at random, and n t ∼ N (0, 1). The radius of the feasible ℓ 1 ball is set to r = 10. Since determining the Hoffman constant is difficult in general, we heuristically set σ according the eigenvalue of the covariance matrix A = 1 T T t=1 a t a ⊤ t which corresponds to the numerical rank of A. We use this choice in all of our experiments which seems to work well. and set the step-size accordingly to η t = 1 σt (note g t (·) in our case is 1-strongly convex). ONS is implemented as suggested in [5]. For both methods we plot the (log) average loss vs. number of iterations (we use T = 10000).
MNIST data: Next we experiment with the MNIST handwritten digit recognition dataset [11]. Specifically, we use the training dataset, keeping only the data related to digits 3, 5. We set b t by assigning value 1 to instances corresponding to the digit 5 and −1 to those corresponding to 3. Finally, in order to increase the amount of data, we replicate the data and concatenate twice. We set the radius of the feasible ℓ 1 ball to r = 5.
CIFAR10 data: we use the CIFAR10 tiny image dataset [10] which contains 50000 32x32 images in RGB format. We convert the images to grayscale and keep only the data related to the classes "automobile" and "truck", assigning the first the label b t = −1 and the second the label b t = 1. Here we also replicate the data twice and set r = 5.
The results for all datasets are presented in Figure 1. It is clearly observable that in all three cases OGD is comparable to ONS in terms of regret and even far better.