Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studied stochastic model based methods (SMOD), and prove complexity bounds for minibatch SMOD and momentum SMOD.

main_review: Strength: the paper proves complexity bounds for SMOD with minibatch and momentum, and show that minibatch provides speedup, which is new to the literature. 


The complexity result, such as Theorem 3.4, indeed implies  linear speedup, however only for m being not too large. Suppose $ m \geq 1/\epsilon^2 $, then the complexity would be $ T_\epsilon = O(\Delta/\epsilon^2) $ which is independent of batch size. As a result, if would be interesting to see in Figure 1, what the plots will be like for even large $m$. In addition, what is the “desired accuracy’’ chosen in the numerical experiments, will the value of accuracy affects the linear speedup of minibatch?

Minor: 
Line 12, “…possibly improve…’’ please remove or rewrite this statements since it’s meaningless. Even in the deterministic setting, momentum is not guaranteed to provides acceleration. However, it might leads to smaller objective function values. It would be good if the authors can check if this is true for the considered problems here. 

Line 149, “B = ”, equal sign missing. 

Line 205, “Despite such a relation’’, a missing

limitations_and_societal_impact: See above for limitations and no negative societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper proposed stochastic model-based method and its momentum version for solving non-smooth non-convex optimization problems. The convergence results of the proposed methods are established. The authors also provide some experimental results for verifying the effectiveness of the proposed methods.
main_review: Originality: The convergence analysis seems non-trivial. 

Quality: The assumptions are too strong. For example, it seems that Assumption 5 is never used in the literature. How to justify it?

Clarity: The paper is well organized, and the writing is clear to me. 

Significance: The “improved” convergence result of SMOD requires additional assumptions (e.g., A5, A6, A7), which makes the contribution of this paper limited. With Assumption 5, having such convergence result is not surprising. The Assumption 5 makes the results no general enough and is not applicable to standard stochastic subgradient methods for solving non-smooth problems. 
limitations_and_societal_impact: No. The new assumption A5 is never used in the lierature.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents several minibatch and momentum extensions of stochastic model-based optimization methods (SMOD) for learning with non-smooth and weakly convex loss functions. For SMOD with minibatch size $m$ and iteration count $K$, the authors showed via a uniform stability argument that the algorithm converges to stationary point at the rate of $O(\frac{1}{\sqrt{mK}})$. Similar convergence rates have been established for an extrapolated variant of SMOD with or without minibatching. The actual performance of the proposed methods is evaluated in a set of experiments on synthetic and real-data robust phase retrieval.
main_review: The paper is technically sound and the main results make sense to me. I am particularly impressed with the clear and clean writing style, and how all steps in the proofs are carefully explained. However, I still have some reservations on the novelty and significance of results as specified below:

- Originality: While interesting, the idea of extending SMOD-type methods to minibatch optimization using stability argument is definitely not new. For example, for distributed learning with convex and Lipschitz losses, the benefit of minibatching has already been revealed for stochastic proximal point (SPP) method through the lens of uniform algorithmic stability theory [1]. More precisely, up to minor differences, Theorem 3.2 is identical the Lemma 2 in [1]. Therefore, the only novel point I can spot in this part is using the generalization bounds in Theorem 3.2 to analyze the convergence of SMOD for weakly convex losses, as summarized in Theorem 3.3 & 3.4. The technical part of these theorems is more or less straightforward given the techniques developed in [2] (i.e., reference [8] in the paper). Overall, the degree of novelty of the minibatch extension is fairly low with respect to the prior work in this line. The proposed momentum extension is relatively more impressive, and somewhat novel as far as I know about. 
 
- Significance of results: My main concern regarding the proposed extrapolated variant of SMOD is the strength of results in Theorem 4.2 & 4.3, which seem showing no significant improvement over the vanilla version. Since the method reduces to a heavy-ball acceleration strategy in the SGD case, it is not surprising that it does not substantially improve the rate of convergence for generic convex or non-convex losses. On the other side, it is well known that heavy-ball is beneficial for accelerating batch GD for quadratic programs. Then a natural question is if it is possible for the extrapolated SMOD method to achieve acceleration at least for quadratic losses? Anyway, a careful discussion on the advantages of the momentum extension is highly desirable to justify the usage of method in theory. 

Minor comments: 

- Clarity: Since Assumption A6 & A7 are of very limited interest unless $M$ and $D$ are extremely small, it is suggested to carrying out the analysis without introducing these void assumptions so that the core results can be presented in a neater way. 

- Experiment: As the comparison is made among stochastic optimization methods, it is desirable to provide error bars in the plots to illustrate the variance of computation.

[1] Wang, Wang, and Srebro. Memory and communication efficient distributed stochastic optimization with minibatch prox. COLT, 2017.

[2] Davis and Drusvyatskiy. Stochastic model-based minimization of weakly convex functions.  SIOPT, 2019.



=== Post rebuttal update ===

The major concerns raised in my initial review on the momentum extension have been much clarified in the author response. It's good to know, based on the augmented results provided during author discussion phase, that the robustness of SMOD to the choices of step-size can be much preserved by its momentum variant. As for the minibatching acceleration analysis, while  the results for weakly-convex problems are somwhat interesting, IMO the technical contribution of this part is too incremental for NeurIPS given the prior work of Wang et al. (2017) and Davis & Drusvyatskiy (2019).  It is suggested to tune down the claim of this part accordingly.  

 Overall, I would still like to change my rating one grid up to 6, apprecaiting the novelty and strength of the momentum extension/analysis of SMOD.

limitations_and_societal_impact: Yes,  the authors have partially addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This contribution introduces and analyzes mini batch variants of stochastic model-based optimization methods when the loss function is possibly nonconvex and non smooth. Their algorithms are accompanied with a theoretical analysis and numerical experiments.
main_review: Overall, I don’t understand what makes those methods different from classical stochastic optimization method. All of those baselines are model based in the sense that the updated parameters throughout the iterations, depend on the loss function and the model employed.
Hence, Algorithm 1 boils down to any proximal and regularized gradient step, which has been around for a long time. 
It would be greatly appreciated if the authors can clarify what makes their method different from what is in the literature.

- Numerical experiments: The authors only compare, in Figure 1 and 2, their method with plain SGD.
Given the sheer size of optimization methods, one would expect much more baselines for fair comparison.

Minor typos:
- In the checklist: « Did you include the license to the code and datasets? [Yes] See Section ??. » what is the section number?
- Using the same notation for the stochastic objective function and the unregularized one is confusing.
- Algorithm 1 writing requires more details: How is the stepsize initialized, how are the m_k decided, what is the output of the method.

limitations_and_societal_impact: No they have not.
review_title: null

Meta-review: 
The paper proposes an analyses of model based methods with mini-batching and momentum. The topic is relevant to the Neurips community. But the reviewers were unclear as to how this fits in and compares to existing work, in particular due to Assumption 5. On that note, since most of the models involve a linearization (excluding the proximal point method) Assumption 5 is essentially smoothness. This makes it a bit confusing given the emphasis of the work on the non-smooth setting. Reviewer Kosw also raised questions as to the technical novelty of the mini-batch analysis based on stability analysis, given closely related prior work. Given the above, I will not recommend the paper be published.

The technical contribution of the paper may be sound and novel, but it appears that it wasn't clear or accessible enough for most of the reviewers. Thus in revising the paper, it may simply be a case of re-writing to improve clarity and the positioning of the paper in the literature. For example, Theorem 3.4 is hard to parse, given the large number of new constant definitions, where the parameter of most interest the mini-batch size (m) is hidden away in several new constants, making it hard to appreciate the speed-up offered by increasing the mini-batch size. 

Some further references on SGD + minibatch analysis (though in the smooth case) include [1] in the non-convex setting and [2] in the convex setting. On understanding SGD with momentum in the nonconvex setting, recently (and arguably concurrent work with yours) SGD with momentum was analysed in [3].  

[1] Better Theory for SGD in the Nonconvex World, Ahmed Khaled, Peter Richtárik, 2020

[2]  SGD: General Analysis and Improved Rates, Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik; ICML 2019.

[3] Aaron Defazio, Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization, arXiv:2010.00406, 2021
Decision: Accept (Poster)