Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization

Summary

This work proposes optimization algorithms that achieve optimal convergence rate and reproducibility for the settings of convex optimization and convex-concave minimax settings. This work settled some of the open questions from the previous work, and extend the results to the minimax setting.

Strengths

- Clear presentation. - Novel technical contributions. - Strong theoretical results and cleanly written proofs.

Weaknesses

- Overall, the presentation is very clear, and the results are rigorous, and I didn't see any major weaknesses. - Some details about Inexact-EG would have been helpful since it seems like a new method developed in this work. In particular, is it a direct extension of Devolder et al. to the minimax setting?

Questions

- Regarding the O(delta^2/\eps^{2/5}) bound on the reproducibility, do you have some intuitions as to why improving upon this would be difficult? Even if it's a heuristic argument, it would help readers understand the main challenge.

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.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

- They discussed them well in the conclusion section.

Summary

The authors proposed and studied optimization algorithms in both the convex and the convex-concave minimax setting, where both the criteria of convergence and reproducibility are measured. The authors provided upper bounds on these criteria for the proposed algorithms that matches nearly all of the lower bounds. While I'm not an expert on this subject (and I leave the judgement of correctness to other experts in this area), I believe this work has reached satisfying results, and I would recommend accept.

Strengths

1. The upper bounds on convergence and reproducibility matches nearly all of the known lower bounds. 2. The presentation of the work is quite clean and readable.

Weaknesses

N/A

Questions

N/A

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.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

The authors investigate the reproducibility problem of algorithms that solve convex and convex-concave minimax optimization problems. They propose new methods with better reproducibility guarantees while maintaining the theoretical state-of-the-art convergence rates.

Strengths

*I want to acknowledge that I got this paper for review **after the deadline**, so I didn't have much time to check every detail, especially the proof.* The idea of using regularization is good. It leads to new theoretical state-of-the-art convergence rates and reproducibility guarantees. This is a solid contribution to the NeurIPS community.

Weaknesses

1. The new method requires $\epsilon$ and the distance $D$ between the starting point $x_0$ and $x^*.$ (e.g. Theorem 3.3.) I am not sure that the previous methods in Table 1 need these parameters. Do the authors discuss these important limitations? 2. Algorithm 1 is a well-known method in the optimization community. For instance, see https://arxiv.org/pdf/1603.05642.pdf. It is called "regularization technique" or "regularization reduction." I believe that the authors should cite the previous works that consider Algorithm 1. 3. Wrong citation [55] in Theorem 3.3. The paper [55] doesn't provide an analysis of AGD for strongly convex functions. It is better to cite any of Nesterov's books.

Questions

.

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.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

.

Summary

The paper considers the problem of ensuring reproducibility in convex optimization. It builds on a recent framework for understanding reproducibility initiated by Ahn et al. The paper considers both minimization and minimax optimization (the latter being a new setting investigated in this work). The key results of the paper are the following: 1. Minimization problems: The paper shows an improvement in the convergence-reproducibility tradeoffs under inexact initialization and inexact gradients compared to the results of Ahn et al. For inexact initialization, the paper shows that an L2 regularized version of AGD simultaneously obtains optimal convergence and optimal reproducibility. For inexact gradients, the same algorithm obtains sub-optimal reproducibility but with optimal convergence. 2. Minimax optimization: L2 regularized versions of existing algorithms achieve optimal reproducibility and near-optimal gradient complexity. Similar to Ahn et al., SGD attains optimal reproducibility and convergence under a stochastic gradient oracle.

Strengths

1. The problem of developing reproducible optimization algorithms is well-motivated and relevant. Various empirical studies have shown that randomness in initialization, training, data augmentation and numerical instabilities can lead to models which make significantly different predictions on test points. 2. The paper demonstrates a valuable algorithmic principle of using L2 regularization to ensure reproducibility. All the results in the paper (apart from those for a stochastic gradient oracle) are obtained by incorporating L2 regularization into prior algorithms. The results strongly suggest that there could be deeper connections between stability and reproducibility, since L2 regularization is also a similarly useful techniques for ensuring algorithmic stability. Investigating this could be an interesting direction of future work. 3. The paper improves stronger bounds across a number of settings compared to prior work. It also demonstrates that suspected instability issues of AGD are not a barrier to obtaining reproducibility guarantees for it. The paper also broadens the study of reproducibility to minimax optimization, with a similar message for it.

Weaknesses

1. The writing of the paper is decent overall, but could do with some improvements. The paper does not motivate reproducibility adequately on its own. Some of the comments seem to concern reproducibility in science broadly rather than the particular issues which concern reproducibility in modern ML. Since the paper has a lot of different results, some more intuition behind the specific bounds that are obtained could be useful. For example, the paper could comment on the reproducibility obtained in different settings and why these bounds arise from the algorithm. 2. Though I can understand that there is not too much space given the number of results, some intuition for the technical ideas which go into the bounds would be good as well. In particular, what are the main ideas behind extending reproducibility to minimax optimization? Does the intuition for why L2 regularization works for reproducibility in minimization mostly carry over and give the bounds for minimax optimization?

Questions

Overall, this paper makes a good contribution on a relevant problem and I don't have any major concerns or questions. Some other suggestions are included above.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

These are discussed adequately.

Summary

The paper studies the problem of reproducibility in convex optimization. The notion of reproducibility, borrowed from prior work, measures the "stability" of the output of a procedure under noisy initialization or gradient computation. For the smooth convex setting, they design an algorithm based on running accelerated gradient descent on a regularized objective, which achieves optimal reproducibility and convergence rate. This answers an open question from prior work. The authors further extend their results to the minmax optimization setting deriving many new results.

Strengths

1. Reproducibility has become an important topic in modern machine learning. Since (convex) optimization is the dominant algorithmic paradigm for modern ML, it is imporant to formulate and study reproducibility in optimization. The topic of the paper thus is important and timely. 2. The paper obtains the optimal bounds on convergence and reproducibility for the smooth convex setting, something which prior work conjectured to be unattainable. This is an important contribution. Further, they managed to also get optimal, and non-trivial rates for the minmax optimization, a setting which has received considerable attention lately. 3. The paper is well written. Granted that it covers a lot of algorithms and results, the writing is to the point and the flow of ideas is natural.

Weaknesses

1. About the definition of reproducibility: since this is a new field, I presume that the community has not yet agreed upon a definition. However, it seems to me that the only paper using the definition in this paper is the prior work of Ahn et al. Does adhering to this definition indeed reflect reprodubility in practice, in some sense? Even in optimization settings, there are other sources of instability not accounted for in the analysis, for instance, truncation and rounding due to the finite precision. Is adhering to reproducility (say with respect to initialization) and disregarding potential numerical instability arising in other steps give some meaningful in practice? 2. Related to the above, some experiments demonstrating usefulness of the framework would strengthen the paper. In the current version, there are no experiments. 3. The underlying idea is very simple and has been used many a times in (related) prior works -- regularization makes the problem strongly convex and thus aids leasds to (various forms of) stability. Nonetheless, the authors build on this to provide non-trivial bounds for many settings. 4. Some technical details, which I presume are in prior work, are not covered in the main text. Something that confused me is how to define "optimal reroducibility", which is referred many a times in the paper. Some text explaining it, perhaps in the preliminaries will be helpful. 5. What if we consider an inexact initialization as well as inexact grdient, with the same $\delta$ say -- is it possible to say something about this from the algorithms proposed? 6. The authors analyze a number of algorithms in the minmax setting, as a result this part of the paper looks rather dense with Thm statements. Some organization of what is to come will help the reader. From my understanding, Alg3, Inexact Proximal Point Method, strictly improves over all others? If yes, this should be conveyed early on in this section.

Questions

Please answer the questions posed in the weekaneses.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The work is limited to a certain notion of reproducility, used only in one prior work, and thus which may or may not be the definition as the area matures. Further, even though the authors identify two sources of instability: initialization and gradient computation, they are studied separately. A unified analysis can perhaps reflect more about the practical aspects.

Summary

In this paper, the authors introduce a novel algorithmic framework that can achieve near optimal convergence while preserving optimal reproducibility, for minimizing smooth convex objectives and minimax optimization of convex-concave objectives. Here, reproducibility under inexact initialization oracles, inexact deterministic gradient oracles, and inexact stochastic gradient oracles are considered. The key idea is to optimize a regularized strongly convex objective ( or Strongly convex - strongly concave objective for minimax optimization) using a given base algorithm, and bounding the error introduced by the regularization. The authors derive convergence and reproducibility guarantees that match or improve existing guarantees for different base algorithms applied to the proposed framework.

Strengths

* The paper discuss about theoretically improving the trade-off between optimal convergence and optimal reproducibility of algorithms, which is an important emerging research area. * The paper is fairly easy to read, and the methods and results are presented in a clear manner. * Using the proposed algorithmic framework, the authors show, contrary to what was previously believed, that accelerated gradient descent (AGD) method can achieve near optimal convergence preserving optimal reproducibility, which seems like a non-trivial and interesting result.

Weaknesses

* The paper covers only convex (convex-concave) objective minimization (minimax optimization), which prevents the results of this paper being applied to many applications where reproducibility is a challenge (e.g. reinforcement learning) as mentioned in the introduction of the paper. * The paper considers a constrained optimization setting for minimax optimization, while most applications of optimization, such as machine learning, will be deployed in an unconstrained setting. This might again prevent these results being applied to many practical applications. * The dependence of the convergence bounds on the diameter of $\mathcal{X}$ and $\mathcal{Y}$ in Theorems 4.4. and 4.6 makes the corresponding bounds too loose when $\mathcal{X}$ and $\mathcal{Y}$ are significantly large. Minor comments * Using $x^*_{r’}$ to denote $\underset{x\in\mathcal{X}}{\operatorname{argmax}}\\{ F(x) + (r/2) \Vert x - x_0' \Vert^2\\}$, it might suggest $x^*_{r’}$ corresponds to the optimum when $r’$ is used as the regularization parameter, which can be a bit confusing. * Introduction of Assumptions 3.1 and 4.1 seems abrupt, and some discussion on the assumption (e.g. their implications and how these assumptions compare with prior work) seems missing.

Questions

* What kind of modifications to the proposed algorithmic framework or the assumptions on the objectives will allow this framework (or similar framework) being applied to the non-convex setting? * Intuitively, why it is necessary to consider the constrained optimization setting for minimax optimization when obtaining these results given using the proposed framework?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This work only considers convex (convex-concave) setting, and some convergence results contain logarithmic factors, which are recognized by the authors in the conclusion. In addition to these, this work considers a constrained minimax optimization setting, which might limit the applicability of the corresponding results in practical applications.

Respond

Can the authors also comment on the following weakness? > Algorithm 1 is a well-known method in the optimization community. For instance, see https://arxiv.org/pdf/1603.05642.pdf. It is called "regularization technique" or "regularization reduction." I believe that the authors should cite the previous works that consider Algorithm 1. Do the authors discuss the connection between these methods and their method?

Rebuttal acknowledgment

I thank the authors for the clarifications. In light of satisfactory clarifications, I raise my score.

Thanks for the rebuttal

Thank you, the proposed updates sound good and I'm happy to still recommend the paper for acceptance.

Thanks!

I thank the authors for their detailed response and pointing to experiments in Appendix D. I encourage the authors to include some of the above discussion, especially those around definiton of optimal resproducibiliy from Ahn et al, as well as combination of the two settings, to the revised version. I increase my score to 7.