Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presented the mini-batch extension of STP method in the finite-sum problem. The paper analyzed the complexity of minibatch STP in both non-convex and convex cases and examine the performance of MiSTP under various settings. The experiment showed that MiSTP converged faster than STP in terms of number of epochs. It also compared MiSTP with SGD and showed that MiSTP could converge to a good approximation or exactly the same solution as SGD. Moreover, MiSTP  compares favorably against several state-of-the-art ZO methods.




strength_and_weaknesses: ### Strength

1. It's easy to follow and understand the technical details. The paper is well organized and quite readable. The theoretical analysis is sound. 

2. The experiments are quite detailed, which clearly demonstrates the great performance of  MiSTP in a wide range of problems. 


### Weakness

- Since the paper considers finite sum setting, developing a variance reduced algorithm can substantially enrich the contribution and solidness of the paper

- It is not clear to me what theoretical advantage MiSTP has, compared with existing algorithm such as RSGF or ZO-SVRG. 

- In the theoretical part the authors show the complexity under convex and non convex case but the experiment part is about strong convex problem. Can you also develop the rate for strongly convex setting?

A minor issue:
Should we call the algorithm a zeroth-order method as opposed to zero-order method? 
clarity,_quality,_novelty_and_reproducibility: 
Novelty:

- The paper extended a recently proposed STP algorithm for zeroth order optimization to the finite sum setting. However, the technical extension to stochastic setting seems to be very standard. For example, the Key lemma follows almost the same development of Lemma 3.5 of [1].



[1] Bergou, E.H., Gorbunov, E. and Richtárik, P., 2020. Stochastic three points method for unconstrained smooth minimization. *SIAM Journal on Optimization*, *30*(4), pp.2726-2749.



summary_of_the_review: Overall, the paper provides a novel zeroth-order algorithm for stochastic convex and nonconvex optimization. Both theoretical analysis and experimental results are  well-supported. However, I still have some concern about the technical contribution. I am not fully convinced why the proposed method is more advantageous over existing algorithms. Maybe I missed something, any theoretical or application insights are welcome.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies smooth zeroth-order optimization and extends the STP method to the finite-sum setting. The proposed method is very simple and easy to implement. The authors also provide convergence analysis and empirically verified the efficiency of the proposed method.
strength_and_weaknesses: Strength:

1. The paper is well-written and easy to follow.
2. The MiSTP method is simple and easy to implement. It only needs an approximation of the function evaluation.

Weaknesses:

My main concern is about the experiments. All models used in the experiments (ridge regression, regularized logistic regression, and fully connected NN) can be efficiently solved by gradient-based methods. None of these methods require the use of zeroth-order optimization. I suggest the authors perform experiments on some ML applications where computing gradients is intractable. The authors may refer to the experiments of the ZO-SVRG paper(Liu et al., 2018).

other concerns:

1. Thm 1 and 2 require $\sigma_{|B|}<O(\epsilon^2)$, which means that the batch size may be proportional to $\epsilon^{-2}$. Since $\epsilon$ could be very small, the batch size may be very large.
2. I suggest the authors briefly introduce the main difficulty of extending STP to MiSTP.
clarity,_quality,_novelty_and_reproducibility: The writing is mostly clear. The proposed method is novel, but the quality of the empirical comparison is below the bar of ICLR.

summary_of_the_review: Overall, I think the proposed method is interesting, but the experiments part greatly reduces the quality of this paper.

---

After rebuttal:

I'm disappointed that the paper does not contain experiments on problems for which gradients are not available. Thus I will keep my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this submission, the authors study zeroth-order optimization methods for minimizing deterministic finite-sum problem. In particular, the authors present mini-batch three points zeroth-order method in which the objective function is calculated at three different points at each iteration over a fixed mini-batch of functions from the finite-sum. They also present sample complexity of their proposed method for both convex and nonconvex settings and conduct some numerical experiments to show performance of the algorithm.
strength_and_weaknesses: The idea of the manuscript is similar to that of (Bergou et al., 2020) and the only difference is that the approximation of the objective function is considered for the three-point estimate over mini-batches. However, the authors assume that they can calculate the objective function at different points over a fixed choice of functions from the finite-sum which is not truly stochastic setting. Moreover, no noise is involved in estimating each $f_i$. The sample complexities have been proposed based on $\mu_D$ which hides the dependence on the problem dimension. The numerical experiments have been also conducted just over low-dimensional settings. No comparison with existing results has been presented.
clarity,_quality,_novelty_and_reproducibility: The idea has been used before for the deterministic problems and the setting considered in this submission is not truly stochastic.
summary_of_the_review: The contribution is incremental and the results have not been presented clearly.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission proposes a minibatch stochastic three points method, which only requires an approximation of the objective function at each iteration. It is an extension of a previous work of stochastic three points method that requires the exact evaluation of objective functions.
strength_and_weaknesses: Strengthes:
Compared to STP, evaluating objective value on a batch of data instead of the full data can make the algorithms much more practical.

Weakness:

1. The motivation of this work is not well justified. What are the advantages of using this STP-type algorithms compared to other existing works such as two-point estimators? Even though STP was proposed in another work, it is still necessary to clearly discuss the motivation in order to help the audience to understand the significance of this work. 

2. Given the existing STP work, this submission extends it to a version that only requires an approximation of the objective instead of an accurate evaluation. What are the challenges in the analysis? Can the introduced noise by inaccurate estimation of objective values just be controlled in similar way to in the analysis of stochastic gradient descent? Therefore, I wonder what are the specific challenges and key techniques to solve these challenges in this submission?

3. The experiments in Section 4.1 are for easy problems where gradients can be easily computed and so SGD are applicable. And experiments in Section 4.2 are not compared with other zero order methods. Hence, the true performance of the proposed MiSTP is questionable. Besides, the problems in Section 4.1 are strongly convex which expect better complexity rates than those in Theorem 1 and Theorem 2. Maybe the authors can consider to add the analysis of strongly convex cases as well.



clarity,_quality,_novelty_and_reproducibility: More clarity is needed to understand the motivation, strength and novelty of this work. It lacks empirical results on complicated tasks and comprehensive comparison to other methods in order to make the effectiveness of the proposed algorithm convincing.
summary_of_the_review: I tend to vote for rejection based on the current manuscript being lack of motivation,  not having adequate comparison to existing methods and not showing novelty in terms of analysis techniques.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors study zeroth-order optimization methods for minimizing deterministic finite-sum problem.
They present mini-batch three points zeroth-order method in which the objective function is calculated at (two) different points at each iteration over a fixed mini-batch of functions from the finite-sum.
Sample complexity for convex and nonconvex settings is proposed and some numerical experiments illustrate the performance of the algorithm.

justification_for_why_not_higher_score: All models used in the experiments (ridge regression, regularized logistic regression, and fully connected NN) can be efficiently solved by gradient-based methods. None of these methods require the use of zeroth-order optimization: the authors should perform experiments on some ML applications where computing gradients is intractable (see for instance Liu et al., 2018).
The theoretical advantage MiSTP with existing algorithm such as RSGF or ZO-SVRG could be more carefully described.
The differences with Bergou et al. 2020 should be highlighted to underline the current contribution of this work.
Developing a variance reduced algorithm can substantially enrich the contribution of the paper.

justification_for_why_not_lower_score: The writing is mostly clear. The proposed method is novel.
Decision: Reject