Abstract
Zerothorder optimization is the process of minimizing an objective $f(x)$,given oracle access to evaluations at adaptively chosen inputs $x$. In thispaper, we present two simple yet powerful GradientLess Descent (GLD) algorithmsthat do not rely on an underlying gradient estimate and are numerically stable.We analyze our algorithm from a novel geometric perspective and present a novelanalysis that shows convergence within an $\epsilon$ball of the optimum in$O(kQ\log(n)\log(R/\epsilon))$ evaluations, for {\it any monotone transform} ofa smooth and strongly convex objective with latent dimension $k < n$, where theinput dimension is $n$, $R$ is the diameter of the input space and $Q$ is thecondition number. Our rates are the first of its kind to be both 1)polylogarithmically dependent on dimensionality and 2) invariant undermonotone transformations. We further leverage our geometric perspective to showthat our analysis is optimal. Both monotone invariance and its ability toutilize a low latent dimensionality are key to the empirical success of ouralgorithms, as demonstrated on BBOB and MuJoCo benchmarks.
Quick Read (beta)
Gradientless Descent: HighDimensional ZerothOrder Optimization
Abstract
Zerothorder optimization is the process of minimizing an objective $f(x)$, given oracle access to evaluations at adaptively chosen inputs $x$. In this paper, we present two simple yet powerful GradientLess Descent (GLD) algorithms that do not rely on an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and present a novel analysis that shows convergence within an $\u03f5$ball of the optimum in $O(kQ\mathrm{log}(n)\mathrm{log}(R/\u03f5))$ evaluations, for any monotone transform of a smooth and strongly convex objective with latent dimension $$, where the input dimension is $n$, $R$ is the diameter of the input space and $Q$ is the condition number. Our rates are the first of its kind to be both 1) polylogarithmically dependent on dimensionality and 2) invariant under monotone transformations. We further leverage our geometric perspective to show that our analysis is optimal. Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on BBOB and MuJoCo benchmarks.
1 Introduction
We consider the problem of zerothorder optimization (also known as gradientfree optimization, or bandit optimization), where our goal is to minimize an objective function $f:{\mathbb{R}}^{n}\to \mathbb{R}$ with as few evaluations of $f(x)$ as possible. For many practical and interesting objective functions, gradients are difficult to compute and there is still a need for zerothorder optimization in applications such as reinforcement learning [MGR18, SHC+17, CRS+18], attacking neural networks [CZS+17, PMG+17], hyperparameter tuning of deep networks [SLA12], and network control [LCC+17].
The standard approach to zerothorder optimization is, ironically, to estimate the gradients from function values and apply a firstorder optimization algorithm [FKM05]. [NS11] analyze this class of algorithms as gradient descent on a Gaussian smoothing of the objective and gives an accelerated $O(n\sqrt{Q}\mathrm{log}((L{R}^{2}+F)/\u03f5))$ iteration complexity for an $L$Lipschitz convex function with condition number $Q$ and $R=\parallel {x}_{0}{x}^{*}\parallel $ and $F=f({x}_{0})f({x}^{*})$. They propose a twopoint evaluation scheme that constructs gradient estimates from the difference between function values at two points that are close to each other. This scheme was extended by [DJW+15] for stochastic settings, by [GL13] for nonconvex settings, and by [SHA17] for nonsmooth and nonEuclidean norm settings. Since then, firstorder techniques such as variance reduction [LKC+18], conditional gradients [BG18], and diagonal preconditioning [MGR18] have been successfully adopted in this setting. This class of algorithms are also known as stochastic search, random search, or (natural) evolutionary strategies and have been augmented with a variety of heuristics, such as the popular CMAES [AH05].
These algorithms, however, suffer from high variance due to nonrobust local minima or highly nonsmooth objectives, which are common in the fields of deep learning and reinforcement learning. [MGR18] notes that gradient variance increases as training progresses due to higher variance in the objective functions, since often parameters must be tuned precisely to achieve reasonable models. Therefore, some attention has shifted into direct search algorithms that usually finds a descent direction $u$ and moves to $x+\delta u$, where the step size is not scaled by the function difference.
The first approaches for direct search were based on deterministic approaches with a positive spanning set and date back to the 1950s [BRO58]. Only recently have theoretical bounds surfaced, with [GRV+15] giving an iteration complexity that is a large polynomial of $n$ and [DV16] giving an improved $O({n}^{2}{L}^{2}/\u03f5)$. Stochastic approaches tend to have better complexities: [SMG13] uses line search to give a $O(nQ\mathrm{log}(F/\u03f5))$ iteration complexity for convex functions with condition number $Q$ and most recently, [GBS+19] uses importance sampling to give a $O(n\overline{Q}\mathrm{log}(F/\u03f5))$ complexity for convex functions with average condition number $\overline{Q}$, assuming access to sampling probabilities. [SMG13] notes that direct search algorithms are invariant under monotone transforms of the objective, a property that might explain their robustness in highvariance settings.
In general, zeroth order optimization suffers an at least linear dependence on input dimension $n$ and recent works have tried to address this limitation when $n$ is large but $f(x)$ admits a lowdimensional structure. Some papers assume that $f(x)$ depends only on $k$ coordinates and [WDB+17] applies Lasso to find the important set of coordinates, whereas [BG18] simply change the step size to achieve an $O(k{(\mathrm{log}(n)/\u03f5)}^{2})$ iteration complexity. Other papers assume more generally that $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)$ only depends on a $k$dimensional subspace given by the range of ${\mathbf{P}}_{\mathbf{A}}$ and [DKC13] apply lowrank approximation to find the lowdimensional subspace while [WZH+13] use random embeddings. [HKY17] assume that $f(x)$ is a sparse collection of $k$degree monomials on the Boolean hypercube and apply sparse recovery to achieve a $O({n}^{k})$ runtime bound. We will show that under the case that $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)$, our algorithm will inherently pick up any lowdimensional structure in $f(x)$ and achieve a convergence rate that depends on $k\mathrm{log}(n)$. This initial convergence rate survives, even if we perturb $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)+h(x)$, so long as $h(x)$ is sufficiently small.
We will not cover the whole variety of blackbox optimization methods, such as Bayesian optimization or genetic algorithms. In general, these methods attempt to solve a broader problem (e.g. multiple optima), have weaker theoretical guarantees and may require substantial computation at each step: e.g. Bayesian optimization generally has theoretical iteration complexities that grow exponentially in dimension,
and CMAES lacks provable complexity bounds beyond convex quadratic functions. In addition to the slow runtime and weaker guarantees, Bayesian optimization assumes the success of an inner optimization loop of the acquisition function. This inner optimization is often implemented with many iterations of a simpler zerothorder methods, justifying the need to understand gradientless descent algorithms within its own context.
1.1 Our contributions
In this paper, we present GradientLess Descent (GLD), a class of truly gradientfree algorithms (also known as direct search algorithms) that are parameter free and provably fast. Our algorithms are based on a simple intuition: for wellconditioned functions, if we start from a point and take a small step in a randomly chosen direction, there is a significant probability that we will reduce the objective function value. We present a novel analysis that relies on facts in high dimensional geometry and can thus be viewed as a geometric analysis of gradientfree algorithms, recovering the standard convergence rates and step sizes. Specifically, we show that if the step size is on the order of $O(\frac{1}{\sqrt{n}})$, we can guarantee an expected decrease of $1\mathrm{\Omega}(\frac{1}{n})$ in the optimality gap, based on geometric properties of the sublevel sets of a smooth and strongly convex function.
Our results are invariant under monotone transformations of the objective function, thus our convergence results also hold for a large class of nonconvex functions that are a subclass of quasiconvex functions.
Specifically, note that monotone transformations of convex functions are not necessarily
convex. However, a monotone transformation of a convex function is always quasiconvex. The maximization of quasiconcave utility functions, which is equivalent to the minimization of quasiconvex functions, is an important topic of study in economics (e.g. [AE61]).
Intuition suggests that the stepsize dependence on dimensionality can be improved when $f(x)$ admits a lowdimensional structure. With a careful choice of sampling distribution we can show that if $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)$, where ${\mathbf{P}}_{\mathbf{A}}$ is a rank $k$ matrix, then our step size can be on the order of $O(\frac{1}{\sqrt{k}})$ as our optimization behavior is preserved under projections. We call this property affineinvariance and show that the number of function evaluations needed for convergence depends logarithmically on $n$. Unlike most previous algorithms in the highdimensional setting, no expensive sparse recovery or subspace finding methods are needed. Furthermore, by novel perturbation arguments, we show that our fast convergence rates are robust and holds even under the more realistic assumption when $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)+h(x)$ with $h(x)$ being sufficiently small.
Theorem 1 (Convergence of GLD: Informal Restatement of Theorem 7 and Theorem 14).
Let $f\mathit{}\mathrm{(}x\mathrm{)}$ be any monotone transform of a convex function with condition number $Q$ and $R\mathrm{=}\mathrm{\parallel}{x}_{\mathrm{0}}\mathrm{}{x}^{\mathrm{*}}\mathrm{\parallel}$. Let $y$ be a sample from an appropriate distribution centered at $x$. Then, with constant probability,
$$f(y)f({x}^{*})\le (f(x)f({x}^{*}))\left(1\frac{1}{5nQ}\right)$$ 
Therefore, we can find ${x}_{T}$ such that $\mathrm{\parallel}{x}_{T}\mathrm{}{x}^{\mathrm{*}}\mathrm{\parallel}\mathrm{\le}\u03f5$ after $T\mathrm{=}\stackrel{\mathrm{~}}{O}\mathit{}\mathrm{(}n\mathit{}Q\mathit{}\mathrm{log}\mathit{}\mathrm{(}R\mathrm{/}\u03f5\mathrm{)}\mathrm{)}$ function evaluations. Furthermore, for functions $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}\mathrm{+}h\mathit{}\mathrm{(}x\mathrm{)}$ with rank $k$ matrix ${\mathrm{P}}_{\mathrm{A}}$ and sufficiently small $h\mathit{}\mathrm{(}x\mathrm{)}$, we only require $\stackrel{\mathrm{~}}{O}\mathit{}\mathrm{(}k\mathit{}Q\mathit{}\mathrm{log}\mathit{}\mathrm{(}n\mathrm{)}\mathit{}\mathrm{log}\mathit{}\mathrm{(}R\mathrm{/}\u03f5\mathrm{)}\mathrm{)}$ evaluations.
Another advantage of our nonstandard geometric analysis is that it allows us to deduce that our rates are optimal with a matching lower bound (up to logarithmic factors), presenting theoretical evidence that gradientfree inherently requires $\mathrm{\Omega}(nQ)$ function evaluations to converge. While gradientestimation algorithms can achieve a better theoretical iteration complexity of $O(n\sqrt{Q})$, they lack the monotone and affine invariance properties. Empirically, we see that invariance properties are important to successful optimization, as validated by experiments on synthetic BBOB and MuJoCo benchmarks that show the competitiveness of GLD against standard optimization procedures.
Algorithm  Iteration Complexity  Monotone  kSparse  kAffine 

[NS11]  $n\mathrm{log}(({R}^{2}+F)/\u03f5)$  No  No  No 
[BG18]  $n\mathrm{log}(F/\u03f5)$  No  Yes  No 
[SMG13]  $n\mathrm{log}(F/\u03f5)$  Yes  No  No 
[GBS+19]  $n\mathrm{log}(F/\u03f5)$  Yes  No  No 
This paper (GLD)  $n\mathrm{log}(R/\u03f5)$  Yes  Yes  Yes 
2 Preliminaries
We first define a few notations for the rest of the paper. Let $\mathcal{X}$ be a compact subset of ${\mathbb{R}}^{n}$ and let $\parallel \cdot \parallel $ denote the Euclidean norm. The diameter of $\mathcal{X}$, denoted $\parallel \mathcal{X}\parallel ={\mathrm{max}}_{x,{x}^{\prime}\in \mathcal{X}}\parallel x{x}^{\prime}\parallel $, is the maximum distance between elements in $\mathcal{X}$. Let $f:\mathcal{X}\to \mathbb{R}$ be a realvalued function which attains its minimum at ${x}^{*}$. We use $f(\mathcal{X})=\{f(x):x\in \mathcal{X}\}$ to denote the image of $f$ on a subset $\mathcal{X}$ of ${\mathbb{R}}^{n}$, and $\mathcal{B}(c,r)=\{x\in {\mathbb{R}}^{n}:\parallel cx\parallel \le r\}$ to denote the ball of radius $r$ centered at $c$.
Definition 2.
The level set of $f$ at point $x\mathrm{\in}\mathrm{X}$ is ${\mathrm{L}}_{c}\mathit{}\mathrm{(}f\mathrm{)}\mathrm{=}\mathrm{\{}y\mathrm{\in}\mathrm{X}\mathrm{:}f\mathit{}\mathrm{(}y\mathrm{)}\mathrm{=}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{\}}$. The sublevel set of $f$ at point $x\mathrm{\in}\mathrm{X}$ is ${\mathrm{L}}_{c}^{\mathrm{\downarrow}}\mathit{}\mathrm{(}f\mathrm{)}\mathrm{=}\mathrm{\{}y\mathrm{\in}\mathrm{X}\mathrm{:}f\mathit{}\mathrm{(}y\mathrm{)}\mathrm{\le}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{\}}$. When the function $f$ is clear from the context, we omit it.
Definition 3.
We say that $f$ is $\alpha $strongly convex for $\alpha \mathrm{>}\mathrm{0}$ if $f\mathit{}\mathrm{(}y\mathrm{)}\mathrm{\ge}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{+}\mathrm{\u27e8}\mathrm{\nabla}\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}y\mathrm{}x\mathrm{\u27e9}\mathrm{+}\frac{\alpha}{\mathrm{2}}\mathit{}{\mathrm{\parallel}y\mathrm{}x\mathrm{\parallel}}^{\mathrm{2}}$ for all $x\mathrm{,}y\mathrm{\in}\mathrm{X}$ and $\beta $smooth for $\beta \mathrm{>}\mathrm{0}$ if $f\mathit{}\mathrm{(}y\mathrm{)}\mathrm{\le}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{+}\mathrm{\u27e8}\mathrm{\nabla}\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}y\mathrm{}x\mathrm{\u27e9}\mathrm{+}\frac{\beta}{\mathrm{2}}\mathit{}{\mathrm{\parallel}y\mathrm{}x\mathrm{\parallel}}^{\mathrm{2}}$ for all $x\mathrm{,}y\mathrm{\in}\mathrm{X}$.
Definition 4.
We say that $g\mathrm{\circ}f$ is a monotone transformation of $f$ if $g\mathrm{:}f\mathit{}\mathrm{(}\mathrm{X}\mathrm{)}\mathrm{\to}\mathrm{R}$ is a monotonically (and strictly) increasing function.
Monotone transformations preserve the level sets of a function in the sense that ${\mathcal{L}}_{x}(f)={\mathcal{L}}_{x}(g\circ f)$. Because our algorithms depend only on the level set properties, our results generalize to any monotone transformation of a strongly convex and strongly smooth function. This leads to our extended notion of condition number.
Definition 5.
A function $f$ has condition number $Q\mathrm{\ge}\mathrm{1}$ if it is the minimum ratio $\beta \mathrm{/}\alpha $ over all functions $g$ such that $f$ is a monotone transformation of $g$ and $g$ is $\alpha $strongly convex and $\beta $ smooth.
When we work with low rank extensions of $f$, we only care about the condition number of $f$ within a rank $k$ subspace. Indeed, if $f$ only varies along a rank $k$ subspace, then it has a strong convexity value of $0$, making its condition number undefined. If $f$ is $\alpha $strongly convex and $\beta $smooth, then its Hessian matrix always has eigenvalues bounded between $\alpha $ and $\beta $. Therefore, we need a notion of a projected condition number. Let $\mathbf{A}\in {\mathbb{R}}^{d\times k}$ be some orthonormal matrix and let ${\mathbf{P}}_{\mathbf{A}}={\mathrm{\mathbf{A}\mathbf{A}}}^{\top}$ be the projection matrix onto the column space of $\mathbf{A}$.
Definition 6.
For some orthonormal $\mathrm{A}\mathrm{\in}{\mathrm{R}}^{d\mathrm{\times}k}$ with $d\mathrm{>}k$, a function $f$ has condition number restricted to $\mathrm{A}$, $Q\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}\mathrm{\ge}\mathrm{1}$, if it is the minimum ratio $\beta \mathrm{/}\alpha $ over all functions $g$ such that $f$ is a monotone transformation of $g$ and $h\mathit{}\mathrm{(}y\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}\mathrm{A}\mathit{}y\mathrm{)}$ is $\alpha $strongly convex and $\beta $ smooth.
3 Analysis of Descent Steps
The GLD template can be summarized as follows: given a sampling distribution $\mathcal{D}$, we start at ${x}_{0}$ and in iteration $t$, we choose a scalar radii ${r}_{t}$ and we sample ${y}_{t}$ from a distribution ${r}_{t}\mathcal{D}$ centered around ${x}_{t}$, where ${r}_{t}$ provides the scaling of $\mathcal{D}$. Then, if $$, we update ${x}_{t+1}={y}_{t}$; otherwise, we set ${x}_{t+1}={x}_{t}$. The analysis of GLD follows from the main observation that the sublevel set of a monotone transformation of a strongly convex and strongly smooth function contains a ball of sufficiently large radius tangent to the level set (Lemma 15). In this section, we show that this property, combined with facts of highdimensional geometry, implies that moving in a random direction from any point has a good chance of significantly improving the objective.
As we mentioned before, the key to fast convergence is the careful choice of step sizes, which we describe in Theorem 7. The intuition here is that we would like to take as large steps as possible while keeping the probability
of improving the objective function reasonably high, so by insights in highdimensional geometry, we choose a step size of $\mathrm{\Theta}(1/\sqrt{n})$. Also, we show that if $f(x)$ admits a latent rank$k$ structure, then this step size can be increased to $\mathrm{\Theta}(1/\sqrt{k})$ and is therefore only dependent on the latent dimensionality of $f(x)$, allowing for fast highdimensional optimization. Lastly, our geometric understanding allows us to show that our convergence rates are optimal with a matching lower bound. Without loss of generality, this section assumes that $f(x)$ is strongly convex and smooth with condition number $Q$.
3.1 Step Size
Theorem 7.
For any $x$ such that $\frac{\mathrm{3}}{\mathrm{5}\mathit{}Q}\mathit{}\mathrm{\parallel}x\mathrm{}{x}^{\mathrm{*}}\mathrm{\parallel}\mathrm{\in}\mathrm{[}{C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{]}$, we can find integers $$ such that if $r\mathrm{=}{\mathrm{2}}^{{k}_{\mathrm{1}}}\mathit{}{C}_{\mathrm{1}}$ or $r\mathrm{=}{\mathrm{2}}^{\mathrm{}{k}_{\mathrm{2}}}\mathit{}{C}_{\mathrm{2}}$, then a random sample $y$ from uniform distribution over ${B}_{x}\mathrm{=}\mathrm{B}\mathit{}\mathrm{(}x\mathrm{,}\frac{r}{\sqrt{n}}\mathrm{)}$ satisfies
$$f(y)f({x}^{*})\le \left(f(x)f({x}^{*})\right)\left(1\frac{1}{5nQ}\right)$$ 
with probability at least $\frac{\mathrm{1}}{\mathrm{4}}$.
Proving the above theorem requires the following lemma about the intersection of balls in high dimensions and it is proved in the appendix.
Lemma 8.
Let ${B}_{\mathrm{1}}$ and ${B}_{\mathrm{2}}$ be two balls in ${\mathrm{R}}^{n}$ of radii ${r}_{\mathrm{1}}$ and ${r}_{\mathrm{2}}$ respectively. Let $\mathrm{\ell}$ be the distance between the centers. If ${r}_{\mathrm{1}}\mathrm{\in}\mathrm{[}\frac{\mathrm{\ell}}{\mathrm{2}\mathit{}\sqrt{n}}\mathrm{,}\frac{\mathrm{\ell}}{\sqrt{n}}\mathrm{]}$ and ${r}_{\mathrm{2}}\mathrm{\ge}\mathrm{\ell}\mathrm{}\frac{\mathrm{\ell}}{\mathrm{4}\mathit{}n}$, then
$$\mathrm{vol}\left({B}_{1}\cap {B}_{2}\right)\ge {c}_{n}\mathrm{vol}\left({B}_{1}\right),$$ 
where ${c}_{n}$ is a dimensiondependent constant that is lower bounded by $\frac{\mathrm{1}}{\mathrm{4}}$ at $n\mathrm{=}\mathrm{1}$.
3.2 Gaussian Sampling and Low Rank Structure
A direct application of Lemma 8 seems to imply that uniform sampling of a highdimensional ball is necessary. Upon further inspection, this can be easily replaced with a much simpler Gaussian sampling procedure that concentrates the mass close to the surface to the ball. This procedure lends itself to better analysis when $f(x)$ admits a latent lowdimensional structure since any affine projection of a Gaussian is still Gaussian.
Lemma 9.
Let ${B}_{\mathrm{1}}$ and ${B}_{\mathrm{2}}$ be two balls in ${\mathrm{R}}^{n}$ of radii ${r}_{\mathrm{1}}$ and ${r}_{\mathrm{2}}$ respectively. Let $\mathrm{\ell}$ be the distance between the centers. If ${r}_{\mathrm{1}}\mathrm{\in}\mathrm{[}\frac{\mathrm{\ell}}{\mathrm{2}\mathit{}\sqrt{n}}\mathrm{,}\frac{\mathrm{\ell}}{\sqrt{n}}\mathrm{]}$ and ${r}_{\mathrm{2}}\mathrm{\ge}\mathrm{\ell}\mathrm{}\frac{\mathrm{\ell}}{n}$ and $X\mathrm{=}\mathrm{(}{X}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{X}_{n}\mathrm{)}$ are independent Gaussians with mean centered at the center of ${B}_{\mathrm{1}}$ and variance $\frac{{r}_{\mathrm{1}}^{\mathrm{2}}}{n}$, then
$$\mathrm{\mathbf{P}\mathbf{r}}[X\in {B}_{2}]>c,$$ 
where $c$ is a dimensionindependent constant.
Assume that there exists some rank $k$ projection matrix ${\mathbf{P}}_{\mathbf{A}}$ such that $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)$, where $k$ is much smaller than $n$. Because Gaussians projected on a $k$dimensional subspace are still Gaussians, we show that our algorithm has a dimension dependence on $k$. We let ${Q}_{g}(\mathbf{A})$ be the condition number of $g$ restricted to the subspace $\mathbf{A}$ that drives the dominant changes in $f(x)$.
Theorem 10.
Let $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}$ for some unknown rank $k$ matrix ${\mathrm{P}}_{\mathrm{A}}$ with $$ and suppose $\frac{\mathrm{3}}{\mathrm{5}\mathit{}Q}\mathit{}\mathrm{\parallel}{\mathrm{P}}_{\mathrm{A}}\mathit{}\mathrm{(}x\mathrm{}{x}^{\mathrm{*}}\mathrm{)}\mathrm{\parallel}\mathrm{\in}\mathrm{[}{C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{]}$ for some numbers ${C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{\in}{\mathrm{R}}^{\mathrm{+}}$. Then, there exist integers $$ such that if $r\mathrm{=}{\mathrm{2}}^{{k}_{\mathrm{1}}}\mathit{}{C}_{\mathrm{1}}$ or $r\mathrm{=}{\mathrm{2}}^{\mathrm{}{k}_{\mathrm{2}}}\mathit{}{C}_{\mathrm{2}}$, then a random sample $y$ from a Gaussian distribution $\mathrm{N}\mathit{}\mathrm{(}x\mathrm{,}\frac{{r}^{\mathrm{2}}}{k}\mathit{}\mathrm{I}\mathrm{)}$ satisfies
$$f(y)f({x}^{*})\le \left(f(x)f({x}^{*})\right)\left(1\frac{1}{5k{Q}_{g}(\mathbf{A})}\right)$$ 
with constant probability.
Note that the speedup in progress is due to the fact that we can now tolerate the larger sampling radius of $\mathrm{\Omega}(1/\sqrt{k})$, while maintaining a high probability of making progress. If $k$ is unknown, we can simply use binary search to find the correct radius with an extra factor of $\mathrm{log}(n)$ in our runtime.
The lowrank assumption is too restrictive to be realistic; however, our fast rates still hold, at least for the early stages of the optimization, even if we assume that $f(x)=g({\mathbf{P}}_{\mathbf{A}}x)+h(x)$ and $h(x)\le \delta $ is a fullrank function that is bounded by $\delta $. In this setting, we can show that convergence remains fast, at least until the optimality gap approaches $\delta $.
Theorem 11.
Let $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}\mathrm{+}h\mathit{}\mathrm{(}x\mathrm{)}$ for some unknown rank $k$ matrix ${\mathrm{P}}_{\mathrm{A}}$ with $$ where $g\mathrm{,}h$ are convex and $\mathrm{}h\mathrm{}\mathrm{\le}\delta $. Suppose $\frac{\mathrm{3}}{\mathrm{5}\mathit{}Q}\mathit{}\mathrm{\parallel}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{}{z}^{\mathrm{*}}\mathrm{\parallel}\mathrm{\in}\mathrm{[}{C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{]}$ for some numbers ${C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{\in}{\mathrm{R}}^{\mathrm{+}}$ where ${z}^{\mathrm{*}}$ minimizes $g\mathit{}\mathrm{(}z\mathrm{)}$. Then, there exist integers $$ such that if $r\mathrm{=}{\mathrm{2}}^{{k}_{\mathrm{1}}}\mathit{}{C}_{\mathrm{1}}$ or $r\mathrm{=}{\mathrm{2}}^{\mathrm{}{k}_{\mathrm{2}}}\mathit{}{C}_{\mathrm{2}}$, then a random sample $y$ from a Gaussian distribution $\mathrm{N}\mathit{}\mathrm{(}x\mathrm{,}\frac{{r}^{\mathrm{2}}}{k}\mathit{}\mathrm{I}\mathrm{)}$ satisfies
$$f(y)f({x}^{*})\le \left(f(x)f({x}^{*})\right)\left(1\frac{1}{10k{Q}_{g}(\mathbf{A})}\right)$$ 
with constant probability whenever $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{}f\mathit{}\mathrm{(}{x}^{\mathrm{*}}\mathrm{)}\mathrm{\ge}\mathrm{60}\mathit{}\delta \mathit{}k\mathit{}{Q}_{g}\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}$.
3.3 Lower Bounds
We show that our upper bounds given in the previous section are tight up to logarithmic factors for any symmetric sampling distribution $\mathcal{D}$. These lower bounds are easily derived from our geometric perspective as we show that a sampling distribution with a large radius gives an extremely low probability of intersection with the desired sublevel set. Therefore, while gradientapproximation algorithms can be accelerated to achieve a runtime that depends on the squareroot of the condition number $Q$, gradientless methods that rely on random sampling are likely unable to be accelerated according to our lower bound. However, we emphasize that monotone invariance allows these results to apply to a broader class of objective functions, beyond smooth and convex, so the results can be useful in practice despite the seemingly worse theoretical bounds.
Theorem 12.
Let $y\mathrm{=}x\mathrm{+}v$, where $v$ is a random sample from $r\mathit{}\mathrm{D}$ for some radius $r\mathrm{>}\mathrm{0}$ and $\mathrm{D}$ is standard Gaussian or any rotationally symmetric distribution. Then, there exist a region $X$ with positive measure such that for any $x\mathrm{\in}X$,
$$f(y)f({x}^{*})\ge \left(f(x)f({x}^{*})\right)\left(1\frac{\sqrt{5\mathrm{log}(nQ)}}{nQ}\right)$$ 
with probability at least $\mathrm{1}\mathrm{}\frac{\mathrm{1}}{\text{\mathit{p}\mathit{o}\mathit{l}\mathit{y}}\mathit{}\mathrm{(}n\mathit{}Q\mathrm{)}}$.
4 Gradientless Algorithms
In this section, we present two algorithms that follow the same Gradientless Descent (GLD) template: GLDSearch and GLDFast, with the latter being an optimized version of the former when an upper bound on the condition number of a function is known. For both algorithms, since they are monotoneinvariant, we appeal to the previous section to derive fast convergence rates for any monotone transform of convex $f(x)$ with good condition number. We show the efficacy of both algorithms experimentally in the Experiments section.
4.1 Gradientless Descent with Binary Search
Although the sampling distribution $\mathcal{D}$ is fixed, we have a choice of radii for each iteration of the algorithm. We can apply a binary search procedure to ensure progress. The most straightforward version of our algorithm is thus with a naive binary sweep across an interval in $[r,R]$ that is unchanged throughout the algorithm. This allows us to give convergence guarantees without previous knowledge of the condition number at a cost of an extra factor of $\mathrm{log}(n/\u03f5)$.
Theorem 13.
Let ${x}_{\mathrm{0}}$ be any starting point and $f$ a blackbox function with condition number $Q$. Running Algorithm 1 with $r\mathrm{=}\frac{\u03f5}{\sqrt{n}}\mathrm{,}R\mathrm{=}\mathrm{\parallel}\mathrm{X}\mathrm{\parallel}$ and $\mathrm{D}\mathrm{=}\mathrm{N}\mathit{}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{I}\mathrm{)}$ as a standard Gaussian returns a point ${x}_{T}$ such that $\mathrm{\parallel}{x}_{T}\mathrm{}{x}^{\mathrm{*}}\mathrm{\parallel}\mathrm{\le}\mathrm{2}\mathit{}{Q}^{\mathrm{3}\mathrm{/}\mathrm{2}}\mathit{}\u03f5$ after $O\mathrm{(}nQ\mathrm{log}{\mathrm{(}n\mathrm{\parallel}\mathrm{X}\mathrm{\parallel}\mathrm{/}\u03f5\mathrm{)}}^{\mathrm{2}}\mathrm{)}$ function evaluations with high probability.
Furthermore, if $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}$ admits a lowrank structure with ${\mathrm{P}}_{\mathrm{A}}$ a rank $k$ matrix, then we only require $O\mathrm{(}k{Q}_{g}\mathrm{(}\mathrm{A}\mathrm{)}\mathrm{log}{\mathrm{(}n\mathrm{\parallel}\mathrm{X}\mathrm{\parallel}\mathrm{/}\u03f5\mathrm{)}}^{\mathrm{2}}\mathrm{)}$ function evaluations to guarantee $\mathrm{\parallel}{\mathrm{P}}_{\mathrm{A}}\mathit{}\mathrm{(}{x}_{T}\mathrm{}{x}^{\mathrm{*}}\mathrm{)}\mathrm{\parallel}\mathrm{\le}\u03f5$. This holds analogously even if $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}\mathrm{+}h\mathit{}\mathrm{(}x\mathrm{)}$ is almost lowrank where $\mathrm{}h\mathrm{}\mathrm{\le}\delta $ and $\u03f5\mathrm{>}\mathrm{60}\mathit{}\delta \mathit{}k\mathit{}{Q}_{g}\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}$.
4.2 Gradientless Descent with Fast Binary Search
GLDSearch (Algorithm 1) uses a naive lower and upper bound for the search radius $\parallel {x}_{t}{x}^{*}\parallel $, which incurs an extra factor of $\mathrm{log}(1/\u03f5)$ in the runtime bound. In GLDFast, we remove this extra factor dependence on $\mathrm{log}(1/\u03f5)$ by drastically reducing the range of the binary search. This is done by exploiting the assumption that $f$ has a good condition number upper bound $\widehat{Q}$ and by slowly halfing the diameter of the search space every few iterations since we expect ${x}_{t}\to {x}^{*}$ as $t\to \mathrm{\infty}$.
Theorem 14.
Let ${x}_{\mathrm{0}}$ be any starting point and $f$ a blackbox function with condition number upper bounded by $Q$. Running Algorithm 2 with suitable parameters returns a point ${x}_{T}$ such that $f\mathit{}\mathrm{(}{x}_{T}\mathrm{)}\mathrm{}f\mathit{}\mathrm{(}{x}^{\mathrm{*}}\mathrm{)}\mathrm{\le}\u03f5$ after $O\mathit{}\mathrm{(}n\mathit{}Q\mathit{}{\mathrm{log}}^{\mathrm{2}}\mathit{}\mathrm{(}Q\mathrm{)}\mathit{}\mathrm{log}\mathit{}\mathrm{(}\mathrm{\parallel}\mathrm{X}\mathrm{\parallel}\mathrm{/}\u03f5\mathrm{)}\mathrm{)}$ function evaluations with high probability.
Furthermore, if $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}$ admits a lowrank structure with ${\mathrm{P}}_{\mathrm{A}}$ a rank $k$ matrix, then we only require $O\mathit{}\mathrm{(}k\mathit{}{Q}_{g}\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}\mathit{}\mathrm{log}\mathit{}\mathrm{(}n\mathrm{)}\mathit{}{\mathrm{log}}^{\mathrm{2}}\mathit{}\mathrm{(}{Q}_{g}\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}\mathrm{)}\mathit{}\mathrm{log}\mathit{}\mathrm{(}\mathrm{\parallel}\mathrm{X}\mathrm{\parallel}\mathrm{/}\u03f5\mathrm{)}\mathrm{)}$ function evaluations to guarantee $\mathrm{\parallel}{\mathrm{P}}_{\mathrm{A}}\mathit{}\mathrm{(}{x}_{T}\mathrm{}{x}^{\mathrm{*}}\mathrm{)}\mathrm{\parallel}\mathrm{\le}\u03f5$. This holds analogously even if $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}g\mathit{}\mathrm{(}{\mathrm{P}}_{\mathrm{A}}\mathit{}x\mathrm{)}\mathrm{+}h\mathit{}\mathrm{(}x\mathrm{)}$ is almost lowrank where $\mathrm{}h\mathrm{}\mathrm{\le}\delta $ and $\u03f5\mathrm{>}\mathrm{60}\mathit{}\delta \mathit{}k\mathit{}{Q}_{g}\mathit{}\mathrm{(}\mathrm{A}\mathrm{)}$.
5 Experiments
We tested GLD algorithms on a simple class of objective functions and compare it to Accelerated Random Search (ARS) by [NS11], which has linear convergence guarantees on strongly convex and strongly smooth functions. To our knowledge, ARS makes the weakest assumption among the zerothorder algorithms that have linear convergence guarantees and perform only a constant order of operations per iteration. Our main conclusion is that GLDFast is comparable to ARS and tends to achieve a reasonably low error much faster than ARS in high dimensions ($\ge 50$). In low dimensions, GLDSearch is competitive with GLDFast and ARS though it requires no information about the function.
We let ${H}_{\alpha ,\beta ,n}\in {\mathbb{R}}^{n\times n}$ be a diagonal matrix with its $i$th diagonal equal to $\alpha +(\beta \alpha )\frac{i1}{n1}$. In simple words, its diagonal elements form an evenly space sequence of numbers from $\alpha $ to $\beta $. Our objective function is then ${f}_{\alpha ,\beta ,n}:{\mathbb{R}}^{n}\to \mathbb{R}$ as ${f}_{\alpha ,\beta ,n}(x)=\frac{1}{2}{x}^{\top}{H}_{\alpha ,\beta ,n}x$, which is $\alpha $strongly convex and $\beta $strongly smooth. We always use the same starting point $x=\frac{1}{\sqrt{n}}(1,\mathrm{\dots},1)$, which requires $\parallel X\parallel =\sqrt{Q}$ for our algorithms. We plot the optimality gap $f({b}_{t})f({x}^{*})$ against the number of function evaluations, where ${b}_{t}$ is the best point observed so far after $t$ evaluations. Although all tested algorithms are stochastic, they have a low variance on the objective functions that we use; hence we average the results over 10 runs and omit the error bars in the plots.
We ran experiments on ${f}_{1,8,n}$ with imperfect curvature information $\widehat{\alpha}$ and $\widehat{\beta}$ (see Figure 3 in appendix). GLDSearch is independent of the condition number. GLDFast takes only one parameter, which is the upper bound on the condition number; if approximation factor is $z$, then we pass $8z$ as the upper bound.
ARS requires both strong convexity and smoothness parameters. We test three different distributions of the approximation error; when the approximation factor is $z$, then ARSalpha gets $(\alpha /z,\beta )$, ARSbeta gets ($\alpha ,z\beta $), and ARSeven gets $(\alpha /\sqrt{z},\sqrt{z}\beta )$ as input. GLDFast is more robust and faster than ARS when the condition number is overapproximated. When the condition number is underestimated, GLDFast still steadily converges.
5.1 Monotone Transformations
In Figure 1, we ran experiments on ${f}_{1,8,n}$ for different settings of dimensionality $n$, and its monotone transformation with $g(y)=\mathrm{exp}(\sqrt{y})$. For this experiment, we assume a perfect oracle for the strong convexity and smoothness parameters of $f$. The convergence of GLD is totally unaffected by the monotone transformation. For the lowdimension cases of a transformed function (bottom half of the figure), we note that there are inflection points in the convergence curve of ARS. This means that ARS initially struggles to gain momentum and then struggles to stop the momentum when it gets close to the optimum. Another observation is that unlike ARS that needs to build up momentum, GLDFast starts from a large radius and therefore achieves a reasonably low error much faster than ARS, especially in higher dimensions.
5.2 BBOB Benchmarks
To show that practicality of GLD on practical and nonconvex settings, we also test GLD algorithms on a variety of BlackBox Optimization Benchmarking (BBOB) functions [HFR+09]. For each function, the optima is known and we use the log optimality gap as a measure of competance. Because each function can exhibit varying forms of nonsmoothness and convexity, all algorithms are ran with a smoothness constant of 10 and a strong convexity constant of 0.1. All other setup details are same as before, such as using a fixed starting point.
The plots, given in Appendix C, underscore the superior performance of GLD algorithms on various BBOB functions, demonstrating that GLD can successfully optimize a diverse set of functions even without explicit knowledge of condition number. We note that BBOB functions are far from convex and smooth, many exhibiting high conditioning, multimodal valleys, and weak global structure. Due to our radius search produce, our algorithm appears more robust to nonideal settings with nonconvexity and ill conditioning. As expected, we note that GLDFast tend to outperform GLDSearch, especially as the dimension increases, matching our theoretical understanding of GLD.
5.3 Mujoco Control Benchmarks and Affine Transformations
We also ran experiments on the Mujoco benchmarks with varying architectures, both linear and nonlinear. This demonstrates the viability of our approach even in the nonconvex, high dimensional setting. We note that however, unlike e.g. ES which uses all queries to form a gradient direction, our algorithm removes queries which produce less reward than using the current argmax, which can be an information handicap. Nevertheless, we see that our algorithm still achieves competitive performance on the maximum reward. We used a horizon of $1000$ for all experiments.
Env.  Arch  Rew. at (${10}^{4}$, ${10}^{5}$, Max) Queries  Rew. Thresh. 
HalfCheetahv1  L  3799, 3903, 4064  3430 
HalfCheetahv1, Proj200  L  1594 , 3509 , 4342  3430 
HalfCheetahv1  H41  2741, 3074, 3392  3430 
Hopperv1  L  1017, 3359, 3375  3120 
Hopperv1  H41  2708, 3370, 3566  3120 
Reacherv1  L  70, 5, 4  10 
Reacherv1  H41  231, 17, 15  10 
Swimmerv1  L  365, 369 , 369  325 
Swimmerv1  H41  353, 369, 369  325 
Walker2dv1  L  1027 , 2201, 2201  4390 
Walker2dv1  H41  1630, 1963, 2146  4390 

We further tested the affine invariance of GLD on the policy parameters from using Gaussian ball sampling, under the HalfCheetah benchmark by projecting the state $s$ of the MDP with linear policy to a higher dimensional state $Ws$, using a matrix multiplication with an orthonormal $W$. Specifically, in this setting, for a linear policy parametrized by matrix $K$, the objective function is thus $J(KW)$ where ${\pi}_{K}(Ws)=KWs$. Note that when projecting into a high dimension, there is a slowdown factor of $\mathrm{log}\frac{{d}_{new}}{{d}_{old}}$ where ${d}_{new},{d}_{old}$ are the new high dimension and previous base dimension, respectively, due to the binary search in our algorithm on a higher dimensional space. For our HalfCheetah case, we projected the 17 base dimension to a 200length dimension, which suggests that the slowdown factor is a factor $\mathrm{log}\frac{200}{17}\approx 3.5$. This can be shown in our plots in the appendix (Figure 15).
6 Conclusion
We introduced GLD, a robust zerothorder optimization algorithm that is simple, efficient, and we show strong theoretical convergence bounds via our novel geometric analysis. As demonstrated by our experiments on BBOB and MuJoCo benchmarks, GLD performs very robustly even in the nonconvex setting and its monotone and affine invariance properties give theoretical insight on its practical efficiency.
GLD is very flexible and allows easy modifications. For example, it could use momentum terms to keep moving in the same direction that improved the objective, or sample from adaptively chosen ellipsoids similarly to adaptive gradient methods. [DHS11, MS10]. Just as one may decay or adaptively vary learning rates for gradient descent, one might use a similar change the distribution from which the ballsampling radii are chosen, perhaps shrinking the minimum radius as the algorithm progresses, or concentrating more probability mass on smaller radii.
Likewise, GLD could be combined with random restarts or other restart
policies developed for gradient descent. Analogously to adaptive
per–coordinate learning rates [DHS11, MS10], one could
adaptively change the shape of the balls being sampled into ellipsoids with
various lengthscale factors. Arbitrary combinations of the above variants are also possible.
References
 [AE61] (1961) Quasiconcave programming. Econometrica: Journal of the Econometric Society, pp. 779–800. Cited by: §1.1.
 [AH05] (2005) A restart cma evolution strategy with increasing population size. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, Vol. 2, pp. 1769–1776. Cited by: §1.
 [BG18] (2018) Zerothorder (non)convex stochastic optimization via conditional gradient and gradient updates. In Advances in Neural Information Processing Systems, pp. 3455–3464. Cited by: Table 1, §1.
 [BRO58] (1958) A discussion of random methods for seeking maxima. Operations research 6 (2), pp. 244–251. Cited by: §1.
 [CZS+17] (2017) Zoo: zeroth order optimization based blackbox attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15–26. Cited by: §1.
 [CRS+18] (2018) Structured evolution with compact architectures for scalable policy optimization. arXiv preprint arXiv:1804.02395. Cited by: §1.
 [DKC13] (2013) Highdimensional gaussian process bandits. In Advances in Neural Information Processing Systems, pp. 1025–1033. Cited by: §1.
 [DV16] (2016) Worst case complexity of direct search under convexity. Mathematical Programming 155 (12), pp. 307–332. Cited by: §1.
 [DJW+15] (2015) Optimal rates for zeroorder convex optimization: the power of two function evaluations. IEEE Transactions on Information Theory 61 (5), pp. 2788–2806. Cited by: §1.
 [DHS11] (2011) Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research 12 (Jul), pp. 2121–2159. Cited by: §6.
 [FKM05] (2005) Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the sixteenth annual ACMSIAM symposium on Discrete algorithms, pp. 385–394. Cited by: §1.
 [GL13] (2013) Stochastic firstand zerothorder methods for nonconvex stochastic programming. SIAM Journal on Optimization 23 (4), pp. 2341–2368. Cited by: §1.
 [GBS+19] (2019) A stochastic derivative free optimization method with momentum. arXiv preprint arXiv:1905.13278. Cited by: Table 1, §1.
 [GRV+15] (2015) Direct search based on probabilistic descent. SIAM Journal on Optimization 25 (3), pp. 1515–1541. Cited by: §1.
 [HFR+09] (2009) RealParameter BlackBox Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report Technical Report RR6829, INRIA. Cited by: §5.2.
 [HKY17] (2017) Hyperparameter optimization: a spectral approach. arXiv preprint arXiv:1706.00764. Cited by: §1.
 [LI11] (2011) Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics 4 (1), pp. 66–70. Cited by: Appendix A.
 [LCC+17] (2017) Zerothorder online alternating direction method of multipliers: convergence analysis and applications. arXiv preprint arXiv:1710.07804. Cited by: §1.
 [LKC+18] (2018) Zerothorder stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3727–3737. Cited by: §1.
 [MGR18] (2018) Simple random search provides a competitive approach to reinforcement learning. arXiv preprint arXiv:1803.07055. Cited by: §1, Table 2.
 [MS10] (2010) Adaptive bound optimization for online convex optimization. In COLT 2010  The 23rd Conference on Learning Theory, Haifa, Israel, June 2729, 2010, pp. 244–256. Cited by: §6.
 [NS11] (2011) Random gradientfree minimization of convex functions. Technical report Université catholique de Louvain, Center for Operations Research and Econometrics (CORE). Cited by: Table 1, §1, §5.
 [PMG+17] (2017) Practical blackbox attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506–519. Cited by: §1.
 [SHC+17] (2017) Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864. Cited by: §1.
 [SWD+17] (2017) Proximal policy optimization algorithms. CoRR abs/1707.06347. External Links: Link, 1707.06347 Cited by: Table 2.
 [SHA17] (2017) An optimal algorithm for bandit and zeroorder convex optimization with twopoint feedback. Journal of Machine Learning Research 18 (52), pp. 1–11. Cited by: §1.
 [SLA12] (2012) Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951–2959. Cited by: §1.
 [SMG13] (2013) Optimization of convex functions with random pursuit. SIAM Journal on Optimization 23 (2), pp. 1284–1309. Cited by: Table 1, §1.
 [WDB+17] (2017) Stochastic zerothorder optimization in high dimensions. arXiv preprint arXiv:1710.10551. Cited by: §1.
 [WZH+13] (2013) Bayesian optimization in high dimensions via random embeddings. In TwentyThird International Joint Conference on Artificial Intelligence, Cited by: §1.
Appendix A Proofs of Section 3
Lemma 15.
If $h$ has condition number $Q$, then for all $x\mathrm{\in}\mathrm{X}$, there is a ball of radius ${Q}^{\mathrm{}\mathrm{1}}\mathit{}\mathrm{\parallel}x\mathrm{}{x}^{\mathrm{*}}\mathrm{\parallel}$ that is tangent at $x$ and inside the sublevel set ${\mathrm{L}}_{x}^{\mathrm{\downarrow}}\mathit{}\mathrm{(}h\mathrm{)}$.
Proof.
Write $h=g\circ f$ such that $f$ is $\alpha $strongly convex and $\beta $smooth for some $\beta =Q\alpha $ and $g$ is monotonically increasing. From the smoothness assumption, we have for any $s$,
$f\left(x\frac{1}{\beta}\nabla f(x)+s\right)$  
$\le f(x)+\u27e8\nabla f(x),s\frac{1}{\beta}\nabla f(x)\u27e9+\frac{\beta}{2}{\parallel s\frac{1}{\beta}\nabla f(x)\parallel}^{2}$  
$=f(x)+\frac{\beta}{2}\left({\parallel s\parallel}^{2}\frac{1}{{\beta}^{2}}{\parallel \nabla f(x)\parallel}^{2}\right).$ 
Consider the ball $B=\mathcal{B}(x\frac{1}{\beta}\nabla f(x),\frac{1}{\beta}\parallel \nabla f(x)\parallel )$. For any $y\in B$, the above inequality implies $f(y)\le f(x)$. Hence, when we apply $g$ on both sides, we still have $h(y)\le h(x)$ for all $y\in B$. Therefore, $B\subseteq {\mathcal{L}}_{h(y)}^{\downarrow}$.
By strong convexity, $\parallel \nabla f(x)\parallel \ge \alpha \parallel x{x}^{*}\parallel $. It follows that the radius of $B$ is at least $\frac{\alpha}{\beta}\parallel x{x}^{*}\parallel $. ∎
Proof of Lemma 8.
Without loss of generality, consider the unit distance case where $\mathrm{\ell}=1$. Furthermore, it suffices to prove for the smallest possible radius ${r}_{2}=1\frac{1}{4n}$.
Since ${r}_{1}{r}_{2}\le \mathrm{\ell}\le {r}_{1}+{r}_{2}$, the intersection ${B}_{1}\cap {B}_{2}$ is composed of two hyperspherical caps glued end to end. We lower bound $\mathrm{vol}\left({B}_{1}\cap {B}_{2}\right)$ by the volume of the cap ${C}_{1}$ of ${B}_{1}$ that is contained in the intersection. Consider the triangle with sides ${r}_{1},{r}_{2}$ and $\mathrm{\ell}$. From classic geometry, the height of ${C}_{1}$ is
$${c}_{1}=\frac{1}{2}\left(1+{r}_{1}^{2}{r}_{2}^{2}\right)>0.$$  (1) 
The volume of a spherical cap is [LI11],
$$\mathrm{vol}\left({C}_{1}\right)=\frac{1}{2}\mathrm{vol}\left({B}_{1}\right){I}_{1\frac{{c}_{1}^{2}}{{r}_{1}^{2}}}(\frac{n+1}{2},\frac{1}{2}).$$ 
where $I$ is the regularized incomplete beta function defined as
$${I}_{x}(a,b)=\frac{{\int}_{0}^{x}{t}^{a1}{(1t)}^{b1}\mathit{d}t}{{\int}_{0}^{1}{t}^{a1}{(1t)}^{b1}\mathit{d}t}$$ 
where $x\in [0,1]$ and $a,b\in (0,\mathrm{\infty})$. Note that for any fixed $a$ and $b$, ${I}_{x}(a,b)$ is increasing in $x$. Hence, in order to obtain a lower bound on $\mathrm{vol}\left({C}_{1}\right)$, we want to lower bound $1\frac{{c}_{1}^{2}}{{r}_{1}^{2}}$ or equivalently, upper bound $\frac{{c}_{1}^{2}}{{r}_{1}^{2}}.$
Write ${r}_{1}=\frac{\alpha}{2\sqrt{n}}$ for some $\alpha \in [1,2]$. From Eq. (1),
$${c}_{1}=\frac{1}{4n}+\frac{{\alpha}^{2}}{8n}\frac{1}{32{n}^{2}}.$$ 
Hence,
$$\frac{{c}_{1}}{{r}_{1}}=\frac{1}{16\sqrt{n}}\left(\frac{8}{\alpha}+4\alpha \frac{1}{n}\right)$$ 
Since $g(\alpha )=\frac{8}{\alpha}+4\alpha $ is convex in $[1,2]$, $g(\alpha )\le \mathrm{max}(g(1),g(2))=12.$ It follows that $\frac{{c}_{1}}{{r}_{1}}\le \frac{1}{16\sqrt{n}}\left(12\frac{1}{n}\right)\le \frac{3}{4\sqrt{n}}.$ So, $1\frac{{c}_{1}^{2}}{{r}_{1}^{2}}\ge 1\frac{9}{16n}.$ To complete the proof, note that ${V}_{n}:={I}_{1\frac{9}{16n}}(\frac{n+1}{2},\frac{1}{2})$ is increasing in $n$, and ${V}_{1}=\frac{1}{4}$. As $n$ goes to infinity, this value converges to $1$ as ${B}_{1}\subset {B}_{2}$. ∎
Proof of Lemma 7.
Let $\nu =\frac{1}{5nQ}$. Let $q=(1\nu )x+\nu {x}^{*}$. Let ${B}_{q}=\mathcal{B}({c}_{q},{r}_{q})$ be a ball that has $q$ on its surface, lies inside ${\mathcal{L}}_{q}^{\downarrow}$, and has radius ${r}_{q}={Q}^{1}\parallel x{x}^{*}\parallel $. Lemma 15 guarantees its existence.
Suppose that
$$\mathrm{vol}\left({B}_{x}\cap {B}_{q}\right)\ge \frac{1}{4}\mathrm{vol}\left({B}_{x}\right)$$  (2) 
and that a random sample $y$ from ${B}_{x}$ belongs to ${B}_{q}$, which happens with probability at least $\frac{1}{4}$. Then, our guarantee follows by
$f(y)f({x}^{*})$  $\le f(q)f({x}^{*})$  
$\le (1\nu )f(x)+\nu f({x}^{*})f({x}^{*})$  
$\le (1\nu )\left(f(x)f({x}^{*})\right)$ 
where the first line follows from Lemma 15 and second line from convexity of $f$.
Therefore, it now suffices to prove Eq. 2. To do so, we will apply Lemma 8 after showing that the radius of ${B}_{x}$ and ${B}_{q}$ are in the proper ranges. Let $\mathrm{\ell}=\parallel x{c}_{q}\parallel $ and note that
$\mathrm{\ell}$  $\le \parallel xq\parallel +{r}_{q}$  (3)  
$\le \nu \parallel x{x}^{*}\parallel +{r}_{q}=\nu \parallel x{x}^{*}\parallel +{Q}^{1}\parallel q{x}^{*}\parallel $  
$\le (\nu +{Q}^{1}(1\nu ))\parallel x{x}^{*}\parallel $  (4)  
$\le \frac{6}{5Q}\parallel {b}_{x}{x}^{*}\parallel .$ 
Since $x$ is outside of ${B}_{q}$, we also have
$\mathrm{\ell}$  $\ge {r}_{q}={Q}^{1}\parallel q{x}^{*}\parallel ={Q}^{1}(1\nu )\parallel x{x}^{*}\parallel $  
$\ge \frac{4}{5Q}\parallel {b}_{x}{x}^{*}\parallel .$  (5) 
It follows that
$$\frac{\mathrm{\ell}}{2}\le \frac{3}{5Q}\parallel {b}_{x}{x}^{*}\parallel \le \mathrm{\ell}.$$ 
In the ${\mathrm{log}}_{2}$ space, our choice of ${k}_{1}$ is equivalent to starting from ${\mathrm{log}}_{2}{C}_{1}$ and sweeping through the range $[{\mathrm{log}}_{2}{C}_{1},{\mathrm{log}}_{2}{C}_{2}]$ at the interval of size 1. This is guaranteed to find a point between $\frac{\mathrm{\ell}}{2}$ and $\mathrm{\ell}$, which is also an interval of size 1. Therefore, there exists a ${k}_{1}$ satisfying the theorem statement, and similarly, we can prove the existence of ${k}_{2}$.
Finally, it remains to show that ${r}_{q}\ge (11/(4n))\mathrm{\ell}.$
From Eq. (3), it suffices to show that $\parallel xq\parallel \le \frac{\mathrm{\ell}}{4n}$ or equivalently $\nu \parallel x{x}^{*}\parallel \le \frac{\mathrm{\ell}}{4n}$. From Eq. (4),
$$\parallel xq\parallel =\nu \parallel x{x}^{*}\parallel \le \nu Q{(1\nu )}^{1}\mathrm{\ell}.$$ 
For any $Q,n\ge 1$, $1\nu \ge \frac{4}{5}$. So,
$$\nu Q{(1\nu )}^{1}=\frac{1}{5n}{(1\nu )}^{1}\le \frac{1}{4n}$$  (6) 
and the proof is complete. ∎
Proof of Lemma 9.
Without loss of generality, let $\mathrm{\ell}=1$ and ${B}_{2}$ is centered at the origin with radius ${r}_{2}$ and ${B}_{1}$ is centered at ${e}_{1}=(1,0,\mathrm{\dots},0)$. Then, we simply want to show that
$$\mathrm{\mathbf{P}\mathbf{r}}[{(1+{X}_{1})}^{2}+\sum _{i=2}^{n}{X}_{i}^{2}\le {r}_{2}^{2}]>{c}_{n}$$ 
By Markov’s inequality, we see that ${\sum}_{i=2}^{n}{X}_{i}^{2}\le 2{r}_{1}^{2}=2/n$ with probability at most $1/2$. And since ${X}_{1}$ is independent and ${r}_{2}\ge 11/n$, it suffices to show that
$$\mathrm{\mathbf{P}\mathbf{r}}[{(1+{X}_{1})}^{2}\le 14/n]>\mathrm{\Omega}(1)$$ 
Since ${X}_{1}$ has standard deviation at least ${r}_{1}/\sqrt{n}\ge 1/(2n)$, we see that the probability of deviating at least a few standard deviation below is at least a constant. ∎
Proof of Theorem 10.
Proof of Theorem 11.
By the boundedness of $h$, since $f(x)f({x}^{*})\ge 60\delta k{Q}_{g}(\mathbf{A})$, we see that $g({\mathbf{P}}_{\mathbf{A}}x)g({x}^{*})\ge 60\delta k{Q}_{g}(\mathbf{A})2\delta >0$. By Lemma 9, we see that if we sample from a Gaussian distribution $y\sim \mathcal{N}(x,\frac{{r}^{2}}{k}\mathbf{I})$, then if ${z}^{*}$ is the minimum of $g(x)$ restricted to the column space of $\mathbf{A}$, then
$$g({\mathbf{P}}_{\mathbf{A}}y)g({z}^{*})\le \left(g({\mathbf{P}}_{\mathbf{A}}x)g({z}^{*})\right)\left(1\frac{1}{5k{Q}_{g}(\mathbf{A})}\right)$$ 
with constant probability. By boundedness on $h$, we know that $h(y)\le h(x)+2\delta $. Furthermore, this also implies that $g({\mathbf{P}}_{\mathbf{A}}{x}^{*})\le g({z}^{*})+2\delta $. Therefore, we know that the decrease is at least
$f(y)f({x}^{*})$  $=g({\mathbf{P}}_{\mathbf{A}}y)g({\mathbf{P}}_{\mathbf{A}}{x}^{*})+h(y)h({x}^{*})$  
$\le g({\mathbf{P}}_{\mathbf{A}}y)g({z}^{*})+2\delta $  
$\le \left(g({\mathbf{P}}_{\mathbf{A}}x)g({z}^{*})\right)\left(1{\displaystyle \frac{1}{5k{Q}_{g}(\mathbf{A})}}\right)+2\delta $  
$\le \left(g({\mathbf{P}}_{\mathbf{A}}x)g({\mathbf{P}}_{\mathbf{A}}{x}^{*})+2\delta \right)\left(1{\displaystyle \frac{1}{5k{Q}_{g}(\mathbf{A})}}\right)+2\delta $  
$\le \left(f(x)f({x}^{*})+4\delta \right)\left(1{\displaystyle \frac{1}{5k{Q}_{g}(\mathbf{A})}}\right)+2\delta $  
$\le \left(f(x)f({x}^{*})\right)\left(1{\displaystyle \frac{1}{5k{Q}_{g}(\mathbf{A})}}\right)+6\delta $ 
Since $f(x)f({x}^{*})\ge 10\delta k{Q}_{g}(A)$, we conclude that
$$\left(f(x)f({x}^{*})\right)\left(1\frac{1}{5k{Q}_{g}(\mathbf{A})}\right)+6\delta \le \left(f(x)f({x}^{*})\right)\left(1\frac{1}{10k{Q}_{g}(\mathbf{A})}\right)$$ 
and our proof is complete. ∎
Proof of Theorem 12.
Our main proof strategy is to show that progress can only be made with a radius size of $O(\sqrt{\mathrm{log}(nQ)}/(nQ))$; larger radii cannot find descent directions with high probability. Consider a simple ellipsoid function $f(x)={x}^{\top}Dx$, where $D$ is a diagonal matrix and ${D}_{11}\le {D}_{22}\le \mathrm{\dots}\le {D}_{nn}$, where WLOG we let ${D}_{11}=1$ and ${D}_{ii}=Q$ for $i>1$. The optima is ${x}^{*}=0$ with $f({x}^{*})=0$.
Consider the region $X=\{x=({x}_{1},{x}_{2},\mathrm{\dots},{x}_{n})1\ge {x}_{1}\ge 0.9,{x}_{i}\le 0.1/(Q\sqrt{n})\}$. Then, if we let $v\sim N(0,I)$ be a standard Gaussian vector, then for some radius $r$, we see that the probability of finding a descent direction is:
$\mathrm{\mathbf{P}\mathbf{r}}[f(x+rv)\le f(x)]$  $=\mathrm{\mathbf{P}\mathbf{r}}[{({x}_{1}+r{v}_{1})}^{2}+{\displaystyle \sum _{i>1}}{D}_{ii}{({x}_{i}+r{v}_{i})}^{2}\le {x}_{1}^{2}+{\displaystyle \sum _{i>1}}{D}_{ii}{x}_{i}^{2}]$  
$=\mathrm{\mathbf{P}\mathbf{r}}[2r{x}_{1}{v}_{1}+{r}^{2}{v}_{1}^{2}+Q{\displaystyle \sum _{i>1}}(2r{x}_{i}{v}_{i}+{r}^{2}{v}_{i}^{2})\le 0]$  
$\le \mathrm{\mathbf{P}\mathbf{r}}[2r{x}_{1}{v}_{1}\le Q{\displaystyle \sum _{i>1}}2r{x}_{i}{v}_{i}Q{r}^{2}{\displaystyle \sum _{i>1}}{v}_{i}^{2}]$  
$=\mathrm{\mathbf{P}\mathbf{r}}[{v}_{1}{X}_{1}\le Q{\displaystyle \sum _{i>1}}{x}_{i}{v}_{i}{\displaystyle \frac{1}{2}}Qr{\displaystyle \sum _{i>1}}{v}_{i}^{2}]$ 
By standard concentration bounds for subexponential variables, we have
$$\mathrm{\mathbf{P}\mathbf{r}}[\frac{1}{n1}\sum _{i>1}{v}_{i}^{2}1\ge t]\le 2{e}^{(n1){t}^{2}/8}$$ 
Therefore, with exponentially high probability, ${\sum}_{i>1}{X}_{i}^{2}\ge n/2$. Also, since ${x}_{i}\le 0.1/(Q\sqrt{n})$, Chernoff bounds give:
$$\mathrm{\mathbf{P}\mathbf{r}}\left[\right\sum _{i>1}{x}_{i}{v}_{i}\ge t]\le 2{e}^{50{(Qt)}^{2}}$$ 
Therefore, with probability at least $11/{(nQ)}^{3}$, ${\sum}_{i>1}{v}_{i}{X}_{i}\le \sqrt{\mathrm{log}(nQ)}/Q$.
If $Qrn\ge \mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)})$, then we have
$Q{\displaystyle \sum _{i>1}}{v}_{i}{X}_{i}{\displaystyle \frac{1}{2}}Qr{\displaystyle \sum _{i>1}}{X}_{i}^{2}$  $\le \mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)})$ 
We conclude that the probability of descent is upper bounded by $\mathrm{\mathbf{P}\mathbf{r}}[{v}_{1}{X}_{1}\le \mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)})]$. This probability is exactly $\mathrm{\Phi}(l)$, where $\mathrm{\Phi}$ is the cumulative density of a standard normal and $l=\mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)})$. By a naive upper bound, we see that
$\mathrm{\Phi}(l)$  $={\displaystyle \frac{1}{\sqrt{2\pi}}}{\displaystyle {\int}_{l}^{\mathrm{\infty}}}{e}^{{x}^{2}/2}\mathit{d}x$  
$\le {\displaystyle \frac{C}{l}}{\displaystyle {\int}_{l}^{\mathrm{\infty}}}x{e}^{{x}^{2}/2}\mathit{d}x$  
$={\displaystyle \frac{C}{l}}{e}^{{l}^{2}/2}$ 
Since $l=\mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)})$, we conclude that Therefore, we conclude that with probability at least $11/poly(nQ)$, we have $f(y)f({x}^{*})\ge f(x)f({x}^{*})$.
Otherwise, we are in the case that $Qrn\le O(\sqrt{\mathrm{log}(nQ)})$. Arguing simiarly as before, with high probability, our objective function and each coordinate can change by at most $O(\sqrt{\mathrm{log}(nQ)}/(Qn))$.
Next, we extend our proof to any symmetric distribution $\mathcal{D}$. Since $\mathcal{D}$ is rotationally symmetric, if we parametrize $v=(r,\theta )$ is polarcoordinates, then the p.d.f. of any scaling of $\mathcal{D}$ must take the form $p(v)={p}_{r}(r)u(\theta )$, where $u(\theta )$ induces the uniform distribution over the unit sphere. Therefore, if $Y$ is a random variable that follows $\mathcal{D}$, then we may write $Y=Rv/\parallel v\parallel $, where $R$ is a random scalar with p.d.f ${p}_{r}(r)$ and $v$ is a standard Gaussian vector and $R,X$ are independent.
As previously argued, $\parallel v\parallel \in [0.5n,1.5n]$ with exponentially high probability. Therefore, if $R\ge \mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)}/Q)$, the same arguments will imply that $Y$ is a descent direction with polynomially small probability. Thus, when $Y$ is a descent direction, it must be that $R\le \mathrm{\Omega}(\sqrt{\mathrm{log}(nQ)}/Q)$ and as argued previously, our lower bound follows similarly.
∎
Appendix B Proofs of Section 4
Proof of Theorem 13.
By the Gaussian version of Theorem 7 (full rank version of Theorem 10), as long as our binary search sweeps between minimum search radius $r\le \frac{3}{5Q\sqrt{n}}\parallel x{x}^{*}\parallel $ and maximum search radius of the diameter of the whole space $R=\parallel \mathcal{X}\parallel $, the objective value will decrease multiplicatively by $1\frac{1}{5nQ}$ in each iteration with constant probability. Therefore, if $\parallel {x}_{t}{x}^{*}\parallel \ge 2Q\u03f5$ and we set $r=\frac{\u03f5}{\sqrt{n}}$ and $R=\parallel \mathcal{X}\parallel $, then with high probability, we expect $f({x}_{T})f({x}^{*})\le \beta {Q}^{2}{\u03f5}^{2}$ after $T=O(nQ\mathrm{log}(\parallel \mathcal{X}\parallel /(Q\u03f5)))$ iterations, where we note that $F=f({x}_{0})f({x}^{*})\le \beta {\parallel \mathcal{X}\parallel}^{2}$ by smoothness.
Otherwise, if there exists some ${x}_{t}$ such that $\parallel {x}_{t}{x}^{*}\parallel \le 2Q\u03f5$, then $f({x}_{T})f({x}^{*})\le f({x}_{t})f({x}^{*})\le 4\beta {Q}^{2}{\u03f5}^{2}$. Therefore, by strong convexity, we conclude that in either case, $\parallel {x}_{T}{x}^{*}\parallel \le 2{Q}^{3/2}\u03f5$. Finally note that each iteration uses a binary search that requires $O(\mathrm{log}(R/r))=O(\mathrm{log}(n\parallel \mathcal{X}\parallel /\u03f5))$ function evaluations.
Therefore, by combining these bounds, we derive our result. The lowrank result follows from applying Theorem 10 and Theorem 11 instead.
∎
Proof of Theorem 14.
Let $H=O(nQ\mathrm{log}(Q))$ be the number of iterations between successive radius halving and we initialize $R=\parallel \mathcal{X}\parallel $ and half $R$ every $H$ iterations. We call the iterations between two halving steps an epoch. We claim that $\parallel {x}_{i}{x}_{0}\parallel \le R$ for all iterations and proceed with induction on the epoch number. The base case is trivial.
Assume that $\parallel {x}_{i}{x}_{0}\parallel \le R$ for all iterations in the previous epoch and let iteration ${i}_{s}$ be the start of the epoch and iteration ${i}_{s}+H$ be the end of the epoch. Then, since $\parallel {x}_{{i}_{s}}{x}^{*}\parallel \le R$, we see that $f({x}_{{i}_{s}})f({x}^{*})\le \beta {R}^{2}$ by smoothness. If $\frac{R}{4\sqrt{Q}}\le \parallel {x}_{i}{x}^{*}\parallel \le 4\sqrt{Q}R$ for all $i$ in the previous epoch, then by the Gaussian version of Theorem 7 (Theorem 10), since we do a binary sweep from $\frac{R}{4Q}$ to $4\sqrt{Q}R$, we can choose $\mathcal{D}$ accordingly so that we are guaranteed that our objective value will decrease multiplicatively by $1\frac{1}{5nQ}$ with constant probability at a cost of $O(\mathrm{log}(Q))$ function evaluations per iteration. This implies that with high probability, after $O(nQ\mathrm{log}(Q))$ iterations, we conclude
$$f({x}_{{i}_{s}+H})f({x}^{*})\le \frac{1}{4Q}(f({x}_{{i}_{s}})f({x}^{*}))\le \frac{\alpha}{4}{\parallel {x}_{{i}_{s}}{x}^{*}\parallel}^{2}\le \frac{\alpha}{4}{R}^{2}$$ 
Otherwise, there exists some $1\le j\le H$ such that $\parallel {x}_{{i}_{s}+j}{x}^{*}\parallel \ge 4\sqrt{Q}R$ or $\parallel {x}_{{i}_{s}+j}{x}^{*}\parallel \le \frac{R}{4\sqrt{Q}}$. If it is the former, then by strong convexity, $f({x}_{{i}_{s}+j})f({x}^{*})\ge \alpha {\parallel {x}_{{i}_{s}+j}{x}^{*}\parallel}^{2}\ge 2\beta {R}^{2}$, which contradicts the fact that $f({x}_{{i}_{s}})f({x}^{*})\le \beta {R}^{2}$ by smoothness. If it is the latter, then by smoothness, we reach the same conclusion:
$$f({x}_{{i}_{s}+H})f({x}^{*})\le f({x}_{{i}_{s}+j})f({x}^{*})\le \beta {\parallel {x}_{{i}_{s}+j}{x}^{*}\parallel}^{2}\le \frac{\alpha}{4}{R}^{2}$$ 
Therefore, by strong convexity, we have
$$\parallel {x}_{{i}_{s}+H}{x}^{*}\parallel \le \sqrt{\frac{f({x}_{{i}_{s}+H})f({x}^{*})}{\alpha}}\le \frac{R}{2}$$ 
And our induction is complete. Therefore, we conclude that after $\mathrm{log}(\parallel \mathcal{X}\parallel /\u03f5)$ epochs, we have $\parallel {x}_{T}{x}^{*}\parallel \le \u03f5$. Each epoch has $H$ iterations, each with $O(\mathrm{log}(Q))$ function evaluations and so our result follows.
The lowrank result follows from applying Theorem 10 and Theorem 11 instead. However, note that since we do not know the latent dimension $k$, we must extend the binary search to incur an extra $\mathrm{log}(n)$ factor in the binary search cost.
∎