Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 

The paper studies a rather simple setting of convex optimization, but in a comprehensive way. 
questions: -
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

Strengths.
  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. 
  2. The results are new and very interesting, which help us to understand why ML models are often irreproducible.
  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.
  4. I believe this work opens many new directions for future study.

Weaknesses.
  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.
questions: I do have some questions for the authors though.

1. 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.

2. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
This 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. 

Weaknesses:
I 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. 

In 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!

I 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. 

Finally, 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). 

Typos:
line 249-250: "(epsilon)-deviation bounds for parametter reproducibility immediately transform into (epsilon, delta)- deviation bounds for parameter reproducibility" 
line 297: the lower bound is 1/eps + delta^2/eps^2 in the smooth setting, not 1/eps^2
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.
review_title: null

Meta-review: metareview: The paper studies how the noise inherent in optimization affects “reproducibility,” which the authors measure by the Euclidean distance between two independent runs of the algorithm. The results of the paper reveal fundamental tradeoffs between computation (in terms of gradient oracle complexity) and the proposed notion of reproducibility. The reviewers have reached a clear consensus toward accepting this paper, citing its novelty and technical depth. I concur, and recommend acceptance as a spotlight presentation.
confidence: Certain
Decision: Accept