Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents and analyzes an accelerated algorithm for convex and strongly convex minimization when the objective function is an expectation of a convex function. It claims that the algorithm is optimal w.r.t. Mini-batch size and the convergence rate. The presented algorithm reaches the best-known rate for the accelerated stochastic algorithm and also shows the dependence on the mini-batch size is also optimal.  
main_review: Significance: The paper considers minimizing the population risk in machine learning models, which is one of the major optimization problems in ML. 

Novelty: The paper presents a novel algorithm and also discovers a new upper bound for the second moment of the stochastic gradient. Using this upper bound it analyzes the presented algorithm under different assumptions and recovers the optimal upper bounds.   

Clearity: it is easy to follow and understand all the technical details and main text of the paper. However, there are some typos here and there that need to be fixed. 




My question

1- The method has a limitation in the sense that it requires knowing L*. Could you replace this with some upper or lower bounds? 
	
2- There is no experimental section. It would be helpful to see the performance of the algorithm on the model with real data. 

3- Your algorithm is not an anytime algorithm. How can you make it an anytime algorithm? 

4-  It is not clear why theorem 2 is not trivial based on the alg 2. 



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper improves the complexity bound w.r.t. minibatch speedup given by Cotter et al and Liu et al. for minibatch accelerated gradient descent for certain objectives (under sharpness condition). Generally the paper is well-organized with solid theoretical analysis and is easy to follow.


main_review: The structure of this paper is very clear.  It presents sharper complexities of accelerated sgd than state-of-the-art result by using a refined bound on stochastic noice. The technical analysis is solid, from the theoretical aspect, I think the improvement is quite interesting and the contribution is sufficient. However, it would be much better if the author can empirically verify the algorithm performance.

The paper tries to design the minibatch algorithm with fixed batch size, can the author also briefly discuss how to use varying batch size, this seems to be a more practical strategy in applications.

I am a little concerned about the parameters in this paper and the assumptions. For example, in assumption 2, it requires some nonstandard parameters such as L^* and B (Assumption 2), which are usually unknown in practice.  In assumption 3, the algorithm also needs the growth condition.

I understand that the paper aims to obtain the sharpest bound possible, but it would also be great if it also discuss what if those parameters are under/overestimated. Would that has a significant impact on the performance? 

Can the author also provide some preliminary experiments to to show the superior performance of the proposed approach. 


On eq (4), $\ell(w,z)\Rightarrow \nabla\ell(w,z)$.

Eq (59) $\nabla F(w_t^{md})\Rightarrow \nabla L(w_t^{md})$.

Line 300 $E\|\nabla \ell(w^*;z)\|^2$

limitations_and_societal_impact: Perhaps the application of this approach does not include regularized problems in which the objective is far bigger than zero. For example, underdertermined linear system is mentioned in the paper. In practice we can add $\ell_1$ term to enforce sparsity, then we have $L^*>>0$.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies an accelerated stochastic gradient method with minibatching for expected risk minimization problems and provides the optimal convergence rate. Remarkable points are that (i) the dependency of the obtained rate on the minibatch size is also optimal, meaning the linear speedup by increase the minibatch size, and (ii) the rate reflects the acceleration due to the interpolation by evaluating the variance at the solution using the optimal value of the objective.
main_review: [Contributions]

Since the minibatching technique is frequently adopted in machine learning applications, the research into minibatch efficiency is important. In addition, relaxation of the uniform boundedness assumption on the noise is also an interesting topic. In this context, I think this study makes a good contribution. Concretely, the method achieves the optimality regarding the number of iterations $T$ and the minibatch size $b$ and shows the acceleration due to the interpolation by taking into account the optimal value of the objective.

Accelerated stochastic gradient methods for the expected risk minimization were studied in Lan [14] and Cotter et al. [8]. Compared to these studies, the obtained rate has advantages as follows: 

- The rate in Lan [14] is optimal in $T$ but is suboptimal in $b$. Moreover, there is no acceleration due to the interpolation because [14] uses the uniform boundedness on the noise instead of the evaluation of the noise at the optimal solution.
- The rate in Cotter et al. [8] is optimal in $T$ and accelerated by the interpolation, but is suboptimal in $b$.

Hence, I think this submission makes a certain contribution in the context.

[Additional references]

There are several missing references. 

For finite-sum problems, some methods achieve the accelerated convergence rate and linear speed up by the minibatching simultaneously. For instance, see the following papers:

- Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods, 2017.
- T. Murata and T. Suzuki. Doubly accelerated stochastic variance reduced dual averaging method for regularized empirical risk minimization, 2017.
- A. Nitanda, T. Murata, T. Suzuki. Sharp Characterization of Optimal Minibatch Size for Stochastic Finite Sum Convex Optimization, 2019.

The minimum minibatch size to achieve the optimal iteration complexity was discussed in the last paper. 

The linear speedup by increasing minibatch size up to a certain size was shown for SAGA in the following paper, although they only consider the non-accelerated method.

- N. Gazagnadou, R. M. Gower, and J. Salmon. Optimal Mini-Batch and Step Sizes for SAGA, 2019.

Acceleration due to the interpolation was also considered in the relaxed condition, i.e., PL-condition in the following:

- R. Bassily, M. Belkin, S. Ma. On exponential convergence of SGD in non-convex
over-parametrized learning, 2018.

The faster convergence under strong and weak growth conditions was shown in 

- S. Vaswani, F. Bach, and M. Schmidt. Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Perceptron), 2018.

These conditions are closely related to the interpolation.

Moreover, an extension of the weak growth condition, which does not require perfect interpolation was also considered in 

- R.M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtarik. SGD: General Analysis and Improved Rates, 2019.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the behavior of accelerated minibatch SGD under smoothness, bounded variance of gradient at optimum and/or quadratic growth assumptions. They also provide a meta algorithm to generate fast methods of solving convex optimization problems satisfying growth conditions from methods of solving convex problems without growth conditions.
main_review: This paper is technically sound and clearly written.  

Strengths:
1. Analysis of minibatch accelerated gradient methods under a slightly different set of assumptions with justification using examples for those assumptions.
2. A general technique to create algorithms for problems satisfying growth conditions using known algorithms to minimize convex functions.
3. They also provide lower bounds showing optimality of convergence rates.

Weaknesses: (in decreasing order of importance)
1. Although the assumption of bounded variance of the gradient only at optimum is weaker than having bounded variance of the gradient at all points, the assumption of having each sample function being smooth is stronger than having only the population function being smooth as is in some of the referred papers. It is unclear to me why one set of assumptions is better than the other. The only example explaining the assumption is that of least squares regression, but having $||w^*|| \leq B $, we can upper bound the dependence of the gradient on $||w||$ by considering a bounded domain. More examples showing the benefits of this set of assumptions compared to the previous ones would be useful.
2. It is not very clear to understand what is the one line message of the paper. It seems like having 3 seemingly disjoint contributions, especially section 7, which seems a bit disconnected from the rest of the paper. Some effort can be made to make the paper gel together better.
3. Interpolation problems are only defined in the special case when $\mathcal{D}$ is the empirical distribution and not for the general case. Having interpolation problems in the title is slightly misleading because this can confuse the reader regarding whether the results hold only for ERM or for population loss minimization. Either having a general \textit{definition} of interpolation problems and checking whether the results go through for that or removing the stress on interpolation problems would be useful.
3. Some of the results are not compared to related work on methods for interpolation problems with growth conditions listed below:

[1] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex
functions. SIAM Journal on Optimization, 29(1):207–239, 2019.
[2] H. Asi and J. C. Duchi, Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity, SIAM Journal on Optimization, 29 (2019), pp. 2257–2290, https://arXiv.org/abs/1810.05633.
[3] Karan Chadha, Gary Cheng, and John C Duchi. Accelerated, optimal, and parallel: Some results on model- based stochastic optimization. arXiv preprint arXiv:2101.02696, 2021.
[4] S. Vaswani, F. Bach, M. Schmidt. Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Percepton).
[5] S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, S. LaCoste-Julien. Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates.

limitations_and_societal_impact: See main review for weaknesses.
review_title: null

Meta-review: All reviewers recommend accepting the paper. Please take the time to consider the reviewer's comments and update the paper when preparing the final version. In particular, please discuss the additional related references brought up in the reviews.
Decision: Accept (Poster)