Tight Risk Bounds for Gradient Descent on Separable Data
Authors: Matan Schliserman
Tomer Koren
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Convex optimization
Gradient Descent
separable data
generalization bounds
Stochastic Gradient Descent.
TL;DR: We establish tight upper and lower (population) risk bounds for Gradient Descent in the setting of linear classification with separable data.

Abstract: We study the generalization properties of unregularized gradient methods applied to separable linear classification---a setting that has received considerable attention since the pioneering work of Soudry et al. (2018).
We establish tight upper and lower (population) risk bounds for gradient descent in this setting, for any smooth loss function, expressed in terms of its tail decay rate.
Our bounds take the form $\Theta(r_{\ell,T}^2 / \gamma^2 T + r_{\ell,T}^2 / \gamma^2 n)$, 
where $T$ is the number of gradient steps, $n$ is size of the training set, $\gamma$ is the data margin, and $r_{\ell,T}$ is a complexity term that depends on the tail decay rate of the loss function (and on $T$).
Our upper bound greatly improves the existing risk bounds due to Shamir (2021) and Schliserman and Koren (2022), that either applied to specific loss functions or imposed extraneous technical assumptions, and applies to virtually any convex and smooth loss function.
Our risk lower bound is the first in this context and establish the tightness of our general upper bound for any given tail decay rate and in all parameter regimes.
The proof technique used to show these results is also markedly simpler compared to previous work, and is straightforward to extend to other gradient methods; we illustrate this by providing analogous results for Stochastic Gradient Descent.

Tight Risk Bounds for Gradient Descent on Separable Data
Matan Schliserman
Tomer Koren 12
Blavatnik School of Computer Science, Tel Aviv University Google Research, Tel Aviv
Abstract
We study the generalization properties of unregularized gradient methods applied to separable linear classification-44 setting that has received considerable attention since the pioneering work of Soudry al. [14]. We establish tight upper and lower (population) risk bounds for gradient descent in this setting, for any smooth loss function, expressed in terms of its tail decay rate. Our bounds take the form O(r2, + r /r",,, where T is the number of gradient steps, is size of the training set, y is the data margin, and Ft,r is complexity term that depends on the tail decay rate of the loss function (and on T). Our upper bound greatly improves the existing risk bounds due to Shamir 13] and Schliserman and Koren [12, that either applied to specific loss functions or imposed extraneous technical assumptions, and applies to virtually any convex and smooth loss function. Our risk lower bound is the first in this context and establish the tightness of our general upper bound for any given tail decay rate and in all parameter regimes. The proof technique used to show these results is also markedly simpler compared to previous work, and is straightforward to extend to other gradient methods; we illustrate this by providing analogous results for Stochastic Gradient Descent.
Introduction
Recently, there has been a marked increase in interest regarding the generalization capabilities of unregularized gradient-based learning methods. One specific area of attention in this context has been the setting linear classification with separable data, where a pioneering work by Soudry et al. [14] showed that, when using plain gradient descent to minimize the empirical risk classification loss (such as the logistic loss), the
linearly
separable training set with an exponentially-taile trained predictor will asymptotically converge in direction to the max-margin solution. As result, standard margin-based generalization bounds for linear predictors suggest that, provided the number of gradient steps (T) is sufficiently large, the produced solution will not overfit, despite the lack of explicit regularization and the fact that its magnitude (i.e., Euclidean norm) increases indefinitely with T. This result has since been extended incorporate other optimization algorithms and loss functions
9 5
Despite the high interest in this problem, the tight finite-time (population) risk performance of unregularized gradient methods, and even just of gradient descent, have not yet been fully understood. high margin solution exhibited by Soudry et al. [4] (for the logistic loss) occurs
The convergence at a slow logarithmic rate, thus, the risk bounds for the trained predictors only become effective when T at least exponentially large in comparison to the size of the training set n and the margin y. In more recent work, Shamir [13 established risk bounds of the form 2 1 1/y²n) for several gradient methods in this setting (still with the logistic loss), that apply for smaller and more realistic values of T:
*Corresponding author; senlisermmn@mil. acu.ac.il.. il.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Table 1: Comparison between the bounds established this work and bounds established in previous work for for gradient descent on y-separable data; here, the number of gradient steps and is size the training set. Logarithmic factors other than log 7' factors are suppressed from the bounds. Examples of how our general bounds are instantiated for some concrete loss functions are presented in Table 2 below.
Paper
Class of losses
Type bound
Upper bound log'T YT
Lower bound
Shamir
Logistic loss
0-1 loss
(0)
(population)
y'n
y"7
General convex;
smooth; I Lipschitz;
Risk (population)
2ar T3 y'n
y²
Schliserman and Koren [12]
Decay rate of &
General convex;
smooth;
Risk (population)
3 y-T
126 An
A-6 aT
(..)-self-bouudede
Decay rate of &
Convex linear models;
Telgarsky [16
inndrratcaall-boundeedee Decay rate of &
Risk
Ta.r (d) yVT
(population)
Convex linear models;
Risk
2
2.r
2a y
Far y'n
This paper
smooth;
Decay rate of Φ
(population)
y
y'n
The lower bound is shown for the empirical (logistic) risk. b is (c. (c.66)-ell-bounddee bounded if for every x, holds that [V/(()) cf(xx for < 1/2, this property stronger than smoothness of f. / is (c1, e2) quadratically bounded if, for every and z, (x, s ci +c2+ +| ||=|))
The upper bound is valid when n.
Later Schliserman and Koren [12 gave more general analysis that extends the bounds of Shamir 13 to a wide range of smooth loss functions satisfying a certain "self- holf-bouunedness"" condition, and Telgarsky [16) provided test-loss analysis of stochastic mirror descent
suuudratically-boundee losses. However, all of these works either assume a specific loss (e.g., the logistic loss), impose various conditions on the loss function (beyond smoothness), or do not establish the tightness of their bounds in all regimes of parameters (T, n and y), and especially in the regime where the number of gradient steps T is larger than the sample size (see Table for details).
1.1 Our contributions
In this work, we close these gaps by showing nearly matching upper and lower risk bounds for gradient descent, which hold essentially for any smooth loss function, and for any number of steps T and sample size n. Compared recent prior work in this context [33 16 [2]. our results do not require any additional assumptions on the loss function besides its smoothness, and they strictly improve upon the existing bounds by their dependence on T. Further, to the best of our knowledge, risk lower bounds were not previously explored in this context, and the lower bounds we give establish, for the first time, the precise risk convergence rate of gradient descent for any smooth loss function and in all regimes of T and
In some more detail, our results assume the following form. Let Co.p be the class of nonnegative, convex and f-smooth loss functions (()) that decay to zero (as it - oo) faster than reference "tail function" : oo) - R. The function & is merely used to quantify how rapidly the tails of loss functions in Co. decay to zero. Then, the risk upper and lower bounds we prove for gradient descent are of the following form
Br 6.T
Br O.
+
(1)
2T
22n
FFor simplicity, we specialize the bounds here to gradient descent with stepsize 17 = =0118), but the bounds hold more generally any stepsize smaller than (1/B).

---

co in terms of the logistic loss Table 2: Examples of tight population risk bounds established in this paper for gradient descent y-separable data, instantiated for several different loss tail decay rates. Details on the derivation the bounds from the general Theorems and can be found in Appendix A
Tail decay (+)
Risk bound
log" (T)
(T)
exp(-x)
Iog(7)
+
y²T
y²n
1
T zra
x-a
(y²T) नमो
+
log 2 (T)
log (T)
exp(-x")
log (T)
+
y
y2n
The bounds depend on the tail function & through the term rørr that, roughly, equals o (x) for chosen such that = (<)) (for the precise statements refer to Theorems I and and for concrete examples of implied bounds, see Table 2
The form of Eq. ① resembles the bounds given in recent work by Schliserman and Koren 12] However, the latter work imposed an extraneous "seff-boundedness" assumption (stronger than smoothness, see Table that we do not require, and they did not establish the tightness of their bounds, as we do in this paper by providing matching lower bounds. On the flip side, their upper bounds apply in broader stochastic convex optimization setup, whereas our bounds are specialized to generalized linear models for classification.
In terms of techniques, our proof methodology is also distinctly (and perhaps somewhat surprisingly) simple compared to previous work. Our upper bounds rely two elementary properties that gradient methods admit when applied to a smooth and realizable objective: low training loss and low norm of the produced solutions. Both properties bounds for smooth gradient descent, when paired with conditions implied by the decay rate of the loss function. Finally, to bound the gap between the population risk and the empirical risk, we employ classical result of Srebro et al. [15] that bounds the generalization gap of linear models in the so-called "low-noise" (i.e., nearly realizable) smooth regime using local Rademacher complexities. Somewhat surprisingly, this simple combination of tools already give sharp risk results that improve upon the state-of-the offte--f-the-art [13 12 [6] both in terms of tightness of the bounds and the light set of assumptions they rely on.
obtained from fairly standard arguments and convergence
We remark here that the proof scheme summarized above be generalized essentially any gradient method for which one can prove simultaneously bounds on the optimization error and the norm of possible solutions produced by the algorithm. In the sequel, we focus for concreteness standard gradient descent, but in Appendix B we also give bounds for Stochastic Gradient Descent (SGD), which is shown to admit both of these properties with high probability over the input sample.
An interesting conclusion from our bounds pertains to the significance of early stopping. We see that gradient descent, even when applied overfit with respect the the surrogate loss (i.e., reach a trivial @(1) risk) as the number of steps T grows. The time by which gradient descent starts overfitting depends on the tail decay rate of the loss function: the slower the decay rate, the shorter the time it takes to overfit. Interestingly, a similar phenomenon may not occur for the zero-one loss of the trained predictor. For example, Soudry et al. [4] show that with the logistic loss, gradient descent does not overfit in terms of the zero-one as T approached anfinit--hheeaa at the same time, it does overfit itself, as seen from our lower bounds.
smooth loss functions that decay rapidly to zero, might
Summary of contributions.
To summarize, the main contribution of this paper are as follows:
Our first main result (in Section 3 is a high probability risk upper bound for gradient descent the setting of separable classification with convex and smooth loss function. Our bound matches the best known upper bounds [13 12 and greatly extend them to allow for virtually any convex and smooth loss function, considerably relaxing various assumptions imposed by prior work.
3

---

Our second main result (in Section 4 is nearly matching lower bound for the risk of gradient descent, establishing the tightness of our analysis given the smoothness and tail-decay conditions. The tightness of our bounds holds across tail decay rates and different regimes of the parameters T, and y. To our knowledge, these constitute the first (Iet alone tight) risk lower bounds this context, despite long line of work on linear classification with separable data.
We also provide analogous results for Stochastic Gradient Descent with replacement (in Appendix[B] mainly to emphasize that that our analysis uses only two elementary properties of the optimization algorithm: low optimization error and low norm of the produced solution. The same analysis can be generalized to any gradient method that admits these two properties.
1.2 Additional related work
Unregularized gradient methods on separable data. The most relevant work to ours is of Schliserman and Koren [12], who used algorithmic stability and two simple conditions of self- boundedness and realizability which the loss functions hold, to get generalization bounds for gradient methods with constant step size in the general setting of stochastic convex and smooth optimization. Then, they derived risk bounds which hold in expectation for the setting of linear classification with separable data for every loss function which decays O. The exact bound was depend in the rate of decaying to 0 of the function. For the Lipschitz case their risk bound with respect to the loss function for any choice of such that g/ (x) s 1/y²T. For example, for the logistic loss, the bound translates to Ollog" (T)/>² / + log'
É is (()-1())2 (s)2/>²T++ +
(T)
(Tg (T)
In another work, Telgarsky [16]. showed a high probability risk bound for T S n for Batch Mirror Decent with step size 17 = I/VT in linear models, using a reference vector, which when selected properly, can be translated to a risk bound of O(t-1(s) /V) for gradient descent applied on the loss function e, and to a (log /YVT) for the logistic loss.
Fast rates for smooth and realizable optimization. The problem of smooth and realizable optimization, also known as the "low-noise" regime of stochastic optimization, is a very well rescarched problem. Srebro al. [15] showed that stochastic gradient descent achieved risk bound of 0(1/n) in this setting. For linear models, they also showed that ERM achieve similar fast rates by using local Rademacher complexities. Later (10) showed that SGD converges linearly when the loss function is also strongly convex. In more recent works, 7 used stability arguments to show that SGD with replacement with T achieve risk of (11n).
Lower bounds. A lower bound related to ours appears in Ji and Telgarsky 4 In this work, the authors showed lower bound of |[w]- w'll 2 log(n) /log(7). In our work, however, we get lower bound directly for the loss itself and not for this objective. More recently, Shamir [13 showed a lower bound of 52(1 1 2T) for the empirical risk of GD when applied on the logistic loss which is tight up to log factors. When generalizing this technique for other objectives, e.g., functions that decay polynomially to zero, the log factors become polynomial factors and the bound becomes not tight, even in the regime T & n where the 1/T term in the bounds is dominant, In contrast, we establish nearly tight bounds for virtually any tail decay rate, and in all regimes of T and n.
2 Problem Setup
We consider the following typical linear classification setting. Let D be distribution over pairs (x, y). where x Rd is a d-dimensional feature vector and y R is a real number that represents the corresponding label. We assume that data is scaled so that ||x||| s 1 and |y| s (with probability one with respect to D). We focus on the setting of separable, or realizable, linear classification with margin. Formally, we make the following assumption.
Assumption (realizability). There exists a unit vector w' E Rd and y > 0 such that y(w" 2 almost surely with respect to the distribution D.
Equivalently, we will identify each pair (x, y) with the vector 2 = yx, and realizability implies that w" 2 2 y with probability 1. Our assumptions then imply that ||ı|| z with probability 1.
Given a nonnegative loss function é R - Rt the objective is to determine a model w Rd that minimizes the (population) risk, defined as the expected value of the loss function over the distribution

---

D. namely
L(w)= = = 2)].
(2)
For finding such a model, we use set of training examples S = (.), which drawn i..d. from D and an empirical proxy, the empirical risk, which is defined as
Σ(w) = n Σ
a(w 21).
(3)
2.1 Loss functions
The loss functions l considered in this paper are nonnegative, convex and f-smooth We also require that is strictly monotonically decreasing and lim ((u) The vast majority of loss functions used in supervised learning for classification satisfy these conditions; these include, for example, the logistic loss (f(u) = log( + e e)"),, the probit loss (E(u) logg 1 erf(u))), and the squared hinge loss (f(u) = (max
0))
main goal of this paper is quantify how do the achievable bounds the risk depend properties of the loss function l used, and most crucially on the rate in which 8 decays to zero as its argument approaches infinity. To formalize this, we need a couple of definitions.
Definition (tail function). We say that o [0, oo) - is a tail function if Φ
(i) is nonnegative, 1-Lipschitz and ß-smooth convex function; is strictly monotonically decreasing such that lim 6(u) O;
iiii) satisfies (0) 2 1 and ( (0) 1
Every tail function & defines class of loss functions characterized by the rate & decays to zero. Definition (é-tailed class). For a tail function 6, the class Ce.s is the set all nonnegative, convex, 8-smooth and monotonically decreasing loss functions e R - R* such that ((u) S d(u) for all " 2 O.
We detail several examples for tail functions in Appendix A
2.2 Gradient Descent
The algorithm that we focus in this paper is standard gradient descent (GD) with a fixed step size > 0 applied to the empirical risk Z; this method is initialized at 0 and at each step = ,....
performs an update
W/+1 w, r7Vi(w,))
The algorithm returns the final model, wr.
We remark however that most of the results we present in the sequel can be straightforwardly adapted other gradient methods; we include results for Stochastic Gradient Descent (SGD) in Appendix [ and the same proof techniques can be used to analyze multi-epoch and/or mini-batched SGD, gradient flow, and more.
3 Risk Upper Bounds
We begin by giving general upper bound for the risk of gradient descent, when the loss function E is taken from the class Cs.p. Our main result in this section is the following.
Theorem 1. Let & be a tail function and let f be any loss function from the class Co.B- Fix T.n and 8 > 0. Then, with probability at least 1 - 8 (over the random sample S of size n), the output of GD applied L with step size S 1/2B initialized at =0 has
L(WT) 4K (()) 32KB(6 (E)) (log² n 4lg
4K (E)) log B
y2n
for any 8 $ 1 such that 2T s ($ (6- (x))2/, where K < 10 a numeric constant.
"A differentiable function E R - R is said to be B-smooth over R (fv s E(u)+t' (w)- (1-w)))00000
for all e R.
5

---

The expression (6 ( increases indefinitely as approaches O; therefore, for any T. there exists an & that satisfies the theorem's 's condition. For several examples of how this bound is instantiated for different tail decay functions 6, see Table 2 and Appendix A
In the remainder of this section prove Theorem | The structure of the the proof will be follows: First, we bound the norm of the GD solution; by smoothness and realizability, we get that the norm will remain small compared optimization error in this setting, the relies on the same reference point. Finally, we use a fundamental result due to Srebro the risk guarantee. As discussed broadly in the introduction, this proof scheme can be generalized to other gradient methods which satisfy the properties of model with low norm and low optimization error.
reference point with small loss value. Second, we get bound on the
(reviewed the subsection below) together with both bounds derive
3.1 Preliminaries: Uniform Convergence Using Rademacher Complexity
One property of linear models is that in this class of problems is that have dimension and aagorithm-indepene the empirical risk and the population risk of specific model. A main technical tool for bounding this difference is the Rademacher Complexity [2). The worst-case Rademacher complexity of an hypothesis class H for any sample size given by:
dimeeniioninndeeenden independent uniform convergence bounds, that enables to bound the difference between
N Σ MZZ))O
R₂ (H) = sup UnifUi((((1)))))
sup R
Zo
We are interested in models that achieve low empirical risk on smooth objectives. A fundamental result of Srebro al. [15] bounds the generalization gap under such conditions:
Proposition 1 (15) Theorem 1). Let H be hypothesis class with respect to some non negative and B-smooth function, E(1 y), such that for every w H, y, |[(wx y)1 s b. Then, for any 0 we have, with probability at least - 5 over sample of size n, uniformly for all h H.
b blog 8
b blog
L(h) I(h)
(I())
Blog (n)
(
+
n
n
where K < 10S is numeric constant.
3.2 Properties of Gradient Descent on Smooth Objectives
In this section we prove that GD satisfies the two desired properties- low norm and low optimization error. We begin with showing that the norm of wr, the output of GD after T iterations, is low, as stated in the following lemma,
Lemma 1. Let & be a tail function and let E E C..B. Fix any & > and point w E Rd such that [(w") & (exists due realizability). Then, the output of T-stpp GD, applied on L with stepsize 17 S 1/B initialized at w 0 has,
|| & 2||w",ll :ll 2
Now, bound the optimization error of GD every function Co.g. Gg by using variant of Lemma 13 from (12). The proof is fairly standard and appears in Appendix C
Lemma 2. Let & be a tail function and let E Co.g. Fix any & and point w e Rd such that I(w")) S &. Then, the output of -stess GD, applied on L with stepsize 1) S 1/B initialized at w = has,
Ż(wr) S ||
+ 2E.
n/T
3.3 Proof Theorem
We now turn to prove Theorem] | The proof is simple consequence of the properties proved above and Proposition We first claim that there exists model w with low norm such that [(w") s

---

which implies, through Lemmas 1 and 2 that wr of gradient descent has both low optimization error and it remains bounded within a ball small radius. Then, we use Proposition translate the low optimization error to low risk.
Proof of Theorem First, we show that there exists a model w's with low norm such that L(w") s e. Let & S 1 and & E Cæ.s. By separability, there exists unit vector w such that w" . Iz for every in the training set S. Moreover, l is monotonic decreasing. Then, for w' = (5))))) w* and every 2 S,
= ( (0- w' 2i s 1 (-)(6) y) s (1)).
((w's -2)
y
Then, by the fact that a (s) 2 O, we have ((w 21) S 10(5s(0010 (((0)())) s 5 (s)) = & for all i, hence
I(w")) i=1
c(w 2)) s e.
Now, for such that T s ( we get by Lemma
46
|| s 2|l 2
Y
For the same e, by Lemma
|| İ(WT)= S
+ 28 S 10 (E)
q/f'
Denote Bg {w ||w|| S rs). where for brevity rs = 46 (8) /y. We have, by Lemma 10 f(x) s 2 + B||x yyl? for all x, Rd (see proof in Appendix
C. Then, together with the fact that ||=|], ||'1|| s and choosing & such that & x (z)² /I, with probability
12
max (e(w 2)1 S 20(w(2)) + 4Br2 S 2$ + 4Br S wEB,
+ +fr
8n7
Moreover, B is hypothesis class of linear predictors with norm at most We know that the norm of the examples is at most 1, thus, it follows that the Rademacher complexity B R, (Bg) r vn (e.g..16 Theorem 3].
Now, by the choice of E, have Σ(wr) 3r /66TT. Thus, Proposition implies that with probability least 1 - 6, for every w Bg and any & such that & / /r
L(WT) s
3r2
+ K
\
3r2
vB log
1.5 n
Ts
b bogg
+ B
Blog
n 12 b log
16n7T
1677
n
n
n
Plugging in the bound on b, dividing by 2 and using twice the fact that xy s f + fy² for all x,
L(WT)
3
3
Volog 1.5
InT 48) log 1
Blog"
( 4B) log
+ K
16n1T
16n7
Vn
3
vB log
1.5
n
log
48 1
B log
log
4B log
16n7T
K
V 16n/
Vn
+
8nTI
+
8n''n
2
3
vB log 1.5
log 5
4B
B Blog
log 1
4B 8
16n7T
32nT
2
Vn
81/T'
n
n
817Tn
n
3
3
B Blog²
log 6
1
4/ log 0
B Blog²
log
4 log 1 n
K
167T
32nT
n
8nTn
8nTn
7K
2KB (lgg 3
4 log
K Klog 1 4nTn
< 32nT
The theorem follows by rearranging the inequality.
7

---

4 Risk Lower Bounds
In this section we present our second main result: lower bound showing that the bound we proved in Section 3 for gradient descent is essentially tight for loss functions in the class Co.B, for any given tail function & and any B Formally, we prove the following theorem.
Theorem 2. There exists constant C such that the following holds. For any tail function d, sample size n 2 35 and any T, there exist a distribution D and loss function E Co.B. such that for T Ttepps GD over sample S = {zi j=z sampled ii.dd from D, initialized at w O with stepsize S 1/2B, it holds that
(128E)) -(0--(128))
+ +C (0 (8
E[L(wT)] 2 C
y2n
for any 8 < 255 such that T 2 (0 (8))/)))
We remark that the right-hand side of the bound is well defined, as restrict & to be sufficiently small as ensure that all arguments to &-1 are at most 1 (recall that admits all values in [0, 4] due to our assumptions that <(0) 2 4). Further, the lower bound above matches the upper bound given in Theorem I up to constants, unless the tail function & decays extremely slowly, and slower than any polynomial (at this point, however, the entire bound becomes almost vacuous).
To prove Theorem 2 we consider two different regimes: the first is where T * n, when the first term in the right-hand side of the bound is dominant; and the T < regime where the second term is dominant. We begin by focusing on the first regime, and prove the following.
Lemma 3. There exists a constant C2 such that the following holds. For any tail function Φ, sample size n 2 35 and any and T, there exist a distribution D with margin y, loss function & E Co.B such that for GD over a sample S {2a)/ sampled i..d from D, initialized w1 = O with stepsize
n $ 1/2B, it holds that
B6 _6 (1286)²
E[L(wT)] 2 C
y²n
I such that Ty²T 2 (6)3/%) for any 8< < 256
To prove the lemma, we construct learning problem for which the risk of GD can be lower bounded. We design a loss function l which exhibits a decay to zero at a rate similar to that of the function & for x > O, and behaves as a quadratic function for O. The distribution D is constructed such that there are two fixed examples in its support, denoted žj and z2, that are both sampled with constant probability and are almost opposite in direction to each other: Z2 is aligned with -21 except for small component, denoted p, which is orthogonal to z1. Crucially, since and Z2 point in nearly opposite directions, minimizing optimization error requires the GD iterate to have substantial component aligned with the vector v (otherwise, the loss for z2 will be large). Finally, we define another example, denoted as Z3, that has significant component in the opposite direction -v. We arrange the distribution D so that z3 is sampled with with probability roughly 1/n. The lower bound now follows by observing that, if 23 is sampled at test time, but did not appear in the training set (this happens with probability x 1/n), the test error is quadratically large in the magnitude of the GD iterate along- -v.
We now turn to formally proving Lemma 3
Proof. Given y 1 I , let us define the following distribution D:
21 (1,0,0)
with prob. 59 (1 1);
64
D
22 = (-4.3y, 0)
with prob. 2 (1 4
23 == (0, (0.- 4y
with prob. 1
n'
and loss function:
(x(x)
x x2 0;
((x) = (()) 0' (0())x 4222 <<> O.
First, note that the distribution separable: for w' = (y, 1 it holds that w"z, = y for every i (1. Moreover, Lemma II in Appendix ensures that indeed & E Co.p.
8

---

Next, let S be sample of i.i.d. examples from D and let z' D be validation example independent
from S. Denote by 82 [0, 1] the fraction of appearances of 2g in the sample S, and by A A2 the following events;
A = fz' A Z3 $ S),
A2 = {62 E 32 $1.
In Lemma 12 (found in Appendix D). we show that
Pr(Ar 0 A2)
(5)
120en
Furthermore, in the proof of Theorem Then by Lemma 2 and the choice of E,
there exists vector w which holds ||w s (
20 (6)
((w)) s 2
4E.
(6)
y²
For the remainder of the proof, we condition on the event A₁ n A2. First, we show that wy 22 Indeed, if it were not the case, then ((WT 22) <(0); together with Eq. (6) we obtain
1
48 2 [(wr) 2 62((WT 22) 2 32 ((0).
64
which is contradiction to (0) 2 4. Moreover, wr 2 0. Again, we show this by contradiction.
Conditioned on A2, have ô1 Then, if (y(1) 0, ((T 21) (0), and
7 (00) 2
7
4s Σ(Wr) ōi((wT 21)
64
8
16"
which is contradiction. In addition, we notice that is the only possible example whose third entry non zero. Given the event A₁, we know that Z3 is not in Equivalently, for every E S, z(3) As result,
(3) = -7 Σ vL(w)) = -1
2(3))(ww=))= =0
s=l ZcS
Then, we get that,
WT 23 (2).).
(7)
8
Then, using the fact that wT- 22 2 0, ((T 22) = (wT 22), and conditioned on Az, we have
((wT z2) = (WT 222 = 32T()wr)).
which implies
WT 22 2 x 6 (wr)(
(8)
Therefore, by combining Eq. ( with the fact that (1) 2 0.
3yw7(2) wT(1)
3ywt (2)
t (32
2
which implies, (2) 2 + (32i(32 (wr)). By Eq. (7.
1
Σ3 (2 -
24y x (32ī(wr)).
We therefore see that for every such that & 2 (6)) TT.
C(WT 23) 2 2 (WT
23)2 2
B
x (32I(wT)) (wT))
2 1152y2
B
(0- (128s))
2
24y
where in the final inequality we again used Eq. of total expectation,
( We conclude the proof using Eq. and the law
E[L(WT)] E[((WT z²)] E(((wT z') An n A2] Pr(Ai A2).
(Expectations here are taken with respect to both the sample and the validation example z'.)

---

Second, we focus the second expression in the lower bound of Theorem which is dominant in the early stages optimization.
Lemma 4. There exists constant C2 such that the following holds. For any tail function 6, and for any n, T and y, there exist a distribution D with margin y, loss function & Co.B such that for GD initialized al O with stepsize 1/2B over an i.d. sample S = {zi 1n from D and w = holds
(6 (8-1))))2
E[I(WTT]] C2
y²Tn
for any $ to such that TTyT o (8)2//
The argument for proving Lemma is similar to that of Lemma Here we define I-Lipschitz loss function l that decays to zero at the same rate o, and distribution such that there is a possible example 21 which sampled with high probability and an almost "opposite" example 22, that with constant probability,, appears rarely in the training set S. The lower bound follows from the fact that although z2 appears in the dataset, the gradients of the loss function are bounded and thus not large enough to make the trained predictor classify z2 correctly. The full proof can be found in Appendix [.2]
Finally, derive Theorem 2 directly from Lemmas 3 and 4
Proof of Theorem Let C min(Ci. C2), where Ci and C2 are the constants from Lemmas (128E))² / ynn, the theorem follows from Lemmat 4
and 4 respectively. If (Φ (88))² /T2n otherwise, follows from Lemma
Acknowledgments
Funded by the European Union (ERC, OPTGEN, 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (grant number 2549/19), from the Len Blavatnik and the Blavatnik Family foundation, and from the Adelis Foundation.
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
[2] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[3] Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv: 1803.07300, 2018.
[4] Ziwei Ji and Matus Telgarsky. A refined primal-dual analysis of the implicit bias. Journal of Environmental Sciences (China) English Ed, 2019.
[5] Ziwei Ji, Miroslav Dudík, Robert E. Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2109-21366 PMLR, 09-12 Jul 2020.
[6] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008
[7] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. International Conference on Machine Learning, pages 5809-5819. PMIR, 2020.
10

---

[8] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019.
[9] Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019.
[10] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[11] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[12] Matan Schliserman and Tomer Koren. Stability implicit bias of gradient methods separable data and beyond. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, PMLR, 02-05 Jul 2022.
pages
[13] Ohad Shamir. Gradient methods never overfit on separable data. The Journal of Machine Learning Research, 2((1):847733866 2021.
[14] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2222-2878, 2018.
[15] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In
J. Lafferty, C. Williams, J. Shawe-TTaylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume Curran Associates, Inc., 2010.
[16] Matus Telgarsky. Stochastic linear optimization never overfits with quadratically- bounded losses general data. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 Proceedings of Machine Learning Research, pages 1453-5488 PMLR, 02-05 Jul 2022.


Reviews:
[{"review_id": "VDj6h2WjST", "reviewer": "Reviewer_5FbM", "summary": "This paper establishes tight upper and lower bounds on the population risk of linear models trained with gradient descent (GD) on linearly separable data. In contrast to previous work, the paper's result only requires a smoothness assumption on the loss function, and the upper bounds are adaptive to the loss function's tail decay. Surprisingly, the authors achieve this result using standard techniques, with the generalization bound of [Srebro et al., 2010] based on local Rademacher complexity playing a pivotal role.\n\n**References**\n\n[Srebro et al., 2010]: Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. *NIPS* 2010.", "questions": "- What were some important losses (either from a theoretical or practical point of view) that previous works failed to cover?\n- When does it make sense to use loss functions with slow (e.g., polynomial) tail decay? It seems that loss functions with slow tails may encourage the predictor to increase the margin of already correct answers at the cost neglecting misclassified samples.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Minimal assumptions and standard proof technique.** The only assumptions on the loss function for the population risk upper bound are convexity, monotonicity, and smoothness, which leads to a clean theorem statement. Moreover, the proof only involves standard tools; one shows upper bounds the norm of the GD iterate and the empirical risk, and combines these two using the generalization bound from Srebro et al. (2010). In addition, the authors construct a lower bound which shows that their upper bound is nearly optimal for essentially all tail decay rates of the loss function. The minimality of assumptions, tightness of upper bounds, and simplicity of proof techniques showcases the paper’s strength. ", "weaknesses": "**Motivation for studying losses with diverse tail decays?** Having a more general theorem is beneficial, especially if it can be achieved without much sophistication. Still, I am curious about the utility of the upper bound’s generality. Were there important examples of losses that previous works failed to capture? Are there examples of loss functions with polynomial tails that have been used in the context of classification?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and suggestions. We respond in length to all of your questions below; in case there are any remaining concerns, we will be glad to clarify them during the discussion period.\n\n> Re Motivation for studying losses with diverse tail decays\n\nThe relationship between properties of loss function and the generalization of gradient methods has been studied a lot recently, specifically in the setting of classification with separable data (e.g., citations [5,12] in our paper).  Our paper contributes to this line of work by demonstrating that generalization is tightly characterized by the loss function’s tail decay rate.  To support this claim,  our bounds are made very general and they capture a large variety of loss functions.\n\n> “What were some important losses (either from a theoretical or practical point of view) that previous works failed to cover?” \n\nFirst, the removal of the self-boundedness condition helps us to remove several log(T) factors in the super-exponential tail regime, compared to Schliserman and Koren (2022).  Second, we also remove their Lipschitz assumption and get a tight bound also for non-Lipschitz functions (e.g., the probit loss). \n\nBut most importantly, the main contribution of the paper is the matching lower bound that we establish for the class of smooth functions with a given tail decay rate (what we call $C_{\\phi,\\beta}$). From a theoretical perspective, there is significance in removing extraneous assumptions (self-boundedness and the Lipschitz condition) so that the upper and lower bounds end up matching not only in their rates but also in the set of assumptions they rely on.\n\n> “When does it make sense to use loss functions with slow (e.g., polynomial) tail decay?”\n\nThis is a great question - and one that did not yet receive a complete and satisfying answer, to the best of our knowledge.  One earlier work [5] did study polynomially tailed losses, and showed that the iterates of GD in this case converge to a direction with a non-trivial (but not maximal) margin, in contrast to losses with exponential tail, where there is convergence to max margin solution [14].  Our tight bounds show that this phenomenon is real, and in fact, polynomial tails are indeed strictly weaker than exponential tails as far as the generalization of GD is concerned. \n"}, {"review_id": "qmKBCdECyp", "reviewer": "Reviewer_MaTy", "summary": "This paper studies the generalization properties of gradient methods for convex, smooth and decreasing losses (e.g., logistic and polynomial losses) over linearly separable data distributions.  The contributions are 1) a generalization bound based on Rademacher complexity which does not require the self-boundedness assumption for the loss and 2) a lower bound on the test loss which nearly matches the upper-bound. Overall, the results indicate that Rademacher complexity (or algorithmic stability) analyses for data-dependent generalization of GD are rate-optimal, as the lower bounds match the upper bounds in $n,T,\\gamma$. ", "questions": "please see the section above. ", "limitations": "The paper does not have a conclusions section. It can be insightful if the authors discuss some limitations of the methodology and data assumptions. There is no potential negative societal impact associated with this work.  ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is in general well-written and clear, although few inconsistencies exist throughout the main body.\n\n The studied problem is interesting as understanding generalization of GD on separable data is foundational to machine learning. This paper takes a step in this direction by studying linear models. The paper's results imply that the commonly studied margin-based generalization bounds which usually take the form $1/(\\gamma^2 n)$ cannot be improved in $\\gamma,n$, or other parameters related to tail behavior, unless additional assumptions on data are imposed. The paper's claims are new and are also applicable to a broad class of smooth losses.\n\nThe main contribution of the paper which is the lower test loss bound for a certain class of convex loss functions involves the construction of a new data distribution which can be useful for future works. ", "weaknesses": "weaknesses and some questions:\n\n1- The derived upper-bounds are barely an improvement over known results in literature. The authors claim in abstract and also throughout the introduction that their results apply to any smooth loss function. however this is not the case, as the loss in this work must be monotonically decreasing. This excludes the commonly used square-loss whereas previous results by Lei and Ying 2020 can be applied to square loss. I also do not find the condition of self-boundedness existing in previous works limiting as it includes almost all commonly used losses that are also used in this work. Can the authors elaborate on that? \n\n2- Also regarding the training and generalization upper bounds, I am not convinced of the novelty of the approach. The technique based on Srebro et al. is rather simple and well-known. I assume the challenge is in characterizing the rademacher complexity for linearly separable data, but similar analyses have been already done even for more complex models such as neural networks, for example see the papers titled \"Feature selection and low test error in shallow low-rotation ReLU networks\" and \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks\".\n\nCan the authors please comment on the challenges in optimization and generalization analyses and highlight novel steps related to general tail behaviors?\n\n3- How do the bounds look like if $w_1\\neq 0$? Particularly, it is interesting to know how the bounds on generalization behave with respect to initialization. \n\n4- It might be helpful if a new column is added to table 2 explaining what $r_{\\phi,T}$ looks like for each loss. \n\n5- The specific data distribution used for obtaining the lower bound seems very interesting. It can be helpful for readers if the authors provide more discussion on high-level steps of the proof and the their intuition on the designed distribution. \n\n6- It seems the bound of Theorem 1 contains a $\\log ^3(n)$ factor which is missing In Table 2.\n\n7- Table 2 shows that tailes of the form $\\exp(x^{-\\alpha})$ are slightly better in test loss performance than exponential tails. Does it leads to faster convergence for misclassification test error or generally for real-world experiments?\n\n8- I think the previous works on the lower generalization bounds of SVM can be discussed here. e.g.,  \"Optimality of SVM: novel proofs and tighter bounds\" by S Hanneke, A Kontorovich.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and suggestions.  We respond in length to all of your questions below; in case there are any remaining concerns, we will be glad to clarify them during the discussion period.\n\n> 1. Re improvement over known results in literature\n\nFirst, note that monotonicity of the loss function is not a limiting condition, as any reasonable classification loss function should be monotone in its activation. This is in contrast to regression losses, like the squared loss, which are indeed not monotone (as they penalize two-sided errors).  Regarding self-boundedness, the removal of this condition helps us to remove log(T) factors for the super-exponential tail losses, compared to Schliserman and Koren (2022). Another assumption that we remove is the Lipschitz assumption, thus, we get a tight bound also for non-Lipschitz functions (e.g., the probit loss).\n \nThe removal of those two conditions is also important from a theoretical perspective. The main contribution of the paper is the matching lower bound that we establish for the class of smooth functions with a given tail decay rate (what we call  $C_{\\phi,\\beta}$), and, there is significance in removing extraneous assumptions so that the upper and lower bounds end up matching not only in their rates but also in the set of assumptions they rely on.\n\n> 2. Re novelty of the upper bounds approach\n\nThe approach we assume for our upper bound is indeed mostly simple and straightforward - we actually state and discuss this explicitly in the paper (see lines 67-77).  As we explain there, we see this as a strength since previous work in the context of classification with separable data obtained weaker results using more involved proof techniques.\n\nThat said, the main step in our approach is not in characterizing the rademacher complexity — which is indeed very much standard — but rather in showing that, for a very general class of loss functions, the GD iterates remain bounded within a ball of small (tail-decay dependent) radius around initialization, and using rademacher-based uniform convergence on that ball.  Another step is using the same radius for characterizing the convergence rate of GD on the empirical risk.\nFor both of these steps, it is not a priori clear why GD should converge quickly and generalize well despite being executed unconstrained on an unregularized objective, as is the case in our setting, and indeed, this was not the approach taken by much of the previous work in this domain.\n\nPlease see lines 67-77 in the paper discussing this proof approach.  In light of your comments, we will try to improve this discussion in our final version.  Thanks!\n\n> 3. “How do the bounds look like if $w_1 \\neq 0$?”\n\nAs we explain in the paper, our upper bound is implied by two properties of the optimization algorithm - the norm of the iterates and the optimization error.  When $w_1\\neq 0$, the norm of the iterate can be increased by at most $\\|w_1\\|$ compared the current analysis. Moreover, the optimization error can be bounded by $O(\\|w_{\\epsilon}^*-w_1\\|^2/\\gamma^2T + 2\\epsilon)$.  Combining those two bounds with Proposition 1, we can obtain a test risk bound with an additional additive term that depends on $\\|w_1\\|^2$.  \n\nWe emphasize that this method is general and our bounds can be applicable to any non regularized optimization algorithm with low iterate norm and low optimization error.\n\n> 4. “new column is added to table 2 explaining what $r_{\\phi,T}$ looks like”\n\nGood idea, thanks - we will revise the table as you suggest in the final version.\n\n> 5. “It can be helpful the authors provide more discussion on high level steps of the proof and the intuition on the designed distribution”\n\nThanks for this suggestion - we will provide in the final version a more intuitive proof sketch and more high-level explanations around the construction of our lower bound instance. \n\n> 6. “$log^3(n)$ factor is missing In Table 2”\n\nCorrect - in our tables we suppressed logarithmic factors other than $\\log(T)$ factors  (e.g., the $log(1/\\delta)$ factor is also suppressed).  We will make this clear in the revision.  Thanks.\n\n >7.  “Are tails of the form $exp⁡(x^{-\\alpha})$ better in test loss performance than exponential tails for real-world experiments?\n\nThis is a very good question - we are actually not aware of empirical studies that focused on this expected behavior.  \n\n> 8. “Previous works on the lower generalization bounds of SVM can be discussed”\n\nThanks for this suggestion!  We will look into these papers and cite them accordingly in the final version. \n\nIt is also worth noting that the primary focus of our work in on upper bounds and lower bounds for the (population) **risk** of GD, rather than its 0-1 classification error; thus, our lower bounds are inherently different in nature than lower bounds for the 0-1 error (e.g., the ones in \"Optimality of SVM: novel proofs and tighter bounds\").\n"}, {"review_id": "5H7Cqgk3FO", "reviewer": "Reviewer_GaV2", "summary": "This paper examines the problem of learning linearly separable data with margin using gradient descent (GD) and focuses on establishing a population risk bound on the GD output. Previous research in this area has primarily concentrated on understanding the implicit bias and population error associated with solving this task using logistic regression. In contrast, this study introduces a broader class of loss functions known as C_{\\pi,\\beta}, which are non-negative smooth loss functions that converge to zero more rapidly than a reference loss function, \\pi.\n\nThe main contribution of this paper is the derivation of both upper and lower bounds on the population risk of GD (including stochastic gradient descent, SGD) for this class of loss functions. The authors employ a straightforward and elegant proof technique that revolves around controlling the norm of the GD output and its empirical risk. In order to establish a population error guarantee, the authors rely on uniform convergence results specifically tailored for linear models.", "questions": "1- In Corollary 1, the authors instantiate their result for the logistic regression. It shows that when T is exponentially large in the number of samples, then we have overfitting. How does this result compare to Shamir 2021?\n\n\n2- Can the lower bound be extended to the case that it holds for every phi and “every” loss in C_{\\pi,beta}? The current statement is different. \n", "limitations": "One of the limitations is that this paper does not provide any evidence of \"implicit bias\".", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is extremely well-written and easy to follow. Also, this paper shows that bounds on the empirical error of (S)GD and the norm of the solution suffice to provide a sharp analysis of the population error. Compared to other work in this line, proofs in this work are more straightforward. Also, the population risk guarantee in this paper can be seen as an algorithmic-dependent uniform convergence which is also interesting. \n", "weaknesses": "In classification tasks, the ultimate goal is often to minimize the 0-1 loss function, which directly measures the accuracy of classification. However, when employing gradient descent (GD) optimization, it is common to use surrogate loss functions such as logistic loss or hinge loss. These surrogate loss functions approximate the 0-1 loss and are more amenable to optimization.\n\nIn this paper, all the results focus on controlling the population risk of the surrogate loss functions. It is important to note that many surrogate loss functions can provide an upper bound on the 0-1 loss function. However, for the specific case of logistic loss, there appears to be a discrepancy between the upper bound on the logistic loss presented in this paper and the upper bound on the 0-1 loss. This discrepancy suggests that overfitting may occur, and the concept of early stopping becomes relevant.\n\nSomething that I fail to understand is why the authors do not focus on providing classification error bound for C_{pi,beta}.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and suggestions.  We respond in length to all of your questions below; in case there are any remaining concerns, we will be glad to clarify them during the discussion period.\n\n> “Why the authors do not focus on providing classification error bound for $C_{\\phi,\\beta}$”\n\nAs you mentioned in your review, our primary focus in the paper is on the population risk rather than directly on the classification error, following the recent literature in this context (e.g., Schliserman and Koren (2022), and Telgarsky (2022)).  As we discuss in our introduction (and Schliserman and Koren (2022), and Telgarsky (2022) discuss more extensively), there are several reasons to study the loss/risk rather than the error directly; for example, it can lead to several interesting conclusions about the significance of early stopping.\n\nThat said, our risk upper bound for the class of losses $C_{\\phi,\\beta}$ directly implies a similar bound on the (test) classification error, for all losses in this class that also upper bound the 0-1 loss (namely, whose value at zero is one).\n\n> 1. “In Corollary 1, the authors instantiate their result for the logistic regression. It shows that when $T$ is exponentially large in the number of samples, then we have overfitting. How does this result compare to Shamir 2021?”\n\nShamir (2021) gives an upper bound for the test 0-1 error, while we prove a lower bound for the test **loss (risk)**. There is no contradiction between the two results: when running GD on the logistic loss, it is not overfitting with respect to the 0-1 error, however, it may overfit with respect to the risk. This discrepancy between the risk and the 0-1 error is actually a central aspect in our setting (see discussion in lines 83-91).\n\n> “Can the lower bound be extended to the case that it holds for every $\\phi$ and “every” loss in $C_{\\phi,\\beta}?$“\n\nThat’s a good point - the bound cannot unfortunately hold simultaneously for all losses $C_{\\phi,\\beta}$.  Note that $C_{\\phi,\\beta}$ contains all loss functions that decay to zero faster than $\\phi$, and therefore contains losses that decay strictly faster than $\\phi$, say faster than some $\\tilde\\phi \\ll \\phi$.  For such losses, we can obtain a better upper bound from Theorem 1 (the one for the class $C_{\\tilde\\phi,\\beta}$), which means that the lower bound for $C_{\\phi,\\beta}$ cannot hold for them.\n\n\nThis is often the case with lower bounds, of course: one demonstrates a hard instance of the problem within a **class of problems**, in order to conclude that stronger upper bounds for the same class of problems do not exist.\n\n> “This paper does not provide any evidence of ‘implicit bias’”\n\nIn fact, our results do point to some form of “implicit bias”: the “implicit bias” in our setting holds in the form of bias to models with a small norm.  Indeed, we show that despite working in an unregularized and unconstrained regime, the effective set of possible models GD might find is relatively small (with norm bounded by a quantity depending on the tail decay rate).  Then, we can use uniform convergence arguments on this set of possible solutions to obtain generalization bounds.\n"}, {"review_id": "6qD64e8RxQ", "reviewer": "Reviewer_GBsf", "summary": "This paper considers training a convex linear model with gradient descent on linearly separable data. The paper improves the upper bound of the population risk and proves a matching lower bound. ", "questions": "1. For the lower bound in Theorem 1, is there a way you can derive the minimum of the RHS with respect to the epsilon? \n2. In the proof of Theorem 2, you consider two different regimes where $T \\gg n$ and $n \\gg T$. How to see that in Lemma 3 and 4?\n", "limitations": "As a theory paper, I think it's fine to consider linear models. Therefore, I don't see an important limitation. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper closes the gap for training convex linear models with smooth loss functions on linearly separable data, by showing matching upper and lower risk bounds. I believe this can be an important work in this field.  Also, the paper is well-written and the logic is easy to follow. The proof is a bit heavy but the authors managed to make it accessible. ", "weaknesses": "I didn't find a major flaw in this paper. The proof looks correct to me. My only concern is that there seems to have little novelty in techniques as a theoretical work. Especially the improvement on the upper bound of the test risk relies on the results in Srebro et al. [15]. But I believe the proof of the lower bound has some nice intuition, which probably should be further explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and suggestions.  We respond in length to all of your questions below; in case there are any remaining concerns, we will be glad to clarify them during the discussion period.\n\n> Re novelty of techniques \n\nIn terms of upper bounds, we believe that simplicity is an advantage of our proof approach: get stronger (and nearly tight) upper bounds using standard techniques in optimization and online learning, that improve upon more involved proof techniques used in previous works.  We think this is significant as it puts the setting of unregularized & separable linear classification back within a general and common framework, instead of analyzing it with techniques and assumptions that are tailored to the specifics of the problem. \n\nThat said, we also emphasize that, to us, the main technical novelty of the paper is actually in its lower bound constructions, that are new to the literature on unregularized & separable linear classification.\n\n> “The proof of the lower bound has some nice intuition, which probably should be further explained”\n\nAgreed - we will work on including further explanations about the intuition for our final version.  Thanks for this suggestion!\n\n> “In theorem 1, is there a way you can derive the minimum of the RHS with respect to the epsilon?”\n\nGood question - for every tail function $\\phi$, the $\\epsilon$ which optimizes the bound is the one that satisfies the equality $(\\phi^{-1}(\\epsilon)^2)/\\gamma^2T) = \\epsilon$.  That is, the optimal $\\epsilon$ for a given specific class is specified in a general yet somewhat implicit way, but at the same time, can be easily computed in a case-by-case fashion.  In Appendix A we show how to derive the bounds that Theorem 1 implies after choosing the best $\\epsilon$ for a handful of loss classes.\n\n> “In the proof of Theorem 2, you consider two different regimes where T>>n, N>>T. How to see that in Lemma 3 and 4?”\n  \nLemmas 3 and 4 are based on two different hard instances of the problem. For the instance defined in Lemma 3, we get a lower bound of $\\phi^{-1}(128\\epsilon)^2 / \\gamma^2n$, and for the instance defined in Lemma 4, we get a lower bound of $\\phi^{-1}(8\\epsilon)^2 / \\gamma^2T$.  We only consider the relationship between $T$ and $N$ in Theorem 2, where for any regime of parameters we pick the relevant instance that establishes the lower bound (in other words, each of these lemmas is relevant for one of these regimes).\n"}]

Author rebuttal:

Meta-review: This paper considers generalization upper/lower bounds for linear classifiers trained with gradient methods under linearly separable distributions. Under minimal assumptions and general classes of loss functions, the paper establishes tight upper and lower bounds on the population risk.

The reviewers found the paper well-written and clear, and the reviews were in uniform support of acceptance. I also believe that the paper contains solid contributions. Some reviewers, though, raised concerns about the novelty of proofs, which should better be discussed in more detail in the revised manuscript. I agree with Reviewer MaTy that the paper will benefit from adding a conclusion section, discussing the limitations of this paper and future research directions. In the revised manuscript, please make sure to address other questions/issues raised in the reviews/discussions too.
Decision: Accept (spotlight)