A Guide Through the Zoo of Biased SGD
Authors: Yury Demidovich
Grigory Malinovsky
Igor Sokolov
Peter Richtárik
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic optimization
biased SGD
Non-convex analysis
TL;DR: We provide theoretical connections between different sets of assumptions and generalize the analysis of biased SGD

Abstract: Stochastic Gradient Descent (SGD) is arguably the most important single algorithm in modern machine learning. Although SGD with unbiased gradient estimators has been studied extensively over at least half a century, SGD variants relying on biased estimators are rare. Nevertheless, there has been an increased interest in this topic in recent years. However, existing literature on SGD with biased estimators lacks coherence since each new paper relies on a different set of assumptions, without any clear understanding of how they are connected, which may lead to confusion. We address this gap by establishing connections among the existing assumptions, and presenting a comprehensive map of the underlying relationships. Additionally, we introduce a new set of assumptions that is provably weaker than all previous assumptions, and use it to present a thorough analysis of BiasedSGD in both convex and non-convex settings, offering advantages over previous results. We also provide examples where biased estimators outperform their unbiased counterparts or where unbiased versions are simply not available. Finally, we demonstrate the effectiveness of our framework through experimental results that validate our theoretical findings.

A Guide Through the Zoo of Biased SGD
Yury Demidovich Initiative, KAUST
Grigory Malinovsky Initiative, KAUST
yury semmidovch@@kuss. edu. edu.sa
grigorii iaggorii.malee www.mmwwwwiiiiiimmmmmmmmm i @kaust aedu.sa.
Igor Sokolov
Peter Richtárik
Al Initiative, KAUST
AI Initiative, KAUST
igor.sokolov. 10kaust. edu.
peter peter Anter.richtarik@kaue edw. edu.
Abstract
Stochastic Gradient Descent (SGD) is arguably the most important single algorithm in modern machine learning. Although SGD with unbiased gradient estimators has been studied extensively over least half century, SGD variants relying on biased estimators are rare. Nevertheless, there has been an increased interest in this topic in recent years. However, existing literature SGD with biased estimators (BiasedSGD) lacks coherence since each new paper relies on different set of assumptions, without any clear understanding of how they are connected, which may lead to confusion. We address this gap by establishing connections among the existing assumptions, and presenting a comprehensive map of the underlying relationships. Additionally, we introduce new set of assumptions that is provably present thorough analysis
weaker than all previous assumptions, and of BiasedSGD in both convex and non-convex settings, offering advantages over previous results. We also provide examples where biased estimators outperform their unbiased counterparts or where unbiased versions are simply not available. Finally, demonstrate the effectiveness of framework through experimental results that validate our theoretical findings.
Introduction
Stochastic Gradient Descent (SGD) [Robbins and Monro 1951 is a widely used and effective algorithm for training various models in machine learning. The current state-of ootiie-of-hhaaatt -tt-the-rt methods for training deep learning models are all variants of SGD [Goodfellow et al., 2016 Sun 2020). The algorithm has been extensively studied in recent theoretical works [Bottou al.) 2018 Gower et al.)
2019 Khaled Khaled and Richtárik] 2023). In practice and theory, SGD with unhiased gradient oracles mostly used. However, there has been recent surge of interest in SGD with biased gradient oracles, which has been studied in several papers and applied in different domains.
In distributed parallel optimization where data is partitioned across multiple nodes, communication can be bottleneck, and techniques such structured sparsity [Alistarh et al. 22018: Wangni et al. 2018) or asynchronous updates [Niu et al. 2011] are involved to reduce communication costs. Nonetheless, sparsified or delayed SGD-updates are not unbiased anymore and require additional analysis [Stch and Karimireddy 2020: Beznosikov et al. 2020
Zeroth-order methods often utilized when there is access to unbiased gradients, e.g., for optimization of black-box functions [Nesterov and Spokoiny| 2017). or for finding adversarial examples in deep learning (Moosavi-Dezfooli et al.[[011][Chen et al. 2017 Many zeroth-order training methods exploit biased gradient oracles [Nesterov and Spokoiny| [2017] Liu et al.) 2018
Bergou et 2020 Boucherouite al. 2022] Various other techniques smoothing, proximate
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

updates and preconditioning operate with inexact gradient estimators d Aspremont 2008 Schmidt
al. 2011 Devolder al., 2014 Tappenden et al. 2016 Karimireddy al. 2018
The aforementioned applications illustrate that SGD can converge even if it performs biased gradient updates, provided that certain "regularity" conditions are satisfied by the corresponding gradient estimators [Bottou et al., [2018] Ajallocian and Stich 2020) Beznosikov et al. 2020; Condat et al. 2022]. Moreover, biased estimators may show better performance over their unbiased equivalents in certain settings [Beznosikov et al. 2020].
In this work we study convergence properties and worst-case complexity bounds of stochastic gradient descent (SGD) with a biased gradient estimator (BiasedSGD; see Algorithm| for solving general optimization problems of the form
min f(x);
#ER4
where the function f : Rd + R is possibly nonconvex, satisfies several smoothness and regularity conditions.
Assumption 0 Function J is differentiable, L-smooth (i... (v) V [wwil] s L | ull for all I, E ). and bounded from below by f E IR.
We write g(æ) for the gradient estimator, which is biased (i.e., E [g(2)] is not equal to V f(r),, E|] stands for the expectation with respect to the randomness of the algorithm), in general. By gradient estimator we mean a (possibly random) mapping Rdd - IR with some constraints. We denote by y an appropriately chosen learning rate, and x. E Rd is starting point of the algorithm.
Algorithm 1 Biased Stochastic Gradient Descent (BlasedSGD)
Input: initial point x E IRd; learning rate yy > 0 for 0, 2......o. do
2: Construct a (possibly biased) estimator g¹ del g(x") of the gradient fz(x"
3: Compute x²+1 x' - 79
4:
end for
In the strongly convex case, has unique global minimizer which denote by x=, and f(x*)= ft. In the nonconvex case, f can have many local minima and/or saddle points. is theoretically intractable to solve this problem to global optimality [Nemirovsky and Yudin 1983]. Depending on the assumptions on f, and given some error tolerance & >00. will seek to find random vector x E TR such that of the following inequalities holds: i) [f(x)) - f") (convergence in function
values); ii) EE |ar - x= 1=1 < 8 1| x²1 norm convergence).
(iterate convergence); iii) E [[V[(()) < g² (gradient
Sources of bias
Practical applications of SGD typically involve the training of supervised machine learning models via empirical risk minimization (Shalev-Shwartz and Ben-Davin 2014), which leads to optimization problems of finite-sum structure:
((x) 1 Σ M(x)..
In the single-machine setup, n is the number of data points, f(()) represents the loss of model on a data point i. In this setting, data access is expensive, g(x) is usually constructed with subsampling techniques such as minibatching and importance sampling. Generally, subset S S [n] of examples is chosen, and subsequently g(z) is assembled from the information stored in the gradients of V (z)
for E only. This leads to estimators of the form g(x) Exes 0; V f. (x), where v; are random variables typically designed to ensure the unbiasedness [Gower et al. 2019] In practice, points might be sampled with unknown probabilities. In this scenario, a reasonable strategy to estimate the gradient is to take an average of all sampled fi, In general, the estimator obtained is biased, and

---

ABS
Asm
Thm
Thm 0
BND
Biased AHC Asm
Thm 2
Asm 6
Thm Xx
Thm 11
Thm
BVD
Thm
Thm viti
Thm 2
Asm
Thm
Thm
CON
BREQ Asm
SG
FSML
Asm
Thm
Thm 2
Asm
Thm Vii
Asm
v Thn
SG2
Asm 2
Figure 1: Assumption hierarchy. A single arrow indicates implication and an absence of reverse implication. The implications are transitive. dashed line indicates mutual abscence of implications. Our newly proposed assumption Biased ABC the most general one.
such sources of bias can be characterized as arising from lack of information about the subsampling strategy.
In the distributed setting, n represemts the number of machines, and each Ss represents the loss of model z on all the training data stored machine i. Since communication is typically very expensive, modern gradient-type methods rely on various gradient compression mechanisms that are usually randomized. Given appropriately chosen compression map C R Rd the local gradients (z(()) are first compressed C, (Vf(z)), where C, an independent realization of C' sampled by machine i in each iteration, and subsequently communicated to the master node, which performs aggregation (typically averaging). This gives rise to SGD with the gradient estimator the form
1 Σ C. (VA(())
g(x)
Many important compressors performing well in practice are of biased nature (e.g., Top-k, see Def. which, in general, makes g(x) biased as well.
Biased estimators are capable of absorbing useful information in certain settings, e.g., in the het- erogeneous data regime. Unbiased estimators have to be random, otherwise they are equal to the identity mapping. However, greedy deterministic gradient estimators such as Top-k often lead to better practical performance. In [Beznosikov al., 2020, Section 4] the authors show an advantage of the Top-k compressor over its randomized counterpart Rand-k when the coordinates of the vector that we wish compress are distributed uniformly or exponentially. In practice, deterministic biased compressors are widely used for low precision training, and exhibit great performance Alistarh et al. 2018 Beznosikov al. 2020).
3 Contributions
The most commonly used assumptions for analyzing SGD with biased estimators take the form of various structured bounds on the first and the second moments of g(x). We argue that assumptions proposed in the literature often too strong, and may be unrealistic they do not fully capture how
3

---

bias and randomness in g(z) arise in practice. In order to retrieve meaningful theoretical insights into the operation of BiasedSGD, it is important model the bias and randomness both correctly, so that the assumptions we impart are provably satisfied, and accurately, so to obtain as tight bounds as possible. Our work is motivated by the need of more accurate and informative analysis of BiasedSGD in the strongly convex and nonconvex settings, which are problems of key importance in optimization research and deep learning. Our results are generic and cover both subsampling and compression based estimators, among others.
The key contributions of our work are:
Inspired by recent developments in the analysis of SGD in the nonconvex setting [Khaled and
Richtárik 2023 the analysis of BiasedSGD [Bottou al.) 2018 Ajallocian and Stich [202]] the
analysis of biased compressors [Beznosikov et al. 2020 we propose a new assumption, which we
call Biased ABC. for modeling the first and the second moments of the stochastic gradient.
We show in Section 5.2
that [iased ABC is the weakest, and hence the most general, among all
assumptions in the existing literature BiasedSGD we are aware of (see Figure []. including concepts
such as Contractive (CON)
[Cordonnier] 2018 Stich et al. 2018 Beznosikov et al. 2020]. Absolute
(BSS)
[Sahu et al., 2021].
Bias- Variance Decomposition (BDD [Condat et al. 2022] Bounded
Relative Error Quantization (BREQ) [Khirirat et al. 2018b]. Bias-Noise Decomposition (BND)
Ajalloeian and Stich [020]. Strong Growth I (SG1) and Strong Growth 2 (SG2) [Beznosikov et al.
2020]. and First and Second Moment Limits (FSML) Bottou et al., 2018 estimators.
We prove that unlike the existing assumptions, which implicitly assume that the bias comes from either perturbation or compression, Biased ABC also holds settings such as subsampling.
We recover the optimal rates for general smooth nonconvex problems and for problems under the PL condition in the unbiased case and prove that these rates are also optimal in the biased case.
the strongly convex case, we establish similar convergence result in terms of iterate norms as in (Hu et al. 2021a however, under milder assumptions and not only for the classical version of SGD. Our proof strategy is very different and much simpler.
Existing models of biased gradient estimators
Since application of gradient compressor to the gradient constitutes a gradient estimator, below we often reformulate known assumptions and results obtained for biased compressors in the more general form of biased gradient estimators, [Beznosikov et al.) [2020] analyze SGD under the assumption that f is p-strongly convex, and propose three different assumptions for compressors.
Assumption (Strong Growth 1, SG1 -Beznsskoo al. (0020) Let us say that g(x) belongs to a set I (a, 3) of biased gradient estimators, if. for some a, 3 0, for every IRd, g(()) satisfies
[[V[(=)] s [11(w))]]] s ((E[((()) Vz(x)).
Assumption (Strong Growth 2, SG2 Beznosikov et al. (2020) Let us say that g(x) belongs to a set IB2 (T, 3) of biased gradient extimators, if. for some T, for every x E Rdd, g(x) satisfies
1 3 [[o(=)]P]]] (EIg())), V
max [(
(4)
Note that each of Assumptions
1 and imply
E
[1(x)))]] S [V/()))
(5)
Assumption (Contractive, CON Beznosikov et al. [2020] Let us say that g(z) belongs to a set (6) of biased gradient estimators, for some 0r every x E Idd g(x) satisfies
[[o(2)) - ((x)) < ( (1- |vf())]
(6)

---

The last condition is an abstraction of the contractive compression property (see Appendix al. [022] introduce another assumption for biased compressors, influenced by bias-variance decomposition equation for the second moment:
D Condat
[[((x) - (=)))) [[(o(()] V/(=)) + E [19(z)) - [bo())]1
(7)
Let us write the assumption itself.
Assumption (Bias-Variance Decomposition, BVD
Condat et al. 2022 Ler s
for all RR, the gradient estimator g(z) satisfies
[[[g(()) - ff
" /lVf((>)
(8)
E [1(()) -ig()))]
<lVf(<>)1*
Khirirat et al. 2018b proposed another assumption on deterministic compressors.
Assumption (Bounded Relative Error Quantization, BREQ all E R for any p. 2 O,
Khirirat et (018b]) For
(o(x), Vf(z)) M p|Vf(())]'
(10)
Il(()))1 S <
(11)
The restriction below was imposed on the gradient estimator g(z) by Ajalloeian and Stich 2022)]
For the purpose of clarity, we rewrote it in the notation adopted in our paper. We refer the reader to Appendix O for the proof of equivalence of these two definitioins.
Assumption 6 (Bias-Noise Decomposition, BND Ajalloeian and Stich [2020) Let M, o², x2
be nonnegative constants, and ler 0 S m < For all x Re g(x) satisfies
E [[o(x) E [
< M I [+)]]] +
(12)
||B [[({]] [/(x)]
K m [ xp²
(13)
The following assumption introduced by Sahu et al. Gorbunov 20222).
2021
(see also the work of Danilova and
Assumption (Absolute Estimator, ABS Sahu et al. 2021) For all x E Rd, there exists A > such that
E [
(14)
This condition is tightly related to the contractive compression property (see Appendix M). Further, Bottou et al. 20188 proposed the following restriction stochastic gradient estimator.
Assumption (First and Second Moment Limits, FSML Bottou et al. (2018) There constants 0 g u, U> Q O, such that, for all RRa
exist
(v)(), [ [g(x)))
q / < /
(15)
|E [x)]]]
(16)
[l((2)) - - [b(+))]
S U[V[(=)]]
+Q
(17)
Our first theorem, described informally below and stated and proved formally in the appendix, provides required counterexamples of problems and estimators for the diagram in Figure
Theorem (Informal) The assumptions connected by dashed lines in Figure 7 Tare mutually non- implicative.
The result says that some pairs of assumptions are in certain sense unrelated: none implies the other, and vice versa. In the next section, we introduce a new assumption, and provide deeper connections between all assumptions.
5

---

New approach: biased ABC assumption
5.1
Brief history
Several existing restrictions on the first moment of the estimator were very briefty outlined in the
previous section (see 3 (8). (T0) 13 (5)) Khaled and Richtárik [2023] recently introduced very general and accurate Expected Smoothness assumption (we will call the ABC-assumption in this paper) on the second moment of the unbiased estimator. Let note that Polyak and Tsypkin [173] explored a related assumption during their analysis of pseudogradient algorithms. They succeeded in establishing an asymptotic convergence bound for variant of gradient descent in the unbiased scenario. In contrast, our study focuses on non non-asymptotic convergence rates in the biased setting. We generalize the restrictions (3). (10). (15 on the first moment and combine them with the ABC-assumption to develop our Biased ABC framework.
Assumption 9 (Biased ABC) There exist constants A, B, C, 2 0 such that the gradient estima- tor g(z) for every x E R satisfies
(V)(z), E[g(z)))
61V
(18)
E
IN [1]
- -f
(19)
The term A (f((x- - (*) in (19) naturally emerges when we bound the expression of the form Ex=1 % [[ 9: 2 0, i E [m] while can not be confined solely by the norm of the overall gradient B [ nor by a constant C, smoothness suffices to bound this by A (f(x) -*)-
Further. there exist quadratic stochastic optimization problems where the second moment of stochastic gradient is precisely equal to 2(f(z) - f*) (see Richtárik and Takáč (020
Concerning the challenges in verifying the Biased ABC assumption, it is worth mentioning that in Machine Learning, loss functions are commonly bounded from below by f = O. In Tables 2 and 8 provide the constants that validate the fulfillment of our assumption by wide range of practical estimators. Furthermore, Claims can aid in determining these constants for various sampling schemes.
5.2 Biased ABC as the weakest assumption
As discussed in Section there exists a 7oo of assumptions on the stochastic gradients in literature on BiasedSGD. Our second theorem, described informally below and stated and proved formally in the appendix, says that our new Biased ABC assumption is the least restrictive of all the assumptions reviewed in Section 4
Theorem (Informal) Assumption 9 Biased ABC is the weakest among Assumptions 1
Inequality ( of BVD or inequality 13) of BND show that can impose the restriction the first
moment by bounding the norm the bias. We choose incquality (18) that restrains the scalar product
between the estimator and the gradient purpose: this approach turns out to be general
its own. In the proof of Theorem ix (see (46) and (47)) we show that (13) implies (18). Below we show the existence of counterexample that the reverse implication does not hold.
Claim There exists a finite-sum minimization problem for which a gradient estimator that satisfies inequality (88 of Assumption Darioomgnoooe does not satisfy inequality 13 of Assumption 0
The relationships among Assumptions 1 are depicted in Figure based the results of Theorem T [
and Theorem It is evident from Figure that Assumption 6 (BND) and Assumption 8 (FMM)
are mutually non-implicative and represent the most general assumptions among those proposed in Assumptions F
The most significant difference between our Assumption Biased ABC) and Assumptions and is the inclusion of the term A (f(x) f*) the bound on the second moment of the estimator.
In Khaled and Richtárik 2023 the "ABC assumption" was introduced in the unbiased case. However, we aim to establish theory for biased estimators. If we simply remove (18). then g(z) = -V -V((x) satisfies [19 with A B 1, C' 0, yet BiasedSGD clearly diverges in general.

---

Assumption
A
B
C
Asm
SGI
Beznosikov et al
2020
0
g
Amm
SG2
Beznosikov et al.
2020
g²
Asm
CON
2 (2
7)
Avm
RVD
Condat et al.
2022
0
2(1 {
17)
Asm
BRRQ
2018b
Aam
BND
Ajallocian and Stich
2020
2(M + 1) + 1) 2(M + 1)p²
1-m
Asm
ABS
Saha al.
2021
2
2
PSML
Bottou
2018
U + u²
Table I: Summary of known assumptions on biased stochastic gradients. Estimators satisfying any of them, belong to our general Biased ABC framework with parameters A, B, C, and c provided in this table. For proofs, we refer the reader to Theorem 13
The rationale behind this inclusion detailed in Section 5.1 In general, estimators of the form Σ 9. V fz)) where q: 2 0, for E [n.]. often arise in sampling schemes. We present two practical settings with sampling schemes (see Definitions and 2 that can be described within the
Biased ABC framework. These settings, in general, fall outside of the BND and FSML frameworks.
(see Proof of Theorem parts viii and ix we present an example of setting with a minimization problem and gradient estimator that justifies the introduction of this term: BND and
In Section D.2
FSML frameworks do not capture the proposed setting, (iased ABC does capture
In Table we provide a representation of each of Assumptions | in our Biased ABC framework (based on the results of Theorem 13 Note that the constants Table are Ioo pessimistic: given the estimator satisfying one of these assumptions, direct computation of constants in Biased ABC scope for it might lead to much more accurate results. Table 2 we give a description of popular gradient estimators in terms of the Biased ABC framework. Finally, in Table 3 we list several popular
estimators and indicate which of Assumptions 1.9 they satisfy.
Estimator
Def
Riased Independent sampliig
Def.
max, [1.,)
2AA + +
min {p:}
puper)
min,
Top-k
Def.
Aji and Heafield
2017
Def.
4
0
et
2018
Blased Rand-k
Def.
Beznosikov al.
2020
Aduptive sparsifcation
Def. 6
0
0
Bezzosikov al.
2020
General unbiased rounding
Beznosikov al.
2020
Def.
sup
ke 4ugue:1
Natural compreesion
Def. 9
0
0
Horváth et al
2022
Scaled Integgr rounding
Def.
24 x2
Sapio al.
2021
2x
Table 2: Summary of popular estimators with respective parameters A, B, C, b and c, satisfying our general Biased ABC framework. Constants L, are from Assumption 13 A is defined in (26). For
more estimators, see Table g
6 Convergence of biased SGD under the biased ABC assumption
Convergence rates of theorems below are summarized in Table 4 and compared to their counterparts.

---

Estimator Assumption
A1
2
3
A4
A5
A6
A7
8
A9
Biased independent sampling [This paper]
Top-k sparsilication Aji and Heafield 2017
5
4
4
x
Rand-k Stich cl
2018
x
x
Hlased Kand-k Beznosioov et
2020
x
/
x
/
x
Adaptive
sparsification
Beenoskoy
2020
x
x
x
/
General unbiased rounding
Beznosikov ct
2020
x
x
5
x
compression Horvách al.
2022
x
/
x
Scaled Integer rounding Sapio el al.
2021
x
Table Coverage of popular estimators by known frameworks. For more estimators, see Table
6.1 General nonconvex case
Theorem 3 Let Assumptions a hold. Let 8 d f(xx) f and choose the stepsize such that
0 < 7 TB.
b Then the iterates {x' 1120 of BlasedSGD (Algorithm ( satisfy
2 21 LA
80 + LC7
min 0SAST
(20)
byT
While one can notice the possibility of an exponential blow-up in (20). by carefully controlling stepsize we still can guarantee the convergence BlasedSGD. In Corollaries and (see the appendix) we retrieve the results of Theorem 2 and Corollary from (Khaled and Richtárik 2023 for the unbiased case. Corollary 7 (see the appendix) we retrieve the result that is worse than that in [Ajalloeian and Stich 2020, Theorem 4] by multiplicative factor and extra additive term, but under milder conditions (cf. [Biasdd ABC and BND in Figure ! see also Claim [T. If we set A c 0, we recover the result of [Bottou et al. 2018 Theorem 4.8] (see Corollary g in the appendix).
6.2 Convergence under Pł.-condition
One of the popular generalizations of strong convexity in the literature is the Polyak-L.ojssiwwic. assumption [Polyak] 1963 Karimi et al. 2016 Lei et al. 2019). First, we define this condition.
Assumption 10 (Polyak--.ojasieviez) There exists μ > 0 such that V [f(x)) 2/ ( f*), for all x E Rd.
We now formulate theorem that establishes the convergence of BiasedSGD for functions satisfying this assumption and Assumption 9
Theorem Let Assumptions 0 9 and 10 hold. Choose a stepsize such that
Hb
1
0 0 min
(21)
L(A+ pB) pbb
Letling 80 def [(x0)= -
(e, for every T 2 1, we have
LOy
[f(()) 54] (1 7ub)² 8"
(22)
2ub
pb"
When = 0, the last term (22) disappears, and we recover the best known rates under the Polyak- Lojasiewicz condition Karimi et al. 2016). but under milder conditions (see Corollary [00 in the appendix). Further, if we set A 0, we obtain a result that is slightly weaker than the one obtained by Ajalloeian and Stich 20200 Theorem 6), but under milder assumptions (cf. Biased ABC and BND
in Figure see also Claim
6.3 Strongly convex case
Assumption 11 Let be j-stroogly-conver and continuously differentiable.

---

Theorem
Convergence rate
Compared to
Rate we compare to
Match?
B.
126 A
34.Thm
B.
124
26
max
Bists))les)) [L-m)'s
max
Mi3
202
15
Thm
3
mox
Lo
S
Thm 4,8
0
max
L8
1hm
2122+13 Aaae
Thhn
[max
(M
x
Thms
max
L(U-u2)
1
max
2.
gtv
19
/
ThTm 12
Ô
Thm
Thm 13
Ô (
x
Thm 12
Thm 14
(8
x
Table 4: Complexity comparison. We examine whether we can achieve the same convergence rate as obtained under stronger assumptions. In most cases, ensure the same rate, albeit with inferior multiplicative factors due the broader scope of the analysis. The notation Ô (-) hides logarithmic factor of log 28a
Since Assumption 10 more general than Assumption I1 Theorem can be applied to functions
that satisfy Assumption If we set A = 0, we recover Bottou et al.) 2018]] Theorem 4.6] (see Corollary 13 the appendix). If A C c = 0, we retrieve results comparable to those in
[Beznosikov et al.
2020 Theorems 12- 1-], up to a multiplicative factor (see Corollary [4 in the
appendix). Due y-strong convexity, our result 22 also implies an iterate convergence, since we
have - - 1| < _ [f(")) - f(x*)] However, in this case an additional factor of arises.
Below we present a stronger result, yet, at cost of imposing stricter condition on the control variables from Assumption 9
Assumption 12 Let A, B, C and be parameters from Assumption 9 Let μ be strong convexity constant. Let L be smoothness constant. Suppose A + L(B + 2b) holds.
Under Assumptions (2 Ian we establish similar result as the one obtained by Hu et al. [202 la Theorem 1J. The authors impose a restriction of 1 from above on a constant with an analogous role as B 2+1 - 26 in Assumptions and 12 with A = 0. However, unlike
the authors consider only finite sum case which makes our result more general. Moreover, only a biased version SGD with simple sampling strategy is analyzed by Hu et al. (2021a]. Our results are applicable to larger variety of gradient estimators and obtained under milder assumptions. Also, our proof strategy is different, and much simpler.
Theorem
Let Assumptions 0 9 11
and 12 hold. For every positive satisfying A L+L(B+11 2b)
s < μ. choose a stepsize such that
(A + L (B + 1-2bb)
< y S min
(23)
A+ LB
1- 8
Then the iterates of BiasedSGD (Algorithm) 7 for every T 2 satisfy
|| x x²1 7C + C+2c
| x' 11"]] < (1-r(p "))²
E
(24)
In the standard result for (unbiased) SGD, the convergence neighhorhood term has the form of 2C and it can be controlled by adjusting the stepsize. However, due to the generality of our analysis in the biased case, in (24) we obtain an extra uncontrollable neighborhood term of the form C42c. s(p-s)
When A C'
+ O, we recover exactly the classical result for GD. 1,
7 Experiments
Datasets, Hardware, and Code Implementation. The experiments utilized publicly available LibSVM datasets Citasees/Chang and Lin (001]) specifically the splice, a9a, and w8a. These algorithms were developed using Python 3.8 and executed on a machine equipped with 48 cores of Intel(R) Xeon(R) Gold 6246 CPU @ 3.30GHz.

---

Problem Setting, To validate our theoretical findings, we conducted series of nu- merical experiments on binary classification problem. Specifically, we employed logistic regression with non-convex regularizer:
Experiment:
min mER
def 1 f(x)
f())) 71
where fı(x) def log (1 exp (-yaay x)) +
+ zj
and (a4, v6) E 1R (-1, ..... n represent the training data samples. In all experiments, set the regularization parameter to a fixed value of X == 1. We use datasets from the open LibSVM library [Chang and Lin 2011]. We examine the performance
the proposed BiasedSGD method with biased independent sampling without replacement (we call it BiasedSGD-ind) in various settings (see Definition[]. The primary goal of these numerical experiments
demonstrate the alignment of our theoretical findings with the observed experimental results. To assess the performance of the methods throughout the optimization process. monitor the metric f>*)(= recomputed after every 10 iterations. The algorithms are terminated after completing 5000 iterations. For each method, use the largest theoretical stepsize. Specifically, for BlasedSGD the stepsize is determined
according to Corollary and Claim 2 with min VLAK LB LC
b
where = 0, A wax. L min; P.
B 0, C = 2 8 b = min; p; and 0.
More experimental details are provided in Appendix A
Riees/SGiDiink dodeact splice sumpling: unifom
RisesBGID-inn; dosnvet wha sampling utifem
BasniSCDD-in) dlesed dhe sipling: unikem
101
[1
10
12
2000
4000
2000
40003
J0M
40201
ireetions
Figure 2: The performance of BiasedSGD-ind with different choices of probabilities.
The impact of the parameter p on the convergence behavior. In the first experiment, we investigate how the convergence of BiasedSGD-ing is affected as we increase the probabilities Pi. while keeping them equal for all data samples. According to the Corollary 4 larger p; values (resulting in an increase of the expected batch size) allow for a larger stepsize, which, in turn, improves the overall convergence. This behavior is evident in Figure [ The experiment visualized in Figure 2 involves varying the probability parameter within the set {0.01, 0.1, 0.5}. This manipulation directly influences the value of A. consequently affecting the theoretical stepsize y. In the context of BiasedSGD-ind, the stepsize is defined as VLAK A comprehensive compilation of these parameters represented in Table 7
Experiment:
Conclusion
In this work, we consolidate various recent assumptions regarding the convergence of biasedSGD and elucidate their implication relationships. Moreover, we introduce weaker assumption, referred as Biased ABC We also demonstrate that Biased ABC encompasses stochastic gradient oracles that previous assumptions excluded. With this assumption, we provide a proof of biasedSGD convergence across multiple scenarios, including strongly convex, non-convex, and under the Pł.condition. Convergence rates that we obtain are the same up to a constant factor due to the broader setting and in some cases they coincide with the rates obtained under stricter assumptions. Furthermore, we examine the most widely used estimators the literature related to SGD, represent them within the context of our Biased ABC framework, and analyze their compatibility with all previous frameworks.
10

---

Acknowledgements
This work of all authors was supported by the KAUST Baseline Research Scheme (KAUST BRF). The work of Y. Demidovich and P. Richtárik was supported by the KAUST Extreme Computing Research Center (KAUST ECRC), and the work of P. Richtárik was supported by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST AI).
References
Ahmad Ajalloeian and Sebastian U Stich, Analysis of SGD with biased gradient estimators. arXiv preprint arXiv:2008. 00001, 2020.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. pages 440-445, Copenhagen, Denmark, 2017. Association for Computational Linguistics. doi: 10.18653/1/DD17-110555
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsified gradient methods. In Advances Neural Information Processing Systems (NeurlPS), volume 31, pages 5973-5983, 2018.
El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal on Optimization, 30(4):2726-2) 2749, 2020.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002.124110 12410, 2020.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Soumia Boucherouite, Grigory Malinovsky, Peter Richtárik, and EL Bergou. Minibatch stochastic three points method for unconstrained smooth minimization. arXiv preprint arXiv:2209.07888, 2022.
Chih-Chune Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):127,, 2011.
Congliang Chen, Li Shen, Haozhi Huang, and Wei Liu. Quantized Adam with error feedback. ACM Transactions on Intelligent Systems and Technology (TIST), 12(5):1-26, 2021a.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. 700: Zeroth order optimization based black-box attacks deep neural networks without training substitute models. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26, 2017.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 25294 253007 Curran Associates, Inc., 2021b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021c. doi: 10.1 109/TSP2202.33992377
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04677 2021d.
Laurent Condat, Kai Yi, and Peter Richtárik. EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Jean-Bane nan-BBptiste Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Technical report, 2018.

---

Marina Danilova and Eduard Gorbunov. Distributed methods with absolute compression and error compensation. In Mathematical Optimization Theory and Operations Research: Recent Trends: st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2-6, 2022, Revised Selected Papers, pages 163-177. Springer, 2022.
Alexandre d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Opti- mization, 19())1111-1183; 2008.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146 146(1-2)377-75, 2014.
Aritra Dutta, El Houcine Bergou, Ahmed M Abdelmoniem, Chen- Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 381 1-8244,,4 2020.
Iyya Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells whistles: practical algorithmic extensions of modern error feedback. arXiv preprint 10.024,4,, 2021.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. The MIT Press, 2016.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. Advances in Neural Information Processing Systems, 33:20889-20900, 2020.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning (ICML), pages 5200-5209, PMLR, 2019.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. International conference on machine learning, pages 1737-1746.
PMLR, 2015.
Samuel Horváth, Chen-Yo Yu Ho, Ludovit Horváth. Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pages 129-141. PMLR, 2022.
Bin Hu, Peter Seiler, and Laurent Lessard. Analysis of biased stochastic gradient descent using sequential semidefinite programs. Mathematical Programminng 187:383-40$ 2021a.
Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic. SIAM J. on Optimization, 3003):2103-2133 2020a. ISSN 1052-6234. doi: 10.1137/19M1284665 URL https://doii org. 117/9/991111/1991188865
Yifan Hu. Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, cc/
pages 2759-2770, Curran Associates, Inc., 2020b. URL httpps::/proceeeiinggs paper_ www.ffillpppa http:///ppppppp////////aaaaaaaaa
Yifan Hu, Xin Chen, and Niao He. On the bias stas-variance-cos tradeoff of stochastic optimization. In Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information P Processing Systems, volume 34, pages 22119-22131, Curran Associates, Inc., 2021b. URL httpttpepe//ppooceeednggg. http://ppocceddnns.e.eeeeeepppps ccteriisscccpeeeee cttpppsr.ccpppppppcpeeee pappprrflllassslppaapppppapaeeee files/ papp:////a/p/////eee/e/// 19967706677764/78844446666777272 [] .dff
nwwrins.cc..oo
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Theoretical convergence of multi-step model-aggostic meta-learning. 23(1), 2022. ISSN 1532-4435.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak--.ojasiewiez condition. Machine Learning and Knowledge Discovery in Databases, pages -95-8111 181,, 2016.
12

---

Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Adaptive balancing of gradient and update computation times using global geometry and upproximate subproblems. Proceedings of the s1 International Conference Artificial Intelligence and Statistics (AISTATS, 2018.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning (ICML), volume 97, pages 3252-3261, 2019.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL httpaas//pppnneeiee..ettttt id=AU4gHN2VKS Survey Certification.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv: 1806.06573, 2018a.
Sarit Khirirat, Mikael Johansson, and Dan Alistarh. Gradient compression for communication-ligg limited convex optimization. In 2018 IEEE Conference on Decision and Control (CDC), pages 166-171. 171. IEEE, 2018b.
Sarit Khirirat, Sindri Magnússon, and Mikael Johansson. Compressed gradient methods with Hessian- aided error compensation. IEEE Transactions on Signal Processing, 69:998-1011 2020.
Sarit Khirirat, Sindri Magnússon, and Mikael Johansson. Eco-Fedsplit: Federated learning with error- compensated compression. ICASSP 2022-2023 IEEE International Conference on Acoustics, IEEE, 2022.
Speech and Signal Processing (ICASSP), pages
Yunwei Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic Gradient Descent for nonconvex learning without bounded gradient assumptions. In IEEE Transactions on Neural Networks and Learning Systems, pages 1-7. ISSN 2162-2388, 2019.
Rémi Lelue and François Portier. SGD with coordinate sampling: Theory and practice. Journal of Machine Learning Research, 23(442):1-47, 2022.
Daniel Levy, Yair Carmon, John C. Duchi, and Aaron Sidford. Large-scale methods for distribu- tionally robust optimization. In Proceedings of the 34th International Conference Neural Information Processing Systems, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems (NeurIPS), 11:3727-37311 2018.
Konstantin Mishchenko, Bokun Wang, Dmitry Kovalev, and Peter Richtárik. IntSGD: Adaptive floatless compression of stochastic gradients. arXiv preprint arXiv:2102.08374 2021.
Seyed-Mohsen Moosavi-Dezfoolii Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):577-56, 2017.
Feng Niu, Benjamin Recht, Christopher Re, and Stephen Wright. Hogwild: A lock-free approach to parallelizing Stochastic Gradient Descent. Advances in Neural Information Processing Systems (NeurIPS), volume 24, pages 693-701, 2011.
Boris Polyak. Gradient methods for minimizing functionals. U.S.S.R. Computational Mathematics and Mathematical Physics, 3(4):864-87) 1963.
Boris Polyak. Introduction to Optimization. OptimizationSSftwaare Inc., 1987.
13

---

Boris Polyak and Y.Z. Tsypkin. Pseudogradient adaptation and training algorithms. Automation and Remote Control, 34:377-397, 01 1973.
Peter Richtárik and Martin Takáč. Stochastic reformulations of linear systems: Algorithms and convergence theory. SIAM J. Matrix Anal. Appl., 41(2):487-524, 2020. ISSN 0895-4798.
Peter Richtárik, Igor Sokolov, and Hyys Fatkhullin, EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Peter Richtárik, Igor Sokolov, Elnur Gasanov, Ilyas Fatkhullin, Zhize Li, and Eduard Gorbunov. 3PC: Three point compressors for communication-effin distributed training and a better theory for lazy aggregation. In International Conference on Machine Learning (ICML), pages 18596-18648. PMLR, 2022.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400 4074000040711100 1951.
Atal Sahu, Aritra Dutta, Ahmed M Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification total error minimization. Advances in Neural Information Processing Systems (NeurIPS, 34:8133-8144 2021.
Amedeo Sapio, Marco Canini, Chen- Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtárik. Scaling distributed machine learning with in-network aggregation. In In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 785-808. 2021.
Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proxinal-gradient methods for convex optimization. Advances in Neural Information Processing Systems (NeurIPS), 14:1458-1466, 2011.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms.. Cambridge University Press, 2014.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. The Journal of Machine Learning Research, 21(1):913-9648, 2020.
Sebastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Nikko Ström. Scalable distributed dnn training using commodity GPU cloud computing. In Inter- speech 2015, 2015.
Ruo-Ye Yu Sun. Optimization for deep learning: An overview. Journal of the Operations Research Society of China, 8(2):249-299 2020.
Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel Stochastic Gradient Descent with double-pass error-compensated compression. In Proceedings of the 36th International Conference Machine Learning (ICML), 2020.
Rachael Tappenden, Peter Richtárik, and Jacek Gondzio. Inexact coordinate descent: Complexity and preconditioning. Journal of Optimization Theory and Applications, 170:144-1777 2016.
Jie Wang, Rui Gao, and Yao Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109. 1926, 2021.
Jianqiao Wangni, Jialei Wang, Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 1306-1316, 2018
14


Reviews:
[{"review_id": "kXvaZmFXxB", "reviewer": "Reviewer_8vPv", "summary": "This paper focuses on the relationships among various assumptions used in the analysis of biased SGD. The authors establish connections among the large number of existing assumptions present in the literature, and propose an assumption (Biased ABC) which captures all prior assumptions. The authors also show that this assumption captures stochastic gradient oracles that prior assumptions did not allow. Using this assumption, they give a simple proof of SGD convergence in a number of settings (both convex and non-convex). While in some cases, the rates are slightly suboptimal (due in part to the more general setting they consider), in many cases, these proofs recover the same (or nearly the same) bounds of prior work under weaker assumptions.", "questions": "[Regarding Assumption ABC]\n\nI found the term $A(f(x) - f^*)$ term in eq. (19) to be somewhat mysterious, yet there is not much discussion in the main body of your paper as to why you consider this term in the variance bound. In the appendix, it becomes somewhat clear that you introduce $A$ to handle “Biased independent sampling”, but this this isn’t discussed much in the paper. Are there other reasons why you consider this term in the variance bound?\n\nIt is worth noting that a similar assumption (in the unbiased setting) was considered by Polyak and Tsypkin (1973) “Pseudogradient Adaptation and Training Algorithms” (see the first equation in their Section 3). They also don’t really discuss why they consider this term in the variance bound. I don’t think I’ve seen this type of assumption anywhere else in the literature (except in Khaled and Richtárik (2023) “Better theory for SGD in the nonconvex world”, as you mention). Perhaps you have some insights into this? Also, it is probably worth giving the Polyak and Tsypkin paper a citation, given the similarity of your assumptions.\n\n[Regarding the discussions in weaknesses section above]\n\nCould you please address if the error in the proof of Theorem 2 viii and ix is easy to overcome? (I will set my score now to weak accept due to this error). \n\nCould you please describe how you plan to incorporate the feedback on paper organization?\n\n[Regarding Theorem 3]\n\nTheorem 3 gives a guarantee on $\\min_t E[||\\nabla f(x_t)||^2]$, while, at least for the unbiased setting, the results of Ghadimi and Lan (2013) give convergence for the average iterate. Looking at your proof, it appears that you actually get convergence for a weighted average of the gradients, but where the *smaller* iterates are weighted higher. That seemed quite counter-intuitive to me, as I would have expected a higher weighting of later iterates. Do you have any intuition on why the weighting is this way? Is there any hope in getting convergence of the average iterate in your framework?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper provides a very nice overview of the assumptions made in various works on analysis of biased SGD. They establish relationships among these assumptions, and suggest an assumption (Biased ABC) which captures all of these assumptions. This characterization will surely be of great utility to researchers interested or working in this area. By taking a more general assumption, they are able to recover a number of existing results in the literature, sometimes slightly generalizing the results by weakening the assumptions. Sometimes, however, the results obtained are slightly cruder (due to their assumption being weaker). Although there are no significant new proof techniques (at least that I saw) in this paper, I think there is a lot of value in simplifying and unifying results of prior works.", "weaknesses": "[Theorem 2 viii and ix]\n\nIf I am not mistaken, it appears there is a bug in the proof of “The reverse implication does not hold” part of Theorem 2 viii and ix. You consider $f_1(x) = (x_1^2 - x_2^2)/2$ and $f_2(x) = -f_1(x)$, and claim “Due to Claim 2, it satisfies Assumption 9 (functions $f_1$ and $f_2$ are $1$-smooth)”. To apply Claim 2, however, Assumption 13 must hold, which not only requires the functions $f_i$ to be smooth, but also to be bounded from below. $f_1(x)$ is clearly not bounded from below (take $x_1=0$ and $x_2 \\rightarrow +\\infty$). Thus, it seems that Claim 2 cannot be applied to your example.\n\n[Organization of the paper]\n\nI personally found the paper a bit hard to navigate. I think this is largely due to the sheer number of claims, definitions, and parts of proofs that are in the paper. I think some reorganization could greatly improve the readability of the paper.\n\nFor instance, when reading section B of the appendix, you mention the Biased independent sampling without replacement (Definition 1). I was curious why Assumption 8 can break for this setting (i.e., why you need $A>0$ in Assumption 9), but actually understanding this required finding the proof of Claim 2 and the proof of Theorem 2 viii and ix. It didn’t feel like a natural flow to have to dig so much for what seemed to be the punchline of introducing Definition 1. Is there a way to bring this all in one place?\n\nI understand that organizing a paper with so many short results is difficult. However, I think that some results are less interesting than others, and perhaps can be moved to the end of the paper to reduce clutter. For instance, I think the main interesting parts of Theorem 2 concern Assumption 9. Perhaps you can separate these parts from the others, so that these are easier to find?\n\nAnother note is that some parts of the appendix feel like they do not have enough bridge text. For instance, section C is just a long list of Definitions and Claims. Could you add some text describing these settings, or why they might be interesting to the reader?\n\nAlso, in the main body, you mention lots of assumptions, but there is no mention of actual examples where the stochastic gradients satisfy these examples. All of this is saved for the appendix. I think it would help readability of the paper if some of the less interesting assumptions were moved to the appendix (perhaps only keep a couple of the main assumptions in the main body), and you moved some of the examples to the main body (e.g., the Biased independent sampling w/o replacement, or another of your choosing).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Strengths:**\n\n**Answer:**\n\nWe appreciate for the time and dedication you devoted to sharing your valuable perspectives on our paper. Your comments were tremendously beneficial. We also extend our thanks for recognizing the fundamental concepts within our paper. We have taken into account and addressed all the concerns raised in the text below.\n\n>**Weaknesses:**\n\n>**[Theorem 2 viii and ix]:**\n\n**Answer:**\n\nThank you for the checking this proof! We appreciate that you find a mistake. We agree that these two parts of the theorem are not correct. Please check the fixed proof of Theorem 2 viii and ix in the general response above. \n\n>**[Organization of the paper] **\n\n>Is there a way to bring this all in one place?\n\n**Answer:**\n\nThank you for reviewing Appendix B. We agree that introducing Definition 1 closer to the proof of Theorem 2 makes sense. One option is to place it in Appendix C alongside other gradient estimators. Alternatively, it could be introduced near the proof of Theorem 2. Our preference is to include Definition 1 in Appendix C with the other estimators, as we find this to be the best approach. Your suggestions are welcome and appreciated.\n\n>Perhaps you can separate...\n**Answer:**\n\nWe appreciate your suggestion. We are considering dividing the theorem into two distinct sections. The initial section will encompass statements from i to vii, while the subsequent section will incorporate statements viii and ix. Additionally, we plan to allocate these two segments into separate subsections. This arrangement will not only facilitate convenient access but will also enhance their visibility within the table of contents.\n\n>Could you add some text...\n\n**Answer:**\n\nWe appreciate your valuable comment. We agree with your suggestion to add explanatory comments between definitions and claims for clarity. We're committed to providing practical examples to enhance understanding and adding intuitive explanations after theoretical claims. Your feedback has refined our work, and we're excited to implement these improvements.\n\n> I think it would help readability...\n\n**Answer:**\n\nThank you for your idea! With an additional page expected in the camera-ready version, we're excited about the potential to add more examples to the main paper. However, moving some definitions to the appendix might not be possible due to their role in Figure 1. Balancing visual coherence and conceptual integrity is a priority as we consider this. Your input is invaluable in shaping our approach, and we're committed to enhancing the paper's quality and effectiveness.\n\n>Questions:\n>[Regarding Assumption ABC]\n\n**Answer:**\n\nWe can shed light on the reasoning behind the utilization of the term $A(f(x)−f∗)$ as follows. When delving into the analysis of the 2nd moment of a gradient estimator, a common scenario emerges where we find ourselves needing to constrain the expression $E := \\sum_{i=1}^n q_i\\Vert \\nabla f_i(x) \\Vert^2$, where $f(x) = \\frac{1}{n}\\sum_{i=1}^n f_i(x)$. While $E$ cannot be confined solely by the norm of the overall gradient $B\\Vert\\nabla f(x)\\Vert^2$, nor by a constant $C$, smoothness suffices to bound this by $A(f(x)−f∗)$. Further, there exist quadratic stochastic opt problems where the 2nd moment of an (unbiased) stochastic gradient is precisely equal to $2(f(x)-f_*)$ (take expectation on both sides of (3.11) in Richtarik, Takac, Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory, SIMAX 2020).\n\nWhen functions show varying gradient magnitudes and estimators align closely with those magnitudes, constraining the 2nd moment of the estimator becomes tough. In such cases, bounding the 2nd moment becomes impossible. We'll delve into this in our paper, especially in Sec 5, providing clarifying explanations for better understanding.\n\n>Also, it is probably worth giving the Polyak and Tsypkin paper a citation...\n\n**Answer:**\n\nMuch appreciated, we will reference the work of Polyak and Tsypkin (1973). As highlighted by Khaled and Richtárik (2023) in their publication \"Better theory for SGD in the nonconvex world,\" Polyak and Tsypkin explored a related assumption during their analysis of pseudogradient algorithms. They succeeded in establishing an asymptotic convergence bound for a variant of gradient descent in the unbiased scenario. In contrast, our study focuses on non-asymptotic convergence rates in the biased setting.\n\n>[Regarding the discussions in weaknesses section above]\n\n**Answer:**\n\nPlease answers regarding weaknesses above. Overall, we are going to move definition 1 to appendix C or even closer to Theorem 2. \n\n>[Regarding Theorem 3]\n\n**Answer:** We need to obtain telescoping sum in equation (57) from equation (56). Equation (56) states that\n$$  \\frac{\\gamma b}{2} r^t \\leq\\left(1+L A \\gamma^2\\right) \\delta^t-\\delta^{t+1}+\\frac{L C \\gamma^2}{2}+c \\gamma.$$\nIn order to have  telescoping sum we need to have coordinated coefficients with consistent indices. To make it possible we use $w_t=\\frac{w_{t-1}}{1+L A \\gamma^2}$. Finally, we obtain\n$$\\frac{b w_t r^t}{2} \\leq \\frac{w_{t-1}}{\\gamma} \\delta^t-\\frac{w_t}{\\gamma} \\delta^{t+1}+\\frac{L C \\gamma w_t}{2}+\\frac{c w_t}{2},$$\nFor every $ 0 \\leq t \\leq T-1$, we get \n$$\\frac{b}{2} \\sum_{t=0}^{T-1} w_t r^t \\leq \\frac{w_{-1}}{\\gamma} \\delta^0-\\frac{w_{T-1}}{\\gamma} \\delta^T+\\frac{L C \\gamma+c}{2} \\sum_{t=0}^{T-1} w_t.$$\nThe underlying idea is that the term ${1+L A \\gamma^2}$ surpasses the value of $1$, necessitating a reduction by the same factor to align coefficients. However, obtaining guarantees for the average iterate at this level of generality remains a challenge. It is possible that by considering more specific assumptions, we can derive a rate for the average iterate.\n\nWe believe our comments have effectively addressed your concerns. We kindly request a reconsideration of your initial evaluation. The added explanations may justify a higher score. Please acknowledge if further discussion is necessary."}, {"review_id": "tAGqNhN1H1", "reviewer": "Reviewer_PDsK", "summary": "This paper summarizes various recent assumptions about the convergence of biased SGD and exposes their implication relations. Furthermore, it proposes a weaker assumption, Biased ABC,  in terms of implication relations and analyzes the results under this assumption.", "questions": "Although the implication shows that Biased ABC is the weaker assumption, at first glance it seems that this assumption is more difficult to check because it requires more variables to be shown to exist and f* is needed than the other assumptions.\nTo explain more intuitively why this assumption is weaker, please explain a situation that can be checked with this assumption but not with the other assumptions, or a situation that applies to this assumption but not to the other assumptions.\nAlso, I know that if Assumption 8 holds, then Assumption 9 holds, but I could not catch the proof that the converse does not hold, so please tell me where in the Appendix it is written.\nThis is important for showing the weakness of Assumption 9, which leads directly to raising the score.\nSince the experiment section is halfway through, wouldn't it be better to put it into the experiment part of the Appendix and write a discussion and conclusion?\n The experiment itself does not seem to make much sense in this paper.", "limitations": "Too many pages in Appendix make it difficult to check the correctness of proofs in the limited peer review period of an international conference.\nCurrently, it is difficult to see that the assumption is weaker than Assumption 8.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper summarizes various recent assumptions about the convergence of biased SGD and exposes their implication relations. \nIt is well written and in particular, Figure 1 is informative.", "weaknesses": "It seems that submitting a paper, which has an Appendix of 50 pages including proofs, to an international conference where the peer review period is short and there is not enough time to adequately check proofs, is a negative impression in itself.\nIn addition, the fact that the paper ends with a section on experiments and does not include a summary gives a half-hearted impression of the paper's presentation, which I suppose cannot be helped given the insufficient number of pages, but conversely, it seems to mean that this paper is not suitable for an international conference with a tight page limit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Strengths:**\n\n**Answer:**\n\nWe extend our sincere appreciation for the dedication of your time and effort in sharing your valuable feedback and insights on our work. Your comments have proven to be immensely valuable. Additionally, we would like to convey our gratitude to the reviewer for recognizing the fundamental concepts within our paper and for highlighting the ease of readability. We have taken into consideration all the concerns raised by the reviewer, and our responses can be found below.\n\n>**Weaknesses:**\n\n**Answer:**\n\nWe politely disagree that paper with 50 pages is not appropriate for international conference. There are many examples of large papers accepted to top international conferences such as ICML, NeurIPS, etc. Let us provide such examples:\n\nSecure Distributed Training at Scale ICML 2022 (https://proceedings.mlr.press/v162/gorbunov22a.html) has **61 pages**\n\nA Statistical Analysis of Polyak-Ruppert Averaged Q-Learning AISTATS 2023 (https://proceedings.mlr.press/v206/li23b.html) has **55 pages**\n\nVariational inference via Wasserstein gradient flows NeurIPS 2022 (https://openreview.net/pdf?id=K2PTuvVTF1L) has **44 pages**\n\nLinearly Converging Error Compensated SGD NeurIPS 2020 (https://proceedings.neurips.cc/paper/2020/file/ef9280fbc5317f17d480e4d4f61b3751-Paper.pdf)** has **99 pages**\n\nCan Reinforcement Learning Efficiently Find Stackelberg-nash Equilibria In General-sum Markov Games With Myopic Followers? ICLR 2022 (https://openreview.net/pdf?id=rqfwi51Tgc) has **40 pages**\n\nLocal SGD: Unified Theory and New Efficient Methods AISTATS 2021(http://proceedings.mlr.press/v130/gorbunov21a/gorbunov21a-supp.pdf) has **80 pages**\n\nRecognizing the limitations imposed by the compressed time frame allocated for proof validation, we wish to emphasize our strong conviction that the paper we have submitted is indeed worthy of being showcased at this conference. The crux of our belief rests upon the inherent value embedded within our exploration of the biased SGD method, which we assert holds the potential to deliver substantial benefits to numerous researchers within the machine learning community.\n\nThe significance of our study lies in its potential to contribute to a deeper understanding of the nuanced aspects of biased SGD, an area of growing relevance within the realm of machine learning. By unraveling the intricacies and implications of this method, our work has the capacity to provide fresh insights, innovative techniques, and potentially transformative perspectives that could resonate with a wide spectrum of researchers, spanning from novices to seasoned experts.\n\nMoreover, we envision that the dissemination of our findings at this conference could catalyze valuable discussions, foster collaboration, and prompt further exploration within the ML community. The opportunity to share our research in this context holds the promise of stimulating intellectual exchange and collective growth, ultimately advancing the field's collective knowledge and pushing the boundaries of what is currently understood.\n\nIn conclusion, we firmly maintain that the substantial potential impact of our paper, coupled with its alignment with the overarching goals and interests of the conference, render it a fitting candidate for inclusion in the conference proceedings. We eagerly anticipate the chance to present our work and engage in the rich discourse that such a platform affords.\n\n>**Questions:**\n\n**Answer:**\n\nWe appreciate your inquiry. In many real-world applications of Machine Learning, loss functions exhibit a nonnegative nature, thereby resulting in f* being simply equivalent to 0. The illustration in Figure 1 suggests that Assumption 8 (FSML) serves as a foundation for Assumption 9 (BiasedABC), and this relationship is substantiated by the proof provided in Theorem 2, specifically in part viii. Similarly, the diagram implies that Assumption 6 (BND) implies Assumption 9 (BiasedABC), a deduction which is corroborated by the evidence presented in Theorem 2, part ix. Within these segments of Theorem 2, we also establish the non-validity of the converse implications.\n\nIn alignment with the diagram's transitivity principle, the aforementioned connections constitute the entirety of the verifications required. To demonstrate the non-validity of the reverse implications from Assumption 9 to both Assumption 8 and Assumption 6, we employ the same counterexample. It is essential to note that an error exists in the proofs provided for parts viii and ix (pages 30-32), as astutely pointed out by Reviewer 8vPv. Consequently, we present an alternative counterexample, akin to the example put forth in Proposition 1 by Khaled and Richtarik (2013), which effectively substantiates both segments of Theorem 2. Please check the general response.\n\nIt is important to highlight that the proof of Claim 1 (page 32) also serves to demonstrate that Assumption 9 does not imply Assumption 6. This is owing to the fact that our scalar product condition pertaining to the bias is considerably less restrictive than its counterpart (13) as delineated in Assumption 6. Overall, we fixed the Theorem 2 viii and ix in the general response, so we showed an example when Assumptions 6 and 8 do not hold, but new Assumption 9 still holds.\n\nAnticipating an additional page allocation for the camera-ready version, we plan to integrate specific sections for discussions and clarifications. However, should the extra page not be approved, we will exclude the incorporation of plots within the main content.\n\nWe value your attention to detail and your discerning insights, which significantly contribute to the refinement of our work. \n\n>**Limitations**\n\n**Answer**:\nPlease check replies above.\n\nWith confidence in our comments addressing your concerns, we respectfully request a reconsideration of your evaluation. We hope our responses prove more satisfactory and justify a higher score. Please acknowledge if more discussion is needed.\n\n\n\n\n\n\n"}, {"review_id": "QjfeRJmJMS", "reviewer": "Reviewer_84Sm", "summary": "This paper establishes connections among the existing assumptions found in the literature on Stochastic Gradient Descent (SGD) with biased estimators. The authors provide a comprehensive map that illustrates the relationships between these assumptions, addressing the lack of coherence found in previous works. Furthermore, they introduce a new set of assumptions, namely Biased ABC that have been proven to be weaker than the previous ones. It enables a thorough analysis of Biased SGD in both convex and non-convex settings. The paper also showcases examples where biased estimators outperform their unbiased counterparts or where unbiased versions are not available. Finally, the authors validate their theoretical findings through experimental results, which further supports the effectiveness of their framework.", "questions": "1. Is there an example to support Claim 1?\n", "limitations": "1. Figure 1 summarized one of the main contribution of this paper. However, the way it presented right now is not ideal. Especially after including the blue dashed lines. With so many lines that are flying around, the main message that this figure tries to deliver is not well received, in my opinion. I would recommend the author find a more concise way to present the connections in Figure 1.\n\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper provides a comprehensive overview of the existing literature elaborating on connections between the existing assumptions and the proposed assumption used in the analysis for biased SGD.\n\nOften, when comparing two theoretical results, one may demonstrate slightly tighter result by relying on stricter assumptions, while the other may provide a slightly worse dependence but arguing they have milder assumption. Assessing which approach is superior can be a challenging task. In this regard, the authors have tackled a crucial and significant subject. They have made a good effort towards unifying the various assumptions by proposing a new set of assumption which believed to be weaker than all previous ones. These proposed assumptions cover the existing assumptions, and the convergence results can be suitably adapted accordingly.\n\n", "weaknesses": "The newly proposed assumption Biased ABC is an incremental work based on existing work on biased SGD and the work done by Khaled and Richtárik [2023] for unbiased SGD. I felt there is not much novelty exists in this newly proposed assumption.\n\nAlso, in my opinion,  the balance between the discussion on the background and introduction of existing assumptions and the presentation of the authors' own theoretical results could be further improved.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Strengths:**\n\n**Answer:**\n\nWe sincerely appreciate the time and effort you dedicated to offering your valuable feedback and insights on our work. Your comments have proven immensely helpful. Our gratitude extends to the reviewer for identifying the foundational concepts within our paper. In the sections that follow, we diligently address all concerns raised by the reviewer.\n\n>**Weaknesses:**\n\n**Answer:**\n\nInitially, we independently formulated the scalar product condition outlined in Assumption 9, unaware of its prior introduction by L. Bottou. The absence of explicit mention of the consideration of the biased version of SGD led to our independent derivation. While we recognized that Khaled and Richtarik presented a highly generalized assumption in the unbiased context, we extended it to encompass the biased scenario in the most comprehensive manner we were cognizant of. It's worth noting that Table 4 underscores our analysis's equivalence, highlighting our work's broader scope.\n\nAcknowledging the wealth of ideas already in existence, we concur that our work is founded on established concepts. Yet, the multitude of publications on the subject suggests that the amalgamation of these ideas into Assumption 9 is no straightforward feat.\n\nIndeed, our current paper may not extensively delve into existing assumptions or optimally present our findings. However, should our submission be accepted, we are hopeful that an additional page allocation for the main content will offer us the opportunity to comprehensively discuss prior results, provide a robust motivation for the introduction of our assumption, and succinctly summarize our contributions.\n\n>**Questions:**\n\n**Answer:**\n\nThe example substantiating Claim 1 is located on page 32 within the section dedicated to proving the implications depicted in Figure 1. We appreciate your observation regarding its accessibility, and we are considering subdividing the relevant section into subsections, with a distinct subsection dedicated to the proof of Claim 1. This subdivision should enhance the clarity and facilitate easier navigation to the pertinent content. \n\nNote that we corrected the proof of Theorem 2 viii and ix. You can check the updated proof in the general response above.\n\n>**Limitations:**\n\n**Answer:**\n\nWe sincerely appreciate your feedback regarding the diagram. Our work delves into a multitude of assumptions, and while the visualization of connections is challenging, it remains an essential aspect. The diagrammatic representation offers a concise and convenient presentation compared to a table format. Its effectiveness lies in not needing to illustrate every single relationship due to the transitivity principle. For instance, no lines are drawn between ABS and SG1, as ABS doesn't imply FSML (which encompasses SG1), and conversely, BREQ (a subset of SG1) doesn't imply BND (a subset of ABS).\n\nThis diagram serves to highlight why Theorems 1 and 2 solely focus on the connections indicated by the blue lines and black arrows. The consideration of removing the blue dashed lines is an option under contemplation, as it would potentially necessitate supplementary explanatory text placed outside the diagram, which might not be as reader-friendly. We will weigh this possibility. Importantly, the current format enables readers to easily locate desired connections and corresponding theorem sections with a simple click.\n\nWe are open to exploring the possibility of removing the blue dashed lines from the diagram and replacing them with explanatory footnotes. As we evaluate this approach, it remains uncertain how effectively the new diagram will convey information. Therefore, our intention is to experiment with different alternatives to ascertain the most illustrative and reader-friendly presentation. Your suggestion is valued, and we are committed to refining the diagram in a manner that best enhances clarity and understanding.\n\nThank you once again for your valuable input, which we highly regard in our continuous efforts to enhance the clarity and accessibility of our work.\n\nWe hold a strong belief that our comments have effectively addressed your concerns. With utmost respect, we kindly request you to consider revisiting your initial evaluation. We remain hopeful that our responses will prove more satisfactory, and the additional explanations we've provided could potentially justify an elevated score. Your acknowledgment of our response would be greatly appreciated, particularly if you deem further discussion to be necessary.\n\n"}, {"review_id": "VlexSHCFJc", "reviewer": "Reviewer_R984", "summary": "The paper analyzes the assumptions for biasedSGD for various applications and proposes a more general and weaker ABC-assumption that covers the mentioned assumptions. The paper provides a detailed comparison with several existing literature trying to build up a unified framework for biasedSGD. It seems to be a further generalization of [Ahmad Ajalloeian and Sebastian U Stich, 2020].", "questions": "See weakness. Other questions:\n\n1. Ahmad Ajalloeian and Sebastian U Stich 2020 has been published. Please update the preprint references if they are published.\n2. Table 4, it says that \"In most cases, we ensure the same rate\", but the table 4 last column does not seem to suggest so. \n3. For strongly convex case, what happens when Assumption 12 fail?", "limitations": "The main drawback of the work is its predominant focus on iteration complexity in specific contexts, such as finite-sum, zeroth-order, and distributed stochastic optimization settings. Other perspectives on BiasedSGD, such as sample costs/computational costs for different problem settings, are not sufficiently addressed. Numerous biasedSGD methods applicable to a variety of other contexts are overlooked.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides a clear link of different assumption used in the BiasedSGD literature and compare them in Figure 1. In additional, it proposes a set of assumption for biasedSGD that can guarantee the same iteration complexity as the unbiased SGD. I appreciate the clarity and structure of these relationships as they can be invaluable when addressing a new problem requiring BiasedSGD, thus saving time for the reader.", "weaknesses": "I mainly have two concerns: missing reference on other biasedSGD methods and how the proposed ABC assumption can serve as a useful assumption. \n\nThis paper overlooks a substantial body of literature on biasedSGD in contexts beyond classical stochastic optimization/finite-sum and distributed training settings, such as\n1. Stochastic compositional/minimax/bilevel optimization. [1,2,3]\n2. Conditional stochastic optimization. [4,5,6]\n3. Distributionally robust optimization. [7,8]\n4. Meta learning. [9]\n\nThese works are centered on constructing biased gradient estimators and analyzing biasedSGD. Unlike the manuscript, these studies not only consider iteration complexity but also the total sample size needed to reach the desired solution, given the potential high sampling/computational cost of creating low-bias or unbiased gradient estimators. This angle is neglected in the manuscript, causing the title \"A Guide Through the Zoo of Biased SGD\" to seem overstated. Consequently, Section 2, addressing the source of bias, appears narrow given the wide applicability of biasedSGD.\n\nI suggest that the authors limit their claims, incorporate and discuss the above references, and address other bias sources. Specifically, it would be insightful if they could compare two biasedSGD construction methodologies:\n1. The approach in [1] that progressively reduces the bias level of the biased gradient estimators as the algorithm evolves.\n2. The approach in [5] that constructs low-bias gradient estimators at a cheap cost at each iteration. \nNotably, it seems that [1,2,3] don't meet the proposed ABC condition, but the proposed biasedSGD algorithm can still achieve optimal sample complexity. For [5], the gradient estimator constructed in [5] should satisfy ABC condition or its variants but the submitted paper fails to address the potential high costs of obtaining gradient estimators that adhere to the proposed ABC assumption. The authors should discuss these limitations.\n\nThe proposed ABC assumption appears difficult to validate. It remains unclear when this condition should be employed.\n\n\n\n[1] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.\" Advances in Neural Information Processing Systems 34 (2021): 25294-25307.\n\n[2] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization.\" IEEE Transactions on Signal Processing 69 (2021): 4937-4948.\n\n[3] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"A single-timescale stochastic bilevel optimization method.\" arXiv preprint arXiv:2102.04671 (2021).\n\n[4] Hu, Yifan, et al. \"Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning.\" Advances in Neural Information Processing Systems 33 (2020): 2759-2770.\n\n[5] Hu, Yifan, Xin Chen, and Niao He. \"On the bias-variance-cost tradeoff of stochastic optimization.\" Advances in Neural Information Processing Systems 34 (2021): 22119-22131.\n\n[6] Hu, Yifan, Xin Chen, and Niao He. \"Sample complexity of sample average approximation for conditional stochastic optimization.\" SIAM Journal on Optimization 30.3 (2020): 2103-2133.\n\n[7] Levy, Daniel, et al. \"Large-scale methods for distributionally robust optimization.\" Advances in Neural Information Processing Systems 33 (2020): 8847-8860.\n\n[8] Wang, Jie, Rui Gao, and Yao Xie. \"Sinkhorn distributionally robust optimization.\" arXiv preprint arXiv:2109.11926 (2021).\n\n[9] Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Theoretical convergence of multi-step model-agnostic meta-learning.\" Journal of machine learning research (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Strengths:**\n\n**Answer:**\nWe genuinely appreciate the time and effort you dedicated to our work. Your comments were incredibly useful. In addition, we thank the reviewer for recognizing the fundamental concepts within our paper and highlighting the presentation of our results. In the sections that follow, we assiduously address all concerns raised by the reviewer.\n\n>**Weaknesses:**\n\n**Answer:**\n\nThank you for the feedback and for pointing out that biased gradient estimators are widely used outside classical stochastic optimization/finite-sum and distributed training settings!\n\n>The approach in [5] that constructs low-bias gradient estimators at a cheap cost at each iteration. Notably, it seems that [1,2,3] don't meet the proposed ABC condition, but the proposed biasedSGD algorithm can still achieve optimal sample complexity. For [5], the gradient estimator constructed in [5] should satisfy ABC condition or its variants but the submitted paper fails to address the potential high costs of obtaining gradient estimators that adhere to the proposed ABC assumption. The authors should discuss these limitations.\n\n  \n\nWe are grateful to the reviewers for providing a collection of pertinent and valuable references. These will be duly cited in the revised version of our paper.\n\n  \n\nIt's observed that the results from papers [1-6] don’t appear to align with our proposed ABC assumption. However, this discrepancy doesn’t diminish the value of our contribution. The ABC assumption was formulated for a different problem setup compared to that in papers [1-4].\n\n  \n\nSpecifically, papers [1,3] explore the bilevel optimization problem as shown:\n\n  \n\n$$\n\\min_{x \\in \\mathbb{R}^d} F(x):=\\mathbb{E}_{\\xi}\\left[f\\left(x, y^*(x) ; \\xi\\right)\\right]\n$$\n\n$$\n\\text { s.t. } y^*(x)=\\underset{y \\in \\mathbb{R}^{d^{\\prime}}}{\\arg \\min } \\mathbb{E}_\\phi[g(x, y ; \\phi)]\n$$\n\n  \n\nThis problem differs from ours, which exclusively addresses the unconstrained minimization problem in the form $\\min _{x \\in \\mathbb{R}^d} f(x)$ without any explicit bilevel structure. While, under a particular choice of function $f(x,y)$, the bilevel problem can imply our non-bilevel problem, this is a special case with limited relevance.\n\n  \n\nPaper [2], on the other hand, delves into a nested problem given by:\n\n  \n\n$$\n\\min_{\\theta \\in \\mathbb{R}^d} F(\\theta):=f_N\\left(f_{N-1}\\left(\\cdots f_1(\\theta) \\cdots\\right)\\right)\n$$\n\nwith $f_n(\\cdot):=\\mathbb{E}_{\\xi_n}\\left[f_n\\left(\\cdot ; \\xi_n\\right)\\right], \\quad n=1,2, \\ldots, N$\n\n  \n\nThis is also outside the purview of our paper.\n\n  \n\nPaper [6] tackles another unique problem, termed the conditional stochastic optimization problem:\n\n  \n\n$$\n\\min_{x \\in \\mathcal{X}} F(x):= \\mathbb{E}\\_{\\xi} f_\\{\\xi} \\left(\\mathbb{E}\\_{\\eta \\mid \\xi} g\\_{\\eta(x, \\xi)}\\right)\n$$\n\nover a convex set $\\mathcal{X} \\subseteq \\mathbb{R}^d$\n\n  \n\nIn contrast, the estimation method in paper [5], although orthogonal to our approach, doesn't diverge entirely since it adopts a distinct mathematical framework, specifically the MLMC.\n\n  \n\n>The proposed ABC assumption appears difficult to validate. It remains unclear when this condition should be employed.\n\n Regarding the proposed ABC assumption, we acknowledge reviewers' concerns about its applicability and will address this by directing their attention to Tables 2 and 8, illustrating specific valid scenarios.\n\nEven within classical contexts, numerous scholarly works exist. However, our research exposes a substantial gap, evident in the inadequacy of proposed assumptions in capturing common sources of bias, notably pronounced in intricate sampling schemes, a cornerstone of Federated Learning. Our work extends prior findings to encompass these settings.\n\nContrary to concerns about validation difficulty, our Assumption 9 demands fewer verifications (two) than the classical Assumption 8 (three) by L. Bottou et al. (2018). Most Machine Learning cases have nonnegative loss functions, allowing $f^{*}$ to be set to zero. Our framework embraces instances like Huber Loss, a 1-smooth convex function, and specific sampling estimators, complying with Assumption 9 while diverging from weaker Assumptions 6 and 8. This underscores Assumption 9's effectiveness in specific contexts where established assumptions falter, especially for estimators influenced by sampling bias.\n\n>**Questions:**\n\n**Answer:**\n\nThank you for your questions.\n\nRegarding the references, we value your attention to detail. While we will cross-reference the preprint sources, we are struggling to locate the 2020 publication by Ahmad Ajalloeian and Sebastian U Stich. Could you please share the source link for this publication? Your help will ensure accurate reference updating.\n\nIn Table 4, we establish a consistent rate of change based on factors like $\\kappa=L/\\mu,$ $1/\\varepsilon,$ $L,$ and $\\delta_0$. Notably, other influencing factors can be encompassed within the O-big notation. Nonetheless, we include them explicitly to emphasize that broader applicability comes with increased complexity.\n\nIf Assumption 12 proves invalid, we lack an existing analysis guaranteeing iteration-based convergence under our proposed general Assumption 9. Yet, we do guarantee function value convergence, detailed in Theorem 12 of Section G2. This assurance directly stems from Theorem 4, as Assumption 10 (Polyak–Łojasiewicz) covers a broader context than Assumption 11 (strong convexity). Consequently, Theorem 12 resides in the appendix, while Section 6.3's beginning explicitly states the applicability of Theorem 4 to Assumption 11-compliant functions.\n\nPlease feel free to seek further clarification or share the source link for the aforementioned publication.\n\nWe believe that our responses have effectively addressed your concerns. We respectfully ask you to reconsider your initial evaluation. We are optimistic that our explanations will provide greater satisfaction, and the additional information we have shared could potentially warrant a higher rating. "}]

Author rebuttal:
Dear Reviewers, it was noted by several Reviewers that there is a mistake in the proof of Theorem 2 parts viii-ix, where the absence of the reverse implications from Assumption 9 towards Assumptions 6 and 8 is established. The counterexample we provided was incorrect. We present the corrected version with the proof below. Please, kindly check it! We are intending to replace the current part of the proof with this piece.

Consider function $f$ which is $1$-smooth and lower bounded by $0:$
	$$
	f(x)= \begin{cases}\frac{x^2}{2}, & \text { if }|x|<1, \\\\ |x|-\frac{1}{2}, & \text { otherwise}\end{cases}
	$$
	(Huber Loss). Consider a biased estimator
	$$
	g(x)= \begin{cases}\nabla f(x)+\sqrt{|x|}+1 & \text { with probability } 1 / 2, \\\\ \nabla f(x)-\sqrt{|x|}+1 & \text { with probability } 1 / 2.\end{cases}
	$$
	Observe that $\mathbb{E}g(x)=\nabla f(x) + 1.$ Suppose condition (17) of Assumption 8 holds. Then
	$$
	\exists U, Q\geq 0:\quad \mathbb{E}\left[\Vert g(x)\Vert^2\right] - \Vert \mathbb{E}\left[g(x)\right]\Vert^2 \leq U\Vert \nabla f(x)\Vert ^2+Q.
	$$
Consider the point $x=U+Q+4$, then $|x|>1$ and hence $\nabla f(x)=1$ by the definition of $f.$ Then
	$$
	\mathbb{E}\left[\Vert g(x)\Vert ^2\right] \leq U+Q+4.
	$$
	On the other hand, we fall into contradiction since
	$$
			\mathbb{E}\left[\Vert g(x)\Vert ^2\right] = \frac{1}{2}\left((2+\sqrt{x})^2+(2-\sqrt{x})^2\right) = x + 4 = U+Q+8.
	$$
	It follows that condition (17) of Assumption 8 does not hold. Suppose that condition (12) of Assumption 6 holds. Then
	$$
	\exists M,\sigma^2\geq 0: \quad \mathbb{E}\left[\Vert g(x)\Vert ^2\right] - \Vert \mathbb{E}\left[g(x)\right]\Vert^2 \leq M\Vert\mathbb{E}\left[g(x)\right]\Vert^2+\sigma^2.
	$$
	Consider the point $x=4(M+1) + \sigma^2,$ then $|x|>1$ and hence $\nabla f(x) = 1$ by the definition of $f.$ Then we obtain that
	$$
	\mathbb{E}\left[\Vert g(x)\Vert^2\right] \leq 4(M+1) + \sigma^2.
	$$
	On the other hand, we fall into contradiction since
	$$
			\mathbb{E}\left[\Vert g(x)\Vert^2\right] = \frac{1}{2}\left((2+\sqrt{x})^2+(2-\sqrt{x})^2\right) = x + 4 = 4(M+1) + \sigma^2 + 4.
	$$
	It follows that condition (12) of Assumption 6 does not hold.  We now show that Assumption 9 holds: first, suppose that $x\geq 1$, then
	$$
		\mathbb{E}\left[\Vert g(x)\Vert^2\right] =\frac{1}{2}\left((2+\sqrt{|x|})^2+(2-\sqrt{|x|})^2\right)
		=\frac{1}{2}(8+2|x|)=4+|x|
$$
$$
		=\frac{9}{2}+\left(f(x)-f^{\text {inf }}\right),
	$$
	since for $|x| \geq 1$ we have $f(x)-f^{\inf }=|x|-1 / 2.$  In turn,
	$$
	\langle \nabla f(x), \mathbb{E}\left[g(x)\right]\rangle = \langle \nabla f(x), \nabla f(x) + 1\rangle \geq \Vert \nabla f(x)\Vert^2.
	$$
	Suppose that $x\leq -1,$ then $\nabla f(x) = -1,$ and
	$$
		\mathbb{E}\left[\Vert g(x)\Vert^2\right] =\frac{1}{2}\left((\sqrt{|x|})^2+(-\sqrt{|x|})^2\right) \\
		=|x| =\frac{1}{2}+\left(f(x)-f^{\text {inf }}\right).\\
	$$
	In turn,
	$$
		\langle \nabla f(x), \mathbb{E}\left[g(x)\right]\rangle = \langle \nabla f(x), \nabla f(x) + 1\rangle = \Vert \nabla f(x)\Vert^2 - 1.
	$$
	Now suppose that $|x| \leq 1$, then
	$$
		\mathbb{E}\left[\Vert g(x)\Vert^2\right] =\frac{1}{2}\left((x+\sqrt{|x|})^2+(x-\sqrt{|x|})^2\right) \\
		=x^2+|x| \leq 1+1=2.
	$$
	In turn,
	$$
	\langle \nabla f(x), \mathbb{E}\left[g(x)\right]\rangle = \langle \nabla f(x), \nabla f(x) + 1\rangle =\Vert \nabla f(x)\Vert^2+x\geq \Vert \nabla f(x)\Vert^2 - 1.
	$$
	It means that, for all $x \in \mathbb{R}$,
	$$
	\mathbb{E}\left[\Vert g(x)\Vert^2\right] \leq f(x)-f^{\mathrm{inf}}+\frac{9}{2}
	$$
	and
	$$
	\langle \nabla f(x), \mathbb{E}\left[g(x)\right]\rangle \geq \Vert \nabla f(x)\Vert^2 - 1.
	$$
	It follows that Assumption 9 is satisfied with $A=1 / 2, B=0$, and $C=\frac{9}{2},$ $b = 1,$ $c=1.$

Thank you!

Several reviewers have pointed out that our explanation for the motivation behind the newly proposed Assumption 9 is not sufficiently detailed. Specifically, the introduction of the term 2A(f(x) - f^{*}) in equation (19) lacks clarity and is not adequately addressed in the main section. When bounding the second moment of the sampling gradient estimator, it becomes necessary to bound the weighted sum of the squared norms of individual gradients. However, it is generally not feasible to bound this by the squared norm of the gradient alone (as the gradient is essentially a sum of individual gradients, and the sum of squared functions cannot always be bounded by the square of their sum) or by a constant. This rationale underscores the introduction of the A-term in equation (19), as it aids in bounding the second moment of the sampling gradient estimators.

Concerning the challenges in verifying the BiasedABC assumption, it's worth mentioning that in Machine Learning, loss functions are commonly bounded from below by $f^{*}=0$. Additionally, it's important to note that Assumption 8, introduced in the classical work by L. Bottou, involves checking three conditions as opposed to the two conditions in Assumption 9. In Tables 2 and 8, we present the constants with which numerous practical estimators meet our assumption. Furthermore, Claims 2 – 4 can aid in determining these constants for various sampling schemes.

Meta-review: The paper unifies several previous assumptions and analysis for biased gradient problems.

It is agreed upon reviewers that the paper does a good job in unifying the various existing assumptions on Biased SGD, and will serve as a good reference for future work. Nevertheless, the contribution of the paper on the algorithmic and analytic aspects feels a bit incremental. 

The paper is borderline, but all in all most reviewers believe it should be accepted and hence the decision to accept.
Decision: Accept (poster)