Reproducibility in Optimization: Theoretical Framework and Limits
Authors: Kwangjun Ahn
Prateek Jain
Ziwei Ji
Satyen Kale
Praneeth Netrapalli
Gil I. Shamir
Venue: NeurIPS 2022 Accept (2022)
Keywords: reproducibility
first-order optimization
convex optimization
inexact gradient oracles

Abstract:  We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.

Reproducibility in Optimization:
Theoretical Framework and Limits
Kwangjun Ahn"
Prateek Jain Google Research praj jaijagoogneee.oooooo com
Ziwei Ji Google Research ziweiji@google, com
MIT EECS
kjahn@mit edu
Satyen Kale
Praneeth Netrapalli Google Research pietrapalli@gogg/e com
Gil I. Shamir
Google Research satyenkkle@gooogle.cco
Google Research, Brain Team gshamir@google.cm
Abstract
We initiate a formal study of reproducibility optimization. We define a quanti- tative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.
Introduction
Machine learned models are increasingly entering wider ranges of domains in our lives, driving constantly increasing number important systems. Large scale systems can be trained in highly parallel and distributed training environments, with large amount of randomness in training the models. While some systems may tolerate such randomness leading to models that differ from one another every time model retrains, for many applications, reproducible models required, where slight changes in training do not lead to drastic differences in the model learned.
Beyond practical deployments of machine learned models, the reproducibility crisis in the machine learning academic world has also been well-documented: see [Pineau al., 2021] and the references therein for an excellent discussion of the reasons for irreproducibility (insufficient exploration of hyperparameters and experimental setups, lack sufficient documentation, inaccessible code, and different computational hardware) and for mitigation recommendations, Recent papers [Chen et al., 2020, D' Amour et al., 2020, Dusenberry al., 2020, Snapp and Shamir, 2021, Summers and Dinneen, 2021, Yu et al., 2021] have also demonstrated that even when models are trained on identical datasets with identical optimization algorithms, architectures, and hyperparameters, they produce significantly different predictions
the same example. This type of irreproducibilityy may be caused by multiple factors [D Amour et al., 2020, Fort et al., 2020, Frankle et al., 2020, Shallue al., 2018, Snapp and Shamir, 2021, Summers and Dinneen, 2021], such as non-convexity of the objective, random initialization, nondeterminism in training such as data shuffling, parallelism, random schedules, hardware used, and round off quantization error.. Perhaps surprisingly, even if control for the randomness by using the same "seed" for model initialization, other factors such as numerical errors introduced due nondeterminism modern GPUs (see, e.g., [Zhuang al., 2021]) may still lead to significant differences. It was empirically shown (see, e.g. Achille et al. [2017]) that
Part of this work was done when Kwangjun Ahn was intern at Google Research.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

slight deviations early in training can lead to different optima, with substantial differences in resulting models. Thus we are forced accept some fundamental level of irreproducibility that persists even after fixing all aspects of the training process under our control.
The goal of this paper is initiate formal study of the fundamental limits of irreproducibility. In particular, we focus on the most basic training process: convex optimization. At first glance, it might seem surprising that convex optimization procedures can exhibit irreproducibility since they'r 're guaranteed to converge to an optimal solution. However, in practice, the default convex optimization algorithms are iterative first-order methods; methods that only use first-order oracle to provide an approximate gradient of the function at a given point, and converge to an approximately optimal solution. The first-order oracle a source of irrerroducibility. In stochastic gradient descent, it returns a random vector whose expectation is the true gradient. The randomness in the stochastic gradients can lead to different outcomes of the optimization process. Similarly, there are numerical errors that can arise in the computation of the gradients due to inherent nondetermism in modern GPUs. Beyond the first-order oracle, irreproduciiility may also arise in convex optimization procedures because the initial point is chosen randomly. Thus, attempt to answer the following questions for convex optimization procedures operating with the above sources of irreproduibiiityy
What are the fundamental limits of reproducibility for any convex optimization procedure? Can we design practical and efficient first-order methods that achieve these limits?
We study these questions in variety of settings; including general non-smooth convex functions, smooth convex functions, strongly-oovve functions, finite-sum functions, and stochastic convex optimization, under the different sources of irreproducibility mentioned above. To the best of our knowledge, no prior theoretical work considered such questions.
The primary contribution of this paper is conceptual: the development of rigorous theoretical framework to study the fundamental limits of reproducibility in convex optimization. The concepts developed in this framework can be extended easily to other settings of interest such non-convex optimization. The technical contribution of this paper is the development of lower bounds on the amount of reproducibility, and matching upper bounds via analysis of specifie first-order algorithms in all the different settings of convex optimization described above. Detailed technical descriptions of the results appear below in Subsection 1.1.
At a high level, our study provides the same message for all the different optimization settings we consider. On the lower bound side, we find that any first-order method would need to trade-off convergence rate (computational complexity) for more reproduciblity. On the upper bound side, we find that various forms of gradient descent, when run with lower step-size (and correspondingly, more iterations) already achieve the fundamental limits of reproducibility. One (somewhat surprising) consequence of our results is that advanced techniques like regularization, variance reduction, and acceleration do not improve reproducibility over standard gradient descent methods.
We show, for example, that when optimizing a Lipschitz non-smooth convex function f on a bounded domain using a first-order oracle that computes gradients with even vanishingly small error, two runs of any first-order method that obtains solutions that are (2))(vT)) apart in & distance. Thus, if we run the method for the standard T = ((1/2) iterations required to obtain e-approximate solution for a non-smooth function, then obtained solutions can deviate by 2(11) distance; i.c., the method is maximally irreproducible. To ensure that irreproducibility is small, i.c. that the solutions within small distance 7 of each other, we will need to run at least 0(1((??>)) iterations. Interestingly, standard gradient descent with appropriately chosen learning rate and number of iterations already achieves this trade-off.
suboptimal solution of J after T iterations can generate
Our results demonstrate the challenge of reproducibility even for standard convex optimization. While we provide matching lower and upper bounds in certain general settings, in Section 7, we outline several important open directions. Solutions to these problems should enable better understanding of reproducibility even for deep learning.
1.1 Summary of results
Table I summarizes our key results for our measure of irreproducibility, (e, -d-viiiaioonn (see Defini- tion 3). The (c, 6) deviation measures the amount of change between the outputs of two independent runs of an optimization algorithm, that is guaranteed to achieve e-suboptimality after T iterations,

---

Table 1: Summary of (e, 8)-deviation bounds for various convex optimization settings.
Stochastic Inexact
Non-stochastic Inexact
Inexact Initialization
Gradient Oracle
Gradient Oracle
Oracle
Theorem
Theorem 2
Theorem 3
Smooth
((0%)r)))
-(6")2) ( Ae)
((02)
Smooth Strongly-Cvx.
((e-(()))) Ae)
Nonsmooth
(11((T=2)
((1/(==)) + +//2)
(V/CT=2) + 6²) ((/TTAE)
Nonsmooth Strongly-Cvx.
(1/TAE))
(01)++8))E))
when the computations of the algorithm incur errors of magnitude up to 5. We specifically fo- cus on three different sources of errors: i) stochastic gradient oracles, ii) gradient oracles with non-deterministic numerical errors (Definition 2), and iii) inexact initialization for the optimizer (Definition 1). We analyze the deviation under these sources of errors for four types of function classes: smooth convex functions, non-smooth but Lipschitz convex functions and strongly-convex restrictions of the two. Throughout the paper, A b denotes the minimum between and b.
All lower bounds are for first-order iterative algorithms (a la Nesterov [2018]) that we formally define in (FOI). This is large class of iterative optimization methods, including Stochastic Gradient Descent (SGD), which construct successive iterates adaptively in the linear span of previous iterates. Additionally, for smooth costs and stochastic inexact gradient oracle, we have an information theoretic lower bound of 52 5x(6" ((re())) when S 82 (Theorem 6). We believe such informtation thhooretc lower bounds can be shown for all the settings in this paper. As for the upper bounds, they are all obtained using slowed-down SGD: i.e. SGD using smaller learning rates and more iterations.
For the non-strongly convex cases, one may expect to have high irreproducibility if the minima form a large flat region; however, surprisingly, our upper bounds show that we can always bound the extent of irreproducibility via slowed-down SGD. In the non- con-smooth cases, the main observation is that the deviation does not depend on scale of perturbation by the gradient oracle, i.e., any 8 >> 0 can lead to fairly inreproducible solutions. The non-stochastic gradient oracle setting is strictly harder than the stochastic setting. Naturally, the lower and upper bounds on reproducibility are worse. Interestingly. even though strong convexity implies uniqueness of the global optimum, which intuitively should lead to highly reproducible solutions, we show that when faced with sources of error in computations, the deviation can still be significantly large for any algorithm.
Finally, we study reproducibility of optimization in machine learning settings. Here we have additional structure such as finite-sum minimization (for optimizing training loss) and stochastic convex optimization (for optimizing population loss). We define appropriate notions of errors for these problems and analyze two settings of particular interest. Our main results (Theorem 4 and Theorem 5) show that despite the additional structure in these problems, the bounds given by Table I for the specific settings are nonetheless tight. One consequence is that more sophisticated techniques for these problems such as variance reduction don't 't improve reproducibility.
1.2 Related work
Related notions. In the scientific world, the terms reproducibilitty and replicability are often used interchangeably, but here we distinguish the two, following Pineau et al. [2021]. Reproducibility refers to the requirement that results obtained by a computational procedure (e.g. an experiment or statistical analysis of a data set) should be the same (or largely similar) when the procedure is repeated using the same code on the same data, whereas replicability is different notion that requires that results be reliably the same or similar when the data are changed. The field of statistical hypothesis testing [Lehmann and Romano, 2005] provides rigorous and principled techniques minimize false discoveries and thereby promote replicability. The notion of algorithmic stability can also be seen as quantifying the amount of change in the output when a single data sample is changed. This notion has been extensively studied in the context of providing algorithm-depende bounds [Bousquet and Elisseeff, 2001, Kutin and Niyogi, 2002] and in developing differentially private algorithms [Dwork et al., 2006, McSherry and Talwar, 2007]. In very recent concurrent work, Impagliazzo et al. [2022] define a notion of replicability learning that quite different from ours: they aim to develop algorithms that generate the exact same output with reasonable probability given
generalization
3

---

a fresh sample. Note that despite the title of their paper, technically the notion studied is replicability, not reproducibility, since they study the output of algorithms when the input data are changed.
In this paper, we specifically focus on reproducibility: how much can the results of computation differ when it is re-run on the same data with the same code? Hence, both hypothesis testing and algorithmic stability are orthogonal to the study in this paper, although some of our upper bounds use similar analysis techniques as algorithmic stability. On different note, similar to replicability, the boundary between the notions of irreproducibility and uncertainty in deep models is rather blurred. Several papers considered different aspects of uncertainty (see, e.g., [Lakshminarayanan al., 2017] and references therein), but this line of work has been empirical in nature.
Inexact oracles in optimization. The optimization community has studied the consequences of using inexact error-prone gradient oracles in optimization. Several papers (e.g. [Aybat et al., 2020, Devolder et al., 2014, d' A'Apprmoot, 2008, Cohen et al., 2018] have developed bounds on the optimization error incurred due to the use of inexact oracles. While the sources of errors are similar to the ones studied in this paper, the quantities of interest in these papers are convergence rate and optimization error rather than reproducibility. Interestingly, despite the different objective, some of the high-level conclusions are similar to our paper: for example, accelerated gradient methods do not outperform standard classical methods when used with inexact gradient oracles.
Techniques to improve reproducibility in practice. Several recent empirical papers considered methods that can reduce levels of irreproducibilityy in deep models despite nondeterminism in training. Smooth activations [Du, 2019, Mhaskar, 1997] have been shown [Shamir et al., 2020] to improve reproducibilty over popular activations, as the Rectified Linear Unit [Nair and Hinton, 2010]. Ensembles [Dietterich, 2000] leverage diversity of multiple different solutions to produce an average more reproducible one [Allen-Zhu and Li, 2020]. Co-distillation [Anil et al., 2018) and Anti-distillation [Shamir and Coviello, 2020] leverage ensembles to further push deployed models to be more reproducible. Imposing constraints [Bhojanapalli et al., 2021, Shamir, 2018] forces models to prefer some solutions over others, but may come at the cost of reducing model accuracy performance.
Robustness of dynamical systems. The upper bound results in our paper can be interpreted as robustness results of the (sub)gradient descent dynamics against disturbances. In partieular, our upper bounds can be viewed as some variants of the input-to-state stability [Sontag and Wang, 1995] results for the dynamics (see, e.g., [Tu al., 2022, Definition 3.2)).
Problem Formulation
In this section, define a quantitative measure of irreproducibility amenable to theoretical analysis. Intuitively, a computation is reproducible if it generates the exact same output given the same inputs on two different runs. Irreproducibility arises because low-level operations of a computation produce different answers on two runs due to either randomness or non-determinism.
Our computation of interest is convex optimization via first-order methods, where initialization and gradient computations are the primary operations that constitute the computation and are subject to errors leading to inexact outputs. A natural measure of irreproducibility is the amount of change in the computed solution to the convex optimization problem under inexact gradient computations or inexact initialization. However, there two nuances that must be carefully handled here. First, trivial procedure which ignores its input and outputs a constant solution is perfectly reproducible! Unfortunately, it is perfectly useless convex optimization procedure as well. Thus, in order to compare different procedures by their reproducibility metrics, we must assume that the procedures are guaranteed converge to optimal solution. The second nuance is that we need to assume that the emrors in the gradient or initialization computations are bounded in some manner. Evidently, without such an assumption. any non-trivial convex optimization procedure will be extremely irreproducible. We now use the above considerations to develop a precise definition of a measure of irreprodueibility.
Convex function classes. We assume that the function to be optimized is chosen from a certain class, F, of convex functions, along with their domains, satisfying suitable regularity conditions (e.g. Lipschitzness, smoothness, strong-convexity, etc.) to develop convergence rates. For clarity, we will suppress exact dependence smoothness, Lipschitzness, and dtron--covexxin parameters. In

---

particular, "smooth" will denote convex function whose gradients are O (11)-Lipschiz continuous, "non-smooth a convex function that Oips-Lipsh continuous, and "strongly-conwe an (+(1)- strongly-convex function. Here, O(1) and !((1) denote universal constants independent of the dimension or other problem dependent quantities, which we leave unspecified to ease the exposition.
Convex optimization procedures. Affrst-order convex optimization procedure for F is an algo- rithm that, given any function f E F, and access two (potentially noisy) oracles an initialization oracle, which generates the initial point, and gradient oracle, which computes gradients for s at any given query point- generates a candidate solution Fout for the problem of minimizing f over its domain. Note that the algorithm can only access via the oracles provided. We call such an algorithm E-accurate if it guarantees that f (Z Infgedon, f(x) S E, where the expectation is over any randomness in the computation of oou Several of our lower bounds require more structure for the algorithm: specifically, a first-order iterative (FOI) algorithm (a la Nesterov [2018] is one that starting from the point Zo generated by the initialization oracle, constructs successive iterates
xt - Bo Σí A g(x;) for some { = 0....,
(FOI)
where g(xx)) is the output of the gradient oracle query at æ; and outputs øT for some integer T > 0.
We emphasize that for all f, the coefficients ( can be chosen adaptively based on all the previous computations. The above class of algorithms a canonical one consider when proving lower bounds against gradient oracle based optimization algorithms. We refer readers to [Nesterov, 2018, $2.1.2] for more background. For the case of nonsmooth costs, we additionally assume that the coefficient of the latest gradient is nonzero, i.e., X,= * 0 for all f. We also note that one of our lower bound results (Theorem 6) is informationn-hherrtiii (in the sense of Nemirovski and Yudin [1983]).
Sources of errors in computation. Errors arise due to inexactness the outputs of the initialization or gradient oracles. Queries to these oracles on two different runs of the same algorithm might yield different outputs, but we will control the errors by assuming that the outputs are close to some reference point (that remains fixed over different runs) in suitable metric.
Definition 1 (6- bounded inexact initialization oracle). Given a function f F and a reference initialization point a." domm, a 5-bounded inexact initialization oracle for f is one that generates an initial point wo E domf such that ||000 - 20 S 6.
The gradient computation oracle is said to be 5-bounded if for any f F and any point E domf. it outputs vector g(æ) such that E [[)[z)) V {(=)] < 82 for some f((x) E (f))). where the expectation is over any randomness in the computation of g(x). We consider both stochastic and non-stochastic inexact 5-bounded gradient oracles. A stochastic gradient oracle has the additional property that its output (xx) is a random vector such that E g(x) = ffx)), with different queries being independent of each other. Stochastic inexact gradient oracles arise naturally in machine learning applications due to randomness in minibatching. Non-stochastic inexact gradient oracles model non-deterii numerical errors due the accumulation of floating point errors; for giant machine learning models with billions of parameters, individual floating point errors could add up to a noticeable large error. We formally define the two types of inexact oracles below.
Definition (S-bounded inexact gradient oracle). Given a function f E F,F, and x E domf, let ff() denote the sub-differential of f at ac.
(a) A stochastic inexact d-bounded gradient oracle outputs a random vector g(æ) such that E g(x) = (xx and EE [[g(z) f(x)]]] < 82 for some ff(x) e 0f(z). The expectation is over the randomness in g(x) which is also assumed to be independent for each oracle call.
(b) A non-stochastic inexact ô-bounded gradient oracle outputs non-deterministic vector g(æ)
such that (z)( (==)) < 8² for some V fx)) E (.)))))
Measure of irreproducibility. Let A be a first-order, s-aceurate convex optimization procedure for Ff with access to either a d-bounded initialization oracle (and an exact gradient oracle), or a 5-bounded gradient oracle (and an exact initialization oracle). The (E, dddeviatioon is Definition 3 ((e, -)dveiiai,,) Given a function f E F, let æ and x', denote the outputs of A on two independent runs of A that result in E-accurate solutions.
(a) If a stochastic inexact 5-bounded gradient oracle is used, the (e, d--deiianoon of A is defined as sup E ر| 2²yl12 where the randomness is over the stochastic oracle in the two runs.
5

---

(b) eeethe an inexact 6-bounded initialization oracle or 6-bounded non-stochastic inexact gradient oracle used, the (E, -dddviiatoonn of is defined as supjer sup || e'yll" where the inner supremum is over the two runs.
Here we note that z/ is not necessarily the last iterate of first-order algorithm. Depending on cases, sometimes choose #y be the (weighted) average iterate. We consider || - xry 2|² for the notion of deviation instead of y - x I12; note that x" may not even be unique without strong convexity.
Other notions? Alternate definitions certainly plausible. For example, in machine learning applications, the computed solution æ may be used as a parameter vector for a predictor func- tion Sa which maps inputs to real-valued predictions ý whose quality is measured by loss function E(ý. y) where is the true label of 2. Let æ and x' be outputs of two different runs of the optimization algorithm. Then one can also define (e.6)-dvviation based on prediction reproducibility; e.g. sup= (x) - I (w)(2) (z)l or E, (gx(z) gx) (2)], or loss reproducibility: c.g. (2.)) (((ge(z).)) - ((gx(()),)) x)) or (2,)) (2)) y) E(gr (z), y)), where the expectation adopt Definition 3, which is based on parameter reproducibility, in this paper for the following reasons:
is over the distribution of the examples. Nevertheless,
The convex optimization problems studied in this paper are more basic/fundamental than more structured ML optimization. To the best of our knowledge, there no pre-existing theory even for this basic setting. Parameter reproducibility is a more natural definition here since there is no notion of prediction or loss.
In many ML applications, the predictor function Sa is Lipschitz in æ for any input z. In such cases, (5, deeviatinn bounds for parameter reproducibility immediately transform into (s. 6)- deviation bounds for prediction reproducibility. Similar transformations are also generally possible (s, deveiaion bounds for loss reproducibility.
Without knowledge of how a learned parametric function is deployed for making predictions, it is difficult analyze prediction reproducibility even in ML settings. Hence, parameter deviations provide a reasonable first approximation. Furthermore, in real systems, we often optimize multiple metrics (e.g. performance on sub-segments of populations, for fairness). Parameter reproducibility gives greater assurance on all metrics. A similar argument applies when the test distribution is different from the training distribution.
Finally, several recent works [Shamir et al., 2020, D' Amour al., 2020] have empirically observed that even if two different runs of the algorithm resulted in parameters that have nearly the same loss, the predictions test examples could be very different. One reason this happens is because surrogate losses are used in place of the true metric for optimization. So simply achieving loss reproducibility may not be sufficient for practical applications.
Reproducibility with Stochastic Inexact Gradient Oracles
In this section we consider reproducibility of optimizing convex function f E F where we can access ff only via a stochastic gradient oracle (see Definition 2). This setting covers several important ML optimization scenarios, e.g., when the training data is randomly sampled from population or when the selection mini-batches is randomized. Our main result is the following theorem.
For any E, 8 >> O, and number of iterations T. the (e, -)-eiiiin for optimizing convex functions with a stochastic inexact gradient oracle as follows. Unless indicated otherwise, the lower bounds hold for any FOI algorithm, and the upper bound is achieved by stochastic gradient descent for T = ((1=2)) in the non- won--stonggl-cooveee settings and T 2(1/e) in the strongly-conver settings.
Theorem 1.
Smooth functions: (e, d)-viiaan is ((f((T)))) Furthermore, for the case e S there is matching information theoretic lower bound.
Smooth and strongly convex functions: (e, -)deiiiai is O As).
Lipschitz (non-smooth) functions: (g, 8) -deviatio is (()((T=)).
Lipschitz (non-smooth) and strongly convex functions: (E, -edeiaiio is 0(1/r As).

---

This theorem is proved in several pieces, one corresponding to each setting (i.e., smooth, smooth & strongly convex etc.) and type of bound (i.e., upper or lower). The precise details are given in Appendix A. A few remarks are in order.
Intuitively, smoothness would ensure that a slight error in gradient computation need not imply catastrophic deviation in the iterates. Our matching upper and lower bounds confirm this intuition.
Smoothness:
Non-smoothness: Our results show that even a slight amount of noise in the gradients can lead to drastic imrerroduciiiltty in the non-smooth case. Intuitively, the reason for this phenomenon is that non-smooth functions have non-differentiable points where the slightest amount noise in the gradients can lead to drastically different behavior. This is in line with the empirical observations of Shamir et al. [2020].
Strong convexity: Note that the deviation is smaller than other cases due to the existence of a unique minimizer; the e-aceuracy in the cost already implies an O(e) upper bound on the deviation.
Furthermore, in all the settings, our results show that using an algorithm with larger number of iterations is more helpful; intuitively that is because more gradient samples from the oracle can help reduce the sample noise as an averaging. For example, for smooth functions. if gradient descent type method is run for the standard T O(Y=²) iterations, then the solution obtained might still suffer deviation of 82, which is independent of E. Thus. in order to obtain low deviation, we are forced to run the method for =1/22)) iterations. We also note that by relying on the standard convergence rate lower bounds [Nemirovski and Yudin, 1983], the requirement on 7 e.g.. T = S21 ((1/e²) for the non-strongly convex setting, is without loss of generality. Finally, we remark that the lower bound for smooth functions is information theoretic (i.e., holds against any algorithm) for & S 8².
4 Reproducibility with Non-Stochastic Inexact Gradient Oracles
In this section, we study reproducibility for optimizing function f E FF with non-stochastic inexact gradient oracle access (Definition 2). In particular, we establish lower and upper bounds for first- order algorithms (FOI) on the (s, (deviidiiitioon (Definition 3) despite initialization with the same point To E domf. Recall that this setting allows us to capture reproducibility challenges due to non-deterministic numerical errors introduced by computing device (like GPUs) during floating point computations. The main high-level message here is that unlike in the stochastic gradient oracle case, in the non- non-stochastic gradient oracle setting the iteration complexity T has little to no effect on the (c, 5) -eveiiaiio:: intuitively this because unlike the stochastic setting, is not possible to reduce the error in the gradients by taking more samples and averaging.
Theorem 2. For D O(1), E such that 8 S 5/(2D), and number of iterations T, the (c, 6)- deviation for optimizing convex functions whose optimum has norm at most D with a non-stochastic inexact gradient oracle is as follows. Unless indicated otherwise, the lower bounds hold for any FOI algorithm, and the upper bound is achieved by projected gradient descent for T = M(1fe) in the smooth settings and non-smooth strongly convex setting, and 221/2) in the non-smooth setting.
Smooth functions: (s, -'deviatio is ((6)22))
Smooth and strongly convex functions: (E, 8) -eveiaiin is ( AE).
Lipschitz (non-smooth) functions: ( deviation is ((/(cr3) + 8/2).
Lipschitz (non-smooth) and strongly convex functions: (E, - is @((/r + 8²) A AE).
Like Theorem 1, this theorem is proved in several pieces; see Appendix A. Some remarks follow:
Accelcration v.s. reproducibility? Note that for smooth functions, accelerated methods can get e-suboptimality in only T 0(%/z) iterations. A natural question is if we can achieve similar (c, 6) -dvviiiioooonn for such accelerated methods. However, it is known that accelerated methods are unstable (see e.g., [Devolder et al., 2014, Attia and Koren, 2021]), and cannot even achieve the desired e-accuracy under the inexact oracle model. Hence, we conjecture that iteration complexity of ((1/e) is necessary achieve the desired reproducibility.
Note that Theorem 21 provides similar upper bound result without the assumption that the optimum lies in ball of radius O()).
7

---

Nonsmoothness: Note that the lower bound shows that if gradient descent style methods are run for the standard T 1//E² iterations, then the solutions can be foreed have (1(1) deviation. Hence, to ensure reproducibility, any method would need to have slower convergence rate than T = 1/8..
5 Reproducibility with Inexact Initialization Oracles
We now study reproducibility for optimizing a function f F with an inexact initialization oracle (Definition 1) and establish tight bounds on the (e, -ddeviattn for FOI algorithms. An inexact initialization oracle models situations where the initial values of the parameters are set randomly, or incur some nonddeteriiiistic numerical error.
For any E, 0 and number of iterations T, the (e, -ddiiiiinnnonn for optimizing convex functions with an inexact initialization oracle is as follows. In all cases, the lower bounds hold for any FOI algorithm, and the upper bound achieved by gradient descent for T = (2(1/)) in the smooth settings and non non-smooth strongly convex setting, and T = () in the non-smooth setting.
Theorem 3.
Smooth functions: (e, (..-)ddee -dveviian is (
Smooth and strongly convex functions: (c, 8) -deviatio is (((exp(-9(T))) Λe).
Lipschitz (non-smooth) functions: (e, -'eeiiiin is ((/(T=²) 8²).
Lipschitz (non-smooth) and strongly convex functions: (c, (5,5)- deviiaioo is ((1/TAE)
Like Theorem 1, this theorem is proved in several pieces; see Appendix A. A remark follows:
Nonsmoothness: As in the case of non-smooth optimization with inexact gradient oracles, here as well we see that even the slightest amount of inexactness in initialization can lead non-negligible ireerrducibility. Intuitively this is consequence of mooshmotth:ss:: If the function is not dif- ferentiable the reference point, even a slight bit of inexactness can lead to drastically different trajectories right from the beginning.
6 Reproducibility in Optimization for Machine Learning
So far, we have studied reproducibility in general convex optimization with different sources of perturbation. machine learning, however, optimization problems come with more structure, and hence more nuanced analysis of reproducibility is called for. In this section, we study reproducibil- ity in two specific optimization settings of interest machine learning: finite sum minimization which corresponds to minimizing training loss, and stochastic convex optimization (SCO), which corresponds to minimizing population (or test) loss. Instead of detailed study of different types of convex functions as done in the previous sections, here we focus on few specific cases that yield particularly interesting insights.
6.1 Optimizing Training Loss (Finite Sum Minimization)
Optimizing the training loss in ML can be cast minimizing a function that be written 1 E f((x). Typical optimization methods such finite sum of component functions: f(x) := m stochastic gradient descent can be implemented solve such problems by iteratively sampling one of the component functions and taking its gradient. So randomness in sampling as well as non- deterministic numerical errors in computing of gradient can lead irreproducibility. Randomness in sampling is a property of the algorithm and hence under the control of the algorithm designer; however non-deterministic numerical errors in gradient computations are beyond the control of the designer, and hence we aim to quantify irreprodueibility caused by this specific source (numerical errors). To capture this intuition, we consider the following inexact gradient oracle.
Definition 4 (6-bounded inexact component gradient oracle). A 8-bounded inexact component gradient oracle takes as imput i E (1,2...., m and a point x, and outputs a vector 9;(x)) such that
(z) (. < 82 for some v f(()) 0f((w)).
The number of calls to the component gradient oracle is now our primary measure of complexity. Then, a natural question that arises is whether we can we tightly characterize reproduciblity of typical first-order methods when given access to an inexact component gradient oracle. We first observe

---

that in the special case that all f; are identical, the inexact component gradient oracle reduces to the non-stochastic inexact oracle (Definition 2). Hence, for the smooth and non-smooth function settings. we immediately obtain lower bounds on the (e, ---diiiano via our previous analysis; see Theorem 8 and Theorem 14, respectively.
The non-smooth case in particular is interesting, as the deviation lower bound is (2(3/(T>)) + 6*/²") where T is the number of oracle calls. Now, if we use projected (full-batch) gradient descent (as used for the matching upper bound in Theorem 27), then each iteration would require m oracle calls, hence the (e, 8) deviiatio for such method is ((T/(r=²)- + 5 /=),, which is worse than the lower bound mentioned above. Now, the key question is whether we can reduce this deviation by other means. It turns out that stochastic gradient descent (SGD), where in each step we sample component function to query randomly, when run with an appropriate learning rate and using averaging, matches the optimal deviation up to constant factors. We provide a detailed proof of the result in Appendix G. This provides another justification for using SGD instead of gradient descent in practice.
Theorem 4. For G = 011 and D = O()) let fe be an G-Lipshhitz convex cost function for each i E [m], and assume that the optimum of lies in a ball of radius D. Let > 0 be given parameters such that 8 S 5/(2D), and T = (21/=²) be a given number of iterations. Define the SGD updates as follows: initialize En 0, and for t 0, .,,...? -T where is ~ [n] uniformly at random. Under the inexact component gradient oracle (Definition 4), the average iterate Tr of SGD with stepsize 1 (2/(eT)) satisfies E f(Ør) inf Edom f(x S e and
T-1,
1, set L++1 2t 14.9, (I1a)
aT - 11 = 01/cre/) + 5222), where x is the output of an independent run of SGD.
6.2 Optimizing Population Loss (Stochastic Convex Optimization)
The fundamental problem of machine learning is to find the solution to the following population (or test) loss minimization problem: minimize F(x) Egg= f(x E). where E is an unknown distribution on the examples ç, given access to an oracle that sample from E. When the function F is convex, this is also known as Stochastic Convex Optimization (SCO).
In this setting, the sampling oracle is a natural source of irreprodueibility of optimization methods. To model this, we consider the stochastic global oracle, inspired by Foster et al. [2019].
Definition (6-bounded stochastic global oracle). Given a function F, a 8-bounded stochastic global oracle for F is an algorithm that, on each query, draws an independent sample & E from some distribution E, and outputs a function f((,E) domF + R such that for all x E domF,, we have
F(x)= = Bę-= (xx E), and, E (= {) F()))] 82.
Since in each query, the stochastic global oracle returns the complete specification of f(-,), an algorithm using such an oracle has access to (z, (xx ff(x. E), f²,( for all æ.
Note that the inexact stochastic gradient oracle of Definition 2 is weaker form of the stochastic global oracle. Thus, the key question is: under the powerful stochastic global oracle, can we provide better reproducibility than the lower bounds in Theorem 1? Surprisingly, the answer the above question is negative. That is, despite the stronger oracle setting, there is a function class for which the lower bound on (E, --deviation matches that of Theorem 1.
Theorem S. Assume that < 1/200 and & S 82. Then there exists a family of population costs Fa( = RE-P, fo(xr, {) parametrized by E [1, and 8-hounded stochastic global oracle for Fo. satisfying the following property. Suppose that A is any algorithm that for each 0 E [1,2] uses at most T queries to the stochastic global oracle and outputs 27 that is e-accurate, i.e., E FF inf Fo(x)) S E. Then, there exists 0oad E [1,2] such that Var 2 ((T:))) Pasd
See Subsection B.2 for a detailed proof. On the other hand, Theorem I also shows that standard SGD with the weaker inexact stochastic gradient oracle achieves this lower bound.
7 Conclusions
We presented a framework for studying reproducibility convex optimization, and explored limits of reproducibility for optimizing various function classes under different sources of errors. For each of these settings, we provide tight lower and upper bounds on reproducibility of first order iterative algorithms. Overall, our results provide the following insights: a) Non-smooth functions
9

---

can be highly susceptible to even tiny errors which can creep in due to say numerical errors in GPU. Thus introducing smoothness in deep learning models might help with reproducibility. b) Generally, gradient descent type methods with small learning rate are more reproducible. c) In finite-sum settings, despite more randomness, SGD more reproducible than full-batch gradient descent.
The study in this paper is first step towards addressing the challenging problem of reproducibility in rigorous framework. So, many important directions remain unexplored. For example, study of reproducibility of adaptive methods like AdaGrad that are not captured by (FOl) is interesting. We study reproducibility in a strict form where we measure deviation in terms of the learned parameters of the model. However, in practice, one might care for reproducibility in model predictions only. So, extending our results such ML-driven scenarios should be relevant practice. Finally, while our lower bounds on reproducibility obviously also hold for non-conver optimization, extension of the upper bounds to non-convex settings and potentially, designing novel rigorous methods this setting is a fascinating direction for future work.
Acknowledgments and Disclosure of Funding
Kwangjun Ahn was supported by graduate assistantship from the NSF Grant (CAREER: 1846088), the ONR grant (N00014-200 --2994 and MITTIBM Watson as well as Vannevar Bush fellowship from Office of the Secretary of Defense. Part of this work was done while Kwangjun Ahn was visiting the Simons Institute for the Theory of Computing, Berkeley, California.
References
A. Achille, M. Rovere, and S. Soatto. Critical learning periods deep neural networks. arXiv preprint /rXiv::/111 171.08866,, 2017.
Z. Allen-Zhhe and Y. Li. Towards understanding ensemble, knowledge distillation and self diftiistillation in deep learning. arXiv preprint arXiv:2012.09816, 2020.
R. Anil, G. Pereyra, A. Passos, R. Ormandi, G. E. Dahl, and G. E. Hinton. Large scale distributed neural network training through online distillation. arXiv preprint arXiv:/804.0322 2018.
A. Attia and T. Koren. Algorithmic instabilities of accelerated gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
N. Aybat, A. Fallah, M. Gurbuzbalaban, and A. Ozdaglar. Robust accelerated gradient methods for smooth strongly convex functions. SIAM Journal on Optimization, 30(1):717-751, 2020.
N. Bansal and A. Gupta. Potential-funetion proofs for gradient methods. Theory of Computing, 15 (1):1-32 2019.
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:4381-439) 2020.
H. H. Bauschke, P. L. Combettes, al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
S. Bhojanapalli, K. Wilber, A. Veit, A. S. Rawat, S. Kim, A. Menon, and S. Kumar. On the reproducibility of neural network predictions. arXiv preprint arXiv:2102.03349 2021.
O. Bousquet and A. Elisseeff. Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems, pages 196-202, 2001.
Bubeck. Convex optimization: algorithms and complexity. arXiv preprint 140.::1405.4980, 2014.
Z. Chen, Y. Wang. D. Lin, D. Cheng, L. Hong, E. Chi, and C. Cui. Beyond point estimate: Inferring ensemble prediction variation from neuron activation strength in recommender systems. arXiv preprint arXiv:2008.0700 2020.
M. Cohen, Diakonikolas, and I.. Orecchia. On acceleration with noise-corrupted gradients. In International Conference Machine Learning, pages 1019-1028, PMLR, 2018.
10

---

A. D' Amour, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, Eisenstein, M. D. Hoffman, F. Hormozdiari, N. Houlsby, S. Hou, G. Jerfel, A. Karthikesalingam. M. Lucic, Y. Ma, C. McLean, D. Mincu, A. Mitani, A. Montanari, Z. Nado, V. Natarajan, C. Nielson, T. Osborne, R. Raman, Ramasamy, R. Sayres, J. Schrouff, M. Seneviratne, S. Sequeira, H. Suresh, V. Veitch, M. Vladymyrov, X. Wang. K. Webster, S. Yadlowsky, T. Yun, X. Zhai, and D. Sculley. Underspecification presents challenges for credibility in modern machine learning. arXiv preprint arXiv:2011.03399, 2020.
A. d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal Optimization, 190):1171-1183, 2008.
O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(():37-75, 2014.
T. G. Dietterich. Ensemble methods machine learning. Lecture Notes in Computer Science, pages 1-15, 2000.
S. Du. Gradient Descent for Non-convex Problems in Modern Machine Learning. PhD thesis, Carnegie Mellon University, 2019.
M. W. Dusenberry, D. Tran, E. Choi, J. Kemp, J. Nixon, G. Jerfel, K. Heller, and A. M. Dai. Analyzing the role model uncertainty for electronic health records. In Proceedings of the ACM Conference on Health, Inference, and Learning, pages 204-213, 2020.
C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876 Lecture Notes Computer Science, pages 265-284. Springer, 2006.
Y. C. Eldar. Minimum variance in biased estimation: Bounds and asymptotically optimal estimators. IEEE Transactions on Signal Processing, 52(7):1915-1930 2004.
S. Fort, H. Hu, and B. Lakshminarayanan. Deep ensembles: A loss landscape perspective. arXiv preprint arXiv: 1912000777 2020.
D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference Learning Theory, pages 1119-335. PMLR, 2019.
J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning, pages 3259-3269. PMLR, 2020.
R. Impagliazzo, R. Lei, T. Pitassi, and J. Sorrell. Reproducibility in learning. To appear at STOC 2022 N1t.::22011084::00 2022.
S. Kutin and P. Niyogi. Almost-everywhere algorithmic stability and generalization error. In UAI, pages 275-282, 2002.
B. Lakshminarayanam, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty cstimation using deep ensembles. In Advances in neural information processing systems, pages 6402-6413. 2017.
E. Lehmann and Romano. Testing statistical hypotheses. Springer, 2005.
McSherry and K. Talwar. Mechanism design via differential privacy. FOCS, pages 94 103. IEEE Computer Society, 2007.
H. Mhaskar. On smooth activation functions. In Mathematics of Neural Nenworks, pages 275-279, Springer, 1997.
V. Nair and G. E. Hinton. Rectified linear units improve restricted Boltzmann machines. In ICML, 2010.
A. S. Nemirovski and B. Yudin. Problem complexity and method efficiency optimization. Inley--nterscienne, 1983.

---

Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
J. Pineau, P. Vincent-Lamarre, K. Sinha, V. Larivière, A. Beygelzimer, F. d' Alché Buc, E. Fox, and H. Larochelle. Improving reproducibility in machine learning research: a report from the NeurIPS 2019 reproducibility program. Journal of Machine Learning Research, 22, 2021.
C. J. Shallue, J. Lee, J. Antognini, J. Sohl-Dickstein, R. Frostig, and G. E. Dahl. Measuring the effects of data parallelism on neural network training. arXiv preprint arXiv: 1.06600 2018.
G. I. Shamir. Systems and methods for improved generalization, reproducibility, and stabilization of neural networks via error control code constraints, 2018.
G. I. Shamir and L. Coviello. Anti-distillation: Improving reproducibility of deep networks, arXiv preprint arXiv:2010.09923, 2020.
G. I. Shamir, D. Lin, and L. Coviello. Smooth activations and reproducibility in deep networks. arXiv preprint arKiv:2010.099: 0.9901,.99........... 2020.
R. R. Snapp and G. I. Shamir. Synthesizing irreproducibility in deep networks. arXiv preprint arXiv:2102. 10696, 2021.
E. D. Sontag and Y. Wang. On characterizations of the input-to-state stability property. Systems & Control Letters, 24(5):351-355 1995.
C. Summers and M. J. Dinneen. On nondeterminism and instability in neural network optimization, 2021.
Tu, A. Robey, T. Zhang, and N. Matni. On the sample complexity of stability constrained imitation learning. Proceedings of the 4rd Conference Learning for Dynamics and Control, arXiv preprint arXiv:2102.09166 2022.
H. Yu, Z. Chen, D. Lin, G. Shamir, and J. Han. Dropout prediction variation estimation using neuron activation strength. arXiv preprint arXiv:2110.06435, 2021.
D. Zhuang, X. Zhang, S. L. Song, and Hooker. Randomness in neural network training: Character- izing the impact of tooling. arXiv preprint arXiv:2106.1187. 2021.
12


Reviews:
[{"review_id": "ab1kjBP2hZ1", "reviewer": "Reviewer_YXF1", "summary": "This paper considers the reproducibility of convex optimization algorithms, meaning roughly how much the parameters output by an optimization algorithm can change when the algorithm is run a second (on the same data). The paper studies the reproducibility of first-order convex optimization algorithms under three different types of noise/errors: stochastic gradient noise, inexact gradient computations, and inexact initialization. In all cases, the paper shows that such noise/errors can lead the output of two independent runs of the same algorithm to differ by an amount which depends mainly on (1) the amount of noise/errors, (2) the final optimization accuracy, and (3) the number of iterations used by the algorithm. Tight upper and lower bounds are proven in a number of settings, and one of the main upshots is that in order to match the reproducibility lower bounds, it is necessary to run an optimization algorithm for more iterations than are needed just to reach the desired accuracy.", "questions": "This work looks at something similar to the classic idea of numerical stability. I am not personally super familiar with this literature, but I would be shocked if the numerical stability of various optimization algorithms had not been studied before, and if it has been, it would be good to discuss similarities/differences in the related work section. Have you searched for this type of paper? Is there just nothing relevant?", "limitations": "See weaknesses above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis is an interesting paper with a somewhat new perspective on convex optimization algorithms, and the paper is well-written and clear in how it presents its ideas. I read through the proofs of the theoretical results, and they appear correct to the best of my knowledge. The identified tradeoff between reproducibility and computation is quite intriguing---I have not seen anything like this before, and it seems like something that is worthy of additional investigation. Overall, I think this paper brings some interesting new ideas to the optimization community. \n\nWeaknesses:\nI think that at several points in the paper, it would be useful to make things more concrete with some examples. I feel this most strongly in the discussion of inexact initialization and the (non-stochastic) inexact gradient oracle. In particular, it seems from the motivation that the main source of inexactness would come essentially from numerical errors? If so, it seems to me that \\delta in this case should be extremely small, roughly machine precision, or perhaps machine precision times the square root of the dimension. If this is the case, the irreproducibility level shown in Theorems 2/3 in all cases excluding the non-smooth, non-strongly convex case seem like they would be quite small, and it's not clear to me that we would have anything to worry about here. \n\nIn the strongly convex settings, I feel that the level of irreproducibility is somewhat exaggerated in the prose below the theorems. E.g. around line 283, I don't think that it is the least bit surprising that irreproducibility can manifest at all---of course deviations in the gradients will affect the solution *some* amount, although presumably not too much. And indeed, the level of irreproducibility shown is at most epsilon, which seems quite small, and probably nothing to worry about!\n\nI am also a little skeptical about the formulation of the stochastic optimization oracle and the \"optimizing the population loss\" settings. In particular, if you are someone that is worried about reproducibility, then wouldn't you want to fix the order in which you use your samples? In this case, although there still might be some discrepancy between different runs (due to, e.g., non-stochastic inexactness in the gradient computations, inexact initialization, etc), it would likely be at a much smaller level since corresponding gradients calculated by each run of the algorithm would be based on the same sample. \n\nFinally, I have one slightly unfair complaint, which I don't weigh too heavily since it is a little unfair, but I want to mention it in case there might be a way to address this in future versions of the paper. Essentially, I found all of the results in the paper to be fairly obvious. Although there is a bit of a difference between looking at the iterate distance from the solution \\| x_f - x* \\|^2 and the reproducibility \\| x_f - x'_f \\|^2, these are very similar quantities, and unless I am mistaken, all of the results in this paper can basically be rephrased as saying that these quantities are within a constant factor of each other in the worst case (e.g. I'm pretty sure that Theorem 1 holds as stated also for the quantity \\mathbb{E} \\| x_f - x* \\|^2). \n\nTypos:\nline 249-250: \"(epsilon)-deviation bounds for parametter reproducibility immediately transform into (epsilon, delta)- deviation bounds for parameter reproducibility\" \nline 297: the lower bound is 1/eps + delta^2/eps^2 in the smooth setting, not 1/eps^2", "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": "YWl0KASRF4q", "reviewer": "Reviewer_aZPs", "summary": "This paper studies the notion of reproducibility in convex optimization, defined as the requirement that two runs of the algorithm on the same input should produce the same (or similar) output. The authors define a quantitative notion of irreproducibility (the ($\\epsilon,\\delta$)-deviation) which measures how much an algorithm (that successfully minimizes the objective up to error $\\epsilon$) can change the output when the algorithm has an error of up to $\\delta$. The errors can come from stochastic gradient oracles, or numerical error, or inexact initialization. For each source of error, the authors compute tight bounds on the ($\\epsilon,\\delta$)-deviation for first-order methods, in the cases of smooth and non-smooth, convex and strongly convex functions. The authors also show results for optimization problems motivated by machine learning, including finite-sum optimization and stochastic convex optimization, and show the bounds are tight.", "questions": "-", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a nice paper that studies an interesting conceptual question and proposes a quantitative analysis and answers. The paper is well-written and well-motivated, with good discussion of alternative notions. The setup and definition is clear and concise. The results on the tight bounds on the deviations are very nice, and some of the results surprising. \n\nThe paper studies a rather simple setting of convex optimization, but in a comprehensive way. ", "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": "DFzycLzkCN", "reviewer": "Reviewer_Vi1H", "summary": "This paper studies the reproducibility in optimization and provides the first theoretical framework to analyze the irreducibility of optimization algorithms in modern machine learning problems. The authors have provided the $(\\epsilon, \\delta)$ deviation of first-order stochastic optimization algorithms in different problems (strongly convex, convex smooth, convex non smooth), and support the bounds with information-theoretical lower bounds. The paper is mainly theoretical.", "questions": "I do have some questions for the authors though.\n\n1. Does the results in Table 1 imply that reproducibility is better (i.e., the deviation is smaller) when we do not converge to the neighborhoods of the optimum(i.e., when $\\epsilon$ is large instead of small)? I find it a little bit hard to interpret the results in this direction and I wonder what the authors think. Please correct me if I think it wrong.\n\n2. Although the authors mention that irreducibility for non convex optimization is another potential direction, I do not think it is quite possible to derive an upper bound in the non convex case since convergence in nonconvex problems is (usually) measured by the stationarity in gradients, and any two stationary points can be far away from each other. Therefore, I cannot think of an easy way to adapt the results in this paper to the non convex case. It's worth discussing though.", "limitations": "yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As a theory person, I like the paper very much. The fundamental problem of irreducibility in machine learning is common and cannot be ignored. However, in real-life people simple re-train the models and use the one with the highest performance. This paper is, as far as I know, the first one that studies the problem rigorously and I really appreciate the results.\n\nStrengths.\n  1. The paper is very well-written, with clear notations, nice results, good presentations and easy-to-understand words and sentences. I thank the author for writing such a good paper. \n  2. The results are new and very interesting, which help us to understand why ML models are often irreproducible.\n  3. The authors have nice analysis results in different cases (strongly convex, convex smooth, convex non smooth), and support all of them with lower bounds.\n  4. I believe this work opens many new directions for future study.\n\nWeaknesses.\n  I cannot find any obvious weakness of this paper. I believe as a theory paper, it is already good enough. If the authors can have some simple experiments in convex optimization to support their claims, it would be even better. However, I believe the paper is good as it is.", "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