High Probability Complexity Bounds for Line Search Based on Stochastic Oracles
Authors: Billy Jin
Katya Scheinberg
Miaolan Xie
Venue: NeurIPS 2021 Poster (2021)
Keywords: nonlinear optimization
stochastic optimization
line search
high probability
complexity bound

Abstract: We consider a line-search method for continuous optimization under a stochastic setting where the function values and gradients are available only through inexact probabilistic zeroth and first-order oracles. These oracles capture multiple standard settings including expected loss minimization and zeroth-order optimization. Moreover, our framework is very general and allows the function and gradient estimates to be biased.  The proposed algorithm is simple to describe, easy to implement, and uses these oracles in a similar way as the standard deterministic line search uses exact function and gradient values.  Under fairly general conditions on the oracles, we derive a high probability tail bound on the iteration complexity of the algorithm when applied to non-convex smooth functions. These results are stronger than those for other existing stochastic line search methods and apply in more general settings. 

High Probability Complexity Bounds for Line Search Based on Stochastic Oracles
Billy Jin Cornell University bzj3@cornell.er edu
Katya Scheinberg Corelll University katyas@cornell.. edu
Miaolan Xie Comeell University mx229@cornel1. edu
Abstract
We consider line-search method for continuous optimization under stochastic setting where the function values and gradients are available only through inexact probabilistic zeroth and first-order oracles. These oracles capture multiple stan- dard settings including expected loss minimization and zeroth-order optimization. Moreover, our framework is very general and allows the function and gradient estimates to be biased. The proposed algorithm is simple to describe, easy to im- plement, and uses these oracles in similar way the standard deterministic line search uses exact function and gradient values. Under fairly general conditions the oracles, derive high probability tail bound on the iteration complexity of the algorithm when applied to non-convex smooth functions. These results are stronger than those for other existing stochastic line search methods and apply in more general settings.
Introduction
In this paper, we analyze line-search method when applied to the problem of minimizing an uncon- strained, differentiable, possibly non-convex function RR - R. The goal is find e-stationary point for Φ; that is, a point x with VV(()]l S ε. We make the standard assumption that V is L- Lipschitz, but the knowledge of L not assumed by the algorithm. We consider setting where neither the function value ((x) nor the gradient Vœ(x)) are directly computable. Instead, the algo- rithm is given black-box access to the following probabilistic oracles:
Probabilistic zeroth order oracle. Given a point x, the oracle computes f(, <), (ran- dom) estimate of the function value Φ(x). ç is random variable (whose distribution may depend on I)), with probability space (22, P). We assume the absolute value of the es- timation error e(z) fz, (x)) <(x) (we omit the dependence on & for brevity) to be a "one-sided" sub-exponential-like random variable with parameters (v, b), whose mean is bounded by some constant of > Specifically.
22v2
Eg [e(x)] S E and Eg (ex((A(e(x)) E[e(=))H S exp
AA
0, 6
(1)
Probabilistic first order oracle. Given a point v and a constant a > 0, the oracle computes g(x, {'), (random) estimate of the gradient Vo(x), such that
Per (1g((,, g") V max(cy, kal]g((, <`)I 2
(2)
Here, g is random variable (whose distribution may depend on æ)) with associated proba- bility space Ffr. P'). (1 - 8) (0, 1) is the probability. intrinsic to the oracle, that the
'This is weaker requirement than assuming e(x) to be sub-exponential, only needs to guard against the possibility of the emorr e(x) being large.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

gradient estimate is "sufficiently accurate" with respect to Eg, R. and a. Lastly, K, Eg 2 0 are constants, intrinsic to the oracle, which represent the precision the oracle can achieve. Note that Eg allows the gradient estimate to be bounded away from the true gradient by constant distance.
We will analyze line search algorithm that relies on these two oracles. In the zeroth order oracle, the constants E, and (v, b) are intrinsic. In the first order oracle, K, Eg. and are intrinsic. These values cannot be controlled. On the other hand, a is an input to the first order oracle that can be chosen by the algorithm. In fact, as we shall see in Section 3, a will be the step size of the line search method.
Remark
These two oracles cover several settings, including
Standard supervised learning, where gradients and values of the loss function are computed based on a mini-batch. Here, the random variables & and ç' in the zeroth and first order oracles represent the random set of samples in the mini-batch.
Zeroth order optimization, where gradients are estimated via randomized finite differences using (possibly noisy) function values. This arises in policy gradients in reinforcement learning, is used in [SHC+16] 16] and analyzed in [BCCS21].
A variety of other settings, where the gradients and function estimates may be biased stochastic estimates of the true gradients and function values.
The constants in the oracles determine the precision of the function and gradient estimates. These constants will also dictate the accuracy achievable by the line search method we analyze. Specifi- cally, if = 0 and 3 = O, then the algorithm converges to a stationary point. Otherwise, a precise lower bound is derived for the smallest [z)(] the algorithm can achieve, in terms of the constants in the oracles. It is worth noting that the oracles can be biased. Indeed, the zeroth order oracle can incur arbitrarily large error, as long as satisfies 1. Moreover, the first order oracle only requires g( (xx)) to be a "sufficiently accurate" estimate of VΦ(Iz) with probability 1-5. Thus g(v, 5 ('())) can be an arbitrary vector with probability 5, so in principle can have an arbitrarily large bias.
The line-search algorithm is given in Section 3. is a modification of the standard Armijo-based line search algorithm [NW06], with access to the zeroth and first order oracles. The two small modifications are: 1) The Armijo condition is relaxed by an additive constant 2e,, to account for the inexact function evaluations, and 2) The first order oracle is called in each iteration, and new search direction is generated whenever the step size changes. This allows the method to progress to near-stationary points without assuming the gradient estimates (e.g. the mini-batch gradients in supervised learning) to be Lipschitz continuous.
Our framework and analysis are based on results in [CS17]. [GRVZI8] and [BCS19]. However, there are several key differences. In [CS17] and [BCS19] the line search has access to stronger ora- cles. with cg 0 and [f(x E) < ef deterministically. Under these assumptions, [CS17] and [BCS19] derive an expected iteration complexity bound. In this paper, we provide high probabil- ity tail bound on the iteration complexity, showing that the algorithm is very likely to succeed in a number of iterations on the order of its expected iteration complexity. Moreover, we consider more general oracles, with arbitrary 6g and possibly unbounded [x( ((x)). Thus, we significantly strengthen the results [CS17] and [BCS19]. To the best of our knowledge, the only other high probability complexity bound of this kind is derived in [GRVZ18] for a trust region algorithm under the assumption Eg = and [f E) - p(x)|= = 0 deterministically, which are much stronger oracles.
Stochastic line search has also been analyzed in [PS20] and [VML+19] In [PS20] the assumptions on {)( - (xx) are different. On the one hand, they allow for more general distributions than sub-exponential. On the other hand, it is assumed that [f {) - -(xr) can be made arbitrarily small with some fixed probability. An expected iteration complexity bound is then derived for arbitrarily small e. In contrast, we do not assume this, and analyze the iteration complexity of reaching an e-stationary point, with & lower-bounded by a function of the constants in the oracles. Moreover, our analysis and results are much simpler than those in [PS20] and we derive an iteration complexity bound in high probability, not just in expectation.
In [VML++ 11], the traditional line search is analyzed for empirical loss minimization, where the function oracles are implemented using random mini- batn-bbtchhhe of fixed size. The mini-bate remains

---

fixed during backtracking until standard Armijo condition is satisfied. Thus the search direction remains the same until a step taken. While good computational performance has been reported in [VML+19], its theoretical analysis requires several very restrictive assumptions, especially for non- convex functions. Also, they bound the expected sum of squared gradient norms, while we bound the iteration complexity with high probability. We note that using similar techniques as in [BCS19), our analysis can be extended to the convex and strongly convex cases.
In summary, we present an analysis of an adaptive line search algorithm under very general condi- tions on the gradient and function estimates. The results not only subsume most results in the prior literature, but also substantially extend the framework. Moreover, high probability tail bounds on iteration complexity are derived, instead of only expected iteration complexity.
2 Oracles
In this section, we discuss couple of settings, and show how they are captured by our framework. All norms used are 2-norm.
2.1 Expected loss minimization
Let us first discuss how the oracle definitions apply to expected loss minimization. In this setting, Φ(z) = Ed-DD [f( d).. Here, x is the model parameters. d a data sample following distribution D. and f(z, d) is the loss when the model parameterized by is evaluated on data point d.
In this case, the zeroth and first order oracles can be as follows, where S is a mini-batch sampled from D:
f(z,S)= = S
E((xd)) 9(z,S)= dES
Σ dl
S
dES
In general, S can be chosen depend on We now show how our zeroth and first order oracle conditions are satisfied by selecting an appropriate sample size S).
Proposition 1. Let é(0r, d) = f(r, d) - o(x) be a (D(x), b(axp--suexponeeniia random variable and VarawD [e(x,d) d)] I t(x)?, for some (x)) b(x), Let c(x,S) |f(x, - x(x) and N (S), then
Es (e(x,, S)] S
((x) ((x) and e(x,S) is (()))),(())-suubeee)) subexsonbbeooonniii..
1
VN
with vzz) b(z) Se² max
p(x) }(x)
VN
In the case when the support of D is bounded, l is Lipschitz, and the set of x we consider is bounded, the assumption of Proposition is satisfied. Thus, f(x,S) S) is zeroth order oracle with cf
sup, v ((x),
sup, vzz), and b sup, b(z), and ey can be made arbitrarily small by taking large enough sample.
Under standard assumptions on Vi(x,, d), for instance, suppose Assumption 4.3 [BCN18] holds: for some Me, Mo 2 0 and for all x,
EALD [Vl d) V < M. + M, [|
(4)
one can show g(x, 8) is first order oracle with large enough sample size.
Proposition 2. Let g = g(z, Assuming ELDD V((x d) = Vo(z), then
Me + Mo [ min [S] >
1 + ka)
?
K22 V {
implies
P(lg - -o(x)) < maxfeg, kalg/})) 2 1 - 8.
This bound implies looser bound of:
2M,
2M, (1 na)
SS| 2 max
8e2
6k²a²
3

---

Remark Let discuss what is required from the minibatch size in this setting. Unlike standard SGD, the minibatch size is chosen dynamically. When convergence to a stationary point is desired, 'g has to be zero, and gradient estimate Ib. tends to zero. Thus, lgg Vo(x)] also has to tend to
zero. If M, = O, then fixing the mini-batch size to be at least +x(++ provides a valid first order oracle. Thus, unless a tends zero, the minibatch size remains bounded from below. This is similar to the interpolation condition used in e.g. [BM11, VML* 19]. On the other hand, when Mc > O, the minibatch size has grow in order to approach a stationary point. This is similar to dynamic minibatch size selection, discussed, c.g. in [BCNW12]. The difference between our results and those [BCNW12] is that our batch bound implementable and guarantees convergence, while the one in [BCNW12] is implementable only as a heuristic. As our computational results show, however, fixed and small mini-batels size appears to work very well, perhaps because Mc is small.
2.2 Randomized finite difference gradient approximation
Gradient estimates based on randomized finite differences using noisy function evaluations have become popular for zeroth order optimization, particularly for model-free policy optimization in reinforcement learning [SHC+16, FGKM18].
In this setting, the zeroth order oracle is assumed to be available, but with a more strict assumption that e(x:) Ef deterministically. The first order oracle is obtained using the zeroth order oracle as follows. Let = {u, 1, 1,..., ( be a set of random vectors, with each vector following some "nice" distribution (e.g. standard Gaussian). Then,
12 f(x out, (((0)))((r, E)
g(x,u)=
ui.
(5)
a Ol4
where a is the sampling radius. The proposition below shows that (5) with a large enough sample size gives first order oracle.
Proposition 3. Let g(x,2), and fix eg 2 2VTLL + vnel)
where n is the dimension of x.
Then
LL'o'nnn + 4) + az n 18n Vo(x)]1
12r
4
M 2
min
22'
2
[vo())]
Itaa
implies
P ((11-VV(x)] max ka 2 1 6.
Note that in the setting, cg is a fixed bias dependent on a, and cannot be made arbitrarily small.
Remark Note that Eg defines the neighborhood of convergence for any method that relies this oracle, and the smallest value for 6g is achieved by setting o = O(VE)). Let us now discuss the
minibatch size. Under the assumption that ey is small, | L + 2)(n 4) + 12e7 is also small. Thus when [V>((>]] is larger than or on the order of <g. then the sample set size remains constant and is proportional to In [NS17] constant step size stochastic gradient descent is applied using sample size |4|| = 1, thus each step requires about n fewer samples. However, the step size has to be roughly times smaller to account for the variance of the stochastic oracles based one sample, thus the overall complexity is the same.
Other finite difference approximation schemes and their centralized versions (see [BCCS21] for a reference these) also give suitable first order oracles.
2.3
Other settings
Our oracle framework also fits variety of other settings, as we allow the randomness & and E' of the zeroth and first order oracles to be dependent on and on each other, possibly following different distributions. Moreover, the oracles allow the function and gradient estimations to be arbitrarily bad occasionally, which allows them to capture settings where measurements are corrupted with outliers. The exact derivations of these oracles in these different settings subjects of future exploration.

---

3
Algorithm and notation
We consider the line search algorithm proposed by [BCS19], which is extension of the line search algorithm in [CS17] to the setting of inexact function estimates. In both algorithms, a random gradient estimate is used to attempt step. We name the algorithm "ALOE", which stands for Adaptive Line-search with Oracle Estimations. Compared to [CS17], the key modification of the algorithm is the relaxation of the Armijo condition by additive constant 2 The difference between this algorithm and the more standard line search methods such as the ones in [NW06] and [VML+ 19] is that the gradient estimate is recomputed in each iteration, whether accepted. Note that all input parameters are user controlled, except for éy. In fact, the input ey here only required be some upper bound for E[e(=)]. not necessarily the tightest one. Moreover, our computational results in Section 6 indicate that estimating ey is relatively easy in practice, and the algorithm is robust to the choice of Ey.
step is
Algorithm Adaptive Line-search with Oracle Estimations (ALOE) Input: Parameter Ef of the zeroth order oracle, starting point zo, max step size O'max > initial step size og < O'axx constants 8, 1).
1: for k = 0, 2,....... do
2: Compute gradient approximation gk:
Generate the direction Jk ( (/) using the probabilistic first order oracle, with a Crj-
Check sufficient decrease:
Let x 2 aaggt- Generate f( and f fa & using the probabilistic
zeroth order oracle. Check the modified Armijo condition:
f( 5t) S f( Ex) ag |1 2cg-
4: Successful step:
If (6) holds, then set Tx+1 <- xx and 0441 + min (amxx 7 azz
5: Unsuccessful step:
Otherwise, set J&+1 <- and 01 you.
In this paper we impose the following standard assumption on ((x))
Assumption 1. VØ is L-Lipschitz smooth and 6 is bounded from below by some constant 6".
Let e₁ = (f {x) Φ(zx)l and 6g = 1f (1) from the definition of the zeroth order oracle. We will consider two cases; 1) e and ex are deterministically bounded by ey, in which case v and b in (1) can be chosen be O, and 2) v and are not necessarily zero, in which case we assume the random variables ej + ot are all independent.
- ó(x )I Recall that and et satisfy
Assumption 2. Either eo, e1, are all deterministically bounded by Eg, or the random variables {eu + + e0.e1 + ,...... are independent. Definition (Definition of true iteration). We say an iteration is true l1g - Vo(xx)] max(sg; karllgga)) and ex + +et S 22
false otherwise.
Let Mj denotes the triple (E,, tt whose realizations are (Ex, St. S.... Algorithm generates
a stochastic process adapted to the filtration (Fx : l 2 0}, where Fs = (My, My...., MR). We define the following random variables, measurable with respect to Fs.
Ig fiteration ie is true).
2 (iteration & is successfull.
T := minfk: : |[ S s}. the iteration complexity of the algorithm for reaching
c-stationarity.
Za Ō(xx)= 0" 2 0, measure of progress.
5

---

It is easy to see that T₃ is stopping time of the stochastic process with respect to Fi. We derive a high probability tail bound for T. and obtain an iteration complexity bound in high probability for Algorithm when applied to non-convex functions. The final result is summarized below with simplified constants. The full statement is in Theorem 4.
Theorem 1 (Main convergence result with simplified constants). Suppose Assumptions 1 and hold, and (for simplicity) 0 = 2' Qmax 2 1 and k 2 m Then, for any
E 2 4 max
Egg (1 + Kamaa)) V (L (L+2x)Er
have the following bound on ileration complexity:
For any s 2 0 1-11 -e min =2
202
+
4ey+s C .p. and
2
R
4oy (
o22
(-60- p)2
s2t st
})
PTe 1) 2 1- - exp
2p²
exp
min
8y2 46
Here, u - R
o(mo)=o' Ce*
In((L+2x)oo)
and C
In
2[L+2cx(1 (00mmx)))
Remark This theorem essentially shows that the iteration complexity of Algorithm is bounded by quantity the order of
((20) 0 In((L+ 2x)arp)
4ss p 2 C2T
Ce2
In
with overwhelmingly high probability. If p 1 and = 0, the above quantity essentially recovers the iteration complexity of the deterministic line search algorithm.
Analysis framework for the high probability bound
In this section present the main ideas underlying the theoretical analysis. We first state general conditions on the stochastic process (Assumption 3), from which we are able to derive a high prob- ability tail bound on the iteration complexity. They are listed assumptions here, and in the next section, we will show that they indeed hold for Algorithm I when applied to non-convex smooth functions
Assumption 3 (Properties of the stochastic process). There exist constant ā 0 and non- decreasing function R + R. which satisfies h(a) > for any a > 0, such that for any realization of the algorithm, the following hold for all l < Te:
(i) h(@)= > 8Eg.
(i) (T 1 ( for all k with some p dey M(j
1).
(ii) If T2 = 1then 7x+1 S 7g h((o))) + 46y- (True, successful iterations make progress.)
(iv) If < ā and 1s = then O₂ = 1.
(v) Zx+1 S 2 + 2 + e + et for all k.
The following key lemma follows easily from Assumption 3 (ii) and the Azuma-Hoo Hoeffding inequal- ity [Azu67] applied to the submartingale Σi=1 Is pt.
Lemma 1. For all 1 < Te, and any [0, p). have
(p (p-1)²
p)
P
E
S exp
2p²
We now define another indicator variable that will be used in the analysis.

---

Definition 2 (Large step). For all integers k 2 O, define the random variable Uk as follows:
UR = 1, if min ax+1 2 a 0, if max ax+1) } S a. We will say that step l is a large step if Us- = Otherwise, step k is ammll step.
By the dynamics of the process, every step is either a large step or a small step, but not both.
Our analysis will rely on the following key observation: By Assumption 3, if iteration & has Ug = 1, then Zx gets reduced by at least h((a) 4 > O. We call such an iteration "good" iteration, because it makes progress towards optimality by at least a fixed amount. On the other hand, on any other iteration k. Zy can increase by at most 2 + 6k + + The idea of the analysis is to show that with high probability, the progress made by the good iterations dominates the damage caused by the other iterations. The crux of the proof is to show that with high probability, a large enough constant fraction of the iterations are good (up another additive constant).
The following key lemma is the engine of the analysis. shows that if the stopping time has not been reached and a large enough number of iterations are true, then there must be large number of good iterations.
Lemma 2. For any positive integer t and any e E (2, we have
UnOuI2 < (p-1) 11 2 2
d
IP
T3 > t and
Σ l
2 pt and
t
= 0,
k=0
k=0
where d = max
In ogg In lu 7
4.1 Bounded noise case
In [CS17] and [BCS19], the expected iteration complexity of the line search algorithm is bounded under the assumptions that e(x) = 0 and e(x) S é, for x, respectively. We now derive a high probubility tail bound on the iteration complexity under the assumption that e(x)) S ey for all
x. Note that we do not need to assume that the errors e(x) are independent in the bounded noise setting. Thus, this analysis applies even when the noise is deterministic adversarial.
Under Assumption 3 in the bounded noise setting, we have Zk+1 S 7 + 4eg in all iterations, and Z4+1 I Zx- h(ā:) + 4cg in good iterations. Putting this together with Lemma 2 and the other conditions in Assumption we obtain the following theorem.
Theorem (Iteration complexity in the bounded noise setting). Suppose Assumption 3 holds, and n we have P- 2-
Ck o S Cf at every iteration. Then for any P E ( +
deg P()) and t 2
(p (p-p)" 8)2
(T 51) 2 1
exp
2p²
where R
+ and d = max k(a]
Zo
In ln In
0
4.2 General sub-exponential noise case
We now present high probability bound for the iteration complexity with general sub-exponential noise in the zeroth order oracle. The result very similar to that of Theorem 2. The main difference from the bounded noise analysis is that instead of bounding the "damage" caused on a per- per-iteration basis, we bound the sum of all such damages over all iterations. The fact that the noises are sub- exponential and independent allows us to apply Bernstein's 's inequality to obtain upper bound on this sum that holds with high probability.
Theorem 3 (Iteration complexity in the sub-exponential noise setting). Suppose Assumptions 2 and 4e,ts "(a)
3 hold. Then for any
0, E
(1
.p), and >
R
F. have
b(8)
(p
2)2
P (T S 1) 2 1 exp
min
2p²
where Zo k(a]
+ and d max
on In In
0
7

---

Final iteration complexity of the line search algorithm
In the previous section, we presented high probability tail bounds the iteration complexity, suming Assumption 3 holds. We now verify that Assumption 3 indeed holds for Algorithm when applied smooth functions. Together with the results in Section this allows us derive an explicit high-probability bound on the iteration complexity.
As noted earlier, when either c, (g are not zero, Algorithm does not converge to a stationary point, but converges a neighborhood where [|Vo(z)] E, with bounded from below in terms of ef Eg. The specific relationship is as follows. Inequality 1 (Lower bound on E).
E E> max Eg max 1+ max:
1
4e
0.5L + K
L(1 - 17) 21j 0(1 17))
--n
0(p
2)
max
1- 2((
for some 7) (0, )-
Here 1l can be any value in the interval.
5 when in the bounded noise setting, and
1 - 8 - exp min! # サ} otherwise, with ur = inf { E[e(=)]}
Proposition 4 (Assumption holds for Algorithm 1). If Inequality and Assumption I and 2 hold, then Assumption holds for Algorithm I with the following p. ã and h(o.):
1. 1- when the noise is bounded by ey. and p 1 - - 6exp (-min({ u² otherwise. Here = infa - B[e(x))}}
2 26
2. ā min 1-0 0.6L+x*
211-2n-0(1-1 0(1-1))
[1--)
3. M() min
0 (I+xamax)) J. 0o
2
Applying Theorem now gives the explicit complexity bound for Algorithm 1.
Theorem 4. Suppose the Inequality I on E is satisfied for some E (0, 1-2)) and Assumptions
1 and 2 hold, then we have the following bound on the iteration complexity: For any s 2 0, p e testo
( + Ge2 .P), and 2
I1
(p (D-1))
s²t st
})
P St2 exp
1) exp
min
2p²
8y22 4b
Here, R = 6(20)_0" + max { Cea
Ima--la lu
00. C -min (I+xamee)* 12, (1 7)2 at, with p and a lny
as defined Proposition
Remark Inequality makes sure there exists some P E ( 4erts Cet . p) for some 0. The above theorem is for the general sub-exponential noise setting. In the bounded noise special case, we have st } Bu ab
s = 0, and the last term exp
min
the probability is not present.
Experiments
In this section, we illustrate that the proposed stochastic algorithm ALOE can be at least as efficient in practice as the line search in [VML-11) 19], and much more efficient than full gradient line search. difficult, and taking mini-batches of fixed
From the experiments, we show that estimating é size indeed provides good zeroth and first order oracles in practice.
For illustration, we first conduct experiments on all the datasets for binary classification with 150 to 5000 data points from the Penn Machine Learning Benchmarks repository (PMLB) [RLLC+21]. In total, there are 64 such datasets. Each binary classification problem is formulated as a logistic

---

regression problem with an RBF kernel (with parameter = 1). All experiments were conducted on a 2020 MacBook Pro with an MI chip and 16GB of memory.
We compare the following three algorithms, and they are implemented as follows.
The zeroth and first order oracles are implemented using the same mini-batch of a fixed size within each iteration. Batch sizes are taken to 128. We estimate ef at the beginning of every epoch (i.e. every K iterations, where K equals the total number of data samples divided by 128), by computing times the empirical standard deviation of 30 zeroth order oracle calls with batch size 128 at the current point. We found in practice the algorithm quite robust to how Ef is chosen. The relevant plots are in Appendix F. The parameter we used are 0.8, 0 = 0.2, ag 1 and Ommax = 10.
ALOE.
SLS. The SLS algorithm (also called "SGD Armijo") proposed in 19] differs from ALOE in that cf and that the same mini-batch is used while backtracking until the Armijo condition is satisfied. We implemented the algorithm using mini-bated size 128 and the parameters suggested in their paper. We tried various parameter combinations for SLS and found the performance of the suggested parameters to work best.
Full gradient line search. The full gradient line search algorithm is implemented using the entire dataset for function and gradient evaluations each iteration. Taking e and the other parameters are the same as used in ALOE. For fair comparison in our experiments, we allow full gradient line search to make the same number of passes over each dataset as ALOE.
We conducted 5 trials for each dataset and ran each algorithm with initial points taken randomly from a standard Gaussian distribution. In Figure we compare the overall performance of the three algorithms in the following way. For each dataset and algorithm, the average best value is defined as the average of the minimum training loss attained over 5 different trials. For each dataset we record the difference between the average best values achieved by SLS vs. ALOE, and plot the resulting 64 numbers as histogram. The same is done for full gradient line search vs. ALOE. See Figure 1. Under this metric, ALOE achieves better training loss than SLS algorithm 62 out of 64 datasets, and is always better than the full gradient line search.
Figure 2 illustrates the decay of training losses using these three algorithms for three datasets. In many cases ALOE decreases the training loss more rapidly than the other two algorithms. Testing set accuracy comparisons
also carried out, using random 80 20 splits of datasets, shown in Fig- ure Test accuracy is defined as the proportion data points in the testing set classified correctly. The results show that ALOE is competitive in terms of test accuracy well. More performance and test accuracy plots for different datasets, models and loss functions are in Appendix.
SLS minus ALOE
Full gradient LS minus ALOE
number of datasets
number of datasets
2
30-
20.
20
60
04
0.5
29
24
training loss difference
trainind loss difference
Figure 1: The performance of ALOE is consistently better (above 0) compared to SLS and full gradient line search over the 64 datasets, with bigger advantage over full gradient line search.
Final Remarks
We conclude the paper with a brief overview of our theoretical results with respect to those in [VML+19) 19]. The stochastic line search in [VML+19] is proposed specifically for empirical risk minimization, and the zeroth and first order oracles are implemented using mini-batch of a fixed size. The same mini-batch used for all consecutive unsuccessful iterations. This guarantees that
successful iteration is eventually achieved for Armijo condition with e O, under the assumption

---

Training loss for chess
Training loss for spambase
Training loss spect
12"
SLS
Full gradient L5
Full gradient LS
Full gradient LS
iteration
iteration
iteration
Figure 2: The training loss decays of three algorithms.
Test accuracy chess
Test accuracy of spambase
Test accuracy of spect
ALOE
SLS
0.7
Full gradient LS
38
ALDE
ALOE
08-
SLS
SLS
Full gradient LS
Full gradient
Iteration
iteration
iteration
Figure 3: The testing accuracy improvements of three algorithms.
that for every mini mini-bbtch,, (xz, E¹) is Lipschitz continuous. The convergence analysis then assumes that Mr in (4) (strong growth condition) and in the case when ø is not convex, the step size parameter is bounded above by LM. Thus, the method itself and its convergence are not better than those of stochastic gradient descent with fixed step size bounded by LM. [BCN18]. It is also assumed that the step size reset fixed value at the start of each iteration, which is impractical. Good computational results are reported in [VML** 19] for a heuristic version of the algorithm where the restrictions of the step size are removed.
1
In this paper we analyzed Algorithm under virtually no restriction on the step size parameter. For the sake of simplicity of analysis, assume the step size parameter is reduced and increased by the same multiplicative factor. This can be relaxed to some degree. We also do not assume that g(x, E') is Lipschitz continuous, assumptions is the use of éj. For simplicity of the analysis, é is assumed to be fixed throughout the algorithm. In practice, it can be re-estimated regularly. In many applications, E tends to get smaller as the algorithm progresses towards optimality. Our experiments show that estimating ey is easy and much smaller values for cf than theory dictates.
only impose this condition
Φ. The cost of relaxing all these
works well in practice. Moreover,
8 Acknowledgments
This work was partially supported by NSF Grants TRIPODS 17-40796, NSF Grant CCF 2008434 and DARPA Lagrange award AIR-001117S0033 Miaolan Xie partially supported by PhD Fellowship provided by MunchRe. Billy Jin was partially supported by NSERC fellowship PGSD3- 532673-2019.
The authors grateful to the anonymous referees for their reviews that helped us improve the paper.
10

---

References
[Azu67]
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Math- emalical Journal, 19(3):357 - 367, 1967.
[BCCS21] Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free op- timization. Foundations of Computational Mathematics, 2021.
[BCN18] Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
[BCNW12] R. Byrd, G. M. Chin, J. Nocedal, and Y. Wu. Sample size selection in optimization methods for machine learning. Mathematical Programming, 134:127-155: 2012.
[BCS19] Albert S Berahas, Liyuan Cao, and Katya Scheinberg. Global convergence rate anal- ysis of generic line search algorithm with noise. SIAM Journal on Optimization, 2019.
[BMII]
F. Bach and E. Moulines. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. In Advances Neural Information Processing Systems 24: 25th Annual Conference Neural Information Processing Systems 2011. Pro- ceedings of a meeting held 12-14 December 2011, Granada, Spain., pages 451-459, 2011.
[CS17]
C. Cartis and K. Scheinberg. Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming. 169(2):337-375, 2017.
[FGKM18]
Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator, In International Con- ference on Machine Learning, pages 1467-1476, 2018.
[GRVZ18] Serge Gratton, Clément W Royer, Luís Vicente, and Zaikun Zhang. Complexity and global rates of trust-region methods based on probabilistic models. IMA Journal of Numerical Analysis, 38(3):1579-1599) 2018.
[NS17]
Yurii Nesterov and Vladimir Spokoiny. Random gradient- minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
[NW06]
J. Nocedal and S.J. Wright. Numerical Optimization, Second Edition. Springer, 2006.
[PS20]
Courtney Paquette and Katya Scheinberg. A stochastic line search method with ex- pected complexity analysis. SIAM Journal on Optimization, 30( (0(1):349-37)) 2020.
[RLLC+21] Joseph D Romano, Trang T Le, William La Cava, John T Gregg. Daniel J Goldberg, Praneel Chakraborty, Natasha Ray, Daniel Himmelstein, Weixuan Fu, and Jason H Moore. Pmlb v1.0: open source dataset collection for benchmarking machine learn- ing methods. arXiv preprint arXiv:2012.00058:: 2021.
[SHC+16 16] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolu- tion strategies scalable alternative to reinforcement learning. Technical Report 2016.
[Ver18]
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[VML+19] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
11


Reviews:
[{"review_id": "w8ecTSgJb9O", "reviewer": "Reviewer_EQ5H", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nBelow are some comments. \n- 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?  \n- 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? \n- 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? \n- 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. \n- Line 293: Why is resetting the step size in each iteration is \"impractical\"? \n\nThe presentation is clear. Below are some comments on the presentation: \n- Line 85: Saying the existing assumptions are \"very restrictive\" is vague. In what sense are they restrictive? \n- 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. \n- Line 240: The name of the proposed algorithm should be appear in the second last section. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please address my comments in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "rCR6sa9AgGa", "reviewer": "Reviewer_ApuJ", "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.\nFor 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.\n\nThe random variable in the oracle, could for instance represent the mini-batch used to estimate the required quantity.\nThe authors propose a variant of Armijo Line search that\n - Adds some slack on the Armijo condition depending on the quality of the zeroth order oracle\n - Recompute gradient and function values in each step in the line search instead of using the same one.\n\nFor this line search method the authors show high probability iteration bounds for minimizing a Lipshitz bounded smooth function,\nthat converge to an epsilon stationary point (norm gradient less than epsilon) where epsilon is lower bounded by the quality of the oracles. \nThe 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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\nNonetheless, the experiments confirm that the proposed line searching method works well in this case.\nIt 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,\nalbeit such problems may have a lot of moving parts to control that make it hard to isolate the value of the algorithm proposed.\n\nIt 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),\nat 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?\n\nOverall I think the proposed algorithm is nice and fairly simple which is positive albeit there are some  parameters that need setting.\nThe actual Theorem has a lot of parameters but the overall message can be extracted, and the result is quite general.\n\n- The norms in equation 2, and in general, is that any norm? or maybe the two norm of the vector?\n- Assumption 2, is that a standard assumption that the errors in different steps are independent (they could depend on the same x here)?\n- Does the iteration bound (almost) match an obvious lower bound for this kind of oracles?\n- 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).\n- why use absolute values around |e(x)|  on line 200 - 202, e(x) is already non-negative. Am I missing something there?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "GRNetkJKdC4", "reviewer": "Reviewer_1krj", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI have some confusions in this work, hope authors can add more discussion to address:\n- 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?\n- 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.\n- 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)$. \n\nBased 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not involve issues related to the negative impact of society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "-fXLlGUsVih", "reviewer": "Reviewer_V21B", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The structure of the paper is clear and most contents are easy to follow.\n- Related works are well-addressed to my knowledge.\n\nCons:\n- 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.\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work and I do not see any limitation and negative social impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concern.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

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)