Random Gradient-Free Minimization of Convex Functions

In this paper, we prove new complexity bounds for methods of convex optimization based only on computation of the function value. The search directions of our schemes are normally distributed random Gaussian vectors. It appears that such methods usually need at most n times more iterations than the standard gradient methods, where n is the dimension of the space of variables. This conclusion is true for both nonsmooth and smooth problems. For the latter class, we present also an accelerated scheme with the expected rate of convergence \(O\Big ({n^2 \over k^2}\Big )\), where k is the iteration counter. For stochastic optimization, we propose a zero-order scheme and justify its expected rate of convergence \(O\Big ({n \over k^{1/2}}\Big )\). We give also some bounds for the rate of convergence of the random gradient-free methods to stationary points of nonconvex functions, for both smooth and nonsmooth cases. Our theoretical results are supported by preliminary computational experiments.

1. In [15], u was uniformly distributed over a unit ball. In our comparison, we use a direct translation of the constructions in [15] into the language of the normal Gaussian distribution.

2. Presence of this oracle is the main reason why we call our methods gradient free (not derivative free!). Indeed, directional derivative is a much simpler object as compared with the gradient. It can be easily defined for a very large class of functions. At the same time, definition of the gradient (or subgradient) is much more involved. It is well known that in nonsmooth case, collection of partial derivatives is not a subgradient of convex function. For nonsmooth nonconvex functions, the possibility of computing a single subgradient needs a serious mathematical justification [17]. On the other hand, if we have an access to a program for computing the value of our function, then the program for computing directional derivatives can be obtained by a trivial automatic forward differentiation.

3. The rest of the proof is very similar to the proof of Lemma 2.2.4 in [16]. We present it here just for the reader convenience.

The authors would like to thank two anonymous referees for enormously careful and helpful comments. Pavel Dvurechensky proposed a better proof of inequality (37), which we use in this paper. Research activity of the first author for this paper was partially supported by the grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique - Communautè française de Belgique,” and RFBR research projects 13-01-12007 ofi_m. The second author was supported by Laboratory of Structural Methods of Data Analysis in Predictive Modeling, MIPT, through RF government grant, ag.11.G34.31.0073.

Authors and Affiliations

1. Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL), Leuven, Belgium

   Yurii Nesterov

2. Weierstrass Institute for Applied Analysis and Stochastics (WIAS), Humboldt University of Berlin, Berlin, Germany

   Vladimir Spokoiny

Corresponding author

Correspondence to Yurii Nesterov.

Communicated by Michael Overton.

Y. Nesterov: This work was done in affiliation with Higher School of Economics, Moscow.

Appendix: Proofs of Statements of Sect. 2

Proof of Lemma 1

Denote \(\psi (p) = \ln M_p\). This function is convex in p. Let us represent \(p = (1-\alpha )\cdot 0 + \alpha \cdot 2\) (thus, \(\alpha = {p \over 2}\)). For \(p \in [0,2]\), we have \(\alpha \in [0,1]\). Therefore,

This is the upper bound (16). If \(p \ge 2\), then \(\alpha \ge 1\), and \(\alpha \psi (2)\) becomes a lower bound for \(\psi (p)\). It remains to prove the upper bound in (17).

Let us fix some \(\tau \in (0,1)\). Note that for any \(t \ge 0\) we have

Therefore,

The minimum of the right-hand side in \(\tau \in (0,1)\) is attained at \(\tau = {p \over p+n}\). Thus,

\(\square \)

Proof of Theorem 1

Indeed, for any \(x \in E\) we have \(f_{\mu }(x) - f(x) = {1 \over \kappa } \int \limits _E [ f(x+\mu u) - f(x)] \mathrm{e}^{-{1 \over 2}\Vert u \Vert ^2} \mathrm{d}u\). Therefore, if \(f \in C^{0,0}(E)\), then

Further, if f is differentiable at x, then

Therefore, if \(f \in C^{1,1}(E)\), then

Finally, if f is twice differentiable at x, then

Therefore, if \(f \in C^{2,2}(E)\), then

\(\square \)

Proof of Lemma 2

Indeed, for all x and y in E, we have

It remains to apply (16). \(\square \)

Proof of Theorem 2

Let \(\mu >0\). Since \(f_{\mu }\) is convex, for all x and \(y \in E\) we have

Taking now the limit as \(\mu \rightarrow 0\), we prove the statement for \(\mu = 0\). \(\square \)

Proof of Lemma 3

Indeed, for function \(f \in C^{1,1}(E)\), we have

Let \(f \in C^{2,2}(E)\). Denote \(a_u(\tau ) = f(x+\tau u) - f(x) - \tau \langle \nabla f(x), u \rangle - {\tau ^2 \over 2} \langle \nabla ^2 f(x) u, u \rangle \). Then, \(|a_u(\pm \mu )| \mathop {\le }\limits ^{(7)} {\mu ^3 \over 6} L_2(f) \Vert u \Vert ^3\). Since

we have

\(\square \)

Proof of Lemma 4

Indeed,

It remains to use inequality (17). \(\square \)

Reprints and permissions