Localization, Convexity, and Star Aggregation
Authors: Suhas Vijaykumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: Statistical Learning Theory
Improper Learning
Empirical Risk Minimization
Fast Rates

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 < \infty$, and show that improper variants of empirical risk minimization can attain fast rates for logistic regression and other generalized linear models.

Localization, Convexity, and Star Aggregation
Suhas Vijaykumar"
Statistics Center and Dept. Economies Massachusetts Institute of Technology
Cambridge, MA 02139
suhasv@mit.edd
Abstract
Offset Rademacher complexities have been shown to provide tight upper bounds for the square loss in broad class of problems including improper statistical learning and online learning. We show that the offset complexity can be generalized any loss that satisfies a certain general convexity condition. Further, we show that this condition closely related both exponential concavity and self-concordance, unifying apparently disparate results. By novel geometric argument, many of our bounds translate improper learning in a non-convex class with Audibert's star algorithm. Thus, the offset complexity provides 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 < p < oo, and show that improper variants of empirical risk minimization attain fast rates for logistic regression and other generalized linear models.
Introduction
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. particular, the convergence rate of empirical risk minimization has been shown to depend both on distribution-specifie properties, such as Tsybakov's margin condition (Tsybakov) 2004), as well as caaributiionindeeeeddee or "global" properties, such as VC dimension of the class and curvature of the loss (Mendelson 2002
The local Rademacher complexities of Bartlett 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. (2013) 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.
(2005) address this issue by giving bounds that
We extend offset Rademacher complexities systematically study how eurvature of the loss translates to fast rates of convergence in proper and improper statistical learning. We show many results in the literature convexity of the loss (Bartlett et al. 20066] Mendelson 2002), to newer results on exponential concavity (van Erven al., 2015 Mehta 2017) and self-concordance (Bilodcau et 2020 Martcau-
be studied in common geometric framework: from classical results uniform
et al. 2019).
Remarkably, analysis applies simultaneously 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 (NcurIPS 2021).

---

bounded by the offset Rademacher complexity. Thus, we give 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 al. (2013) to show that when the loss is (j, 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.
We show that (μ, co-cooiyi 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 general proce- dure-the regularized star estimator-whic 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 E IR and each predictor norm bounded by B. our upper bounds on the excess risk take the form
kg polylog(n, k. B, 1/p)
(1)
with probability at least Thus, in the i..d setting, fast rates that depend only logarithmically on B are achievable by a simple, improper variant of empirical risk minimization.
1.1 Relation to Prior Work
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 unified treatment online and statistical learning.
In parallel work, van Erven et al. (015)) have showed that exp-coneavity 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); Mchta (2017)).
Our work unifies these results. In particular, 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. [017]] Audiberri 2009). provide completely unified analysis that simultancously 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 al. (2018), we note that any glm can be recast as learning in 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 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- 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 Gaiffas 2020 Jézéquel et al. 2020).
2 Margin inequalities
We begin our discussion with the following definition which extends the classical uniform convexity (see e.g. CChidume 2009 giving quantitative bound the extent to which the plane tangent at (y. (V)) lies below the graph of
Definition 1. ye: R I be increasing and convex with p(0) 0, and let d(x, y) be a pseudo- metric the vector space B. A differentiable convex function f B - IR with gradient V f is (n, dc-oove for all z, y E B,
f(z) f(y) (Vfly. - v) 2 p(d(x,))
In particular, this condition implies that the lower sets of f.
f= - {2 f(z)) fx))
are strictly convex, and that for any closed and convex K there is a unique i E arg argminge f(x). We adopt the notation that for a subset S B, as denotes the boundary of S, S = S ( OS denotes the interior, and co S 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 crucial for producing good upper bounds. The conventional choice is d(x, y) = jx and μuz) = az?,, corresponding to p-uniform convexity (with modulus a). However, our results on self-concordant and exp-concave losses use non-standard choices of d.
By a standard argument, given in L below, the condition ( on the loss implies that the empirical risk minimizer convex class satisfies geometric margin inequality. Intuitively, another hypothesis performs nearly as well 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. is (n, do-ceveex and minimizes f over K then for all E K
f()) 2 (dd(x,)))
(3)
Proof. Let 2A Ar + (1 Å) be the line segment interpolating x and â,, and put (o(A) f(zx). By convexity of K, we must have 2 E K, hence yp minimized at by optimality of Hence, (A()) - (0)) 2 0 for all X, and Vip must satisfy
V = (V/la, x 53) 20
Thus,
f(x) - f(0) f(x) f(t) - fV 2) 2 u(d(z,)))
proving the lemma.
2.1 The star algorithm
We now introduce first main result, which extends the above analysis to the problem of learning in non-convex class. Surprisingly, in the general setting of (n, c)-coveexity, an inequality matching is always attained by simple, two-step variant of empirical risk minimization.
Let us now introduce the procedure. Given æ S, the "star hull" of with respect to æ is defined by
star(z, (Ax + A)s Is S. E [0, 1]
The procedure may be summarized as follows.
3

---

H2
(case 2)
fx
12
f8
L
fa
fa
H1
81
i
5
2x
K
30 (case 1)
Figure I: Illustration Lemma 3 Con- vexity implies the existence of direct path 2A from x to 2.
Illustration Proposition Depicted is the plane containing (x, 2, T); C' is the minimal cone containing fa with vertex at ê. By optimality of क, S cannot intersect the interior of C U fa. implying existence of one of the indicated paths.
Figure 2:
1: procedure STAR(S,
2: Find & that minimizes f over S
3: Find 7 that minimizes f over star(i, S)
4: Output
5: end procedure
Our next goal is to show that if S is an arbitrary (not necessarily convex) set, and T is the output of the star algorithm, then
f(x) - f()) (fd(x,
(4)
whenever f is (1,, d))coovex.
In particular, if is the empirical risk and S is the function class, then 7 is the "star estimator" introduced by Audibert (2008). Thus, whenever (14, d))-conexitty leads to an upper bound for empirical risk minimization in 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 À + 2A which
linearly interpolates between any two points x and y lies entirely in the set fa \f. so f(zx) 2 f(y). then we have that
f(x) - f()) 2 u(d(z,
This is illustrated in Figure 1 Unfortunately, the existence of such line-segment connecting and relies on the convexity of S. order to extend the argument as we want to, we make two observations. Firstly, the line segment + 2x can be chosen to be any line segment connecting 0f. to ff, and lying entirely fa \Sp Then, since Of and 0fy are level sets, the same argument yields
f(x) f(v) f(=))
p(d(21, 20)).
(5)
Secondly, can show that there exist most three such line-segments which together comprise path from x to ă. By the triangle inequality, at least one of these segments has length greater than 3 x)). Combining this with (5) yields the desired inequality (4). We state this proposition and
prove it formally in Appendix A straightforward illustration of the proof, following the preceding
discussion, provided in Figure 2
Proposition Let S be (n, docovve. Suppose & minimizes S over and minimizes over star(E (i. 5). Then, for any E S.
f(z) f(ū) (td(2,

---

From margins to upper bounds
We will now show how the previous section's margin inequalities lead upper bounds on the excess risk.
3.1 Statistical setting and notation
First, let us introduce the statistical setting and some notation. We observe data in the form of Li.d. pairs {(,,, = c D x R on a common probability space, P. Given a set F of predictors f: D + I and a loss function v R x R + R, we aim minimize the excess ø-risk relative to F. E(F:F, = Esb (x
inf (BO()(X), JEP
Here, (X,Y) an independent pair with the same as the observed data (X,, Yi). We will suppress the dependence on FF and &b where confusion does not arise.
We will use the shorthand h or h2 denote the random variables h(X) or h(X,), and will denote the function (x, + (f((z)), y) by simply (h). Frequently, we combine these two abuses of notation write the (h) = (K),,, Yt). We write & o F for the corresponding class of functions (bb(h) h E F}, and will use E, to denote the empirical expectation E, 6(x.)))
3.2 Empirical margin inequality
Our first lemma extends (μ, dd)coneextty of the loss (1x, y) to the empirical risk. Lemma 5. Suppose that for each y, x + vb(,, y) is (u, d)-onvex in x. Then the empirical tý-risk, given by f (f), is (p, -covve in where dn = p on En (μ d).
Proof. By (p, d))connexity, we have for each sisn
(b( (x( (Vblg. f. gi) 2 ((d(f..g)))
Averaging these inequalities, noting that the inner product and sub- gradient commute with the averaging operation, and also that μ n En (μ (n d), yields Lemma 5
Now, if F is convex with empirical risk minimizer f. applying Lemma 3 with x chosen be the population risk minimizer f gives
E, En - E, Ex 2 En, f*)).
(6)
Similarly, F is not convex and is produced by the star algorithm applied to E, we have by Proposition 4
E ( E., v/) 2 /3)3)
We note that in our applications, a will typically have the form . + cr² so (6) and 7 are comparable up a constant factor 9. To avoid complication,
will only work with the more general inequality The reader may note that in convex class the star estimator coincides with the empirical risk minimizer, so we are treating both cases simultaneously the expense of slightly larger constants.
Example 6 (Square loss). Before proceeding, it is helpful to consider the square loss (,,,, a) (x a²² as an example. A convenient aspect of (u, doccovxexity is that the optimal μ d can be computed as
pld(z, v)) (xx) (by) (V x 3)
lim (x) + (1 A)b((v) - (Ax + (1 A)8),
210
Ox
which in this case is simply (x y) Taking d(x, y) = |x y1 and p(z)= = 22, we recover the familiar inequality
En (Y f
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 We will discuss these results in Section 5.1
to the polsss for all I
5

---

3.3 The offset empirical process
We have now derived family of margin inequalities for the star estimator,
((() E, (i) - En .1/3) 2 O.
(8)
Adding this the excess risk gives us the upper bound
E(f) EV(s) (x) - (En ()(((()))))))))))))))))))))))))) vf)) E.n(d((,
I sup IEP"
(IEn E)(())) (()) Enuld(f.
for = Ux + (1- X)F (the Minkowski sum). After symmetrization and contraction
arguments, which follow along the lines Liang al. 22015). we have the following result. The proof is given in Appendix B
Proposition 7. Let F be model class, vp (Js, d'-coovex loss, and f" the population minimizer of the v--risk Then, the star estimator I satisfies the excess risk bound
Σ 2e((0:(()) (40-))))0000000(000444440 { SEF
EV(E(F) S EV
sup
(10)
where the El are i.i.d. symmetric Rademacher random variables, F Ux AF F (1 X)F, and : + IR is any increasing, convex function.
Remark 8. Proposition 7 quantifies localization for the loss sb. The excess risk is upper bounded by non-centered Rademacher complexity with the asymmetric term -u(d(fi, /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
not contribute much to the excess risk.
Remark 9. This bound contains the unknown quantity f E F, and using it requires taking the supremum over possible f*. This leaves open the possibility of exploiting prior information of the form f E P Ç F. While our bound is stated in expectation, more elaborate symmetrization argument can provide data-dependent bounds on the excess risk, see Liang al. (2015).
4 Exp-concave localization
10 applics to n-exp-concave losses, namely those for We will now investigate how our upper bound which e ov is concave, or equivalently
100)
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 v (t( to the offset m(d(J.(")) Under strong convexity, we have an offset of the form alʃ - f and must resort Lipschitz bound of the form (ff) (ff*) I || ltip If - f to make the necessary comparison. Thus, have upper bounded the first derivative uniformly by ||pb| and lower bounded the second derivative uniformly by
turns out that exp-concave losses possess an offset term of the form (v(() (())) Thus. localization naturally occurs at the same scale as the risk increments. Exp-concavity only requires the ratio " / to stay bounded, which is crucial for the log loss, where ||v/|1 = oc but v (vb²/²² 1. First, we'll establish a particular version (μ, do-coneexity for the logarithmic loss. We will subsequently extend it to all exp-coneave losses.
Lemma 10. For all x, E {6, 1]
In - In In
(-Inx) - (-Iny) - ((-11))) - -)) 2 2l1(1/8) V
(11)
Proof. The left-hand side of (T) equivalent to In(y/x) + (I w)/u = - - 1 with the substitution = In(y) In(x), Finally, verify in Lemma G3 that
- 2lm v4'
(12)
since our assumption x, [6, 1] implies |a| < l1(8/

---

The inequality I establishes that the logarithmic loss, when restricted to [6, 1], is (μ, co-convex for j x x² (128m(1/8)) v 4) and d(x, y) = In - In yl This choice of captures an important fact: the logarithm is more convex precisely when it is faster varying.
Remarkably, simple reduction shows that the same property is enjoyed by bounded, n-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 1-exp-concave loss function which satisfies the uniform bound S m. Then, for each x and y,
- (p)) - (Villy I -- 2 (b(ar) (b))1
(13)
2m V (4/n)
Proof. First note that since e T is concave, we have
exp(-170(Axr (1 A)y)) -e- + (1 A)e-n((())
Note that equality holds A 0. Taking logarithms of both sides and passing to the upper sub-ge bab-gradient& at = therefore yields
1) (V 1
v)
V In no e (o(())) (-)))t))
(14)
We then apply Lemma 10 with r and y replaced by e (=) and e mo(y), and with 8 = e -m Using
(14 to bound the gradient term then yields Proposition
Plugging (3) into Proposition and making a contraction argument yields the following upper bound for the excess ri-risk. The full argument is in Appendix C
Theorem 12. Let 1/ be an n-exp-concave loss function taking values in [0, m).. Then the star estimator in F satisfies the excess risk bound
Σ - -((r(())-(()))
n(vi(f)
})
BV(E(F) S EV
sup f.gEFt
(15)
18m1 V 36
where V is any increasing, convex function and F = UxEjo,1) AF +1 X)F. Alternatively, when ab is p-uniformly convex with modulus a and [иblاι Lipschitz, we have
))
lwllup (Si 9-)) alfi 9:l
EV(E()) & END
sup fiEF
(16)
3
Remark 13. An especially nice feature of 15 well as (18) below, is that all quantities appearing the bound are invariant to affine re-parameterizztioons of the learning problem.
Self-concordance
We close the section by considering self- colcordonndd losses e namely those for which
" < ))
In order to see how localization for self-concordant losses can be fit into the above framework, we rely the following inequality which was also used by Bilodeau al. (2020) Lemma 14 (Nesterov) (2014] Theorem 4.1.7)). Suppose & is self-concordant, and define the local norm || (1 /2 (w). Then
(xx) - (vy)
(V y. x 2 || y yll.. In (1+ -lll
(17)
The first thing that one should note is that, when one takes ta to be the negative logarithm, the above is exactly equivalent to the modulus (12) appearing in the proof of Lemma 10 Thus, upper bound
for exp-concave losses a consequence of self-conncrdaace the logarithm.
The path to general upper bounds via self-concordance is significantly more involved, we will only sketch Applying (17) to the excess risk and performing standard manipulations, one arrives the following upper bound, proved in Appendix D
7

---

Proposition 15. If is self-concordant loss and f is the empirical risk minimizer in a convex class F, then
Σ -(((()))((F)))) - -1fi-fillee))))
EV(E(f)) & EV
sup SEF
(18)
for (=) 2 log(1 2).
(w), and (e are independent, symmetric Rademacher random variables and v/ is any increasing, convex function.
|
Comparing this to (T6). the scale of the offset term has been improved from the modulus of strong convexity, which is the minimum second derivative, the second derivative at the risk minimizer, f" Expressing the increments (f) a/: (f") at scale comparable to I| fi wl is known to be achievable when f belongs to the so-called Dikin ellipsoid of tb,, J*), requiring more careful argument (see e.g. MMrteau--Fery et al. (2019). Notably, we do not know how to extend this bound the improper setting due to the local nature of the offset term.
5
Applications
We will now discuss several applications of Theorem 12 First, we'll sketch how the previous section's s results straightforwardly imply fast rates. We'll then discuss applications, first the p-loss and then to generalized linear models. Proofs in both cases are to be found in Appendix
While most general bound uses chaining, and is provided by Theorem 19 below, the essence of the argument is simple; we will sketch now. Let (.A,A) 2/) be a minimal covering of AA in (v) at resolution e, and define the entropy numbers H2(e, 9) = sup, I, v)) (where the supremum is over probability measures v) 2 Putting S. S. P..) and applying 15 with (z(z = exp(Anz)
gives
45 - 41) 7(3 - 1:)²
Eexp(>n(E(f)- - +)) S Eexp dn
sup s,tES,
18mm V 36
i=1
Anp(s: tt)
E
Σ 8,
Eg exp
Σ (s: (;))
18m1 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, Eg denotes an expectation w.r.t. the multipliers e conditional upon the data. Applying Hoeffding's lemma to the inner expectations with respect to sf gives
T
An(ss - -442 2\2 -,)²
SE
Σ cxp Σ S.ES
18m7 V 36
Choosing X- 36m V 72/n gives Ecxp(\>n(E(I) c)) i EE(SS)) & (2 by Chermoff bound
72
(oF) + In(1/p) <
36m V
(19)
The result (19) extends Mehta (017 Theorem 1) 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 Iivilnp is replaced by the range, m. Here, IIvÍlup appears only implicitly in the covering numbers, entering logarithmically in small classes. For the log loss, this is exponential improvement.
Next, the modulus of strong convexity is replaced by the exp-concavity modulus 7.. 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.
"Our 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- bhebabrobbbylityy bounds where v 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 v o F are equivalent to those of di o FF in all but finite classes, where the gap at most In(1/e). On the other hand, when the entropy numbers of sb o F are polynomial, particularly 6 with q < 2, then they can be polynomially smaller than those of rb o (co (Carl al. 1999).
5.1 Regression with p-loss
A surprising consequence of (19) concerns regression with the p-loss for 2. which is p-uniformly convex but nor strongly convex. When the inputs to the loss are bounded, the standard argument
pursued by Mendelson (202)) 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, B3 is B B-P-e---- --exp-concave,
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 [1).. For p S 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 vff.y) = If yl for > 1 and let the class F and response Y lake values in [-B, B). Then there exists a universal C(p, B) O(p2 BP) such that the star estimator f has excess v--risk bounded as
P (E((,F)22++ Clp, ()a.B)(Haee/Ca.. B, In(1/e) In(1/D)) S P:
(20)
n
By minor extension to Tsybakov (2003
Theorem 1), this result is sharp for each p.
5.2 Improper maximum likelihood
We next derive upper bounds for learning under the log loss, v/ f -n f in a class L. If we interpret f as the likelihood of an observation, empirical risk minimization coincides with maximum likelihood.
In
In this setting, a generalized linear model for multi-class prediction refers to the case where L = ((r,y) > (f(s), y) I E F) for some base class F. Here the link function yp outputs probability distributions over [k:]. and y E I2* is a basis vector encoding the label.
These models are typically formulated as minimizing the loss dieel f In (f((f) v) 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 of & L in order to exploit localization of the log loss. When is surjective, these yield improper predictors under اe9l by composing with a fight-innerrse sot
To illustrate, will derive our quoted bound (I 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. (208)), 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 most dramatic, we need to replace L by the ò-regularization Ls- (1 (1-8) 8)C + 8. The approximation error is controlled as follows.
Lemma 17
(Foster et al. 2018)). ). For all f and 8 E (0, 1/2), the excess risk relative to L.s satisfies
Es::Cs) < E(f:C) + 25
We now state our result. Corollary 18. With probability at least 1 p, the star estimator fo in Ls satisfies
E(j6; C) S c 25 + H2g(e,, L) + In(1/c8) + In ln(1/p) (m((pp))))p)))))))
(21)
n
Let be the generalized linear model corresponding to
FB = fx Wx W kxg || 20200 B}
9

---

with A-Lipschitz. surjective link and features X E R that satisfy |X|| I Rvq. Then with probability least
E FB) In(n) [AKgIn(ABR In(1/p))
(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 plasses-namele those with H2(e, F of order 9 for small e-we need to state the chaining version of our bound, proved in Appendix E
Theorem 19. Let & be n--xp--onccer loss taking values in [0, ml]. Then, with probability least 1 =,, the star estimator f applied to (1,F) F) satisfies
(H2(s) ds 2H2(7) Vn [.'
10
7V88
( en
TV8 +
8()) inf 0sasy
4a +
vn )z{. (23)
en
vn
where H2(s) H2(8, F¹) and c = 36 (1/m An22)
In classes with entropy e our results fall into two regimes. The first covers losses such as the logistic loss, for which - In ou A-Lipschitz. Here, the covering numbers of In oC, differ from those of F by the constant A9, and match the optimal rates for the square loss (Rakhlin et al. 2017].
For general L, the covering numbers of - In oLs may contain an extra factor 8-9, leading to suboptimal rates. Suboptimality follows from combining the minimax regret analysis of Bilodeau al. (2020), which produces the average regret -111(4)))), with 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 significant open problem.
Corollary 20. Consider a generalized linear model with A-Lipschitz loss f + - In (p((), v)- Suppose the entropy numbers H2(e; F) are of order e Then, the regularized star estimator opt o fo 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' -fr appropriately chosen 8' a'tainns the rales appearing on the right.
Here, the symbol S. denotes upper bound that holds with probability p. hiding universal constants and a multiplicatiiv factio (1(/p)).
A 22((3+)) In(n)
2
1/(1+3//2)
< 2
Elyp' o f8) Sp
A 1/2 1/2-1/21n(0
g 2
E(fs) Sp
In(n) q 2
(24)
A 1/9
q > 2
7 1/(2g)
q > 2
In closing, would like to highlight the additional, unresolved problem of designing a computa- tionally efficient implementation of the regularized star estimator-in particular for log-concave link functions & where the first step is 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.
10

---

References
Jean-yves Audibert. Progressive mixture rules are deviation suboptimal. In J. C. Platt, D. Koller. Y. Singer. and S. T. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 41-48. Curran Associates, Inc., 2008.
Jean-Yves Audibert. Fast learning rates in statistical inference through aggregation. The Annals of Statistics, 37 (4):1591 1646, 2009. doi: 10.1214/08- AOS623. htt./tttp///o...og/000.. 121400001111--1111 00014/000006633 A0S623
Peter I.. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities, Annals of Statistics, 3344):1977-1537 August 2005. ISSN 0090-5364, 1168-896. doi: 10. 10.1214/0000336050000000003
Peter L. Bartlett, Michael I. Jordan, and Jon D. Mcauliffe. Convexity, Classification, and Risk Bounds. Journal of the American Statistical Association, 101(473):138-1555 2006. ISSN 0162-1459.
Blair Bilodcau, Dylan Foster, and Daniel Roy. Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance. In International Conference on Machine Learning, pages 919-929. PMLR, November 2020.
Bernd Carl, loanna Kyrezi, and Alain Pajor. Metrie Entropy of Convex Hulls Banach Spaces. Journal of the London Mathematical Society, 60(3):871-866, December 1999. ISSN 0024-6107. doi: 10.1112/
Charles Chidume. Inequalities in Uniformly Convex Spaces. In Charles Chidume, editor, Geometric Properties of Banach Spaces and Nonlinear Itevations, Lecture Notes in Mathematics, pages 29 44. Springer, London, doi: 10. 10079979 1-84882- 190-3_4.
2009. ISBN 1---888--19---3-
Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic Regression: The Importance of Being Improper. In Conference On Learning Theory, pages 167-208. PMLR, July 2018.
Elad Hazan, Tomer Koren, and Kfir Y. Levy. Logistic regression: Tight bounds for stochastic and online optimization. Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of the 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 197-209, Barcelona, Spain, June 2014. PMLR.
Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Efficient improper learning for online logistic regression.
In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 22 of Proceedings of Machine Learning Research, pages 2085-2108. PMLR, 09-12 Jul 2020. URL htttcppp///prccedingg mlr. press/v125 jezequel20a. htmll html
A. Juditsky, P. Rigollet, and A. B. Tsybakov. Learning by mirror averaging. Annals of Statistics, 36(5):
2183-2206, October 2008. ISSN 0090-5364, 2168-8966. doi: 10. 2214/07-AOS544
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher Processes and Bounding the Risk of Function Learning. In Evarist Giné, David M. Mason, and Jon A. Wellner, editors, High Dimensional Probability
II. Progress in Probability, pages 443 457, Boston, MA, 2000. Birkhäuser. ISBN 978 1--11---11-3-5 1358-1. doi: 10. 10.10077978---44122 1-28-11--__
Michel Ledoux and Michel Talagrand. Rademacher Averages, In Michel Ledoux and Michel Talagrand, editors, Probobility in Banach Spoces: Isoperimetry and Processes, Frgehnisse Der Mathematik Und Threr Grenzgebicte, pages 89-121. Springer, Berlin, Heidelherg, 1991. ISBN 978-3-642-20212-4, doi: 10. 00.10077978-336222222222
Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan. Leamingg with Square Loss: Localization through Offsct Rademacher Complexity. Conference on Learning Theory, pages 1260-1285, June 2015.
Ulysse Marteau- Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi. Beyond Least-Squares Fast Rates for Regularized Empirical Risk Minimization through Seff-Conccrdaace. In Conference Learning Theory, pages 2294-2340. PMIR, June 2019.
Nishant Mehta. Fast rates with high probability in exp-concave statistical learning. In Artificial Intelligence and Statistics, pages 1085-1093. PMLR, April 2017.
S. Mendelson. Improving the sample complexity using global data. IEEE Transactions on Information Theory, 48(7):1977- 1991, July 2002. ISSN 0018-9440 doi: 10. 109/11112002..00 1013117.
Jaouad Mourtada and Stéphane Gaiffas, An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. arXiv:1912.10788 [math, stat), 2020.
Yurii Nesterow, Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, first edition, 2014. ISBN 1-4613-4691-6.
Dmitry Panchenko. Symmetrization approach to concentration incqualities for empirical processes. Annols of Probubility, 31(4):2068-2081 October 2003. ISSN 0091-1798, 2168-894X. doi: 10. 1t.1224/aao
Alexander Rakhlin and Karthik Sridharan. Online Non- Pa--aaraettric Regression. In Conference on Learning Theory, pages May 2014.
11

---

Alexander Rakhlin and Karthik Sridharan. Online Nonparametric Regression with General Loss Functions. arXiv:1501.00 06598 [cs, math, statj, Jamuary 2015. Comment: arXiv admin note: substantial text overlap with arXiv:1402.2594.
Alexander Rakhlin, Karthik Sridharan, and Alexandre B. Tsybakov. Empirical entropy. minimax regret and minimax risk. Bermoulli, 23(2):789 824, May 2017. ISSN 1350-7265, doi: 10.3150/14-BEJ66
Philippe Rigollet, Kullback-Leiin aggregation and misspecified generalized linear models. Annals of Statistics, 40K2):39-665, April 2012. ISSN 0090-5364, 21 2168-8966. doi: 10.12 10.1214/1 A-S9661..
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Lafferty, C. Williams, Shawe- Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, pages 2199-2207. Curran Associates, Inc., 2010.
Alexander B. Tsybakov. Optimal aggregation of classifiers in statistical learning. Annals Statistics, 32(1):
135-166, Fehruary 2004. ISSN 0090-5364, 2168-8966. doi: 10.1214/an//1071122
Alexandre B. Tsybakov. Optimal Rates of Aggregation. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Learning Theory and Kernel Machines, Lecture Notes Computer Science, pages 303-313, Berlin, Heidelberg, 2003. Springer. ISBN 978-3-540-45167-99 doi: 10.1007/978- --177-------0- 23.
Tim van Erven, Peter D. Grünwald, Nishant A. Mehta, Mark D. Reid, and Robert C. Williamson. Fast Rates in Statistical and Online Learning. Journal of Machine Learning Research, 16(54):1793 17611181,,1111 2015. ISSN 1533-7928.
12


Reviews:
[{"review_id": "yKIrdmGOJE", "reviewer": "Reviewer_AiEE", "summary": "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:\n(a) they can obtain fast rates for l_p losses for p > 2. \n(b) they can obtain fast rates for exp-concave losses that depend on the range of the loss instead of its Lipschitz constant. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "\nI think the paper provides a comprehensive summary of the machinery of offset Rademacher for obtaining fast rates, and provide new results for some settings. However, I feel that the new contributions are limited, and thus I can not support strongly for acceptance. I also feel that the paper is written in a very contrived manner and it is hard to understand what the new results are and why they are important. A few illustrative examples with a proper comparison to prior work might help in delivering the message of the paper more clearly. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "Mdl7XkLhw9J", "reviewer": "Reviewer_zjpm", "summary": "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.\nThe 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).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper was fascinating to read, and I am quite excited about the results!  Combining the star algorithm with offset Rademacher averages is clever, and the consequences are quite desirable, giving new insights into both. Some inconsistencies in the paper and confusing or underspecified notation mar readability and my understanding of the work slightly, but overall do not severely hinder the paper, though I would like to see them addressed. I have some technical questions regarding proposition 7, and concerns over its usability given that $f^*$ is not in general known, however these may be straightforward to address (upon which I would likely evaluate the paper more favorably).  I would also like to see more explicit comparisons to existing methods (in particular bound decay rates on common problems).\n\n\n\n\nItem 1 of the contributions in the introduction states that you show that offset Rademacher averages work with $(\\mu, d)$ convex functions, but proposition 7 is already using the star-algorithm approach. Presumably a similar result holds in the convex case, without the $\\frac{1}{3}$ constant, but this would be nice to see in the paper, with a clear comparison to Liang 2015.\n\n\n\nMost of my comments revolve around proposition 7.  It is a very nice result, however it does not match the statement in the appendix.  (9) in the appendix differs from (9) in the paper body, and the difference is somewhat non-trivial, as $\\mu$ is multiplied by the Rademacher random variables in the appendix, but not in the body. It also looks like a 2 or a 4 factor might be missing from the $\\mu$ term, if the offset term does not have a complementary constant factor.\nIn the appendix form, subtracting $\\mu$ before multiplying by $\\epsilon_i$ could severely decentralize the function family.  Could this be combined with (empirical) centralization arguments (see, e.g., [1]), to decrease the Rademacher average?\n\n\n\nAn obvious issue with applying this result is that it depends on the population-optimal $f^*$ which in machine learning applications, obviously we can't assume to know. It doesn't seem to me like replacing it with $\\hat{f}$ could work without introducing severe bias that would be difficult to correct for (unlike with localized Rademacher averages, where empirical variances can play the role of true variances, with modest correction factors). It seems that in theorem 11, you fix this by worst-casing over $f^*$ (and calling it $g$), but I would prefer to see this described around proposition 7.  I’d also like to see if the supremum over $g$ could be moved outside the expectation, and if it could be over a subset of $\\cal F$ that is near-optimal (i.e., that contains $f^{*}$ w.h.p.).\n\nAnother point I'd like to make on line 120 / proposition 5.  As far as I can tell, nothing is stopping you from applying the triangle inequality (in $d$) and Jensen’s inequality (in $\\mu$) to get  $f(x) - f(\\tilde{x}) \\geq 3\\mu(\\frac{1}{3} d(x, \\tilde{x}))$. This propagates throughout the paper to a significant improvement to your results, e.g., to proposition 7, and for $(p=2)$-uniform convexity (example 1), it improves your constant-factor gap from 9 to 3.  Faster-decaying offsets may also enable analysis on models for which bounds were previously vacuous.\n\n\nSpecifics:\n\n\n39: “leading to fast upper bound” confusing, should be \"a fast-rate\" or \"a fast-decaying\"?\n\nProposition 1: It was not at all clear on an initial read what $k$ is.  Specifying $k$-class logistic regression would clarify significantly.  Furthermore, what good is a bound on the norm of the predictors, without also bounding the norm of the data? Is $B$ a bound on the dot product of data points and weights vectors?\nFurthermore, in most of the paper, $d$ is a metric, and $B$ a vector space, this could get very confusing.\n\nDefinition 2: The subgradient is in general set-valued. I presume the definition needs to hold either for all or for some subgradient?  Furthermore, the condition is undefined for coincident $x, y$. $\\mu$  needs to be extended, presumably such that $\\mu(0) = 0$ and $\\mu(x) > 0 \\forall x > 0$, or you must restrict $x \\neq y$?  Did you need to use, specifically, the sub-gradient anywhere?  Perhaps the paper would be better off stated for differentiable functions, with an explanation of how it may be extended to the subdifferentiable case?\n\nFrom the proof of Lemma 4, I gather that it's for some subgradient rather than for all, as I believe that proof would fail, for instance, with the function $f(x) = x$ for some (but not all) subgradients.\n\nBefore lemma 6, some explanation of the metric $d_n$ would be greatly appreciated.\n\n\nlemma 6: As far as I can tell, $x$ is a model output, not a model domain member, but this is confusing.  $\\psi$ must be convex in what, the parameter space (function space), or $x$ itself?  It is also not clear what $f_{i}$ is (or $g_{i}$ later in the paper); presumably $f_i = \\psi(f(X_i), Y_i)$?.  Either way, some type qualifiers on $x,y,\\psi$, and $d$ would make such confusion impossible.\n\nI'm a bit confused by the calculus notation on 153: is the limit an upper limit, or does the notation reflect some matter of converting the set-valued subgradient to a scalar?  And presumably the differentiation expresses a partial derivative, but $d$ (particularly when set in italics, rather than roman) is confusing, as it’s often used as a distance function?\n\n156: Stating or bounding the constant would be appreciated.\n\nEquation 7: It's not illegible, but some brackets on the expectations would not go amiss.\n\n161: is $\\equiv$ congruence / equivalence, or definition (sometimes written $\\doteq$, $:=$, $=:$, or $=$ with a triangle)?\n\n\nProp 7: Eq. (9) of the appendix would be easier to read with variably-sized parentheses. Similar applies throughout the appendix.\n\nRemark 8: Is this nomenclature standard?  I think of localization as inherently a scaling or second moment normalization process, whereas this is clearly a shifting argument.  This reviewer is admittedly more familiar with localized Rademacher averages than offset Rademacher averages; perhaps there is no issue.\n\n208: Can $\\sup_{g}$ go outside the expectation?\n\n237: “While most general bound uses chaining and” -> “While the most general bound uses chaining, and”\n\n239: Why do we need to worst-case over probability measures in a chaining bound?  Can we not use empirical covering numbers?  Also, calling the probability measure $\\mu$ will lead to confusion with the function $\\mu$.\n\n317: “Jean-yves Audibert” -> “Jean-Yves Audibert”\n\n\nReferences:\n\n[1] \"Sharp uniform convergence bounds through empirical centralization,\" C Cousins, M Riondato", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Largely N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "86BbA57thcB", "reviewer": "Reviewer_TjwQ", "summary": "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.\nSharp 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).\nFrom 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.\nThe 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).\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "This paper is clear and well-written, and contains a clean extension of results on Star aggregation for square loss to other standard settings such as exp-concave statistical learning. As far as I know, the extension of Star to the exp-concave setting (or for L^p regression), for instance, has not appeared before in the literature (different procedures were considered e.g. by Mehta).\nI also appreciate the derivation of the negative quadratic term for exp-concave losses (reducing first to log-loss) in the right distance in Sec 4.\nAs a result, I definitely recommend acceptance of this paper at Neurips (I did not check the proofs enough to be able to confidently put a high.\n\nDue to significant reviewing load and limited time, I did not really check the proofs in the supplementary material, so (as far as I am concerned) correctness is left to the authors' responsibility.\nHowever, at a high level, I believe the authors' approach is sound. Indeed, Audibert's insight was that ERM can fail in the nonconvex setting if two functions are far from each other but have near-identical risk; however, in this case, the midpoint of the two will have better risk by the parallelogram identity. However, the argument is not specific to the negative quadratic term arising from the parallelogram identity, and it should also extend to other types of uniform convexity, as shown in the paper. Such moduli of convexity are in fact derived in detail both for the considered special cases in the main text, so the ingredients are in place.\n\nBelow are some additional comments:\n- The abstract states: \"Surprisingly, this condition is shown to capture exponential concavity and self-concordance, uniting several apparently disparate results.\"\nAs stated, this seems to be somewhat excessive, since unlike for exp-concave or p-loss, no explicit bound is stated for convex self-concordant ERM from the generic bound (2) as noted in lines 231-2, whether the bound can be leveraged in the improper setting is unclear due to the local nature of the quadratic approximation provided by self-concordance.\n- Naively implemented, the complexity of the Star algorithm for GLMs could potentially scale exponentially with the dimension. A natural open question raised by the authors is whether it can be computed efficiently. In addition to this direction, there is another approach to improper logistic regression besides the mixture/Vovk AA and Star-shaped aggregation, see:\nMourtada, Gaiffas \"An improper estimator with optimal excess risk in misspecified density estimation and logistic regression\",\nwhich is based on regularization using the test sample and is computed at the cost of finding a convex ERM.\n- The statement of Proposition 1 is perhaps too vague at this stage in the text, as the setting is not properly introduced yet.\n- Equation (21): the dependence on log(1/rho) should be in principle be additive rather than multiplicative.\nThe same should hold for Corollary 18.\n- Line 261: \"so we optimal\"\n- For square loss, the constant 1/9 is obtained; if I remember correctly, this is actually the optimal constant for this inequality (as can be seen by considering aligned points?).\n\n--\nUpdate:\nThank you for your reply. \nThe authors addressed my comments, and in light of the reply and other reviews, I would like to maintain my positive evaluation of this paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "0GjPrcRG4Cu", "reviewer": "Reviewer_2t7n", "summary": "This paper provides a unifying framework to study convex empirical risk minimization as well as improper learning under general entropy conditions. The key contribution is to prove a generalized version of the offset Rademacher process which takes into account a general notion of convexity, called $(\\mu, d)$-convexity.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Overall, the paper makes an interesting observation regarding the fast rates in supervised learning. Seemingly disparate conditions of exp-concavity and self-concordance can be viewed in a unified framework.\n\nThere are a few points/questions worth highlighting.\n- One weakness of this work currently seems to be that while it is able to unify existing known upper bounds, it rarely shows applications where rates previously unknown could be derived as a consequence of this unification. One exception is the improvement mentioned in line 248 for the log-loss, but I would like to see that written out more explicitly and highlighted in the main text.\n- Are there possible scenarios where this generalized offset process does not provide the right learning rates even though the underlying functions satisfy $(\\mu, d)$-convexity?\n- In terms of writing, I feel that the paper could substantially improve its readability by providing a notation section which summarizes the various notation used in the paper. For instance, line 144 has a notation $f_i^*, \\hat{f}_i$ which is never defined (the i might also be a typo here). Example 1 uses a function $\\psi$ which is not defined for a single input. Line 161 $h(Z)$ is not defined. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the limitations have been described", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a nice unifying method to obtain fast rates for exp-concave losses, uniformly convex losses etc via an offset rademacher complexity type term. While the rates covered in the paper are not new, the unifying analysis is simple and clean. 

The reviewers are positive about the contributions of the paper and think that the paper is worth publishing. I concur with the reviews and find the contributions of the paper clean and neat. Overall I recommend acceptance. 
Decision: Accept (Poster)