Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization

Introduction

Convex optimization forms the backbone of many algorithms for statistical learning and estimation. Given that many statistical estimation problems are large-scale in nature—with the problem dimension and/or sample size being large—it is essential to make efficient use of computational resources. Stochastic optimization algorithms are an attractive class of methods, known to yield moderately accurate solutions in a relatively short time . Given the popularity of such stochastic optimization methods, understanding the fundamental computational complexity of stochastic convex optimization is thus a key issue for large-scale learning. A large body of literature is devoted to obtaining rates of convergence of specific procedures for various classes of convex optimization problems. A typical outcome of such analysis is an upper bound on the error—for instance, gap to the optimal cost—as a function of the number of iterations. Such analyses have been performed for many standard optimization algorithms, among them gradient descent, mirror descent, interior point programming, and stochastic gradient descent, to name a few. We refer the reader to various standard texts on optimization (e.g., ) for further details on such results.

On the other hand, there has been relatively little study of the inherent complexity of convex optimization problems. To the best of our knowledge, the first formal study in this area was undertaken in the seminal work of Nemirovski and Yudin , hereafter referred to as NY. One obstacle to a classical complexity-theoretic analysis, as these authors observed, is that of casting convex optimization problems in a Turing Machine model. They avoided this problem by instead considering a natural oracle model of complexity, in which at every round the optimization procedure queries an oracle for certain information on the function being optimized. This information can be either noiseless or noisy, depending on whether the goal is to lower bound the oracle complexity of deterministic or stochastic optimization algorithms. Working within this framework, the authors obtained a series of lower bounds on the computational complexity of convex optimization problems, both in deterministic and stochastic settings. In addition to the original text NY , we refer the interested reader to the book by Nesterov , and the lecture notes by Nemirovski for further background.

In this paper, we consider the computational complexity of stochastic convex optimization within this oracle model. In particular, we improve upon the work of NY for stochastic convex optimization in two ways. First, our lower bounds have an improved dependence on the dimension of the space. In the context of statistical estimation, these bounds show how the difficulty of the estimation problem increases with the number of parameters. Second, our techniques naturally extend to give sharper results for optimization over simpler function classes. We show that the complexity of optimization for strongly convex losses is smaller than that for convex, Lipschitz losses. Third, we show that for a fixed function class, if the set of optimizers is assumed to have special structure such as sparsity, then the fundamental complexity of optimization can be significantly smaller. All of our proofs exploit a new notion of the discrepancy between two functions that appears to be natural for optimization problems. They involve a reduction from a statistical parameter estimation problem to the stochastic optimization problem, and an application of information-theoretic lower bounds for the estimation problem. We note that special cases of the first two results in this paper appeared in the extended abstract , and that a related study was independently undertaken by Raginsky and Rakhlin .

The remainder of this paper is organized as follows. We begin in Section 2 with background on oracle complexity, and a precise formulation of the problems addressed in this paper. Section 3 is devoted to the statement of our main results, and discussion of their consequences. In Section 4, we provide the proofs of our main results, which all exploit a common framework of four steps. More technical aspects of these proofs are deferred to the appendices.

Background and problem formulation

We begin by introducing background on the oracle model of convex optimization, and then turn to a precise specification of the problem to be studied.

where $x_{T}$ is the method’s query at time $T$. Note that by definition of $x^{*}_{f}$ as a minimizing argument, this error is a non-negative quantity.

2 Stochastic first-order oracles

Stochastic gradient methods are a widely used class of algorithms that can be understood as operating based on information provided by a stochastic first-order oracle. As a particular example, consider a function of the separable form $f(x)=\frac{1}{n}\sum_{i=1}^{n}h_{i}(x)$, where each $h_{i}$ is differentiable. Functions of this form arise very frequently in statistical problems, where each term $i$ corresponds to a different sample and the overall cost function is some type of statistical loss (e.g., maximum likelihood, support vector machines, boosting etc.) The natural stochastic gradient method for this problem is to choose an index $i\in\{1,2,\ldots,n\}$ uniformly at random, and then to return the pair $(h_{i}(x),\nabla h_{i}(x))$. Taking averages over the randomly chosen index $i$ yields $\frac{1}{n}\sum_{i=1}^{n}h_{i}(x)=f(x)$, so that $h_{i}(x)$ is an unbiased estimate of $f(x)$, with an analogous unbiased property holding for the gradient of $h_{i}(x)$.

3 Function classes of interest

Our first class consists of convex Lipschitz functions:

If we consider the case of a differentiable function $f$, the unbiasedness condition in Definition 1 implies that

A second function class consists of strongly convex functions, defined as follows:

In order to establish this inequality, we note that strong convexity condition with $\alpha=1/2$ implies that

As a third example, we study the oracle complexity of optimization over the class of convex functions that have sparse minimizers. This class of functions is well-motivated, since a large body of statistical work has studied the estimation of vectors, matrices and functions under various types of sparsity constraints. A common theme in this line of work is that the ambient dimension $d$ enters only logarithmically, and so has a mild effect. Consequently, it is natural to investigate whether the complexity of optimization methods also enjoys such a mild dependence on ambient dimension under sparsity assumptions.

Main results and their consequences

We begin by analyzing the minimax oracle complexity of optimization for the class of bounded and convex Lipschitz functions $\mathcal{F}_{\operatorname{\scriptsize{cv}}}$ from Definition 2.

In general, our lower bounds cannot be improved, and hence specify the optimal minimax oracle complexity. We consider here some examples to illustrate their sharpness. Throughout we assume that $T$ is large enough to ensure that the $1/\sqrt{T}$ term attains the lower bound and not the $L/144$ term. (This condition is reasonable given our goal of understanding the rate as $T$ increases, as opposed to the transient behavior over the first few iterations.)

As mentioned previously, the dimension-independent lower bound for the case $p\geq 2$ was demonstrated in Chapter 5 of NY, and shown to be optimalThere is an additional logarithmic factor in the upper bounds for $p=\Omega(\log d)$. since it is achieved using mirror descent with the prox-function $\|\cdot\|_{q}$. For the case of $1\leq p<2$, the lower bounds are also unimprovable, since they are again achieved (up to constant factors) by stochastic gradient descent. See Appendix C for further details on these matching upper bounds.

Even though the results have been stated in a first-order stochastic oracle model, they actually hold in a stronger sense. Let $\nabla^{i}f(x)$ denote the $i_{th}$-order derivative of $f$ evaluated at $x$, when it exists. With this notation, our results apply to an oracle that responds with a random function $\hat{f}_{t}$ such that

along with appropriately bounded second moments of all the derivatives. Consequently, higher-order gradient information cannot improve convergence rates in a worst-case setting. Indeed, the result continues to hold even for the significantly stronger oracle that responds with a random function that is a noisy realization of the true function. In this sense, our result is close in spirit to a statistical sample complexity lower bound. Our proof technique is based on constructing a “packing set” of functions, and thus has some similarity to techniques used in statistical minimax analysis (e.g., ) and learning theory (e.g., ). A significant difference, as will be shown shortly, is that the metric of interest for optimization is very different than those typically studied in statistical minimax theory.

2 Oracle complexity for strongly convex Lipschitz functions

We now turn to the statement of lower bounds over the class of Lipschitz and strongly convex functions $\mathcal{F}_{\operatorname{\scriptsize{scv}}}$ from Definition 3. In all these statements, we assume that $\gamma^{2}\leq\frac{4Ld^{-1/p}}{r}$, as is required for the definition of $\mathcal{F}_{\operatorname{\scriptsize{scv}}}$ to be sensible.

3 Oracle complexity for convex Lipschitz functions with sparse optima

Finally, we turn to the oracle complexity of optimization over the class $\mathcal{F}_{\operatorname{\scriptsize{sp}}}$ from Definition 4.

If $k=\mathcal{O}(d^{1-\delta})$ for some $\delta\in(0,1)$ (so that $\log\frac{d}{k}=\Theta(\log d)$), then this bound is sharp up to constant factors. In particular, suppose that we use mirror descent based on the $\|\cdot\|_{1+\varepsilon}$ norm with $\varepsilon=2\log d/(2\log d-1)$. As we discuss in more detail in Appendix C, it can be shown that this technique will achieve a solution accurate to $\mathcal{O}(\sqrt{\frac{k^{2}\log d}{T}})$ within $T$ iterations; this achievable result matches our lower bound (14) up to constant factors under the assumed scaling $k=\mathcal{O}(d^{1-\delta})$ . To the best of our knowledge, Theorem 3 provides the first tight lower bound on the oracle complexity of sparse optimization.

Proofs of results

We now turn to the proofs of our main results. We begin in Section 4.1 by outlining the framework and establishing some basic results on which our proofs are based. Sections 4.2 through 4.4 are devoted to the proofs of Theorems 1 through 3 respectively.

We begin by establishing a basic set of results that are exploited in the proofs of the main results. At a high-level, our main idea is to show that the problem of convex optimization is at least as hard as estimating the parameters of Bernoulli variables—that is, the biases of $d$ independent coins. In order to perform this embedding, for a given error tolerance $\epsilon$, we start with an appropriately chosen subset of the vertices of a $d$-dimensional hypercube, each of which corresponds to some values of the $d$ Bernoulli parameters. For a given function class, we then construct a “difficult” subclass of functions that are indexed by these vertices of the hypercube. We then show that being able to optimize any function in this subclass to $\epsilon$-accuracy requires identifying the hypercube vertex. This is a multiway hypothesis test based on the observations provided by $T$ queries to the stochastic oracle, and we apply Fano’s inequality or Le Cam’s bound to lower bound the probability of error. In the remainder of this section, we provide more detail on each of steps involved in this embedding.

Our first step is to construct a subclass of functions $\mathcal{G}\subseteq\mathcal{F}$ that we use to derive lower bounds. Any such subclass is parametrized by a subset $\mathcal{V}\subseteq\{-1,+1\}^{d}$ of the hypercube, chosen as follows. Recalling that $\Delta_{H}$ denotes the Hamming metric, we let $\mathcal{V}=\{\alpha^{1},\ldots,\alpha^{M}\}$ be a subset of the vertices of the hypercube such that

meaning that $\mathcal{V}$ is a $\frac{d}{4}$-packing in the Hamming norm. It is a classical fact (e.g., ) that one can construct such a set with cardinality $|\mathcal{V}|\geq(2/\sqrt{e})^{d/2}$.

Based on these functions and the packing set $\mathcal{V}$, we define the function class

Note that $\mathcal{G}(\delta)$ contains a total of $|\mathcal{V}|$ functions by construction, and as mentioned previously, our choices of the base functions etc. will ensure that $\mathcal{G}(\delta)\subseteq\mathcal{F}$. We demonstrate specific choices of the class $\mathcal{G}(\delta)$ in the proofs of Theorems 1 through 3 to follow.

1.2 Optimizing well is equivalent to function identification

This discrepancy measure is non-negative, symmetric in its arguments, and satisfies $\rho(f,g)=0$ if and only if $x^{*}_{f}=x^{*}_{g}$, so that we may refer to it as a premetric. (It does not satisfy the triangle inequality nor the condition that $\rho(f,g)=0$ if and only if $f=g$, both of which are required for $\rho$ to be a metric.)

Given the subclass $\mathcal{G}(\delta)$, we quantify how densely it is packed with respect to the premetric $\rho$ using the quantity

We denote this quantity by $\psi(\delta)$ when the class $\mathcal{G}$ is clear from the context. We now state a simple result that demonstrates the utility of maintaining a separation under $\rho$ among functions in $\mathcal{G}(\delta)$.

Re-arranging yields the inequality $g_{\beta}(\widetilde{x})-g_{\beta}(x^{*}_{\beta})\geq\frac{2}{3}\,\psi(\delta)$, from which the claim (20) follows.

Suppose that for some fixed but unknown function $g_{\alpha^{*}}\in\mathcal{G}(\delta)$, some method $\mathcal{M}_{T}$ is allowed to make $T$ queries to an oracle with information function $\phi(\cdot\,;\,g_{\alpha^{*}})$, thereby obtaining the information sequence

Our next lemma shows that if the method $\mathcal{M}_{T}$ achieves a low minimax error over the class $\mathcal{G}(\delta)$, then one can use its output to construct a hypothesis test that returns the true parameter $\alpha^{*}$ at least $2/3$ of the time. (In this statement, we recall the definition (2) of the minimax error in optimization.)

Suppose that based on the data $\phi(x_{1}^{T};g_{\alpha}^{*})$, there exists a method $\mathcal{M}_{T}$ that achieves a minimax error satisfying

We have thus shown that having a low minimax optimization error over $\mathcal{G}(\delta)$ implies that the vertex $\alpha^{*}\in\mathcal{V}$ can be identified most of the time.

1.3 Oracle answers and coin tosses

We now describe stochastic first order oracles $\phi$ for which the samples $\phi(x_{1}^{T};g_{\alpha})$ can be related to coin tosses. In particular, we associate a coin with each dimension $i\in\{1,2,\ldots,d\}$, and consider the set of coin bias vectors lying in the set

Given a particular function $g_{\alpha}\in\mathcal{G}(\delta)$—or equivalently, vertex $\alpha\in\mathcal{V}$—we consider two different types of stochastic first-order oracles $\phi$, defined as follows:

1.4 Lower bounds on coin-tossing

Finally, we use information-theoretic methods to lower bound the probability of correctly estimating the true parameter $\alpha^{*}\in\mathcal{V}$ in our model. At each round of either Oracle A or Oracle B, we can consider a set of $d$ coin tosses, with an associated vector $\theta^{*}=(\frac{1}{2}+\alpha^{*}_{1}\delta,\ldots,\frac{1}{2}+\alpha^{*}_{d}\delta)$ of parameters. At any round, the output of Oracle A can (at most) reveal the instantiation $b_{i}\in\{0,1\}$ of a randomly chosen index, whereas Oracle B can at most reveal the entire vector $(b_{1},b_{2},\ldots,b_{d})$. Our goal is to lower bound the probability of estimating the true parameter $\alpha^{*}$, based on a sequence of length $T$. As noted previously in remarks following Theorem 1, this part of our proof exploits classical techniques from statistical minimax theory, including the use of Fano’s inequality (e.g., ) and Le Cam’s bound (e.g., ).

where the probability is taken over both randomness in the oracle and the choice of $\alpha^{*}$.

By Fano’s inequality , we have the lower bound

By the independent and identically distributed nature of the sampling model, we have

By chain rule for mutual information , we have

Since the subset $U$ is chosen independently of $\alpha^{*}$, we have $I(\alpha^{*};U)=0$, and so it suffices to upper bound the first term. By definition of conditional mutual information , we have

The reader might have observed that Fano’s inequality yields a non-trivial lower bound only when $|\mathcal{V}|$ is large enough. Since $|\mathcal{V}|$ depends on the dimension $d$ for our construction, we can apply the Fano lower bound only for $d$ large enough. Smaller values of $d$ can be lower bounded by reduction to the case $d=1$; here we state a simple lower bound for estimating the bias of a single coin, which is a straightforward application of Le Cam’s bounding technique . In this special case, we have $\mathcal{V}=\left\{1/2+\delta,1/2-\delta\right\}$, and we recall that the estimator $\widehat{\alpha}(\mathcal{M}_{T})$ takes values in $\mathcal{V}$.

Given a sample size $T\geq 1$ and a parameter $\alpha^{*}\in\mathcal{V}$, let $\{X_{1},\ldots,X_{T}\}$ be $T$ i.i.d Bernoulli variables with parameter $\alpha^{*}$. Let $\widehat{\alpha}$ be any test function based on these samples and returning an element of $\mathcal{V}$. Then for any $\delta\in(0,1/4]$, we have the lower bound

where inequality (i) follows from the calculation following Equation 26 (see proof of Lemma 3), and uses our assumption that $\delta\in(0,1/4]$. Putting together the pieces, we obtain a lower bound on the probability of error

Equipped with these tools, we are now prepared to prove our main results.

2 Proof of Theorem 1

Furthermore, we note that for any $\alpha\neq\beta$, we have

When $\alpha_{i}=\beta_{i}$ then $x_{\alpha}(i)=x_{\beta}(i)=-\alpha_{i}/2$, so that this co-ordinate does not make a contribution to the discrepancy function $\rho(g_{\alpha},g_{\beta})$. On the other hand, when $\alpha_{i}\neq\beta_{i}$, we have

Consequently, any such co-ordinate yields a contribution of $2c\delta/d$ to the discrepancy. Recalling our packing set (15) with $d/4$ separation in Hamming norm, we conclude that for any distinct $\alpha\neq\beta$ within our packing set,

so that by definition of $\psi$, we have established the lower bound $\psi(\delta)\geq\frac{c\delta}{2}$.

Recalling that $c=\frac{L}{2}$, making the substitution $\delta=\frac{18\epsilon}{c}=\frac{36\epsilon}{L}$, and performing some algebra yields

where $c_{0}$ and $c_{1}$ are universal constants. Combined with Theorem 5.3.1 of NY (or by using the lower bound of Lemma 4 instead of Lemma 3), we conclude that this lower bound holds for all dimensions $d$.

As before, for any distinct pair $\alpha,\beta\in\mathcal{V}$, we have the lower bound

Substituting $\delta=18\epsilon/c$ yields the scaling $\epsilon\geq c_{0}\,\frac{c}{\sqrt{T}}$ for all $d\geq 11$, $\epsilon\leq c/72$ and a universal constant $c_{0}$. Recalling that $c=Ld^{1-1/p}$, we obtain the bound (10). Combining this with Theorem 5.3.1 of NY (or by using the lower bound of Lemma 4 instead of Lemma 3) gives the claim for all dimensions.

3 Proof of Theorem 2

We now turn to the proof of lower bounds on the oracle complexity of the class of strongly convex functions from Definition 3. In this case, we work with the following family of base functions, parametrized by a scalar $\theta\in[0,1)$:

A key ingredient of the proof is a uniform lower bound on the discrepancy $\rho$ between pairs of these functions:

Using an ensemble based on the base functions (30), we have

The proof of this lemma is provided in Appendix A. Let us now proceed to the proofs of the main theorem claims.

Case 1: First suppose that $1-\theta\geq 4\delta/(1+2\delta)$, in which case Lemma 5 yields the lower bound

Simplifying the above expression yields that for $d\geq 11$, we have the lower bound

Finally, we observe that $L=cr$ and $\gamma^{2}=(1-\theta)c/(4d)$ which gives $1-\theta=4dr\gamma^{2}/L$. Substituting the above relations in the lower bound (32) gives the first term in the stated result for $d\geq 11$.

To obtain lower bounds for dimensions $d<11$, we use an argument based on $d=1$. For this special case, we consider $f^{+}$ and $f^{-}$ to be the two functions of the single coordinate coming out of definition (30). The packing set $\mathcal{V}$ consists of only two elements now, corresponding to $\alpha=1$ and $\alpha=-1$. Specializing the result of Lemma 5 to this case, we see that the two functions are $2c\delta^{2}r^{2}/(1-\theta)$ separated. Now we again apply Lemma 2 to get an upper bound on the error probability and Lemma 4 to get a lower bound, which gives the result for $d\leq 11$.

Case 2: On the other hand, suppose that $1-\theta\leq 4\delta/(1+2\delta)$. In this case, appealing to Lemma 5 gives us that $\rho(g_{\alpha},\beta)\geq c\delta r^{2}/4$ for $\alpha\neq\beta\in\mathcal{V}$. Recalling that $L=cr$, we set the desired accuracy $\epsilon:=c\delta r^{2}/36=L\delta r/36$. From this point onwards, we mimic the proof of Theorem 1; doing so yields that for all $\delta\in(0,1/4)$, we have

corresponding to the second term in Theorem 1 for a universal constant $c_{0}$.

Finally, the third and fourth terms are obtained just like Theorem 1 by checking the condition $\delta<1/4$ in the two cases above. Overall, this completes the proof for the case $p=1$.

As with the proof of Theorem 1(b), we use Oracle B that returns $d$-dimensional values and gradients in this case, with the base functions defined in equation 30. With this choice, we have the upper bound

Rearranging terms and substituting $\epsilon=\frac{c\delta^{2}r^{2}}{18(1-\theta)}$, we obtain for $d\geq 11$

for a universal constant $c_{0}$. The stated result can now be attained by recalling $c=Ld^{1-1/p}/r$ and $\gamma^{2}=Ld^{-1/p}(1-\theta)/r$ for $1-\theta\geq 4\delta/(1+2\delta)$ and $d\geq 11$. For $d<11$, the cases of $p>2$ and $p=1$ are identical up to constant factors in the lower bounds we state. This completes the proof for $1-\theta\geq 4\delta/(1+2\delta)$.

Finally, the case for $1-\theta<4\delta/(1+2\delta)$ involves similar modifications as part(a) by using the different expression for $\rho(g_{\alpha},g_{\beta})$. Thus we have completed the proof of this theorem.

4 Proof of Theorem 3

We begin by constructing an appropriate subset of $\mathcal{F}_{\operatorname{\scriptsize{sp}}}(k)$ over which the Fano method can be applied. Let $\mathcal{V}(k):=\{\alpha^{1},\ldots,\alpha^{M}\}$ be a set of vectors, such that each $\alpha^{j}\in\{-1,0,+1\}^{d}$ satisfies

It can be shown that there exists such a packing set with |\mathcal{V}(k)|\geq\exp\big{(}\frac{k}{2}\log\frac{d-k}{k/2}\big{)} elements (e.g., see Lemma 5 in Raskutti et al. ).

For any $\alpha\in\mathcal{V}(k)$, we define the function

In this definition, the quantity $c>0$ is a pre-factor to be chosen later, and $\delta\in(0,\frac{1}{4}]$ is a given error tolerance. Observe that each function $g_{\alpha}\in\mathcal{G}(\delta;k)$ is convex, and Lipschitz with parameter $c$ with respect to the $\|\cdot\|_{\infty}$ norm.

Central to the remainder of the proof is the function class $\mathcal{G}(\delta;k):=\{g_{\alpha},\;\alpha\in\mathcal{V}(k)\}$. In particular, we need to control the discrepancy $\psi(\delta;k):=\psi(\mathcal{G}(\delta;k))$ for this class. The following result, proven in Appendix B, provides a suitable lower bound:

Using Lemma 6, we may complete the proof of Theorem 3. Define the base functions

Consider Oracle B, which returns $d$-dimensional gradients based on the function

Our next step is to use Fano’s inequality to lower bound the probability of error in the multiway testing problem associated with this stochastic oracle, following an argument similar to (but somewhat simpler than) the proof of Lemma 3. Fano’s inequality yields the lower bound

By Lemma 6 and our choice $c=L/3$, we have

for a universal constant $c_{0}$, where the second step uses the relation $\delta=\frac{108\epsilon}{Lkr}$ for $k,d\geq 11$. As long as $k\leq\lfloor d/2\rfloor$, we have $\log\frac{d-k}{k/2}=\Theta\left(\log\frac{d}{k}\right)$, which gives the result for $k,d\geq 11$. The result for $k,d\leq 11$ follows Theorem 1(b) applied with $p=\infty$, completing the proof.

Discussion

In this paper, we have studied the complexity of convex optimization within the stochastic first-order oracle model. We derived lower bounds for various function classes, including convex functions, strongly convex functions, and convex functions with sparse optima. As we discussed, our lower bounds are sharp in general, since there are matching upper bounds achieved by known algorithms, among them stochastic gradient descent and stochastic mirror descent. Our bounds also reveal various dimension-dependent and geometric aspects of the stochastic oracle complexity of convex optimization. An interesting aspect of our proof technique is the use of tools common in statistical minimax theory. In particular, our proofs are based on constructing packing sets, defined with respect to a pre-metric that measures how the degree of separation between the optima of different functions. We then leveraged information-theoretic techniques, in particular Fano’s inequality and its variants, in order to establish lower bounds.

There are various directions for future research. It would be interesting to consider the effect of memory constraints on the complexity of convex optimization, or to derive lower bounds for problems of distributed optimization. We suspect that the proof techniques developed in this paper may be useful for studying these related problems.

AA and PLB gratefully acknowledge partial support from NSF awards DMS-0707060 and DMS-0830410 and DARPA-HR0011-08-2-0002. AA was also supported in part by a Microsoft Research Fellowship. MJW and PR were partially supported by funding from the National Science Foundation (DMS-0605165, and DMS-0907632). In addition, MJW received funding from the Air Force Office of Scientific Research (AFOSR-09NL184). We also thank the anonymous reviewers for helpful suggestions, and corrections to our results and for pointing out the optimality of our bounds in the primal-dual norm setting.

Appendix A Proof of Lemma 5

Consequently, using the definition (30) of the base functions, some algebra yields the relations

Using these expressions for $f^{+}_{i}$ and $f^{-}_{i}$, we obtain

A little calculation shows that constrained minimum of the univariate function $h_{i}$ over the interval $[-r,r]$ is achieved at

where we have recalled that $\alpha_{i}$ takes values in $\{-1,+1\}$. Substituting the minimizing argument $x^{*}(i)$, we find that the minimum value is given by

Summing over all co-ordinates $i\in\{1,2,\ldots,d\}$, we obtain

Here we begin by observing that for any two $\alpha,\beta\in\mathcal{V}$, we have

As in our previous calculation, the only coordinates that contribute to $\rho(g_{\alpha},g_{\beta})$ are the ones where $\alpha_{i}\neq\beta_{i}$, and for such coordinates, the function above is minimized at $x^{*}(i)=0$. Furthermore, the minimum value for any such coordinate is $(1+3\theta)cr^{2}/(2d)$.

We split the remainder of our analysis into two cases: first, if we suppose that $\frac{1-\theta}{1+\theta}\geq 2\delta$, or equivalently that $1-\theta\geq 4\delta/(1+2\delta)$, then equation (39) yields that

Combined with our earlier expression (38) for the single function infimum, we obtain that the discrepancy is given by

On the other hand, if we assume that $\frac{1-\theta}{1+\theta}<2\delta$, or equivalently that $1-\theta<4\delta/(1+2\delta)$, then we obtain

Combined with our earlier expression (38) for the single function infimum, we obtain

where step (i) uses the bound $1-\theta<2\delta(1+\theta)$. Noting that $\theta\geq 0$ completes the proof of the lemma.

Appendix B Proof of Lemma 6

We now consider one of the individual terms arising in the definition (16) of the function $g_{\alpha}$. Using the relation (40), it can be written as

Let us consider the minimizer of the $i^{th}$ term in this summation. First, suppose that $\alpha_{i}\neq\beta_{i}$, in which case there are two possibilities.

If $\alpha_{i}\neq\beta_{i}$ and neither $\alpha_{i}$ nor $\beta_{i}$ is zero, then we must have $\alpha_{i}+\beta_{i}=0$, so that the minimum value of $2r$ is achieved at $x(i)=0$.

Otherwise, suppose that $\alpha_{i}\neq 0$ and $\beta_{i}=0$. In this case, we see from Equation (42) that it is equivalent to minimizing $\alpha_{i}x(i)+|x(i)|$. Setting $x(i)=-\alpha_{i}$ achieves the minimum value of $2r$.

In the remaining two cases, we have $\alpha_{i}=\beta_{i}$.

If $\alpha_{i}=\beta_{i}\neq 0$, then the component is minimized at $x(i)=-\alpha_{i}r$ and the minimum value along the component is $2r(1-\delta)$.

If $\alpha_{i}=\beta_{i}=0$, then the minimum value is $2r$, achieved at $x(i)=0$.

Consequently, accumulating all of these individual cases into a single expression, we obtain

Finally, combining equations (41) and (43) in the definition of $\rho$, we find that

where the second equality follows since $\alpha$ and $\beta$ have exactly $k$ non-zero elements each. Finally, since $\mathcal{V}$ is an $k/2$-packing set in Hamming distance, we have $\Delta_{H}(\alpha,\beta)\geq k/2$, which completes the proof.

Appendix C Upper bounds via mirror descent

This appendix is devoted to background on the family of mirror descent methods. We first describe the basic form of the algorithm and some known convergence results, before showing that different forms of mirror descent provide matching upper bounds for several of the lower bounds established in this paper, as discussed in the main text.

We assume that $\Phi$ is a function of Legendre type , which implies that the conjugate dual $\Phi^{*}$ is differentiable on its domain with \nabla\Phi^{*}=\big{(}\nabla\Phi\big{)}^{-1}. For a given proximal function, we let $D_{\Phi}$ be the Bregman divergence induced by $\Phi$, given by

where $\eta_{t}>0$ is a stepsize. In case of stochastic optimization, $\nabla f(x_{t})$ is simply replaced by the noisy version $\widehat{z}(x_{t})$.

A special case of this algorithm is obtained by choosing the proximal function $\Phi(x)=\frac{1}{2}\|x\|_{2}^{2}$, which is $1$-strongly convex with respect to the Euclidean norm. The associated Bregman divergence $D_{\Phi}(x,y)=\frac{1}{2}\|x-y\|_{2}^{2}$ is simply the Euclidean norm, so that the updates (45) correspond to a standard projected gradient descent method. If one receives only an unbiased estimate of the gradient $\nabla f(x_{t})$, then this algorithm corresponds to a form of projected stochastic gradient descent. Moreover, other choices of the proximal function lead to different stochastic algorithms, as discussed below.

Note that this averaged convergence is a little different from the convergence of $x_{T}$ discussed in our lower bounds. In order to relate the two quantities, observe that by Jensen’s inequality

Consequently, based on mirror descent for $T-1$ rounds, we may set $x_{T}=\frac{1}{T-1}\sum_{t=1}^{T-1}x_{t}$ so as to obtain the same convergence bounds up to constant factors. In the following discussion, we assume this choice of $x_{T}$ for comparing the mirror descent upper bounds to our lower bounds.

C.2 Matching upper bounds

Now consider the form of mirror descent obtained by choosing the proximal function

For this case, we use mirror descent based on the proximal function $\Phi_{a}$ with $a=q$. Under the condition $\|x^{*}\|_{\infty}\leq 1$, a condition which holds in our lower bounds, we obtain

which matches the lower bound from Theorem 1(b) (we note that there is an additional log factor here just like the preceding discussion when $p=\mathcal{O}(\log d)$ which we ignore here).

In order to recover matching upper bounds in this case, we use the function $\Phi_{a}$ from Equation (47) with $a=\frac{2\log d}{2\log d-1}$. In this case, the resulting upper bound (46) on the convergence rate takes the form

since $\frac{1}{a-1}=2\log d-1$. Based on the conditions of Theorem 3, we are guaranteed that $x^{*}$ is $k$-sparse, with every component bounded by $1$ in absolute value, so that $\|x^{*}\|_{a}^{2}\leq k^{2/a}\leq k^{2}$, where the final inequality follows since $a>1$. Substituting this upper bound back into Equation (48) yields

Note that whenever $k=\mathcal{O}(d^{1-\delta})$ for some $\delta>0$, then we have $\log d=\Theta(\log\frac{d}{k})$, in which case this upper bound matches the lower bound from Theorem 3 up to constant factors, as claimed.

References