Benign Underfitting of Stochastic Gradient Descent
Authors: Tomer Koren
Roi Livni
Yishay Mansour
Uri Sherman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Gradient Descent
Convex Optimization
Generalization Error Bounds
Algorithmic Stability

Abstract: We study to what extent may stochastic gradient descent (SGD) be understood as a ``conventional'' learning rule that achieves generalization performance by obtaining a good fit to training data. We consider the fundamental stochastic convex optimization framework, where (one pass, $\textit{without}$-replacement) SGD is classically known to minimize the population risk at rate $O(1/\sqrt n)$, and prove that, surprisingly, there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap of $\Omega(1)$. Consequently, it turns out that SGD is not algorithmically stable in $\textit{any}$ sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis). We then continue to analyze the closely related $\textit{with}$-replacement SGD, for which we show that an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate. Finally, we interpret our main results in the context of without-replacement SGD for finite-sum convex optimization problems, and derive upper and lower bounds for the multi-epoch regime that significantly improve upon previously known results.

Benign Underfitting of Stochastic Gradient Descent
Tomer Koren
Roi Livni
Blavatnik School Computer Science
Department of Electrical Engineering
Tel Aviv University and Google Research tkoren@tauex. ac
Tel Aviv University
tau. ac.il
Yishay Mansour
Uri Sherman
Blavatnik School of Computer Science Tel Aviv University and Google Research mansour. yi shay@gmail.ccoom
Blavatnik School of Computer Science
Tel Aviv University
urisherman@mail. tau ac.il
Abstract
We study to what extent may stochastic gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining good fit to training data. We consider the fundamental stochastic convex optimization framework, where (one pass, sethhout-replacementt SGD is classically known minimize the population risk rate 0(1/ and prove that, surprisingly, there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap of (2(1. Consequently, it turns out that SGD is not algorithmically stable in any sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis). We then continue to analyze the closely related with-rreplacemen SGD, for which we show that an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate. Finally, we interpret our main results in the SGD for finite-sum convex optimization problems,
context of and derive upper and lower bounds for the multi-epoch regime that significantly improve upon previously known results.
1 Introduction
Conventional wisdom in statistical learning revolves around what is traditionally known the bias-variance dilemma; the classical theory stipulates the quality of fit the training data be in trade-off with model complexity, aiming for sweet spot where training error is small but yet representative of performance on independent test data.
This perspective is reflected in the vast majority of generalization bound techniques offered by contemporary learning theory. Uniform convergence approaches [36, seek capacity control over the model function class, and employ uniform laws of large numbers to argue convergence of sample averages to their respective expectations. Algorithmic stability [9, 32] on the other hand, builds on controlling sensitivity of the learning algorithm to small changes in its input, and provides algorithm dependent bounds. Nevertheless, despite the conceptual and technical differences between these two methods, both ultimately produce risk bounds by controlling the training error, and the generalization gap. The same true many other techniques, including sample compression [17, 2], PAC-Bayes [1 8, 12], and information theoretic generalization bounds [29, 37, 24), to name few.
In recent years has become clear there are other, substantially different, ways manage the fit vs. complexity trade-off, that are in a sense incompatible with traditional generalization bound techniques. Evidently, heavily over- parameterizee deep neural networks may be trained to perfectly
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

fit training data and generalize well nonetheless [38, 25, 26], thus seemingly disobeying conventional statistical wisdom. This phenomenon has garnered significant attention, with a flurry of research works dedicated to developing new techniques that would be able to explain strong generalization performance of algorithms in this so called interpolation regime (see 6, and references therein). Notably, while these algorithms do not strike a balance between model complexity and fit to the data in the traditional sense, fundamentally, they still minimize the empirical risk as a proxy to test performance.
To summarize, in the classical and modern regimes alike, learning methods are thought of as minimizing some combination of the training error and generalization gap, with reasoning that relies in one way or another on the following trivial, yet arguably most profound, bound:
test-error < train-error + lgeneralization gap)
In this work, we focus on stochastic gradient descent (SGD) the canonical algorithm for training machine learning models nowadays and ask whether its generalization performance can be understood through similar lens. We consider the fundamental stochastic convex optimization (SCO) framework, in which it is well known that SGD minimizes the population risk at a rate of 0(1/vn) [23]. Remarkably, the classical analysis targets the population risk directly, and in contrast with other generalization arguments, at least seemingly does not rely on the above bound. This highlights an intriguing question: Are these quantities, so fundamental to learning theory, relevant to the way that SGD "works"? Put differently, is it possible to provide more "conventional" analysis of SGD that conforms with (I)?
Our main result shows that, perhaps surprisingly, there exist convex learning problems where the above bound becomes vacuous for SGD: namely, SGD minimizes the population risk, but at the same time, it does not minimize the empirical risk and thus exhibits constant generalization gap. This accords neither with the traditional viewpoint nor with that of interpolation, as both recognize the empirical risk as the principal minimization objective. We refer to this phenomenon benign underfilting: evidently, SGD underfits the training data, but its classical analysis affirms this underfitting to be benign, in the sense that test performance is never compromised as result. Our construction presents a learning problem where the output of SGD with step size over n i...d. training examples is (()) sub-optimal w.r.t. the best fit possible, and consequently has generalization gap of the same order. Notably, with the standard step size choice of 1/ Vn necessary to ensure the population risk converges at the optimal rate this lower bound amounts to constant.
Many previously plausible explanations for generalization properties of this algorithm are thereby rendered inadequate, at least in the elementary convex setup we consider here. First, it is clear that SGD cannot be framed as any reasonable regularized empirical risk minimization procedure for the simple reason that it does not minimize the empirical risk, which challenges the implicit regularization viewpoint to the generalization of SGD. Second, any attempt to explain generalization of SGD by uniform convergence over any (possibly data-dependent) hypotheses set cannot hold, simply because the sample average associated with the very same training set SGD was trained on is not necessarily close to its respective expectation. Finally, as it turns out, SGD provides for a strikingly natural example of an algorithm that generalizes well but is not stable in any sense, as the most general notion of algorithmic stability is entirely equivalent to the generalization gap [32].
We then move on to study the generalization gap and empirical risk guarantees of SGD in a broader context. We study the case of non-convex and strongly convex component functions, and present natural extensions of our basic result. addition, we analyse the variant of SGD where datapoints are sampled with-reepaacmmet from the training set, in which case the train error is of course low but perhaps surprisingly the population risk is well behaved. Finally, we make the natural connection to the study of without-replacement SGD for empirical risk minimization, and derive upper and lower bounds for the multi-epoch regime. These last two points are discussed in further detail in the following.
With vs without-replacemmnt SGD. We may view one-pass SGD as processing the data via without-replacemeen sampling from the training set, as randomly reshuffling the examples does not change their unconditional distribution. Thus, it interesting to consider the generalization gap of the closely related algorithm given by running SGD over examples sampled wil/h-replacement from the training set. Considering instability (see the supplementary for a detailed discussion) of SGD for non-smooth losses and the fact that this variant targets the empirical objective, a priori it would
2

---

seem this algorithm would overfit the training set and not provide strong population risk guarantees. Surprisingly, our analysis presented in Section reveals this not the case, and that with a certain iterate averaging scheme the population risk converges at the optimal rate. Consequently, it turns out the generalization gap is well bounded, and therefore that this variant constitutes natural learning rule that is not stable in any sense but the most general one.
vithout-replacement SGD for empirical risk minimization. construction implies lower bound of (2(="1/4) the convergence rate of single epoch of without- replacement SGD for finite sum optimization problems. In this setting, we have a set n convex losses and we wish to minimize their by running SGD over random shufflings of the losses. While the smooth case has been studied extensively (e.g.. [28, 27, 20, 31), the non-smooth case has hardly received much attention. In Section 5 we extend our basic construction lower bound for the multi-epoch regime, and complement it with nearly matching upper bounds.
The example featured in our main
Our techniques. Fundamentally, we exploit the fact that dimension independent uniform convergence does not hold in SCO [32]. This is a prerequisite to any attempt at separating train and test losses of any hypothesis vector, let alone that produced by SGD. Another essential condition is the instability of SGD for non-smooth losses, as any form of stability would immediately imply a generalization gap upper bound regardless of uniform convergence. Our main lower bound draws inspiration from constructions presented in the works of [7] and [1], both of which rely on instability, the latter also exploiting failure of uniform convergence. However, neither of these contains the main ideas necessary to provoke the optimization dynamics required in our example. A crucial ingredient in our construction consists of encoding into the SGD iterate information about previous training examples. This, combined with careful design of the loss function, gradient oracle and population distribution, allows correlating sub-gradients of independent training examples, and in turn guiding the SGD iterates to ascend the empirical risk.
1.1 Summary of main contributions
To summarize, the main contributions of the paper are as follows:
One-pass SGD in SCO. In Section 3, we study the basic SCO setup where the component losses are assumed to be individually convex, and present construction where the expected empirical risk and therefore the generalization gap are both ((Tv7)) We also provide extensions of our main construction demonstrating;
SCO with non-convex component functions may exhibit cases of benign overfitting, where E
- F(D) -
Q))")).
In SCO with A-strongly convex losses the worst case generalization gap is Q(1/A/n) for the standard step size choice.
With vs without replacement SGD in SCO. In Section 4, prove the variant of SGD where the training examples are processed via sampling with-rrplaccmeet from the training set minimizes the population risk at the optimal rate, and thus enjoys generalization gap upper bound bound of (1//pn.
Multi-epoch without-replacemenn SGD. In Section 5, we study convergence rates of without- replacement SGD for finite sum convex optimization problems. We prove a lower bound of 1/4 on the optimization error after K epochs over n convex losses, and complement with upper bounds of 01n1 1/42-1/2) and 0(n-1/4k-11/ for respectively the multi-shuffle and single-shuffle SGD variants.
1.2 Additional related work
Gradient descent, algorithmic stability and generalization. Closely related to our work is the study of stability properties of SGD. For smooth losses, [14] provide upper bounds on the generalization gap by appealing to uniform stability, yielding an ((1/V)) rate for a single epoch of n convex losses and the standard step size choice. In a later work, [7] prove tight rates for uniform stability of SGD in the setting of non-smooth losses, establishing these scale substantially worse: ((7 for step size and n training examples. Our work shows that in fact the worst rate of the generalization gap completely coincides with the uniform stability rate of SGD.
A number of works prior to ours studied the extent to which SGD can be explained by implicit regularization SCO. [16] study the setup where losses are smooth but only required to be convex in expectation, and show SGD may successfully learn when regularized ERM does not. Prior to
3

---

their work, [11] also rule out wide range of implicit regularization based explanations of SGD in the basic SCO setup with convex losses. On a more general level, our work related the study of stability and generalization in modern learning theory, pioneered by [9, 32]. In particular, the failure of (dimension independent) uniform convergence in SCO was established in [32]. The work of [13] improves the dimension dependence in the construction of [32] from exponential to linear in the number of training examples. Notably, the construction featured in our main result requires the dimension to be exponential in the sample size, however the techniques of [13] do not readily extend to our setting. Thus, the optimal dimension dependence for a generalization gap lower bound is left for future work.
Without-replacemeen SGD for empirical risk minimization. A relatively long line of work studies convergence properties of retlaettrellacement SGD from a pure optimization perspective (e.g., [28, 20, 30, 27, 19, 31). Nearly all the papers in this line of work adopt the smoothness assumption, with near optimal bounds established by [20]. An exception is the paper of [33] where an O VnK) upper bound is obtained for datapoints and K epochs, albeit only for generalized linear models over a bounded domain - notably, a setting where uniform convergence holds. Prior to this thread of research, [22] prove a convergence rate of On// VK) for non-smoote loss functions that applics for any ordering of the losses. To the best of our knowledge, this is also the state-of-the-an result for without-replacemmnt SGD in the non-smooth setting without further assumptions on the loss functions.
Benign overfitting vs. benign underfitting. While both benign underfitting and benign overfitting challenge traditional generalization techniques, that postulate the training error represent the test error, as we discuss above these two phenomena point to very different regimes of learning. In particular, [34] shows that benign overfitting requires distributional assumptions for the interpolating algorithm to succeed. In contrast, we show that benign underfitting happens for SGD in a setting where it provably learns (namely, SCO), without any distributional assumptions. We also point out that Corollary shows benign overfitting cannot happen in the setup we consider, hence the two phenomena seem to rise in different setups.
Explaining generalization interpolators. As already discussed, there is a large recent body of work dedicated to understanding why werrpparameterized models trained by SGD to zero training error generalize well [6, 8, and references therein]. In particular, the work of [5] aims at explaining the phenomenon for high dimensional linear models. Some recent papers investigate limitations of certain techniques in explaining generalization of interpolating algorithms: [21] show uniform convergence fails to explain generalization of SGD in setup where the generalization gap is in fact well bounded, thus in sharp contrast to our work; [3] rule out the possibility of large class of excess risk bounds to explain generalization of minimum norm interpolants. Unlike our work, they study properties of possible risk bounds when benign overfitting occurs, and thus do not pertain to SGD that never benignly overfits in SCO.
2 Preliminaries
We consider stochastic convex optimization (SCO) specified by a population distribution X over datapoint set Z, and loss function f: W x Z R where W c Rd is convex and compact. We denote
F(w) == Ex-2.(w;:))
(population loss)
F(w) = 1 f(w;zi),
(empirical loss)
where (z } C Z stands for the training set, which we regularly denote by S. We let w* == min F(w) denote the population minimizer, and w == mwn F(w) denote the empirical risk minimizer (ERM). The diameter of W is defined by maxx,yew (Ilx - yll where II-Il denotes the euclidean norm, and B (1) == {x E Rd ||x|| S 1) denotes the L2 unit ball in Rd. Given a training set = fZi..... 2n} 2" and learning algorithm that outputs a hypothesis Wss we define the generalization gap to be the absolute value of the expected difference between test and train losses;
EsS-z [F(ws) - F( F(ws)]
(generalization gap)

---

Throughout most of the paper, we consider one-pass projected SGD over S;
initialize at W; for 1 = :ur==2..... 2..... Wi+1 c -w (W, nge) with 81 E (wwzz)).
where (w; 2) denotes the set of sub-gradients of f(:2) - RR at the point w e W, and fl: Rd - W the projection operation onto W.
3 generalization gap lower bound for SGD
In this section, we establish our main result; that there exist convex learning problems where SGD incurs large optimization error and therefore also large generalization gap. When losses are convex these two quantities are closely related since in expectation. the empirical risk minimizer cannot significantly outperform the population minimizer (a claim that will be made rigorous shortly after our main theorem). Our construction builds on losses that are highly non-smooth, leading to SGD) taking gradient steps that actually ascend the empirical objective.
Theorem 1. Let
4, d z gonn, and W B3d Then there exists distribution over instance set Z and a 4-Lisschitz convex loss function f: W x - R such that running SGD initialized at w = O, with step size 1j 0 over S ~ 2 yields;
N,
(i) large optimization error; E F(ws) F(w3)) Ω min 7) y - l)
(ii) a large generalization gap; E F(ws)- - F(Ws) = Q min 7 1 nyत
where ws is any suffix averrage of the iterates. In particular, for n = 0(1/mm, the population risk is
E [[F(ws) - F(w = O(1/vn), while the generulization gap and training error are both Q (1).
A detailed proof of Theorem is deferred to the supplementary; in the following we provide an informal overview containing its principal ingredients.
Proof sketch. Let Z == {0, 1)d, and consider population distribution Z such that z(i) with probability We will use a loss function of the form
(w;:)) == llz O will <b(;z),,
where O denotes element-wis product. The high level idea is that the component penalizes w's that correlate with the given sample point 2, and the & function (the details of which are left for the supplementary) is tailored so that it drives the SGD iterates precisely those areas in the L2 ball where it correlates with the training set (zı...., In addition, the choice of parameters is such that the population loss is approximately zero the entire domain.
Taking d sufficiently large compared to 8-1, we ensure that w.h.p., for every round r [n]] there exist many coordinates i [d] with prefix of ones; 21 (f) ... ( 1. With 8 chosen sufficiently small compared to n, we ensure that as long as E [d] is any coordinate chosen independently of [Z++1. ... 2,), w.h.p. this coordinate will have suffix of zeros; 4,+1 (i)
(i) 0.
Our goal is make SGD take steps W1+1 x ww -e;; (where e; denotes the i'th standard basis vector) where i, E [d] is coordinate with the aforementioned property of having prefix of ones followed by a suffix of zeros. Note that since these steps are taken after the prefix of ones has ended, they will inflict large empirical loss from the norm component, but will not be "corrected" by future steps owed
to the suffix zeros. To achieve this, we design & so that it encodes the relevant information into the
SGD iterates. Specifically, & "flags" (using some extra dimensions) all coordinates i E [d] where prefix of ones has been encountered. In addition, using another max component in & we have that for all such coordinates on the iterate w,). In particular, we get that e; E 0f(w,; Then, our gradient oracle just returns a subgradient pointing towards one of these coordinates (for convenience, we use the minimal one) which we denote by i, and SGD makes the desired step.
(0((w;; for any example (as this component in the loss depends only
Notably, the coordinate i, chosen by the subgradient oracle is independent of future examples, and therefore will have a suffix of zeros w.h.p. Hence, as mentioned, this ensures no gradient signal after round will be able to correct the empirical risk ascent on i,. Concluding, have that for the final
5

---

iterate w == Wntl. we get ((1)) = -1 for all 1 E [n], therefore
F(W)
| || = vn = nyvi.
n
similar argument requiring a few more technical steps shows the same is true for any sufix average W. Noting that F(O) = O, we get that the optimization error is (nnVn). The implication for the generalization gap follows immediately with the standard step size choice of 1j = 1/Vi,, owed to SGD's population risk convergence guarantee. For an arbitrary step size, the result follows from simple computation, and the proof concluded.
The magnitude of the generalization gap featured in Theorem I stems from the large optimization error, which results in the empirical risk over-estimating the population risk by large margin. Evidently, for convex losses the converse is always false; the empirical risk will never significantly under-estimate the population risk (a fact that will turn out false when losses are only required to be convex in expectation see Section 3.1). Indeed, stability of the regularized ERM solution implies the ERM does not perform significantly better on the training set compared to the population minimizer w*
Lemma 1. Let W c Rd with diameter D, 2 any distribution over Z, and f: W x Z
R convex
and G-Lipschitz in the first argument. Then E [(w*) - F(w3)) s 4GD
Vn
Proof. Denote the regularized ERM by S arg min 1 L/= fi(w; zi) + [Iwll)) Observe,
4G2
4G2
F(w*) S EF (F(WS) +
s EF((5)
$22" D²
An
An"
where the second inequality follows from stability of the regularized ERM (see Lemma 13). Choosing 2GD/ViD we get that
- -[(((t)-((w3)
= -F(=")-E((w" -EF(w3) s
4GD Vn
as claimed.
Since the optimization error is always positive, we see that the upper bound given by Lemma implies an upper bound on the difference between the population and empirical risks.
Corollary 1. For any distribution % over Z and Lipschitz loss function f: W x Z - R convex in the first argument, running SGD with step size == 1/vnn guarantees E F(ws) F F(ws) S ((11/m).
Proof. We have,
F(W(Ws) F(ws)] E [F(ws) F(w*)] + +E(F(w*) F(ws)]
The population error term the RHS is (1/ vn) by the classical analysis of SGD, The second term is bounded by Lemma 1;
E|
z E ((w - F(w3)) s 4GD/
and the result follows.
In the subsections that follow we continue study the generalization gap in the context of common variants to the hasic SCO setup.
3.1 SCO with non-convex components
When we relax the convexity assumption and only require the losses to be convex in expectation, we can construct learning problem where SGD exhibits case of benign overfitting. In contrast to Theorem 1, here we actually drive the SGD iterates towards an ERM solution, thus achieving a low optimization error and empirical risk that under-estimates the population risk.
Theorem 2. Let n E N, 2 4, d 2 2 W = Bdd (1), and S 1/vπ. Then there exists distribution Z over and 4-iischhitz loss f: W Z where E zw:z) is convex in w, such that for any suffix average w of SGD initialized at O, with step size n
(x:z((w;z)
E [(Ww)) F(ws) 2)

---

The construction and proof of Theorem 2 given in the supplementary follow methodology similar to that of Theorem 1. Here however, we exploit non convex losses to form an empirical loss landscape where the FRM solution significantly outperforms the population minimizer w* (notably, a feat not possible when losses are individually convex, by Corollary 1). Our loss function is deñnedd by 2(w;2)= = E (()) (b(; z), with each component playing a similar role as before. We work with the distribution z {0. 1]" where z(O) = 1 w.p. 6, z(i) = -1 w.p. 6, and z(1) = 0 w.p. 1 26. The intuition is that coordinates accumulating many - -I's offer regions in the L.2 ball where the empirical risk is "too good"' compared to the population risk. We tailor the extra dimensions and Φ in coordination with the 1 values so that the sub-gradients guide the SGD iterates towards these regions, in exactly the same manner the construction of Theorem drives the iterates to high loss regions. We note that while the statement of Theorem is specialized to step size smaller than 1/v7. it may be extended to any step size using arguments similar to those given in the proof of Theorem 1.
3.2 SCO with strongly convex components
Our basic construction extends to the strongly convex case by making only technical modification to Theorem 1. The theorem below concerns the standard step size choice for strongly convex objectives. We provide its proof in the supplementary.
Theorem 3. Let n E N. n Z 10, d 24nlogn, W =Ba (1), and A 1/vn. Then there exists distribution over instance set Z and a 4- 4-Lipschitz, A-strongly convex loss function f: W x Z - R
(i) the optimization error is large: Es-2" [((ss) F(w3)) = Avn
(ii) the generalization gap is large; Es-z" [(Ws)) F [ = AvA
where Ws is any suffix average of SGD initialized at = 0, with step size schedule du = 1/At. Furthermore, the problem instance where this occurs is precisely the A regularized version of the example featured in Theorem 1.
We note that an immediate implication of the above theorem is that if we seek a generalization gap upper bound for a weakly convex problem by means of regularization (meaning, by running SGD on regularized problem), we would have to take this, note that the generalization gap (of any hypothesis) of the regularized problem is the same as that of the original. On the other hand, taking 1 2 I will of course be detrimental to the population error guarantee. Hence, one cannot circumvent the generalization gap lower bound by regularization without compromising the population error.
guarantee gap of (() To see
We conclude this section with note regarding stability rates of SGD in non-smooth SCO. Implicit in Theorem 1, is that average stability of SGD coincides with the tight uniform stability rate of (nvv)) established by [7]. This is because Theorem provides the 2(nym) lower bound on the most general stability notion, which is precisely the generalization gap [32]. We refer the reader to the supplementary for more elaborate discussion.
4 SGD with vs without replacement
In this section, we consider different algorithm in the context of the basic SCO setup; SGD over examples drawn with-replacement from the training set. This is not to be confused with one-pass SGD discussed in Section 3, which corresponds to without-replacemeett SGD on the training set, or alternatively with-replacement SGD over the population distribution. Given a training set S = {ZI..... 2n} Z", we define with-replacement projected SGD initialized W E W by
Wr+1 Nw (w, ng,) where & E a and 2, Unif(S).
Perhaps surprisingly, this version of SGD does not overfit the training data; our theorem below establishes that with proper iterate averaging, the population risk converges at the optimal rate.
Theorem 4. Let W c Rd with diameter D, % be any distribution over Z, and f W x Z - R be convex and G- G-ipssciitz in the first argument. Let S ~ 2" be a training set of datapoints drawn from 2, and consider running SGD over training examples sampled with--relaacmmet, uniformly and independently from S. Then, for step size 1) G upper bound holds;
D and n+1 Σn=1 n-itl n W,, the following
10GD
EE F(W) F(w*)] s
Vn
7

---

Proof. Fix a time-step r E [n], and observe that if we don't condition on S, we may view the random datapoint 2, as mixture between a fresh i...d sample from the population and uniformly distributed sample from the previously processed datapoints S = (ž). .EI.....2.-11. 1
|2~ 2
w.p. f-1
1 = 12 Un
w.p. 1-1 "
With this in mind, denote ((w) f(:: (w) fix S and observe:
Ez [((w;) - [(('') 8
Ez-z ((w":)))(w==z)))
n
f((w)) - -f((tt).
E=1
Rearranging and taking expectation with respect to S we obtain
f(w===)) (1 1- -
= E (w(,) [/()*)/
+
f((w*) - F((wz)
1=1
4GDVI
s E (((w))-f(ww)) f/(
n
where the inequality follows from Lemma
Now, by direct computation we have Σi- (1 -1-
1
n+1 which motivates setting w == 2 Σ n-1+1 w, By convexity of F, Eq. (2), and the standard
2
n+1
regret analysis of gradient descent le.g.. . 15] we have
[F(w) F(#*))
2
Σ
E [F(w,) - F(w*)]
n
2
[(((ww))Fr(w)
- -r((ot)
2
n 4GDVF
n
+
n
n
$ - E
Σ f((w)) -b(w+t)
n
8GD
8
Vii
2 D
nTG
8GD
2m
2
Vn
10GD
Vn
D where the last inequality follows by our choice of 17 = G
Evidently, the averaging scheme dictated by Theorem 4 does little to hurt the empirical risk convergence guarantee, which follows from the standard analysis with little modifications (for completeness we provide formal statement and proof in the supplementary). Combined with Lemma 1, this immediately implies generalization gap upper bound for with-replacement SGD. Notably, this shows with-replacement SGD provides for an example of (natural) algorithm in the SCO learning setup that is not even stable on-average, but nonetheless has a well bounded generalization gap. We refer the reader to the discussion the supplementary for more details.
Corollary 2. For any distribution % and loss function f W x Z - R convex and Lipschitz in the first argument, running SGD with step size and averaging as specified in Theorem ensures
[E[F(W) F(w)]] O(1/mn)
Proof. We have; [[[(W) F(w)] = |E F( [( -P F(w3))l (F -(w))
The first term is upper bounded by convergence of the population risk provided by Theorem 4, the second by Lemma 1, and the third by the standard analysis of SGD (see the supplementary). O
8

---

5 Multi-epoch SGD for empirical risk minimization
In this section, we forgo the existence of a population distribution and discuss convergence properties of without-replacementt SGD (wor-SGD) for finite sum optimization problems. A relatively long line work discussed in the introduction studies this problem in the smooth case. The work of [20] noted smoothness is a necessary assumption to obtain rates that are strictly better than the ( (1/Vn)) guaranteed by rith-replacement SGD for losses and K epochs, due to lower bound that follows from the deterministic case (c.g., [10]). Here we establish that smoothness is in fact necessary to obtain rates that not strictly worse than with-replacement SGID. We consider running multiple passes of wor-SGD to solve the finite sum optimization problem given by the objective
F(w)= = f(w:))
(3)
1=1
where (f(w:))); |,- is set of n convex, G-Lipschitz losses defined over convex and compact domain W R Throughout this section we let w* == min,ew F(w) denote the minimizer of the objective Eq. (3). In every epoch k E [K] we process the losses the order specified by a permutation Ne [n]] [n]] sampled uniformly random, either once in the beginning of the algorithm (single-shuffle) or at the onset of every epoch (multi-shuffle). Multi-epoch wor-SGD initialized w W is specified by the following equations;
w (w ng/), where o O.f (w
wh+ w
where we denote f (w) == f(w; A near-immediate implication of Theorem is that there cxists a set of convex losses on which a single epoch of wor-SGD cannot converge at a rate faster than 1/n2/4, Theorem presented below extends our basic construction from Theorem accommodate multiple epochs. The main challenge here is in devising a mechanism that will allow fresh bad gradient steps to take place on every new epoch.
Theorem 5. Let n, K E N, 2 4, 2 c 4/ 1), d 2 26n log(enk), and w 3 (1) where d' = (nK l)d. Then there exists a set of n convex, 4-pischhitz losses such that after K epochs of either sulti-shuffle or single-shufft SGD initialized at w = 0 with step size S 1/V2nK, it holds that
E[F(W) - F(w") = min 1, 1. ] nnk + +n)).
where W is any suffix average of the last J epochs. In particular, we obtain bound of Q (n-1/4 3-3/4) for any suffix average and any choice of 17-
The proof of Theorem 5 is provided in the supplementary. The construction in the proof takes the idea that the training set can be encoded the SGD iterate to the extreme. The loss function and gradient oracle are designed in such way so as to record the training examples in their full form and order into the iterate. We then exploit this encoded information with an "adversarial" gradient oracle that returns the bad sub-gradients on each gradient step in every new epoch.
Next, we complement Theorem 5 with an upper bound that builds on stability arguments similar to those of the smooth case [20]. Importantly though, lack of smoothness means worse stability rates and necessitates extra care in the technical arguments. Below, we prove the multi-shuffle case, and defer the full details for the single-shuffle case to the supplementary.
Theorem Let S (f: be a set of convex, G- G-Lipschitz losses over a convex and compact domain S Rd of diameter D, and consider running K 2 epochs of wor-SG over S. Then, we have the following guarantees:
(i) For multi- shuffie with step-size n D/(GG K 1/2 we have
3GD
E F[F(W)F((*)) - F(w*)] n 1//221/2
(ii) For single-shuffle, with step-size 1) D/(2 3/33// and assuming K n, we have
10GD
E F F(w*)] 11/4

---

In both of the above bounds, w = nk [eeK w and the expectation is over the random permutations of losses.
Proof (multi-shuffe case). Observe;
F(W) F(w*) s
F(w,) - F(w*)
nK
k=
E=1
F(W?) -f²
nK
k=
K
F(w/) - (W(
n (w²) - (w²)
nk
nk
k=
1=1
R=1
r=1
D²
F(w?) - ff/ (w()) 2nnK 2
+
nk
k=1 1=1
with the last inequality following from the standard nk round regret bound for gradient descent [see e.g., 15]. To bound the other term, using Lemma 10, we relate the difference between the withoutt loss distribution and the full batch objective the uniform stability rate of SGD, which may then be bounded by applying Lemma 11:
E [(F(w))- (w,))
E ETI. [F(wF) - (w/)) wfl
S Ex
[Ge (I - 1)]
Ge (1 - 1) s 2nG Vi.
Concluding, we have that
1
K
2nnK + nG2
122
E(F())
[(( - f (w{)]]
nk
2
k= 1=1
2
132
nG
Vi+
nk
2nn
2
k=1
D)2 +
n2
$ 2
Vn+
2nnK
2
3GD
n 1/44 11/22
where the last inequality follows from our choice of n DK(G))
Acknowledgements and funding disclosure
This work was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grants number 993/17, 2549/19, 2188/20), by the Len Blavatnik and the Blavatnik Family foundation, by the Yandex Initiative in Machine Learning at Tel Aviv University, by grant from the Tel Aviv University Center for AI and Data Science (TAD), and by an unrestricted gift from Google. Any opinions, findings, and conclusions recommendations expressed in this work those of the author(s) and do not necessarily reflect the views of Google.
References
[1] I. Amir, T. Koren, and R. Livni. SGD generalizes better than GD (and regularization doesn't help). In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 63-92. PMLR, 2021.
10

---

[2] S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018.
[3] L. Bartlett and M. Long. Failures of model-dependent generalization bounds for least-norm interpolation. Journal of Machine Learning Research, 22((04):1-15, 2021.
[4] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Reseurch, 3(N0)))443344422 2002.
[5] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49)330063-30077 2020.
[6] L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: a statistical viewpoint. arXiv preprint arXiv:2103.0911 2021.
[7] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
[8] M. Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. arXiv preprint arXiv:2105. 143668, 2021.
[9] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[10] Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4)2231-35 2015.
[11] A. Dauber, M. Feder, Koren, and Livni. Can implicit bias explain generalization? stochastic convex optimization as a case study. Advances in Neural Information Processing Systems, 33, 2020.
[12] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Thirty-Third Conference on Uncertainty in Artificial Intelligence, UA/ 2017, 2018.
[13] V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances in Neural Information Processing Systems, volume 29, 2016.
[14] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR, 2016.
[15] E. Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1909.0520 2019. 2019.
[16] S. Kale, A. Sekhari, and K. Sridharan. Sgd: The role of implicit regularization, batch-size and multiple-epochs. arXiv preprint arXiv:2107.05074, 2021.
[17] N. Littlestone and M. Warmuth. Relating data compression and learnability, 1986.
[18] D. A. McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 170, 1999.
[19] K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
[20] D. Nagaraj, Jain, and Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703 4711. PMLR, 2019.
[21] V. Nagarajan and J. 7. Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[22] A. Nedić and D. Bertsekas. Convergence rate of incremental subgradient algorithms. In Stochastic optimization: algorithmss and applications, pages 223-264. Springer, 2001.

---

[23] A. S. Nemirovskij and D, B. Yudin. Problem complexity and method efficiency in optimization, 1983.
[24] G. Neu. Informitionn-hherrtiic generalization bounds for stochastic gradient descent. arXiv preprint arXfv:2122.0033/ 2021. 2021.
[25] B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6644,,,614, 2014.
[26] B. Neyshabur, Z. L., Bhojanapalli, Y. LeCun, and N. Srebro. The role of over- avee-paramttiizaioonn in generalization of neural networks. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[27] S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020.
[28] B. Recht and C. Ré. Toward a noncommutative arithmetic-geometiic mean inequality: conjec- tures, case-studies, and consequences. In Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2012.
[29] D. Russo and J. Zou. Controlling bias adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1240. PMLR, 2016.
[30] I. Safran and O. Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[31] I. Safran and O. Shamir. Random shuffling beats sgd only after many epochs on ill-conditioned problems. arXiv preprint arXiv:2106. 06880, 2021.
[32] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 1 11:2635 1-2635-2670, 2010.
[33] O. Shamir. Without-replacemmnt sampling for stochastic gradient methods. Advances in neural information processing systems, 29:46-54, 2016.
[34] O. Shamir. The implicit bias of benign overfitting. arXiv preprint arXiv: 11489 2022.
[35] U. Sherman, T. Koren, and Y. Mansour. Optimal rates for random order online optimization. Advances in Neural Information Processing Systems, 34, 2021.
[36] V. Vapnik. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264 281, 1971.
[37] A. Xu and M. Raginsky. Information thheoretcc analysis of generalization capability of learning algorithms. In Proceedings of the 31st International Conference Neural Information Processing Systems, pages 2521-2530, 2017.
[38] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL.)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qopLudnhclc", "reviewer": "Reviewer_1m1F", "summary": "The authors study SGD, with and without replacement, and construct counterexamples for which SGD fails to converge despite the objective being otherwise well-behaved (e.g. convex and smooth).", "questions": "None", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This appears to be a significant work but is inappropriate for the NeurIPS community because it is too theoretical. The dataset Z and the objective function (bottom pg. 5) are simple but it is unclear how this result relates to real-world machine learning problems. This is evidenced by the lack of experiments in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jGkqBJ2J3wi", "reviewer": "Reviewer_56De", "summary": "This paper studies the empirical risk and population risk (together with generalization) for different variants of SGD in the context of stochastic convex optimization (they also extend the analysis to other settings, i.e., convex in expectation, strongly convex). Their main contribution is to construct an example that (one-pass) SGD exhibits both empirical risk and generalization gap of $\\Omega(1)$. Moreover, they show that this phenomenon does not exist if we use with-replacement SGD. Last, they derive upper and lower bounds for without-replacement SGD in the multi-epoch regime.", "questions": "Please see the weaknesses part.", "limitations": "Please see the weaknesses part.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n* This paper studies the behavior of SGD in SCO, providing new intuition of the analysis of test error (population risk). By their construction, even in the convex optimization, there exists an instance that provably minimizes population risk, while the empirical risk is of constant level, resulting in a constant generalization gap. This observation questions the rational optimization-generalization decomposition framework (or ERM framework). The main reason, is that SGD does not minimize the empirical loss, which differs a lot in the smooth setting. In a word, this observation might lead to a new type of analysis of statistical learning, which can have a broad impact on the community.\n* The other observations, together with their proof techniques are also interesting. For example, the comparison between with and without replacement might provide some intuition on the advantage of multi-pass SGD in terms of its implicit regularization.\n* The paper is well-structured and provides good intuition for the proof technique.\n**Weakness:**\n* The construction of the failure seems artificial and might not be general enough. They rely on a special structure that (to my best knowledge) no realistic learning problem has a similar structure. It would be great if the author can provide some connection between their constructed example and some realistic examples.\n* The analysis relies on the averaged solution instead of the last iteration solution, which prevents the general impact of this work. It would be great if the author can at least comment on or conjecture the result for the last iteration case.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OA8ycknaZwB", "reviewer": "Reviewer_6Rm5", "summary": "The paper shows, by considering the stochastic convex optimization framework, that there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap of $\\Omega(1)$ (in the without replacement case). SGD is therefore not algorithmically stable. This phenomenon does not occur for SGD with replacement.", "questions": "- discussions and conclusions are not present\n\nMinors:\n- l338: forgo", "limitations": "Limitations and potential negative societal impact of this work may be discussed more", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the phenomenon reported in the paper is novel, intriguing and potentially impactful in the context of SGD generalization bounds\n- analytical evidence is solid\n- the multi-epoch regime is addressed\n\nWeaknesses:\n- nor discussions nor conclusions are present", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GxIqO9kc4W1", "reviewer": "Reviewer_6KpT", "summary": "The authors provide a stochastic convex optimisation framework in which one passe SGD (classically) minimises the population risk at a $O(1 / \\sqrt{n})$ rate but however exhibits a $\\Omega(1)$ training error and generalisation error.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written. Each result is clear, introduced and commented. The analysis is rigorous and non trivial. Overall I have no criticism concerning the technical results, which I believe are original. However the main results in section 3 seem anedoctal in the sense that (1) nobody does one pass SGD (2) the considered setting is very peculiar and clearly not encountered on a daily basis: cherry picked distribution and loss, $d \\geq 2^{n \\log n}$.  This on its own would not bother me (as mentioned, I find the results original and interesting), however my main concern are the conclusions / interpretations which are drawn from the results.  Overall I find that the introduction is very misleading, here are several claims in it which I believe are misleading / false:\n\n- *\"First, it is clear that SGD cannot be framed as any reasonable regularized empirical risk minimization procedure for the simple reason that it does not minimize the empirical risk, **which challenges the implicit regularization viewpoint to the generalization of SGD**\"*: the implicit regularization viewpoint is crucial in the interpolation setting (setting which is met in practice). Hence I cannot agree with your statement: it does not challenge the viewpoint as you consider a totally different setting.\n\n- *\"Second, any attempt to explain generalization of SGD by uniform convergence over any (possibly data-dependent) hypotheses set cannot hold, simply because the sample average associated with the very same training set SGD was trained on is not necessarily close to its respective expectation\"*:  (1) your result holds only for one pass SGD (which nobody does in practice), hence one could expect the classical train / generalisation gap to hold for multiple passes \n\n- in the abstract: *\"Consequently, it turns out that SGD is not algorithmically stable in any sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis)\"*: again this only holds for one pass SGD which is never considered in practice. \n\n\nMinor comments: \n- in the population risk convergence, it would have been clearer to put the exact convergence bound instead of a big $O( )$ so that it is clear that there is no hidden dependence in the dimension $d$ which would have killed the rate. \n- a conclusion would have been appreciated \n- line 183: $w^*_S = \\arg \\min _w \\hat{F}(w)$: why is the argmin unique ? if not unique which one do you choose ? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept