Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Consider unconstrained smooth optimization with probabilistic zeroth- and first-order oracles. This paper proposes a new gradient descent with line search method and provides a high-probability upper bound of the iteration complexity. The authors highlight that their assumptions on the noisy zeroth- and first-order oracles are weaker than those in literature. 
main_review: I like the idea of querying new noisy gradients even when the Armijo condition is not met in the proposed line search algorithm. I feel this is perhaps the natural approach in the stochastic setting. 

Below are some comments. 
- The numerical experiment does not exactly follow the theory: In the numerical experiment, the mini-batch sizes are fixed, first- and zero-th order oracles use the same minibatch and $\gamma_{\text{dec}} \neq 1 / \gamma_{\text{inc}}$. Why is the theory not followed? What is the empirical result when the theory is strictly followed?  
- It is assumed that the the error of the probabilistic first-order oracle is bounded from above by the norm of the noisy gradient (scaled by a constant) with high probability. This assumption seems to suggest that the mini-batch size cannot be a constant but should increase when the iterates approach a stationary point. Is this increasing mini-batch size necessary? 
- The authors highlight that unlike in existing literature, they do not assume the noisy gradient to be Lipschitz. When is this relaxation of the assumption significant? 
- Line 63--88 addresses related existing results, arguing existing results are restrictive and do not provide high-probability guarantees. It would be good if the authors can clarify the key idea that enables them to make the breakthrough in this paper. 
- Line 293: Why is resetting the step size in each iteration is "impractical"? 

The presentation is clear. Below are some comments on the presentation: 
- Line 85: Saying the existing assumptions are "very restrictive" is vague. In what sense are they restrictive? 
- Line 152--156: The definitions of $I_k$, $\Theta_k$, and $Z_k$ are not used in Section 3. I think their appearance should be postponed to Section 4. 
- Line 240: The name of the proposed algorithm should be appear in the second last section. 
limitations_and_societal_impact: Please address my comments in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposed Adaptive Line-search with Oracle Estimations (ALOE) for nonconvex smooth stochastic optimization, the algorithm is based on modified Armijo condition. The algorithm allows the oracles to be biased and only requires the population function $\phi$ to be Lipschitz smooth and some other mild conditions on the stochastic process.
main_review: The paper aims to solve a practical problem in nonconvex optimization on parameter selection by modified Armijo line-search. The flow of the work is clear. Compared to previous closely related work [VML+19], it extend the setting to stochastic case with biased oracle, and provides a high probability complexity bound.

I have some confusions in this work, hope authors can add more discussion to address:
- In stochastic optimization, generally it will assume that the function/gradient estimation is unbiased with bounded variance, i.e. $\mathbb{E}f(x,\xi)=\phi(x)$, $\mathbb{E}g(x,\xi)=\nabla\phi(x)$, $\mathbb{E}||g(x,\xi)-\nabla \phi(x)||^2\leq\sigma^2$, instead of the norm form in Eq (1) and (2). So it seems that the main convergence result cannot recover the standard unbiased line-search algorithm result (if any, maybe $\mathcal{O}(\epsilon^{-4})$?), because $\epsilon_f=0$ will recover the deterministic line-search result $\mathcal{O}(\epsilon^{-2})$, is that correct, and is there any solution?
- Lower bound requirement on $\epsilon$. It seems that the setting in Eq (1) and (2) should contain the common unbiased setting above ($\mathbb{E}f(x,\xi)=\phi(x)$ but $\mathbb{E}|f(x,\xi)-\phi(x)|$ can still be upper bounded), but common stochastic optimization algorithm with unbiased oracle may not need the lower bound requirement in the accuracy $\epsilon$ (i.e. converge with arbitrary small $\epsilon$), is that correct? Even though chasing high accuracy may not be that important in machine learning, but as a theoretical paper in optimization, I am still wondering what is the case for high accuracy.
- In Assumption 2, it requires the function estimation error $e_i, e_i^+$ to be deterministically bounded by $\epsilon_f$ seems to be much stronger than boundedness in expectation in Eq (1) (authors also mentioned it is strong in Line 65), is that correct? Especially concerning that here the main theorem requires that the accuracy $\epsilon$ to be larger than $\text{poly}(\epsilon_f)$. 

Based on the confusions above, currently I tend to reject, but after the rebuttal, I will appreciate the authors to address my confusion, and definitely reconsider my decision. Thank you.
limitations_and_societal_impact: This work does not involve issues related to the negative impact of society.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studied the line-search method with stochastic zeroth-order and first-order oracle. The author(s) extended prior works by (1) relaxing assumptions (2) providing a high probability bound (exponential tail bound) for the stopping time.
main_review: Pros:
- The structure of the paper is clear and most contents are easy to follow.
- Related works are well-addressed to my knowledge.

Cons:
- Eq (4) holds for the finite sum of convex functions and usually does not hold for nonconvex functions. Therefore I don’t think Proposition 2 could hold for nonconvex function. Assume that Proposition 2 is satisfied, then it means we have an accurate estimate of the true gradient at every saddle point (with prob $1 - \delta$). Can the author(s) provide a nonconvex example that satisfies Proposition 2? I understand that similar assumptions are also used in prior works, but I am confused about whether it is an appropriate assumption.
- One extension of this work to prior work is the $\epsilon_g$ used in eq. (2). But this also makes the theoretical result weaker, $\epsilon$ cannot be smaller than $\epsilon_g / \eta$ (see Assumption 4). I agree that this paper relaxed the assumptions (see eq. (1) and eq.(2)) used in prior works, but the obtained result is also weaker. I don’t think that the relaxed assumption is a significant contribution. The major contribution of this paper I think is the exponential high probability bound obtained (in contrast to the convergence in expectation in prior work). But I am not sure if this result is significant enough to be accepted at NeurIPS.
limitations_and_societal_impact: This is a theoretical work and I do not see any limitation and negative social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers a new line search variant for minimizing functions with access to function value (zero order) and gradient (first order) estimates only through probabilistic oracles.
For both oracles the output is a function of the input point and a random variable, and with probability 1-delta the output is close to the actual value. For the remaining delta probability, the first order oracle assumes nothing while the zero order oracle assumes that large errors are increasingly unlikely, making the requirements for the two oracles different.

The random variable in the oracle, could for instance represent the mini-batch used to estimate the required quantity.
The authors propose a variant of Armijo Line search that
 - Adds some slack on the Armijo condition depending on the quality of the zeroth order oracle
 - Recompute gradient and function values in each step in the line search instead of using the same one.

For this line search method the authors show high probability iteration bounds for minimizing a Lipshitz bounded smooth function,
that converge to an epsilon stationary point (norm gradient less than epsilon) where epsilon is lower bounded by the quality of the oracles. 
The bounds are more general in the sense that less is assumed about the oracles, and that the paper shows high probability iteration bounds, where the usual is a bound on the expected number of iterations. 

main_review: The approach and analysis is made as general as possible and analyzed without assuming convexity. However all the experiments consider a convex problem.
Nonetheless, the experiments confirm that the proposed line searching method works well in this case.
It would have been interesting to see non-convex problem, in particular the case with zeroth order optimization from for instance reinforcement learning as those oracles seem to able to be particularly noisy,
albeit such problems may have a lot of moving parts to control that make it hard to isolate the value of the algorithm proposed.

It seems in the general case minibatch size should depend on the learning rate in the algorithm (in the case where the randomness comes from the minibatches),
at least for the oracles created from mini batches satisfy the assumptions required? Stated differently, if batch size is too small there seems to be no guarantee for the algorithm. What happens in the experiments if the batch size is made much smaller?

Overall I think the proposed algorithm is nice and fairly simple which is positive albeit there are some  parameters that need setting.
The actual Theorem has a lot of parameters but the overall message can be extracted, and the result is quite general.

- The norms in equation 2, and in general, is that any norm? or maybe the two norm of the vector?
- Assumption 2, is that a standard assumption that the errors in different steps are independent (they could depend on the same x here)?
- Does the iteration bound (almost) match an obvious lower bound for this kind of oracles?
- Can it be shown that for these kinds of oracles the recomputation of function value and gradient in each step in the line search is necessary in some sense (could the standard armijo SGD also converge here as that may be cheaper to run (data could be expensive to generate for instance with zeroth order optimization with finite difference approximation in reinforcement learning).
- why use absolute values around |e(x)|  on line 200 - 202, e(x) is already non-negative. Am I missing something there?

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This was perhaps the most difficult decision in my pile, and I felt the need to carefully reviewed the paper myself. The main point against the paper is that the results are similar to many existing results that hold in expectation, and it is unlikely that members of the community would be surprised that this algorithm works with high probability. On the other hand, the authors have done a thorough job both theoretically and empirically. I believe this work will make a good reference on the topic, and the authors have addressed nearly all the points brought up in the reviews (e.g., experiments on non-convex problems and issues with the assumptions). So overall I leaned towards recommending acceptance.

Some additional "reviewer comments" from my readthrough:

- The paper needs to spend more time, especially early in the paper, making connections to machine learning. For example, the paper needs to be more clear that in order to converge the mini-batch size must grow as a stationary point is approached. It should discuss the relationship between the mini-batch size and the error in the gradient (this was brought up in several reviews, and this discussion will be useful for many readers).

- I feel like this algorithm is more-closely related to "growing batch" methods than to stochastic gradient methods. The paper should discuss these related works, and emphasize the connections to them. The paper could also refer to the growing-batch papers as ways people have tried to set the batch size in methods like this (because setting the batch size for hybrid methods like this is not easy, so referring to other papers is probably all you will have space for).

- The paper needs to *explicitly say that there is a minimum batch size required*, given an accuracy level, which is different than the usual SGD setting.

- Given the connection, I would also like to see a growing-batch method in the experiments (SLS does not quite seem like the right method to compare to). 
Decision: Accept (Poster)