High Probability Complexity Bounds for Line Search Based on Stochastic Oracles
Year: 2021

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.

heading: 1 Introduction
text: In this paper, we analyze a line-search method when applied to the problem of minimizing an unconstrained, differentiable, possibly non-convex function : Rn ! R. The goal is to find a "-stationary point for ; that is, a point x with kr (x)k  ". We make the standard assumption that r is LLipschitz, but the knowledge of L is not assumed by the algorithm. We consider a setting where neither the function value (x) nor the gradient r (x) are directly computable. Instead, the algorithm is given black-box access to the following probabilistic oracles:
• Probabilistic zeroth order oracle. Given a point x, the oracle computes f(x, ⇠), a (random) estimate of the function value (x). ⇠ is a random variable (whose distribution may depend on x), with probability space (⌦,F⌦, P ). We assume the absolute value of the estimation error e(x) = |f(x, ⇠(x)) (x)| (we omit the dependence on ⇠ for brevity) to be a “one-sided” sub-exponential-like random variable1 with parameters (⌫, b), whose mean is bounded by some constant ✏f > 0. Specifically,
E⇠ [e(x)]  ✏f and E⇠ [exp{ (e(x) E[e(x)])}]  exp ✓ 2⌫2
2
◆ , 8 2  0, 1
b
. (1)
• Probabilistic first order oracle. Given a point x and a constant ↵ > 0, the oracle computes g(x, ⇠0), a (random) estimate of the gradient r (x), such that
P⇠0 (kg(x, ⇠0) r (x)k max{✏g,↵kg(x, ⇠0)k}) 1 . (2) Here, ⇠0 is a random variable (whose distribution may depend on x), with associated probability space (⌦0,F⌦0 , P 0). (1 ) 2 (0, 1) is the probability, intrinsic to the oracle, that the
1This is a weaker requirement than assuming e(x) to be sub-exponential, as one only needs to guard against the possibility of the error e(x) being too large.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
gradient estimate is “sufficiently accurate” with respect to ✏g,, and ↵. Lastly, , ✏g 0 are constants, intrinsic to the oracle, which represent the precision the oracle can achieve. Note that ✏g allows the gradient estimate to be bounded away from the true gradient by a constant distance.
Remark We will analyze a line search algorithm that relies on these two oracles. In the zeroth order oracle, the constants ✏f and (⌫, b) are intrinsic. In the first order oracle, , ✏g , and are intrinsic. These values cannot be controlled. On the other hand, ↵ is an input to the first order oracle that can be chosen by the algorithm. In fact, as we shall see in Section 3, ↵ will be the step size of the line search method.
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 ⇠0 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, as is used in [SHC+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. Specifically, if ✏f = 0 and ✏g = 0, then the algorithm converges to a stationary point. Otherwise, a precise lower bound is derived for the smallest kr (x)k 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 it satisfies 1. Moreover, the first order oracle only requires g(x, ⇠0(x)) to be a “sufficiently accurate” estimate ofr (x) with probability 1 . Thus g(x, ⇠0(x)) can be an arbitrary vector with probability , so it in principle can have an arbitrarily large bias.
The line-search algorithm is given in Section 3. It 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 2✏f , to account for the inexact function evaluations, and 2) The first order oracle is called in each iteration, and a 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], [GRVZ18] and [BCS19]. However, there are several key differences. In [CS17] and [BCS19] the line search has access to stronger oracles, with ✏g = 0 and |f(x, ⇠) (x)| ✏f deterministically. Under these assumptions, [CS17] and [BCS19] derive an expected iteration complexity bound. In this paper, we provide a high probability 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 ✏g and possibly unbounded |f(x, ⇠) (x)|. Thus, we significantly strengthen the results in [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 ✏g = 0 and |f(x, ⇠) (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 |f(x, ⇠) (x)| are different. On the one hand, they allow for more general distributions than sub-exponential. On the other hand, it is assumed that |f(x, ⇠) (x)| can be made arbitrarily small with some fixed probability. An expected iteration complexity bound is then derived for arbitrarily small ". In contrast, we do not assume this, and analyze the iteration complexity of reaching an "-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+19], the traditional line search is analyzed for empirical loss minimization, where the function oracles are implemented using a random mini-batch of a fixed size. The mini-batch remains
fixed during backtracking until a standard Armijo condition is satisfied. Thus the search direction remains the same until a step is taken. While good computational performance has been reported in [VML+19], its theoretical analysis requires several very restrictive assumptions, especially for nonconvex 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 conditions 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.

heading: 2 Oracles
text: In this section, we discuss a couple of settings, and show how they are captured by our framework. All norms used are 2-norm.

heading: 2.1 Expected loss minimization
text: Let us first discuss how the oracle definitions apply to expected loss minimization. In this setting, (x) = Ed⇠D[`(x, d)]. Here, x is the model parameters, d is a data sample following distribution D, and `(x, d) is the loss when the model parameterized by x 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(x,S) = 1
|S|
X d2S `(x, d), g(x,S) = 1 |S| X d2S rx`(x, d). (3)
In general, S can be chosen to depend on x. We now show how our zeroth and first order oracle conditions are satisfied by selecting an appropriate sample size |S|.
Proposition 1. Let ê(x, d) := `(x, d) (x) be a (⌫̂(x), b̂(x))-subexponential random variable and Vard⇠D [`(x, d)]  ✏̂(x)2, for some ⌫̂(x), b̂(x), ✏̂(x). Let e(x,S) = |f(x,S) (x)| and N = |S|, then
ES [e(x,S)]  1 p N ✏̂(x) and e(x,S) is (⌫(x), b(x))-subexponential,
with ⌫(x) = b(x) = 8e2 max n
⌫̂(x)p N , b̂(x)
o .
In the case when the support of D is bounded, ` is Lipschitz, and the set of x we consider is bounded, the assumption of Proposition 1 is satisfied. Thus, f(x,S) is a zeroth order oracle with ✏f = supx 1p N ✏̂(x), ⌫ = supx ⌫(x), and b = supx b(x), and ✏f can be made arbitrarily small by taking a large enough sample.
Under standard assumptions on r`(x, d), for instance, suppose Assumption 4.3 in [BCN18] holds: for some Mc,Mv 0 and for all x,
Ed⇠D kr`(x, d) r (x)k2 Mc +Mv kr (x)k2 , (4) one can show g(x,S) is a first order oracle with a large enough sample size. Proposition 2. Let g = g(x,S). Assuming Ed⇠Dr`(x, d) = r (x), then
|S| Mc +Mv kr (x)k
2
min
( 1
✏2g ,
(1 + ↵)2
2↵2 kr (x)k2
)
implies P (kg r (x)k  max{✏g,↵kgk}) 1 .
This bound implies a looser bound of:
|S| max ( 2Mc ✏2g , 2Mv(1 + ↵) 2 2↵2 ) .
Remark Let us 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 gk tends to zero. Thus, kg r (x)k also has to tend to zero. If Mc = 0, then fixing the mini-batch size to be at least Mv(1+↵) 2
2↵2 provides a valid first order oracle. Thus, unless ↵ tends to 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 > 0, the minibatch size has to grow in order to approach a stationary point. This is similar to dynamic minibatch size selection, discussed, e.g. in [BCNW12]. The difference between our results and those in [BCNW12] is that our batch bound is implementable and guarantees convergence, while the one in [BCNW12] is implementable only as a heuristic. As our computational results show, however, a fixed and small mini-batch size appears to work very well, perhaps because Mc is small.

heading: 2.2 Randomized finite difference gradient approximation
text: 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)  ✏f deterministically. The first order oracle is obtained using the zeroth order oracle as follows. Let U = {ui : i = 1, . . . , |U|} be a set of random vectors, with each vector following some “nice” distribution (e.g. standard Gaussian). Then,
g(x,U) =
|U|X
i=1
f(x+ ui, ⇠) f(x, ⇠)
|U| ui, (5)
where is the sampling radius. The proposition below shows that (5) with a large enough sample size gives a first order oracle. Proposition 3. Let g = g(x,U), and fix ✏g = 2 ⇣ p nL + p n✏f ⌘ where n is the dimension of x.
Then
|U|
3 4L 2 2n(n+ 2)(n+ 4) + 12✏2f 2 n+ 18n kr (x)k 2
min
8 >< >: 4 ✏2g , 1 ⇣
↵ 1+↵ kr (x)k ✏g 2
⌘2
9 >=
>;
implies P (kg r (x)k  max{✏g,↵kgk}) 1 . Note that in the setting, ✏g is a fixed bias dependent on , and cannot be made arbitrarily small.
Remark Note that ✏g defines the neighborhood of convergence for any method that relies on this oracle, and the smallest value for ✏g is achieved by setting = O( p ✏f ). Let us now discuss the
minibatch size. Under the assumption that ✏f is small, 34L 2 2n(n+ 2)(n+ 4) + 12✏2f 2 is also small. Thus when kr (x)k is larger than or on the order of ✏g , then the sample set size remains constant and is proportional to n. In [NS17] a constant step size stochastic gradient descent is applied using sample size |U| = 1, thus each step requires about n fewer samples. However, the step size has to be roughly n times smaller to account for the variance of the stochastic oracles based on one sample, thus the overall complexity is the same.
Other finite difference approximation schemes and their centralized versions (see [BCCS21] for a reference on these) also give suitable first order oracles.

heading: 2.3 Other settings
text: Our oracle framework also fits a variety of other settings, as we allow the randomness ⇠ and ⇠0 of the zeroth and first order oracles to be dependent on x 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 are subjects of future exploration.

heading: 3 Algorithm and notation
text: We consider the line search algorithm proposed by [BCS19], which is an 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 a 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 an additive constant 2✏f . 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 or not a step is accepted. Note that all input parameters are user controlled, except for ✏f . In fact, the input ✏f here is only required to be some upper bound for E[e(x)], not necessarily the tightest one. Moreover, our computational results in Section 6 indicate that estimating ✏f is relatively easy in practice, and the algorithm is robust to the choice of ✏f .
Algorithm 1 Adaptive Line-search with Oracle Estimations (ALOE) Input: Parameter ✏f of the zeroth order oracle, starting point x0, max step size ↵max > 0, initial step size ↵0 < ↵max, constants ✓, 2 (0, 1).
1: for k = 0, 1, 2, . . . do 2: Compute gradient approximation gk:
Generate the direction gk = g(xk, ⇠0k) using the probabilistic first order oracle, with ↵ = ↵k.
3: Check sufficient decrease: Let x+k = xk ↵kgk. Generate f(xk, ⇠k) and f(x + k , ⇠ + k ) using the probabilistic
zeroth order oracle. Check the modified Armijo condition:
f(x+k , ⇠ + k )  f(xk, ⇠k) ↵k✓ kgkk 2 + 2✏f . (6)
4: Successful step: If (6) holds, then set xk+1 x+k and ↵k+1 min{↵max,
1↵k}. 5: Unsuccessful step:
Otherwise, set xk+1 xk and ↵k+1 ↵k.
In this paper we impose the following standard assumption on (x). Assumption 1. r is L-Lipschitz smooth and is bounded from below by some constant ⇤.
Let ek = |f(xk, ⇠k) (xk)| and e+k = |f(x + k , ⇠ + k ) (x + k )|. Recall that ek and e + k satisfy (1) from the definition of the zeroth order oracle. We will consider two cases; 1) ek and e+k are deterministically bounded by ✏f , in which case ⌫ and b in (1) can be chosen to be 0, and 2) ⌫ and b are not necessarily zero, in which case we assume the random variables ek+ e+k are all independent.
Assumption 2. Either e0, e+0 , e1, e + 1 , . . . are all deterministically bounded by ✏f , or the random variables {e0 + e+0 , e1 + e + 1 , . . .} are independent. Definition 1 (Definition of a true iteration). We say an iteration k is true if kgk r (xk)k max{✏g,↵kkgkk} and ek + e+k  2✏f ,
and false otherwise.
Let Mk denotes the triple {⌅k,⌅+k ,⌅ 0 k}, whose realizations are {⇠k, ⇠ + k , ⇠ 0 k}. Algorithm 1 generates a stochastic process adapted to the filtration {Fk : k 0}, where Fk = (M0,M1, . . . ,Mk). We define the following random variables, measurable with respect to Fk.
• Ik := {iteration k is true}. • ⇥k := {iteration k is successful}. • T" := min{k : kr (xk)k  "}, the iteration complexity of the algorithm for reaching "-stationarity.
• Zk := (xk) ⇤ 0, a measure of progress.
It is easy to see that T" is a stopping time of the stochastic process with respect to Fk. We derive a high probability tail bound for T✏, and obtain an iteration complexity bound in high probability for Algorithm 1 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 2 hold, and (for simplicity) ✓ = 12 , ↵max 1 and  max{L, 1}. Then, for any
" 4max ⇢ ✏g, (1 + ↵max) q (L+ 2)✏f ,
we have the following bound on iteration complexity:
For any s 0, p = 1 e min{ u2 2⌫2 , u2b}, p̂ 2 ( 12 + 4✏f+s C"2 , p), and t
R
p̂ 12 4✏f+s
C"2
,
P (T"  t) 1 exp ✓ (p p̂)2
2p2 t
◆ exp ✓ min ⇢ s2t
8⌫2 , st 4b
◆ .
Here, u = infx{✏f E[e(x)]}, R = (x0) ⇤ C"2 ln((L+2)↵0) ln , and C = 1 2(L+2)(1+↵max)2 .
Remark This theorem essentially shows that the iteration complexity of Algorithm 1 is bounded by a quantity on the order of
1
p 12 4✏f+s C"2
✓ (x0) ⇤
C"2
ln((L+ 2)↵0)
ln
◆
with overwhelmingly high probability. If p = 1 and ✏f = 0, the above quantity essentially recovers the iteration complexity of the deterministic line search algorithm.

heading: 4 Analysis framework for the high probability bound
text: In this section we 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 probability tail bound on the iteration complexity. They are listed as assumptions here, and in the next section, we will show that they indeed hold for Algorithm 1 when applied to non-convex smooth functions . Assumption 3 (Properties of the stochastic process). There exist a constant ↵̄ > 0 and a nondecreasing function h : R ! R, which satisfies h(↵) > 0 for any ↵ > 0, such that for any realization of the algorithm, the following hold for all k < T":
(i) h(↵̄) > 8✏f .
(ii) P(Ik = 1 | Fk 1) p for all k, with some p 2 ( 12 + 4✏f h(↵̄) , 1].
(iii) If Ik⇥k = 1 then Zk+1  Zk h(↵k) + 4✏f . (True, successful iterations make progress.)
(iv) If ↵k  ↵̄ and Ik = 1 then ⇥k = 1.
(v) Zk+1  Zk + 2✏f + ek + e+k for all k.
The following key lemma follows easily from Assumption 3 (ii) and the Azuma-Hoeffding inequality [Azu67] applied to the submartingale Pt 1 k=0 Ik pt.
Lemma 1. For all 1  t  T", and any p̂ 2 [0, p), we have
P
t 1X
k=0
Ik  p̂t
!  exp ✓ (p p̂)2
2p2 t
◆ .
We now define another indicator variable that will be used in the analysis.
Definition 2 (Large step). For all integers k 0, define the random variable Uk as follows:
Uk = ⇢ 1, if min{↵k,↵k+1} ↵̄, 0, if max{↵k,↵k+1}  ↵̄.
We will say that step k is a large step if Uk = 1. Otherwise, step k is a small 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 k has Uk⇥kIk = 1, then Zk gets reduced by at least h(↵̄) 4✏f > 0. We call such an iteration a “good” iteration, because it makes progress towards optimality by at least a fixed amount. On the other hand, on any other iteration k, Zk can increase by at most 2✏f + ek + e+k . 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 to another additive constant).
The following key lemma is the engine of the analysis. It shows that if the stopping time has not been reached and a large enough number of iterations are true, then there must be a large number of good iterations. Lemma 2. For any positive integer t and any p̂ 2 ( 12 , 1], we have
P T" > t and
t 1X
k=0
Ik p̂t and t 1X
k=0
Uk⇥kIk <
✓ p̂ 1
2
◆ t d
2
! = 0,
where d = max n
ln↵0 ln ↵̄ ln , 0
o .

heading: 4.1 Bounded noise case
text: 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)  ✏f for all x, respectively. We now derive a high probability tail bound on the iteration complexity under the assumption that e(x)  ✏f 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 or adversarial.
Under Assumption 3 in the bounded noise setting, we have Zk+1  Zk + 4✏f in all iterations, and Zk+1  Zk h(↵̄) + 4✏f in good iterations. Putting this together with Lemma 2 and the other conditions in Assumption 3, we obtain the following theorem. Theorem 2 (Iteration complexity in the bounded noise setting). Suppose Assumption 3 holds, and ek, e + k  ✏f at every iteration. Then for any p̂ 2 ( 1 2 + 4✏f h(↵̄) , p), and t R
p̂ 12 4✏f h(↵̄)
we have
P (T"  t) 1 exp ✓ (p p̂)2
2p2 t
◆ ,
where R = Z0h(↵̄) + d 2 and d = max
n
ln↵0 ln ↵̄ ln , 0
o .

heading: 4.2 General sub-exponential noise case
text: We now present a high probability bound for the iteration complexity with general sub-exponential noise in the zeroth order oracle. The result is 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-iteration basis, we bound the sum of all such damages over all iterations. The fact that the noises are subexponential and independent allows us to apply Bernstein’s inequality to obtain an upper bound on this sum that holds with high probability. Theorem 3 (Iteration complexity in the sub-exponential noise setting). Suppose Assumptions 2 and 3 hold. Then for any s 0, p̂ 2 ( 12 + 4✏f+s h(↵̄) , p), and t R
p̂ 12 4✏f+s h(↵̄)
, we have
P (T"  t) 1 exp ✓ (p p̂)2
2p2 t
◆ e min n s2t 8⌫2 , st4b o ,
where R = Z0h(↵̄) + d 2 and d = max
n
ln↵0 ln ↵̄ ln , 0
o .

heading: 5 Final iteration complexity of the line search algorithm
text: In the previous section, we presented high probability tail bounds on the iteration complexity, assuming Assumption 3 holds. We now verify that Assumption 3 indeed holds for Algorithm 1 when applied to smooth functions. Together with the results in Section 4, this allows us to derive an explicit high-probability bound on the iteration complexity.
As noted earlier, when either ✏f or ✏g are not zero, Algorithm 1 does not converge to a stationary point, but converges to a neighborhood where kr (x)k ", with " bounded from below in terms of ✏f or ✏g . The specific relationship is as follows. Inequality 1 (Lower bound on ").
" > max ( ✏g ⌘ ,max ⇢ 1 + ↵max, 1 1 ⌘ · s 4✏f
✓(p 12 ) ·max
⇢ 0.5L+ 
1 ✓ ,
L(1 ⌘)
2(1 2⌘ ✓(1 ⌘))
) ,
for some ⌘ 2 (0, 1 ✓2 ✓ ).
Here ⌘ can be any value in the interval. p = 1 when in the bounded noise setting, and p = 1 exp ⇣ min{u 2
⌫2 , u b } ⌘ otherwise, with u = infx{✏f E[e(x)]}.
Proposition 4 (Assumption 3 holds for Algorithm 1). If Inequality 1 and Assumption 1 and 2 hold, then Assumption 3 holds for Algorithm 1 with the following p, ↵̄ and h(↵):
1. p = 1 when the noise is bounded by ✏f , and p = 1 exp ⇣ min{ u 2 2⌫2 , u 2b} ⌘
otherwise. Here u = infx{✏f E[e(x)]}.
2. ↵̄ = min n
1 ✓ 0.5L+ , 2(1 2⌘ ✓(1 ⌘)) L(1 ⌘)
o .
3. h(↵) = min n
✓✏2↵ (1+↵max)2
, ✓↵(1 ⌘)2✏2 o .
Applying Theorem 3 now gives the explicit complexity bound for Algorithm 1.
Theorem 4. Suppose the Inequality 1 on " is satisfied for some ⌘ 2 (0, 1 ✓2 ✓ ), and Assumptions 1 and 2 hold, then we have the following bound on the iteration complexity: For any s 0, p̂ 2 ( 12 + 4✏f+s C"2 , p), and t R
p̂ 12 4✏f+s
C"2
,
P (T"  t) 1 exp ✓ (p p̂)2
2p2 t
◆ exp ✓ min ⇢ s2t
8⌫2 , st 4b
◆ .
Here, R = (x0) ⇤ C"2 +max n ln↵0 ln ↵̄ ln , 0 o , C = min n 1 (1+↵max)2 , (1 ⌘)2 o ↵̄✓, with p and ↵̄ as defined in Proposition 4.
Remark Inequality 1 makes sure there exists some p̂ 2 ( 12 + 4✏f+s C"2 , p) for some s > 0. The above theorem is for the general sub-exponential noise setting. In the bounded noise special case, we have s = 0, and the last term exp ⇣ min n s2t 8⌫2 , st 4b o⌘ in the probability is not present.

heading: 6 Experiments
text: 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+19], and much more efficient than full gradient line search. From the experiments, we show that estimating ✏f is not difficult, and taking mini-batches of a fixed 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 M1 chip and 16GB of memory.
We compare the following three algorithms, and they are implemented as follows.
• ALOE. 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 be 128. We estimate ✏f 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 15 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 is quite robust to how ✏f is chosen. The relevant plots are in Appendix F. The parameter we used are = 0.8, ✓ = 0.2, ↵0 = 1 and ↵max = 10.
• SLS. The SLS algorithm (also called “SGD + Armijo”) proposed in [VML+19] differs from ALOE in that ✏f = 0 and that the same mini-batch is used while backtracking until the Armijo condition is satisfied. We implemented the algorithm using mini-batch 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 on each iteration. Taking ✏f = 0 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 1 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 a 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 in 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 are also carried out, using random 80 : 20 splits of datasets, as shown in Figure 3. Test accuracy is defined as the proportion of data points in the testing set classified correctly. The results show that ALOE is competitive in terms of test accuracy as well. More performance and test accuracy plots for different datasets, models and loss functions are in Appendix.

heading: 7 Final Remarks
text: We conclude the paper with a brief overview of our theoretical results with respect to those in [VML+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 is used for all consecutive unsuccessful iterations. This guarantees that a successful iteration is eventually achieved for Armijo condition with ✏f = 0, under the assumption
that for every mini-batch, g(x, ⇠0) is Lipschitz continuous. The convergence analysis then assumes that Mc = 0 in (4) (strong growth condition) and in the case when is not convex, the step size parameter is bounded above by 1LMv . Thus, the method itself and its convergence are not better than those of a stochastic gradient descent with a fixed step size bounded by 1LMv [BCN18]. It is also assumed that the step size is reset to a 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.
In this paper we analyzed Algorithm 1 under virtually no restriction on the step size parameter. For the sake of simplicity of analysis, we 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, ⇠0) is Lipschitz continuous, we only impose this condition on . The cost of relaxing all these assumptions is the use of ✏f . For simplicity of the analysis, ✏f is assumed to be fixed throughout the algorithm. In practice, it can be re-estimated regularly. In many applications, ✏f tends to get smaller as the algorithm progresses towards optimality. Our experiments show that estimating ✏f is easy and works well in practice. Moreover, one can use much smaller values for ✏f than theory dictates.

heading: 8 Acknowledgments
text: This work was partially supported by NSF Grants TRIPODS 17-40796, NSF Grant CCF 2008434 and DARPA Lagrange award HR-001117S0039. Miaolan Xie was partially supported by a PhD Fellowship provided by MunchRe. Billy Jin was partially supported by NSERC fellowship PGSD3532673-2019.
The authors are grateful to the anonymous referees for their reviews that helped us improve the paper.

Review summaries:
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. 

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.