Localization, Convexity, and Star Aggregation
Year: 2021

Abstract:
Offset Rademacher complexities have been shown to provide tight upper bounds for the square loss in a broad class of problems including improper statistical learning and online learning. We show that the offset complexity can be generalized to any loss that satisfies a certain general convexity condition. Further, we show that this condition is closely related to both exponential concavity and self-concordance, unifying apparently disparate results. By a novel geometric argument, many of our bounds translate to improper learning in a non-convex class with Audibert’s star algorithm. Thus, the offset complexity provides a versatile analytic tool that covers both convex empirical risk minimization and improper learning under entropy conditions. Applying the method, we recover the optimal rates for proper and improper learning with the p-loss for 1 < p <∞, and show that improper variants of empirical risk minimization can attain fast rates for logistic regression and other generalized linear models.

heading: 1 Introduction
text: A central question in statistical learning theory asks which properties of the empirical risk minimizer can be inferred without regard to the underlying data distribution. In particular, the convergence rate of empirical risk minimization has been shown to depend both on distribution-specific properties, such as Tsybakov’s margin condition (Tsybakov, 2004), as well as distribution-independent or “global” properties, such as VC dimension of the class and curvature of the loss (Mendelson, 2002).
The local Rademacher complexities of Bartlett et al. (2005) address this issue by giving bounds that are data dependent and also adapt to the global properties of the learning problem. More recently, the offset Rademacher complexities of Rakhlin and Sridharan (2014) and Liang et al. (2015) have been shown to provide similar bounds for the square loss in several contexts. The offset complexity provides a simplified analysis that transparently relates the geometry of the square loss to statistical properties of the estimator.
We extend offset Rademacher complexities to systematically study how curvature of the loss translates to fast rates of convergence in proper and improper statistical learning. We show many results in the literature can be studied in a common geometric framework: from classical results on uniform convexity of the loss (Bartlett et al., 2006; Mendelson, 2002), to newer results on exponential concavity (van Erven et al., 2015; Mehta, 2017) and self-concordance (Bilodeau et al., 2020; Marteau-Ferey et al., 2019).
Remarkably, our analysis applies simultaneously to convex empirical risk minimization and to improper learning with the star algorithm of Audibert (2008). In each case, excess risk is tightly
∗Supported by the MIT Jerry A. Hausman Graduate Dissertation Fellowship
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
bounded by the offset Rademacher complexity. Thus, we give a clean and unified treatment of fast rates in proper and improper learning with curved loss. Our contributions may be summarized as follows.
1. We generalize the offset Rademacher complexities of Liang et al. (2015) to show that when the loss is (µ, d)-convex (defined below), excess risk is bounded by a corresponding offset Rademacher process.
2. We show in this general setting that the “star algorithm” of Audibert (2008) satisfies an upper bound matching the convex case, allowing us to simultaneously treat convex risk minimization and improper learning under general entropy conditions.
3. We show that (µ, d)-convexity captures the behavior of exponentially concave, uniformly convex, and self concordant losses, leading to fast upper bounds for learning under the p-loss, the relative entropy, and the logistic loss.
4. We observe that generalized linear models (glms) may be expressed as learning in a non-convex class subject to the exponentially concave relative entropy loss, and introduce a general procedure—the regularized star estimator—which attains fast rates in arbitrary glms from a mixture of at most two proper estimators.
In the case of k-ary logistic regression with bounded features X ∈ Rq and each predictor norm bounded by B, our upper bounds on the excess risk take the form
kq
n · polylog(n, k,B, 1/ρ) (1)
with probability at least 1− ρ. Thus, in the i.i.d. setting, fast rates that depend only logarithmically on B are achievable by a simple, improper variant of empirical risk minimization.

heading: 1.1 Relation to Prior Work
text: This paper examines the localization or fast-rate phenomenon, where the excess loss vanishes at a rate exceeding the model’s uniform law of large numbers (Koltchinskii and Panchenko, 2000; Tsybakov, 2004).
Recently, Liang et al. (2015) showed that localization for the square loss is captured by the so-called offset Rademacher complexity. In addition to being analytically straightforward, the offset complexity appears in a minimax analysis of online regression (Rakhlin and Sridharan, 2014), suggesting a unified treatment of online and statistical learning.
In parallel work, van Erven et al. (2015) have showed that exp-concavity of the loss, often studied in online optimization, implies fast rates in the statistical setting via the probabilistic “central condition” (see also Juditsky et al. (2008); Mehta (2017)).
Our work unifies these results. In particular, we show that the offset complexity upper bound can be generalized to arbitrary losses satisfying a certain curvature condition that includes exp-concave losses. These results considerably extend the scope of offset Rademacher complexities in the statistical setting, as we illustrate; we also believe it can refine the minimax analysis of online regression with exp-concave loss, which we leave to subsequent work.
Another noteworthy aspect of our work is its treatment of improper learning—that is, minimizing loss compared to the class F with an estimator that need not belong to F . Unlike prior work, which typically involved aggregation over a finite subset of F (Rakhlin et al., 2017; Audibert, 2009), we provide a completely unified analysis that simultaneously leads to optimal rates for convex empirical risk minimization and improper learning under general entropy conditions. In particular, we circumvent the issue that passing to the convex hull of certain classes can “blow up” their complexity and lead to slower rates (Mendelson, 2002).
We apply our analysis to generalized linear models (glms), such as logistic regression, where standard procedures surprisingly do not attain fast rates (Hazan et al., 2014). Inspired by Foster et al. (2018), we note that any glm can be recast as learning in a non-convex class subject to the exp-concave relative entropy. The star algorithm therefore attains fast rates for a wide class of generalized linear models, improving on prior results that exploit strong convexity (see e.g. Rigollet (2012)).
Unlike other recent works on improper logistic regression, we do not prove a polynomial time complexity for our procedure, nor do we study the online setting; these are left as open problems for future work. However, our procedure remains of interest for its simplicity—it outputs a fixed mixture of two predictors as opposed to optimizing at each query—and for its applicability to arbitrary glms (Foster et al., 2018; Mourtada and Gaïffas, 2020; Jézéquel et al., 2020).

heading: 2 Margin inequalities
text: We begin our discussion with the following definition which extends the classical uniform convexity (see e.g. Chidume (2009)), giving a quantitative bound on the extent to which the plane tangent to f at (y, f(y)) lies below the graph of f . Definition 1. Let µ : R→ R be increasing and convex with µ(0) = 0, and let d(x, y) be a pseudometric on the vector space B. A differentiable convex function f : B → R with gradient ∇f is (µ, d)-convex if for all x, y ∈ B,
f(x)− f(y)− 〈∇f |y, x− y〉 ≥ µ(d(x, y)) (2)
In particular, this condition implies that the lower sets of f , fx = { z ∣∣∣ f(z) ≤ f(x)} ,
are strictly convex, and that for any closed and convex K there is a unique x̂ ∈ arg minx∈K f(x). We adopt the notation that for a subset S ⊂ B, ∂S denotes the boundary of S, S◦ = S \ ∂S denotes the interior, and coS denotes the convex hull. Remark 2. At this point, we are intentionally vague about the role of the metric, d. We shall subsequently see that the choice of d is crucial for producing good upper bounds. The conventional choice is d(x, y) = |x− y| and µ(z) = αzp, corresponding to p-uniform convexity (with modulus α). However, our results on self-concordant and exp-concave losses use non-standard choices of d.
By a standard argument, given in Lemma 3 below, the condition (2) on the loss implies that the empirical risk minimizer in a convex class satisfies a geometric margin inequality. Intuitively, if another hypothesis performs nearly as well as the empirical minimizer in the sample, it must also be d-close to the empirical minimizer. Lemma 3. Let K be a closed, convex subset of B. If f is (µ, d)-convex and x̂ minimizes f over K then for all x ∈ K
f(x)− f(x̂) ≥ µ(d(x, x̂)). (3)
Proof. Let zλ = λx+ (1− λ)x̂ be the line segment interpolating x and x̂, and put ϕ(λ) = f(zλ). By convexity of K, we must have zλ ∈ K, hence ϕ is minimized at λ = 0 by optimality of x̂. Hence, ϕ(λ)− ϕ(0) ≥ 0 for all λ, and ∇ϕ must satisfy
∇ϕ|λ=0 = 〈∇f |x̂, x− x̂〉 ≥ 0.
Thus, f(x)− f(x̂) ≥ f(x)− f(x̂)− 〈∇f |x̂, x− x̂〉 ≥ µ(d(x, x̂)),
proving the lemma.

heading: 2.1 The star algorithm
text: We now introduce our first main result, which extends the above analysis to the problem of learning in a non-convex class. Surprisingly, in the general setting of (µ, d)-convexity, an inequality matching (3) is always attained by a simple, two-step variant of empirical risk minimization.
Let us now introduce the procedure. Given x ∈ S, the “star hull” of S with respect to x is defined by
star(x, S) = {λx+ (1− λ)s | s ∈ S, λ ∈ [0, 1]} .
The procedure may be summarized as follows.
1: procedure STAR(S, f ) 2: Find x̂ that minimizes f over S 3: Find x̃ that minimizes f over star(x̂, S) 4: Output x̃ 5: end procedure
Our next goal is to show that if S is an arbitrary (not necessarily convex) set, and x̃ is the output of the star algorithm, then
f(x)− f(x̃) ≥ µ ( 1 3d(x, x̃) ) (4)
whenever f is (µ, d)-convex.
In particular, if f is the empirical risk and S is the function class, then x̃ is the “star estimator” introduced by Audibert (2008). Thus, whenever (µ, d)-convexity leads to an upper bound for empirical risk minimization in a convex class via the inequality (3), the same bound is enjoyed up to constants by the star algorithm in an arbitrary class.
To prove (4), recall how we proved Lemma 3: we showed that if the line-segment λ 7→ zλ which linearly interpolates between any two points x and y lies entirely in the set fx \ f◦y , so f(zλ) ≥ f(y), then we have that
f(x)− f(y) ≥ µ(d(x, y)).
This is illustrated in Figure 1. Unfortunately, the existence of such a line-segment zλ connecting x and x̃ relies on the convexity of S. In order to extend the argument as we want to, we make two observations. Firstly, the line segment λ 7→ zλ can be chosen to be any line segment connecting ∂fx to ∂fy and lying entirely in fx \ f◦y . Then, since ∂fx and ∂fy are level sets, the same argument yields
f(x)− f(y) = f(z1)− f(z0) ≥ µ(d(z1, z0)). (5)
Secondly, we can show that there exist at most three such line-segments which together comprise a path from x to x̃. By the triangle inequality, at least one of these segments has length greater than 1 3d(x̃, x). Combining this with (5) yields the desired inequality (4). We state this as a proposition and prove it formally in Appendix A. A straightforward illustration of the proof, following the preceding discussion, is provided in Figure 2.
Proposition 4. Let f be (µ, d)-convex. Suppose x̂ minimizes f over S and x̃ minimizes f over star(x̂, S). Then, for any x ∈ S,
f(x)− f(x̃) ≥ µ ( 1 3d(x, x̃) ) .

heading: 3 From margins to upper bounds
text: We will now show how the previous section’s margin inequalities lead to upper bounds on the excess risk.

heading: 3.1 Statistical setting and notation
text: First, let us introduce the statistical setting and some notation. We observe data in the form of n i.i.d. pairs {(Xi, Yi)}ni=1 ⊂ D × R on a common probability space, P. Given a set F of predictors f : D → R and a loss function ψ : R× R→ R, we aim to minimize the excess ψ-risk relative to F ,
E(f̂ ;F , ψ) =̇ Eψ(f̂(X), Y )− inf f∈F {Eψ(f(X), Y )]}.
Here, (X,Y ) is an independent pair with the same law as the observed data (Xi, Yi). We will suppress the dependence on F and ψ where confusion does not arise. We will use the shorthand h or hi to denote the random variables h(X) or h(Xi), and will denote the function (x, y) 7→ ψ(h(x), y) by simply ψ(h). Frequently, we combine these two abuses of notation to write ψi(h) =̇ ψ(h(Xi), Yi). We write ψ ◦ F for the corresponding class of functions {ψ(h) |h ∈ F}, and will use En to denote the empirical expectation 1n ∑ i δ(Xi,Yi).

heading: 3.2 Empirical margin inequality
text: Our first lemma extends (µ, d)-convexity of the loss x 7→ ψ(x, y) to the empirical risk. Lemma 5. Suppose that for each y, x 7→ ψ(x, y) is (µ, d)-convex in x. Then the empirical ψ-risk, given by f 7→ Enψ(f), is (µ, dn)-convex in f , where dn =̇ µ−1 ◦ En(µ ◦ d).
Proof. By (µ, d)-convexity, we have for each 1 ≤ i ≤ n ψi(f)− ψi(g)− 〈∇ψ|gi , fi − gi〉 ≥ µ(d(fi, gi)).
Averaging these inequalities, noting that the inner product and sub-gradient commute with the averaging operation, and also that µ ◦ µ−1 ◦ En(µ ◦ d) = En(µ ◦ d), yields Lemma 5.
Now, if F is convex with empirical risk minimizer f̂ , applying Lemma 3 with x chosen to be the population risk minimizer f∗ gives
Enψ(f∗)− Enψ(f̂) ≥ Enµ(d(f̂ , f∗)). (6)
Similarly, if F is not convex and f̃ is produced by the star algorithm applied to Enψ, we have by Proposition 4 Enψ(f∗)− Enψ(f̃) ≥ Enµ(d(f̃ , f∗)/3). (7) We note that in our applications, µwill typically have the form x 7→ cx2, so (6) and (7) are comparable up to a constant factor of 9. To avoid complication, we will only work with the more general inequality (7). The reader may note that in a convex class the star estimator coincides with the empirical risk minimizer, so we are treating both cases simultaneously at the expense of slightly larger constants. Example 6 (Square loss). Before proceeding, it is helpful to consider the square loss ψ(x, a) = (x − a)2 as an example. A convenient aspect of (µ, d)-convexity is that the optimal µ ◦ d can be computed as
µ(d(x, y)) = ψ(x)− ψ(y)− 〈∇ψ|y, x− y〉
= lim λ↓0
∂
∂λ λψ(x) + (1− λ)ψ(y)− ψ(λx+ (1− λ)y),
which in this case is simply (x − y)2. Taking d(x, y) = |x − y| and µ(z) = z2, we recover the familiar inequality En(Y − f∗)2 − En(Y − f̂)2 ≥ En(f∗ − f̂)2. Moving to the non-convex case with the star algorithm introduces a factor of 1/9 on the right-hand side, improving on Liang et al. (2015) by a constant. This analysis extends, with little complication to the p-loss for all 1 < p <∞. We will discuss these results in Section 5.1.

heading: 3.3 The offset empirical process
text: We have now derived a family of margin inequalities for the star estimator,
Enψ(f∗)− Enψ(f̃)− Enµ(d(f∗, f̃)/3) ≥ 0. (8) Adding this to the excess risk gives us the upper bound
E(f̃) = Eψ(f̃)− Eψ(f∗) ≤ (En − E)(ψ(f∗)− ψ(f̃))− Enµ(d(f̃ , f∗)/3)
≤ sup f∈F ′
{ (En − E)(ψ(f∗)− ψ(f))− Enµ(d(f, f∗)/3) } (9) for F ′ = ∪λ∈[0,1]λF + (1 − λ)F (the Minkowski sum). After symmetrization and contraction arguments, which follow along the lines of Liang et al. (2015), we have the following result. The proof is given in Appendix B. Proposition 7. Let F be a model class, ψ a (µ, d)-convex loss, and f∗ the population minimizer of the ψ-risk. Then, the star estimator f̃ satisfies the excess risk bound
EΨ(E(f̃)) ≤ EΨ ( sup f∈F ′ { 1 n n∑ i=1 2ε′i(ψi(f ∗)− ψi(f))− (1 + ε′i)µ( 13d(fi, f ∗ i )) }) (10)
where the ε′i are i.i.d. symmetric Rademacher random variables, F ′ = ∪λ∈[0,1]λF + (1− λ)F , and Ψ : R→ R is any increasing, convex function. Remark 8. Proposition 7 quantifies localization for the loss ψ. The excess risk is upper bounded by a non-centered Rademacher complexity with the asymmetric term −µ(d(fi, f∗i )/3). This term captures the fact that hypotheses f which are far from f∗ perform worse in expectation, and are thus unlikely to be selected. As a result, these hypotheses do not contribute much to the excess risk. Remark 9. This bound contains the unknown quantity f∗ ∈ F , and using it requires taking the supremum over possible f∗. This leaves open the possibility of exploiting prior information of the form f∗ ∈ P ( F . While our bound is stated in expectation, a more elaborate symmetrization argument can provide data-dependent bounds on the excess risk, see Liang et al. (2015).

heading: 4 Exp-concave localization
text: We will now investigate how our upper bound (10) applies to η-exp-concave losses, namely those for which e−ηψ is concave, or equivalently
ψ′′/(ψ′)2 ≥ η. It turns out that this condition leads to very natural bounds on the excess risk. To provide intuition as to why, note that exploiting the bound (10) requires comparing the risk increments ψ(f) − ψ(f∗) to the offset µ(d(f, f∗)). Under strong convexity, we have an offset of the form α|f − f∗|2 and must resort to a Lipschitz bound of the form ψ(f)− ψ(f∗) ≤ ‖ψ‖lip |f − f∗| to make the necessary comparison. Thus, we have upper bounded the first derivative uniformly by ‖ψ‖lip and lower bounded the second derivative uniformly by α.
It turns out that exp-concave losses possess an offset term of the form |ψ(f) − ψ(f∗)|2. Thus, localization naturally occurs at the same scale as the risk increments. Exp-concavity only requires the ratio ψ′′/(ψ′)2 to stay bounded, which is crucial for the log loss, where ‖ψ‖lip = ∞ but ψ′′/(ψ′)2 = 1. First, we’ll establish a particular version (µ, d)-convexity for the logarithmic loss. We will subsequently extend it to all exp-concave losses. Lemma 10. For all x, y ∈ [δ, 1]
(− lnx)− (− ln y)−∇(− ln)|y(x− y) ≥ | lnx− ln y|2
2 ln(1/δ) ∨ 4 . (11)
Proof. The left-hand side of (11) is equivalent to ln(y/x) + (x − y)/y = e−z − 1 + z with the substitution z =̇ ln(y)− ln(x). Finally, we verify in Lemma G3 that
e−z − 1 + z ≥ z 2
2 ln(1/δ) ∨ 4 , (12)
since our assumption x, y ∈ [δ, 1] implies |z| ≤ ln(1/δ).
The inequality (11) establishes that the logarithmic loss, when restricted to [δ, 1], is (µ, d)-convex for µ : x 7→ x2/(2 ln(1/δ)∨ 4) and d(x, y) = | lnx− ln y|. This choice of d captures an important fact: the logarithm is more convex precisely when it is faster varying.
Remarkably, a simple reduction shows that the same property is enjoyed by bounded, η-exp-concave losses. Thus, we neatly recover past results on exp-concave learning (cf. Mehta (2017)), and extend them to the improper setting. Proposition 11. Suppose ψ is an η-exp-concave loss function which satisfies the uniform bound 0 ≤ ψ ≤ m. Then, for each x and y,
ψ(x)− ψ(y)− 〈∇ψ|y, x− y〉 ≥ |ψ(x)− ψ(y)|2
2m ∨ (4/η) . (13)
Proof. First note that since e−ηψ is concave, we have
exp(−ηψ(λx+ (1− λ)y)) ≥ λe−ηψ(x) + (1− λ)e−ηψ(y). Note that equality holds at λ = 0. Taking logarithms of both sides and passing to the upper sub-gradient at λ = 0 therefore yields
−η 〈∇ψ|y, x− y〉 ≥ 〈 ∇ ln |e−ηψ(y) , e−ηψ(x) − e−ηψ(y) 〉 . (14)
We then apply Lemma 10 with x and y replaced by e−ηψ(x) and e−ηψ(y), and with δ = e−ηm. Using (14) to bound the gradient term then yields Proposition 11.
Plugging (13) into Proposition 7 and making a contraction argument yields the following upper bound for the excess ψ-risk. The full argument is in Appendix C. Theorem 12. Let ψ be an η-exp-concave loss function taking values in [0,m]. Then the star estimator in F satisfies the excess risk bound
EΨ(E(f̃)) ≤ EΨ ( sup f,g∈F ′ { 1 n n∑ i=1 4ε′i(ψi(f)− ψi(g))− η(ψi(f)− ψ(gi))2 18mη ∨ 36 }) . (15)
where Ψ is any increasing, convex function and F ′ = ∪λ∈[0,1]λF + (1− λ)F . Alternatively, when ψ is p-uniformly convex with modulus α and ‖ψ‖lip-Lipschitz, we have
EΨ(E(f̃)) ≤ EΨ ( sup f,g∈F ′ { 1 n n∑ i=1 4 ‖ψ‖lip (fi − gi)ε ′ i − α|fi − gi|p 3p }) . (16)
Remark 13. An especially nice feature of (15), as well as (18) below, is that all quantities appearing in the bound are invariant to affine re-parameterizations of the learning problem.
Self-concordance
We close the section by considering self-concordant losses ψ, namely those for which
ψ′′′ ≤ 2(ψ′′) 32 . In order to see how localization for self-concordant losses can be fit into the above framework, we rely on the following inequality which was also used by Bilodeau et al. (2020). Lemma 14 (Nesterov (2014, Theorem 4.1.7)). Suppose ψ is self-concordant, and define the local norm ‖z‖ψ,w =̇ √ z2ψ′′(w). Then
ψ(x)− ψ(y)− 〈∇f |y, x− y〉 ≥ ‖x− y‖ψ,y − ln ( 1 + ‖x− y‖ψ,y ) . (17)
The first thing that one should note is that, when one takes ψ to be the negative logarithm, the above is exactly equivalent to the modulus (12) appearing in the proof of Lemma 10. Thus, our upper bound for exp-concave losses is a consequence of self-concordance of the logarithm.
The path to general upper bounds via self-concordance is significantly more involved, so we will only sketch it. Applying (17) to the excess risk and performing standard manipulations, one arrives at the following upper bound, proved in Appendix D.
Proposition 15. If ψ is a self-concordant loss and f̂ is the empirical risk minimizer in a convex class F , then
EΨ(E(f̃)) ≤ EΨ ( sup f∈F ′ { 1 n n∑ i=1 4(ψi(f)− ψ(f∗i ))ε′i − ω ( ‖fi − f∗i ‖ψ,f∗i )}) , (18)
for ω(z) = z − log(1 + z), ‖z‖ψ,w =̇ √ z2ψ′′(w), and (ε′i) n i=1 are independent, symmetric Rademacher random variables and Ψ is any increasing, convex function.
Comparing this to (16), the scale of the offset term has been improved from the modulus of strong convexity, which is the minimum second derivative, to the second derivative at the risk minimizer, f∗. Expressing the increments ψi(f)− ψi(f∗) at a scale comparable to ‖fi − f∗i ‖ψ,f∗i is known to be achievable when f belongs to the so-called Dikin ellipsoid of (Enψ, f∗), requiring a more careful argument (see e.g. Marteau-Ferey et al. (2019)). Notably, we do not know how to extend this bound to the improper setting due to the local nature of the offset term.

heading: 5 Applications
text: We will now discuss several applications of Theorem 12. First, we’ll sketch how the previous section’s results straightforwardly imply fast rates. We’ll then discuss applications, first to the p-loss and then to generalized linear models. Proofs in both cases are to be found in Appendix F.
While most general bound uses chaining, and is provided by Theorem 19 below, the essence of the argument is simple; we will sketch it now. Let S (A, ν) be a minimal covering of A in L2(ν) at resolution , and define the entropy numbersH2( ,G) =̇ supν ln(#S (G, ν)) (where the supremum is over probability measures ν).2 Putting S =̇ S (ψ◦F ′,Pn) and applying (15) with Ψ(z) = exp(λnz) gives
E exp(λn(E(f̃)− )) ≤ E expλn ( sup s,t∈S { 1 n n∑ i=1 4ε′i(si − ti)− η(si − ti)2 18mη ∨ 36 })
≤ E ∑ s,t∈S Eε exp ( n∑ i=1 4λε′i(si − ti)− λη(si − ti)2 18mη ∨ 36 ) ,
where we first moved the supremum outside exp (by monotonicity of exp) and then bounded it by a sum (by positivity of the arguments). Here, Eε denotes an expectation w.r.t. the multipliers ε′i, conditional upon the data. Applying Hoeffding’s lemma to the inner expectations with respect to ε′i gives
≤ E ∑ s,t∈S exp ( n∑ i=1 2λ2(si − ti)2 − λη(si − ti)2 18mη ∨ 36 ) .
Choosing λ∗ = 36m ∨ 72/η gives E exp(λ∗n(E(f̃)− )) ≤ E(#S )2 ≤ exp{2H2( , ψ ◦ F ′)}, so by a Chernoff bound
P ( E(f̃) ≥ + ( 36m ∨ 72
η
)( 2H2( , ψ ◦ F ′) + ln(1/ρ)
n
)) ≤ ρ. (19)
The result (19) extends Mehta (2017, Theorem 1) to the non-convex and improper setting for the price of a factor 9, and differs from the standard bound in numerous ways. Firstly, the Lipschitz constant ‖ψ‖lip is replaced by the range, m. Here, ‖ψ‖lip appears only implicitly in the covering numbers, entering logarithmically in small classes. For the log loss, this is an exponential improvement.
Next, the modulus of strong convexity is replaced by the exp-concavity modulus η. This implies that the optimal 1/n rate can be obtained, in both proper and improper settings, for losses which are not strongly convex but are exp-concave, notably regression with p-loss for p > 2.
2Our results can be sharpened by restricting the supremum to empirical probability measures on n data points. With further work, it is also possible to derive high-probability bounds where ν is restricted to be the empirical distribution of the observed data, see Remark 9.
Lastly, we show in Appendix Lemma G4 that the entropy numbers of ψ ◦ F ′ are equivalent to those of ψ ◦ F in all but finite classes, where the gap is at most ln(1/ ). On the other hand, when the entropy numbers of ψ ◦F are polynomial, particularly −q with q < 2, then they can be polynomially smaller than those of ψ ◦ (coF) (Carl et al., 1999).
5.1 Regression with p-loss
A surprising consequence of (19) concerns regression with the p-loss for p > 2, which is p-uniformly convex but not strongly convex. When the inputs to the loss are bounded, the standard argument pursued by Mendelson (2002) and Bartlett et al. (2006) (and also Rakhlin and Sridharan (2015) in the online setting) exploits uniform convexity, producing the suboptimal rate exponent p/(2p− 2) < 1. However, the p-loss for inputs in [−B,B] is B−p-exp-concave, so we recover optimal (1/n)-type rates matching the square loss (cf. Audibert (2009)). Indeed, the suboptimal rates occur exactly when one plugs (16) into the above argument instead of (15). For 1 < p ≤ 2, the loss is both strongly convex and exp-concave, so the two bounds coincide up to constants.
Corollary 16 (cf. Mendelson (2002, Theorem 5.1)). Let ψ(f, y) = |f − y|p for p > 1 and let the class F and response Y take values in [−B,B]. Then there exists a universal C(p,B) = O(p2pBp) such that the star estimator f̃ has excess ψ-risk bounded as
P ( E(f̃ ,F) ≥ + C(p,B)(H2( /Cp,B ,F) + ln(1/ ) + ln(1/ρ))
n
) ≤ ρ, (20)
By a minor extension to Tsybakov (2003, Theorem 1), this result is sharp for each p.

heading: 5.2 Improper maximum likelihood
text: We next derive upper bounds for learning under the log loss, ψ : f 7→ − ln f in a class L. If we interpret f as the likelihood of an observation, empirical risk minimization coincides with maximum likelihood.
In this setting, a generalized linear model for multi-class prediction refers to the case where L = {(x, y) 7→ 〈ϕ(f), y〉 | f ∈ F} for some base class F . Here the link function ϕ outputs probability distributions over [k], and y ∈ Rk is a basis vector encoding the label.
These models are typically formulated as minimizing the loss ψ[ϕ] : f 7→ − ln 〈ϕ(f), y〉 over f ∈ F , which is equivalent for proper learning. Since L may be non-convex even for convex F , however, one must consider improper predictors f̂ 6∈ L in order to exploit localization of the log loss. When ϕ is surjective, these yield improper predictors under ψ[ϕ] by composing with a right-inverse, ϕ†.
To illustrate, we will derive our quoted bound (1) for logistic regression. In this setting, Hazan et al. (2014) showed that improper learning is necessary for fast rates with sub-exponential dependence on the predictor norm, B. This was achieved by Foster et al. (2018), whose results fall neatly into the aforementioned recipe: they propose a mixed prediction corresponding to an exponentially weighted average, which is simply another estimator that takes values in the convex hull of L. For classes not bounded away from 0, where the improvement is most dramatic, we need to replace L by the δ-regularization Lδ = (1− δ)L+ δ. The approximation error is controlled as follows. Lemma 17 (Foster et al. (2018)). For all f and δ ∈ (0, 1/2], the excess risk relative to Lδ satisfies
E(f ;Lδ) ≤ E(f ;L) + 2δ
We now state our result.
Corollary 18. With probability at least 1− ρ, the star estimator f̃δ in Lδ satisfies E(f̃δ;L) ≤ + 2δ + C ln(1/δ) ( H2(δ ,L) + ln(1/ δ) + ln(1/ρ)
n
) (21)
Let L be the generalized linear model corresponding to FB = { x 7→Wx ∣∣W ∈ Rk×q, ‖W‖2→∞ ≤ B}
with A-Lipschitz, surjective link ϕ and features X ∈ Rq that satisfy ‖X‖2 ≤ R √ q. Then with probability at least 1− ρ
E(ϕ† ◦ f̃δ;FB) ≤ ln(n)
n
{ Ckq ln(ABRn √ k) + ln(1/ρ) } . (22)
Our bound for logistic regression, quoted in the introduction, follows after noting that the soft-max function is 1-Lipschitz and surjective.
Before investigating how these bounds translate to larger classes—namely those with H2( ,F) of order −q for small —we need to state the chaining version of our bound, proved in Appendix E. Theorem 19. Let ψ be an η-exp-concave loss taking values in [0,m]. Then, with probability at least 1− 9e−z , the star estimator f̃ applied to (ψ,F) satisfies
E(f̃) ≤ inf 0≤α≤γ
{ 4α+
10√ n ∫ γ α √ H2(s) ds+ 2H2(γ) cn + γ √ 8π√ n + ( 2 cn + γ √ 8√ n ) z } , (23)
where H2(s) =̇ H2(s, ψ ◦ F ′) and c = 36−1(1/m ∧ η/2).
In classes with entropy −q, our results fall into two regimes. The first covers losses such as the logistic loss, for which − ln ◦ϕ is A-Lipschitz. Here, the covering numbers of − ln ◦Lδ differ from those of F by the constant Aq, and we match the optimal rates for the square loss (Rakhlin et al., 2017).
For general L, the covering numbers of − ln ◦Lδ may contain an extra factor δ−q, leading to suboptimal rates. Suboptimality follows from combining the minimax regret analysis of Bilodeau et al. (2020), which produces the average regret n−1/(1+q), with a standard online-to-batch reduction. We note that the upper bound of that paper is non-constructive, whereas these upper rates come with an explicit algorithm. Tightening our analysis to close this gap, or proposing an algorithm that attains the correct rates, remains a significant open problem. Corollary 20. Consider a generalized linear model with A-Lipschitz loss f 7→ − ln 〈ϕ(f), y〉. Suppose the entropy numbers H2( ;F) are of order −q . Then, the regularized star estimator ϕ† ◦ f̃δ with δ = 1/n satisfies the rates appearing on the left.
On the other hand, for an arbitrary class L taking values in [0, 1] subject to the log loss, the regularized star estimator f̃ ′δ′—for appropriately chosen δ ′—attains the rates appearing on the right.
Here, the symbol .ρ denotes an upper bound that holds with probability 1 − ρ, hiding universal constants and a multiplicative factor ln(1/ρ).
E(ϕ† ◦ f̃δ) .ρ  Aqn−2/(2+q) ln(n) q < 2 Aqn−1/2 ln(n) q = 2
Aqn−1/q q > 2
E(f̃ ′δ′) .ρ  n−1/(1+3q/2) q < 2 n−1/4 ln(n) q = 2
n−1/(2q) q > 2
(24)
In closing, we would like to highlight the additional, unresolved problem of designing a computationally efficient implementation of the regularized star estimator—in particular for log-concave link functions ϕ where the first step is a convex program, such as logistic regression. This problem is left to future work.
Acknowledgments and Disclosure of Funding
This work was partially funded by the MIT Jerry A. Hausman Graduate Dissertation Fellowship. We would like to thank Alexander Rakhlin, Victor Chernozhukov, and Anna Mikusheva for their extensive guidance and for many helpful conversations. We would also like to thank Stefan Stein and Claire Lazar Reich for their helpful feedback on the manuscript. All errors are, however, the fault of the author.

Review summaries:
This paper is concerned with the excess risk analysis of empirical risk minimization (ERM) over convex function classes, as well as Audibert's 'improper' Star-shaped aggregation procedure over nonconvex classes (which reduces to ERM in the convex setting), in statistical learning. Sharp bounds have been obtained in the case of least-squares regression, and this paper considers additional settings such as exp-concave statistical learning, as well as losses satisfying different types of uniform convexity (such as p-convexity). From a technical point of view, the analysis relies on an extension of the offset Rademacher complexities (introduced and leveraged for square loss by Liang, Rakhlin and Sridharan to analyze convex ERM and nonconvex Star) to other uniformly convex losses, in particular exp-concave ones; it is shown that an analogue of this offset process also controls the excess risk in these cases. The main outcomes of this analysis are applications to regression with p-loss for p>2, and to improper learning of generalized linear models (such as logistic regression). 

The paper provides a unified analysis of fast rates in statistical learning. In particular, they provide excess risk bounds for the star-ERM solution for various loss functions by bounding the offset Rademacher complexity. In particular, they identify a general property: the suboptimality gap of a point with respect to the star-ERM solution is lower bound by distance (under a particular metric) between that point and the star-ERM solution. They derive this metric for various assumptions on the loss functions like uniform convexity, exp-concavity, self-concordance, etc. In terms of new results, using these techniques: (a) they can obtain fast rates for l_p losses for p > 2.  (b) they can obtain fast rates for exp-concave losses that depend on the range of the loss instead of its Lipschitz constant.  

This paper introduces a notion of $(\mu, d)$ convexity, with connections to strong convexity and self-concordancy, and shows that the excess risk is bounded by an offset Rademacher average, where the offset involves this convexity concept. The authors show that their method is sufficient to handle a broad class of loss functions, including the $p$-loss and cross-entropy loss, generalizing previous work with square loss, and even operates on non-convex model spaces via the star algorithm. Finally, they show that for exponentially concave, uniformly convex, and self-concordant loss functions, their results have particularly convenient and elegant forms. In particular, they show relevant and interesting applications, with $p$-loss, and generalized linear models (improper maximum likelihood).