A Universal Black-Box Optimization Method with
Almost Dimension-Free Convergence Rate Guarantees

Let $\mathcal{V}$ be a $d$-dimensional space with norm $\lVert\cdot\rVert$. In what follows, we will write $\mathcal{Y}\equiv\mathcal{V}^{\ast}$ for the dual of $\mathcal{V}$, $\langle y\mathopen{},\mathopen{}x\rangle$ for the pairing between $y\in\mathcal{Y}$ and $x\in\mathcal{V}$, and $\lVert y\rVert_{\ast}\equiv\sup\{\langle y\mathopen{},\mathopen{}x\rangle:\lVert x\rVert\leq 1\}$ for the dual norm on $\mathcal{Y}$. Given an extended-real-valued convex function $f\colon\mathcal{V}\to\mathbb{R}\cup\{\infty\}$, we will write $\operatorname{dom}f\equiv\{x\in\mathcal{V}:f(x)<\infty\}$ for its effective domain and $\partial f(x)\equiv\{y\in\mathcal{Y}:f(x^{\prime})-f(x)-\langle y\mathopen{},\mathopen{}x^{\prime}-x\rangle\geq 0\;\text{for all $x^{\prime}\in\mathcal{V}$}\}$ for the subdifferential of $f$ at $x\in\operatorname{dom}f$. Any element $g\in\partial f(x)$ will be called a subgradient of $f$ at $x$, and we will write $\operatorname{dom}\partial f\equiv\{x\in\operatorname{dom}f:\partial f\neq\varnothing\}$ for the domain of subdifferentiability of $f$.

The main focus of our paper is the solution of convex minimization problems of the form

where $\mathcal{X}$ is a closed convex subset of $\mathcal{V}$ and $f\colon\mathcal{V}\to\mathbb{R}\cup\{\infty\}$ is a convex function with $\operatorname{dom}f=\operatorname{dom}\partial f=\mathcal{X}$. To avoid trivialities, we will assume throughout that the solution set $\mathcal{X}^{\ast}\coloneqq\operatorname*{arg\,min}f$ of (Opt) is non-empty, and we will write $x^{\ast}$ for a generic minimizer of $f$.

Other than this blanket assumption, our main reqularity requirements for $f$ will be as follows:

1. (1)

   Lipschitz continuity:

   $$\lvert f(x^{\prime})-f(x)\rvert\leq G\lVert x^{\prime}-x\rVert$$

   (LC)

   for some $G\geq 0$ and for all $x,x^{\prime}\in\mathcal{X}$.

2. (2)

   Lipschitz smoothness:

   $$f(x^{\prime})\leq f(x)+\langle\nabla f(x)\mathopen{},\mathopen{}x^{\prime}-x\rangle+\frac{L}{2}\lVert x^{\prime}-x\rVert^{2}$$

   (LS)

   for some $L\geq 0$ and for all $g\in\partial f(x)$, $x,x^{\prime}\in\mathcal{X}$.

Since $\operatorname{dom}\partial f=\mathcal{X}$, the above requirements are respectively equivalent to assuming that $f$ admits a selection of subgradients $\nabla f(x)\in\partial f(x)$ with the properties below:

1. (1)

   Bounded (sub)gradient selection:

   $$\lVert\nabla f(x)\rVert_{\ast}\leq G$$

   (BG)

   for some $G\geq 0$ and for all $x\in\mathcal{X}$.

2. (2)

   Lipschitz (sub)gradient selection:

   $$\lVert\nabla f(x^{\prime})-\nabla f(x)\rVert_{\ast}\leq L\lVert x^{\prime}-x\rVert$$

   (LG)

   for some $L\geq 0$ and for all $x,x^{\prime}\in\mathcal{X}$.

In the rest of our paper, we will assume that $f$ satisfies at least one of (BG) or (LG).

To solve (Opt), we will consider iterative methods and algorithms with access to a stochastic first-order oracle (SFO), i.e., a black-box device that returns a (possibly random) estimate of a subgradient of $f$ at the point at which it was queried. Formally, following Nesterov [38], an stochastic first-order oracle (SFO) for $f$ is a measurable function $\operatorname{\mathsf{G}}\colon\mathcal{X}\times\Omega\to\mathcal{Y}$ such that

where $(\Omega,\mathcal{F},\operatorname{\mathbb{P}})$ is a complete probability space and $\nabla f(x)$ is a selection of subgradients of $f$ as per (BG)/(LG). The oracle’s statistical precision will then be measured by the associated noise level $\sigma\coloneqq\operatorname{ess}\sup_{\omega,x}\lVert\operatorname{\mathsf{G}}(x;\omega)-\nabla f(x)\rVert_{\ast}$ (assumed finite). In particular, if $\sigma=0$, $\operatorname{\mathsf{G}}$ will be called perfect (or deterministic); otherwise, $\operatorname{\mathsf{G}}$ will be called noisy.

In practice, the oracle is called repeatedly at a sequence of query points $x_{t}$ with a different random seed $\omega_{t}$ drawn according to $\operatorname{\mathbb{P}}$ at each time.²²2In the sequel, $t$ may take both integer and half-integer values. In this way, at the $t$-th query to (SFO), the oracle $\operatorname{\mathsf{G}}$ returns the gradient signal

where $U_{t}$ denotes the “gradient noise” of the oracle (obviously, $U_{t}\equiv 0$ if the oracle is perfect). For measurability purposes, we will write $\mathcal{F}_{t}$ for the history (adapted filtration) of $x_{t}$, so $x_{t}$ is $\mathcal{F}_{t}$-measurable (by definition) but $\omega_{t}$, $g_{t}$ and $U_{t}$ are not. In particular, conditioning on $\mathcal{F}_{t}$, we have $\operatorname{\mathbb{E}}[g_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{t}]=\nabla f(x_{t})$ and $\operatorname{\mathbb{E}}[U_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{t}]=0$, justifying in this way the terminology “gradient noise” for $U_{t}$.

We close this section by noting that the best convergence rates that can be achieved by an iterative algorithm that outputs a candidate solution $\bar{x}_{T}\in\mathcal{X}$ after $T$ queries to (SFO) are:³³3In general, the query and output points – $x_{T}$ and $\bar{x}_{T}$ respectively – need not coincide, hence the different notation. The only assumption for the rates provided below is that the output point $\bar{x}_{T}$ is an affine combination of $x_{1},g_{1},\dotsc,x_{T},g_{T}$ [38, 11].

1. (1)

   $f(\bar{x}_{T})-\min f=\operatorname{\mathcal{O}}(1/\sqrt{T})$ if $f$ satisfies (BG) and $\operatorname{\mathsf{G}}$ is deterministic.

2. (2)

   $f(\bar{x}_{T})-\min f=\operatorname{\mathcal{O}}(1/T^{2})$ if $f$ satisfies (LG) and $\operatorname{\mathsf{G}}$ is deterministic.

3. (3)

   $\operatorname{\mathbb{E}}[f(\bar{x}_{T})-\min f]=\operatorname{\mathcal{O}}(1/\sqrt{T})$ if $\operatorname{\mathsf{G}}$ is stochastic.

In general, without finer assumptions on $f$ or $\operatorname{\mathsf{G}}$, the dependence of these rates on $T$ cannot be improved [38, 11]; we will revisit this issue several times in the sequel.

As a first step, we present three archetypal problems to motivate and illustrate the general setup that follows.

Examples 1, 2 and 3 all suffer from the “curse of dimensionality”: for instance, the dimensionality of a vector Gaussian channel with $M=256$ input entries is $d\approx 6.5\times 10^{4}$, while a combinatorial bandit for recommendation systems may have upwards of several million arms. Nonetheless, these examples also share a number of geometric properties that make it possible to design scalable optimization algorithms with (almost) dimension-free convergence rate guarantees. We elaborate on this in the next section.

We begin by considering the well-known mirror-prox (MP) method of Nemirovski [36]. Following [22, 35], this is defined via the recursion

where

1. (1)

   $t=1,2,\dotsc\,$ denotes the method’s iteration counter (for the origins of the half-integer notation, see Facchinei & Pang [18] and references therein).

2. (2)

   $\gamma_{t}>0$ is the algorithm’s step-size sequence.

3. (3)

   $g_{t}$ and $g_{t+1/2}$ are stochastic gradients of $f$ obtained by querying the oracle $\operatorname{\mathsf{G}}$ at $X_{t}$ and $X_{t+1/2}$ respectively.

4. (4)

   $P_{#1}(\cdot)$ is a generalized projection operator known as the method’s “prox-mapping” (more on this later).

The most elementary instance of (MP) is the extra-gradient (EG) algorithm of Korpelevich [25], in which case the method’s prox-mapping is the Euclidean projector

for all $x\in\mathcal{X}$, $y\in\mathcal{Y}$. More generally, the prox-mapping in (MP) is defined in terms of a Bregman regularizer as follows:

In terms of output, the candidate solution returned by (MP) after $T$ iterations is the so-called “ergodic average”

Then, assuming the method’s step-size $\gamma_{t}$ is chosen appropriately (more on this below), $\bar{X}_{T}$ enjoys the following guarantees [22, 42]:

1. \edefnit\selectfonta\edefnn)

   If $f$ satisfies (BG), then

   	$\displaystyle\operatorname{\mathbb{E}}[f(\bar{X}_{T})-\min f]$	$\displaystyle=\operatorname{\mathcal{O}}\left(\sqrt{\frac{G^{2}+\sigma^{2}}{K_{h}}\frac{D_{1}}{T}}\right)$		(9a)
   	$\displaystyle\operatorname{\mathbb{E}}[f(\bar{X}_{T})-\min f]$	$\displaystyle=\operatorname{\mathcal{O}}\left(\frac{LD_{1}}{K_{h}T}+\sigma\sqrt{\frac{D_{1}}{K_{h}T}}\right)$		(9b)

In the above, $D_{1}=D(x^{\ast},X_{1})$ is the minimum Bregman divergence between a solution $x^{\ast}$ of (Opt) and the initial state $X_{1}$ of (MP). In particular, if (MP) is initialized at the prox-center $x_{c}=\operatorname*{arg\,min}h$ of $\mathcal{X}$, we have

We will refer to $R_{h}=\max h-\min h$ as the range of $h$.

To quantify the interplay betwen the problem’s dimensionality and the rate guarantees (9) for (MP), it will be convenient to introduce the normalized regularity parameters

and the associated shape factor

Since at least one of the terms $G/\sqrt{K_{h}}$, $L/K_{h}$ and $\sigma/\sqrt{K_{h}}$ appears in (9), it follows that the leading term in $T$ scales as $\operatorname{\mathcal{O}}(\chi\sqrt{D_{1}/T})$ in non-smooth / stochastic environments, and as $\operatorname{\mathcal{O}}(\chi^{2}D_{1}/T)$ in smooth, deterministic problems.

The importance of the normalized parameters $G_{h}$, $L_{h}$, $\sigma_{h}$ and the shape factor $\chi$ lies in the fact that they do not depend on the ambient norm $\lVert\cdot\rVert$ (a choice which, to a certain extent, is arbitrary). Indeed, if $\lVert\cdot\rVert$ and $\lVert\cdot\rVert^{\prime}$ are two norms on $\mathcal{V}$ that are related as $\lVert\cdot\rVert\leq\mu\lVert\cdot\rVert^{\prime}$ for some $\mu>0$, it is straightforward to verify that $h$ is $(\mu^{2}K_{h})$-strongly convex relative to $\lVert\cdot\rVert^{\prime}$. Likewise, in terms of dual norms we have $\lVert\cdot\rVert_{\ast}\geq(1/\mu)\lVert\cdot\rVert^{\prime}_{\ast}$, so the constants $G$, $\sigma$ and $L$ would respectively become $\mu G$, $\mu\sigma$ and $\mu^{2}L$ when computed under $\lVert\cdot\rVert^{\prime}$. In general, these inequalities are all tight, so a change in norm does not affect the shape factor $\chi$; accordingly, any dependence of $\chi$ on $d$ will be propagated verbatim to the guarantees (9).

In Table 1, we provide the values of $R_{h}$ and $\chi$ for the following cases:

1. (1)

   The Euclidean regularizer $h(x)=\lVert x\rVert_{2}^{2}/2$ that gives rise to the extra-gradient algorithm (4).

2. (2)

   The entropic regularizer $h(x)=\sum_{i=1}^{d}x_{i}\log x_{i}$ for the simplex setup of Example 1.

3. (3)

   The von Neumann regularizer $h(\mathbf{X})=\operatorname{tr}(\mathbf{X}\log\mathbf{X})+(1-\operatorname{tr}\mathbf{X})\log(1-\operatorname{tr}\mathbf{X})$ for the spectrahedron setup of Example 2.

4. (4)

   The unnormalized entropy $h(x)=\sum_{i=1}^{d}(x_{i}\log x_{i}-x_{i})$ for the combinatorial setup of Example 3.

These derivations are standard, so we omit the details. For posterity, we only note that the logarithmic dependence on $d$ is asymptotically optimal, cf. [13, 12] and references therein.

As can be seen from Table 1, the mirror-prox algorithm achieves an almost dimension-free rate of convergence when used with a suitable regularizer. However, this comes with two important caveats: First, the algorithm’s rate in the smooth case falls short of the optimal $\operatorname{\mathcal{O}}(1/T^{2})$ dependence in $T$, so (MP) is suboptimal in this regard. Second, to achieve the rates presented in Eq. 9, the algorithm’s step-size $\gamma_{t}$ must be tuned with prior knowledge of the problem’s parameters: in particular, under (BG), the algorithm must be run with step-size $\gamma_{t}\propto 1/\sqrt{(G^{2}+\sigma^{2})T}$ while, under (LG), the algorithm requires $\gamma_{t}=K_{h}/L$ if $\sigma=0$ and $\gamma_{t}\propto 1/(\sigma\sqrt{T})$ otherwise. This creates an undesirable state of affairs because the parameters $G$, $L$ and $\sigma$ are usually not known in advance, and (MP) can – and does – fail to converge if run with an untuned step-size.

In the rest of this section, we briefly discuss the UnixGrad algorithm of Kavis et al. [24] which expands on the mirror-prox template in the following two crucial ways: \edefnit\selectfonta\edefnn) it introduces an iterate-averaging mechanism in the spirit of Cutkosky [16] to enable acceleration; and \edefnit\selectfonta\edefnn) it employs an adaptive step-size policy that does not require any tuning by the optimizer. In so doing, UnixGrad interpolates smoothly between the optimal convergence rates described in Section 2 without requiring any prior knowledge of $G$, $L$ or $\sigma$.

Concretely, UnixGrad proceeds as (MP), but instead of querying $\operatorname{\mathsf{G}}$ at $X_{t}$ and $X_{t+1/2}$, it introduces the weighted query states

where $\alpha_{t}$ is a “gradient weighting” parameter. Then, building on an idea by Rakhlin & Sridharan [41, 42], the oracle queries $g_{t}\leftarrow\operatorname{\mathsf{G}}(\bar{X}_{t};\omega_{t})$ and $g_{t+1/2}\leftarrow\operatorname{\mathsf{G}}(\bar{X}_{t+1/2};\omega_{t+1/2})$ are used to update the method’s step-size as

where

is the so-called Bregman diameter of $\mathcal{X}$.

With all this in hand, Kavis et al. [24] provide the following bounds if UnixGrad is run with $\alpha_{t}=t$:

1. \edefnit\selectfonta\edefnn)

   If $f$ satisfies (BG), then

   	$\displaystyle\operatorname{\mathbb{E}}[f(\bar{X}_{T+1/2})-\min f]$	$\displaystyle=\operatorname{\mathcal{O}}\bigg{(}\frac{B_{h}\sqrt{G^{2}+\sigma^{2}}}{\sqrt{K_{h}T}}\bigg{)}$		(16a)
   	$\displaystyle\operatorname{\mathbb{E}}[f(\bar{X}_{T+1/2})-\min f]$	$\displaystyle=\operatorname{\mathcal{O}}\left(\frac{B_{h}^{2}L}{K_{h}T^{2}}+\frac{B_{h}\sigma}{\sqrt{K_{h}T}}\right)$		(16b)

As we mentioned in Section 2, the bounds (16) cannot be improved in terms of $T$ without further assumptions, so UnixGrad is universally optimal in this regard.

That being said, these guarantees also uncover an important limitation of UnixGrad, namely that the bounds (16) become void when the method is used in conjunction with one of the non-Euclidean frameworks of Examples 1, 2 and 3. For example, the Bregman diameter of the simplex under the entropic regularizer is $B_{h}=\sup_{x,x^{\prime}}\sum_{i}x_{i}\log(x_{i}/x^{\prime}_{i})=\infty$, so the multiplicative constants in (16) become infinite (and the bounds themselves become meaningless). However, since the use of these regularizers is crucial to obtain the scalable, dimension-free convergence rates reported in Table 1, ⁴⁴4In particular, since the shape factor of the Euclidean regularizer is $\chi=\sqrt{d}$, employing UnixGrad with ordinary Euclidean projections would not lead to scalable guarantees. we are led to the open question we stated before:

Is it possible to achieve almost dimension-free convergence rates
while retaining an order-optimal dependence on $T$?

We address this question in the next section.