Information-based complexity, feedback and dynamics in convex programming

I Introduction

Many problems arising in such areas as communications and signal processing, contrtol, machine learning, economics, and many others require solving mathematical programs of the form

A systematic study of these fundamental limits was initiated in the 1970’s by Nemirovski and Yudin . In their framework, an optimization algorithm is a sequential procedure that repeatedly queries a black-box oracle for information about the function being optimized, each query depending on the past information. The oracle may be deterministic (for example, giving the value of the function and its derivatives up to some order at any point) or stochastic. This leads to the notion of information-based complexity, i.e., the smallest number of oracle calls needed to minimize any function in a given class to a desired accuracy. The results in are very wide in scope and cover a variety of convex programming problems in Banach spaces; finite-dimensional versions are covered in and .

For deterministic oracles, Nemirovski and Yudin derived lower bounds on the information complexity of convex programming using a “counterfactual” argument: given any algorithm that purports to optimize all functions in some class $\mathcal{F}$ to some degree of accuracy $\varepsilon$ using at most $T$ oracle calls, one explicitly constructs, for a particular history of queries and oracle responses, a function in $\mathcal{F}$ which is consistent with this history, and yet cannot be $\varepsilon$-minimized by the algorithm using fewer than $T$ oracle calls (see also ). A similar approach was also used for stochastic oracles.

Proper application of this method of resisting oracles requires a lot of ingenuity. In particular, the stochastic case involves fairly contrived noise models, unlikely to be encountered in practice. In this paper, which expands upon our preliminary work , we will show that the same (and many other) lower bounds can be derived using a much simpler information-theoretic technique reminiscent of the way one proves minimax lower bounds in statistics . Namely, we reduce optimization to hypothesis testing with controlled observations and then relate the resulting probability of error to information complexity using Fano’s inequality and a series of mutual information bounds. These bounds highlight the role of feedback in choosing the next query based on past observations. One notable feature of our approach is that it does not require constructing particularly “strange” functions or noise models. Moreover, we derive a “law of diminishing returns” for a wide class of convex optimization schemes, which says that the decay of optimization error is offset by the decay of the rate at which the algorithm can reduce its uncertainty about the objective function.

The idea of relating optimization to hypothesis testing is not new. For instance, Shapiro and Nemirovski derive a lower bound on the information complexity of a certain class of one-dimensional linear optimization problems by reducing optimization to a binary hypothesis testing problem pertaining to the parameter of a Bernoulli random variable (the outcome of a coin toss). The reduction consists in showing that any good optimization algorithm can be converted into an accurate estimator of the coin bias based on repeated independent trials; then one can derive the lower bound on the information complexity (equivalently, the minimum necessary number of coin tosses) from the data processing inequality for divergence (or Fano’s inequality). This approach was recently extended to multidimensional optimization problems by Agarwal et al. . Like the present paper, their work uses information-theoretic methods to derive lower bounds on the oracle complexity of convex optimization, and their results are qualitatively similar to some of ours. However, what sets our work apart from is that we explicitly account for the controlled manner in which the algorithm interacts with the oracle. This, in turn, allows us to derive tight lower bounds on the rate of error decay for certain types of infinite-step descent algorithms, which is not possible with the reduction to coin tossing.

Sequential procedures have become increasingly popular in the field of machine learning, mostly due to the abundance of data and the resulting need to perform computation on-line. Convex optimization is not the only sequential setting being studied: recent research in machine learning has also focused on such scenarios as active learning, multi-armed bandits, and experimental design, to name a few. In all these settings, one element is common: each additional “action” should provide additional “information” about some unknown quantity. Translating this intuitive notion of “information” into precise information-theoretic statements is often difficult. Our contribution consists in offering such a translation for convex optimization and closely related problems.

The $n\times n$ identity matrix will be denoted by $I_{n}$.

All abstract spaces are assumed to be standard Borel (i.e., Borel subsets of a complete separable metric space), and will be equipped with their Borel $\sigma$-fields. If $\mathsf{Z}$ is such a space, then $\mathcal{B}_{\mathsf{Z}}$ will denote the corresponding $\sigma$-field. All functions between such spaces are assumed to be measurable. If $\mathsf{Z}_{1}$ and $\mathsf{Z}_{2}$ are two such spaces, then a Markov kernel from $\mathsf{Z}_{1}$ to $\mathsf{Z}_{2}$ is a mapping $P:\mathcal{B}_{\mathsf{Z}_{2}}\times\mathsf{Z}_{1}\to$, such that for any $z_{1}\in\mathsf{Z}_{2}$ $P(\cdot|z_{1})$ is a probability measure on $(\mathsf{Z}_{2},\mathcal{B}_{\mathsf{Z}_{2}})$ and for any $B\in\mathcal{B}_{\mathsf{Z}_{2}}$ $P(B|\cdot)$ is a measurable function on $\mathsf{Z}_{1}$. We will use the standard notation $P(dz_{2}|z_{1})$ for such a kernel.

Given a random triple $(Z_{1},Z_{2},Z_{3})\in\mathsf{Z}_{1}\times\mathsf{Z}_{2}\times\mathsf{Z}_{3}$, the conditional mutual information between $Z_{2}$ and $Z_{3}$ given $Z_{1}$ is

where (4) follows from Bayes’ rule and from (I-A). In other words, the conditional mutual information $I(Z_{2};Z_{3}|Z_{1})$ is given by the conditional divergence between the joint distribution of $Z_{1},Z_{2},Z_{3}$ and the distribution under which $Z_{2}$ and $Z_{3}$ are conditionally independent given $Z_{1}$.

II Sequential optimization algorithms and their information-based complexity

The theory of IBC is concerned with intrinsic difficulty of computational problems in terms of the minimum amount of information needed to solve every problem in a given class with a given guarantee of accuracy. The word “information” here does not refer to information in the sense of Shannon, but rather to what is known a priori about the problem being solved, as well as what an algorithm is allowed to learn during its operation. There are three aspects inherent in this notion of information — it is partial, noisy, and priced. Let us explain informally what these three terms mean in the context of optimization by means of a simple example.

Let $\mathsf{X}=$, and consider the function class

where $W$ and $Z$ are an i.i.d. pair of ${\mathcal{N}}(0,\sigma^{2})$ random variables.

The interaction of the algorithm and the oracle takes place as follows. Let $\{(W_{t},Z_{t})\}^{\infty}_{t=1}$ be an i.i.d. sequence. At time $t=1,2,\ldots$, the algorithm computes the query $X_{t}$ as a function of the past queries $X_{\tau},1\leq\tau\leq t-1$ and the corresponding oracle responses $Y_{\tau}=Y(\theta,X_{\tau},(W_{\tau},Z_{\tau})),1\leq\tau\leq t-1$. At time $t=0$ the algorithm knows only that $f\in\mathcal{F}$; this represents the a priori information. At time $t\geq 1$, the algorithm acquires additional data $(X^{t},Y^{t})=((X_{1},Y_{1}),\ldots,(X_{t},Y_{t}))$, and so can refine its a priori information. At every time step, the information is partial in the sense that there are (potentially infinitely) many functions consistent with it, and it is also noisy due to the presence of the additive disturbances $(W^{t},Z^{t})$.

where the expectation is taken w.r.t. the noise process $\{(W_{t},Z_{t})\}^{\infty}_{t=1}$. For this particular problem it can be shown that

The first entry $(\sigma^{2}=0,0\leq\varepsilon<1/2)$ follows because the algorithm can just query $x_{1}=0$, obtain the response $y_{1}=((1/2)\theta^{2},-\theta)$, and immediately compute $x_{2}=\theta$; the last entry $(\sigma^{2}>0,\varepsilon\geq 1/2)$ follows because the maximum value of any $f_{\theta}\in\mathcal{F}$ on $\mathsf{X}$ is at most $1/2$. The intermediate regime $(\sigma^{2}>0,\varepsilon\in(0,1/2))$ is more involved. The main contribution of the present paper is a unified information-theoretic framework for deriving lower bounds on the IBC of arbitrary sequential algorithms for solving convex programming problems.

The above discussion can be formalized as follows:

A problem class is a triple $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$ consisting of the following objects:

An oracle $\mathcal{O}=(\mathsf{Y},P)$, where $\mathsf{Y}$ is the oracle information space and $P(dy|f,x),dy\in\mathcal{B}_{\mathsf{Y}},f\in\mathcal{F},x\in\mathsf{X}$, is a Markov kernelRecall that $\mathcal{F}$ is a subset of $C(\mathsf{X})$, the space of all continuous real-valued functions on $\mathsf{X}$. Equipped with the usual sup norm, $C(\mathsf{X})$ is a separable Banach space, so a Markov kernel from $\mathcal{F}\times\mathsf{X}$ into $\mathsf{Y}$ is well-defined..

Some restrictions must be imposed in order to exclude oracles that are “too informative,” an extreme example being $\mathsf{Y}=\mathcal{F}\times\mathsf{X}$ and $P(dy|f,x)=\delta_{f,x}(dy)$. One way to rule this out is to require the oracle in question to be local :

We say that an oracle $\mathcal{O}$ is local if for every $x\in\mathsf{X}$ and every pair $f,f^{\prime}\in\mathcal{F}$ such that $f=f^{\prime}$ in some open neighborhood of $x$, we have

It is easy to see that the oracle described right before the definition is not local. Indeed, fix a point $x\in\mathsf{X}$ and consider any two functions $f,f^{\prime}\in\mathcal{F}$ that agree on some open neighborhood of $x$, but are not equal outside this neighborhood. Then $P(dy|f,x)=\delta_{f,x}(dy)$, but $P(dy|f^{\prime},x)=\delta_{f^{\prime},x}(dy)$, which violates locality. Most oracles encountered in practice are local (see, for instance, the examples in Section III).

To gain more insight into stochastic oracles, we can appeal to the basic structural result for Markov kernels: If $\mathsf{Z}_{1}$ and $\mathsf{Z}_{2}$ are standard Borel spaces, then any Markov kernel $P(dz_{2}|z_{1})$ from $\mathsf{Z}_{1}$ to $\mathsf{Z}_{2}$ can be realized in the form $Z_{2}=\Phi(z_{1},W)$, where $W$ is a random variable uniformly distributed on $$and$\Phi:\mathsf{Z}_{1}\times\to\mathsf{Z}_{2}$is a measurable mapping [13, Lemma 3.22]. Thus, for any stochastic oracle$P(dy|f,x)$we can find a deterministic oracle$\psi:\mathcal{F}\times\mathsf{X}\to\mathsf{U}$with some information space$\mathsf{U}$and a measurable mapping$\Phi:\mathsf{U}\times\to\mathsf{Y}$, such that$P$ can be realized as

with $W$ as above. Thus, $P$ will be local in the sense of Definition 2 whenever its “deterministic part” $\psi$ is local.

Next, we make the notion of an optimization algorithm precise. In this paper, we deal only with deterministic algorithms, although all the results can be easily extended to cover randomized algorithms as well (cf. for details):

A $T$-step algorithm for a given $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$ is a sequence of mappings $\mathcal{A}=\{\mathcal{A}_{t}:\mathsf{X}^{t-1}\times\mathsf{Y}^{t-1}\to\mathsf{X}\}^{T+1}_{t=1}$. The set of all $T$-step algorithms for $\mathcal{P}$ will be denoted by $\mathfrak{A}_{T}(\mathcal{P})$.

The interaction of any $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$ with $\mathcal{O}$, shown in Figure 1, is described recursively as follows:

At time $t=0$, a problem instance $f\in\mathcal{F}$ is selected by Nature and revealed to $\mathcal{O}$, but not to $\mathcal{A}$.

$\mathcal{A}$ queries $\mathcal{O}$ with $X_{t}=\mathcal{A}_{t}(X^{t-1},Y^{t-1})$, where $(X_{\tau},Y_{\tau})\in\mathsf{X}\times\mathsf{Y}$ is the algorithm’s query and the oracle’s response at time $\tau\leq t-1$.

$\mathcal{O}$ responds with a random element $Y_{t}\in\mathsf{Y}$ according to $P(dY_{t}|f,X_{t})$.

At time $t=T+1$, $\mathcal{A}$ outputs the candidate minimizer $X_{T+1}=\mathcal{A}_{T+1}(X^{T},Y^{T})$.

We can view the set-up of Figure 1 as a discrete-time stochastic dynamical system with an unknown “parameter” $f\in\mathcal{F}$, input sequence $\{X_{t}\}$, and output sequence $\{Y_{t}\}$. The objective is to drive the system as quickly as possible to an $\varepsilon$-minimizing state, i.e., any $x\in\mathsf{X}$ such that $f(x)-f^{*}<\varepsilon$, for every $f\in\mathcal{F}$. We are interested in the fundamental limits on the speed with which this can be done. Defining the error of $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$ on $f\in\mathcal{F}$ by

Fix a problem class $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$. For any $r\geq 1$, $\varepsilon>0$, and $\delta\in(0,1)$, we define the $r$th-order $(\varepsilon,\delta)$-complexity and the $\varepsilon$-complexity of $\mathcal{P}$, respectively, as

When the underlying problem class $\mathcal{P}$ is clear from context, we will write simply $K^{(r)}(\varepsilon,\delta)$ and $K^{(r)}(\varepsilon)$. Moreover, when $r=1$ we will simply write $K_{\mathcal{P}}(\cdot)$ or $K(\cdot)$.

The following is immediate from definitions (the proof is in Appendix B):

For any $\mathcal{P},r\geq 1,\varepsilon>0,\delta\in(0,1)$,

The complexities $K^{(r)}_{\mathcal{P}}(\varepsilon,\delta)$ and $K^{(r)}_{\mathcal{P}}(\varepsilon)$ capture the intrinsic difficulty of sequential optimization over the problem class $\mathcal{P}$ using any finite-step algorithm. However, most iterative optimization algorithms used in practice (such as stochastic gradient descent) are not run for a prescribed finite number of steps. Instead, they are run for however many steps are necessary until a desired accuracy is reached. Moreover, the error of the successive candidate minimizers produced by such an algorithm should decay monotonically with time. This observation motivates the following definitions:

A weak infinite-step algorithm for $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$ is a sequence of mappings $\mathcal{A}=\{\mathcal{A}_{t}:\mathsf{X}^{t-1}\times\mathsf{Y}^{t-1}\to\mathsf{X}\}^{\infty}_{t=1}$. The set of all weak infinite-step algorithms for $\mathcal{P}$ will be denoted by $\mathfrak{A}_{\infty}(\mathcal{P})$.

Given a problem class $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$ and some $r\geq 1$, an algorithm $\mathcal{A}\in\mathfrak{A}_{\infty}(\mathcal{P})$ is $r$-anytime if

We can now ask about fundamental limits on the rate of convergence in (9):

For any problem class $\mathcal{P}$, we define the $r$-anytime exponent as

According to the above definitions, the candidate minimizer $X_{t+1}$ produced by a weak infinite-step algorithm $\mathcal{A}\in\mathfrak{A}_{\infty}(\mathcal{P})$ after $t$ queries is simultaneously the query at time $t+1$. Many algorithms used in practice, such as stochastic gradient descent, are weak infinite-step algorithms. A more general class of algorithms, which we may call strong infinite-step algorithms, would also include strategies in which the process of issuing queries (i.e., gathering information about the objective) is separated from the process of generating candidate minimizers. Stochastic gradient descent with trajectory averaging is an example of such a strong algorithm. We do not consider strong infinite-step algorithms in this paper (except for a brief discussion in Appendix A), although their study is an interesting and important avenue for further research.

III Examples of problem classes and preview of selected results

The following six examples show the variety of settings captured by our framework, ranging from “standard” optimization problems to such scenarios as parameter estimation, sequential experimental design, and active learning.

Take $\mathcal{F}^{L}_{\rm Lip}$ as above, but now suppose that the oracle responds with

As in the previous example, the oracle responds with

such that for every $\theta\in\mathsf{X}$ $f_{\theta}(\theta)=\min_{x\in\mathsf{X}}f_{\theta}(x)$. Consider also the oracle $\mathcal{O}=(\mathsf{Y},P)$, defined by

This oracle ignores the query $x$ and simply outputs a random element $Y\sim P_{\theta}$. The problem class $(\mathsf{X},\mathcal{F},\mathcal{O})$ thus describes the statistical problem of estimating the parameter of a probability distribution. More generally, we can consider the function class

For each fixed $y\in\mathsf{Y}$, the function $x\mapsto F(x,y)$ is convex

$f_{\theta}(\theta)=\min_{x\in\mathsf{X}}f_{\theta}(x)$

with $f_{\theta}(x)\geq f_{\theta}(\theta)\equiv\operatorname{var}(P_{\theta})$, so we recover the problem of estimating the mean.

Thus, the role of $Q_{\theta}$ is to provide a measure of performance (or goodness-of-fit) of the final estimate of $\theta$, while $P_{\theta,x}$ describes the experimental model (i.e., the relationship between the input $X$ and the response $Y$ given the parameter $\theta$).

Our last example is at the intersection of statistical learning theory and sequential experimental design. Let

To define the oracle, suppose that there exist some $0<c,C<1/2$ and $\kappa\in[1,\infty)$, such that

where the first inequality holds for all $x$ in a sufficiently small neighborhood of $\theta$. This oracle provides a noisy subgradient of $f_{\theta}$ at $x$, and the amount of noise depends on the distance between $x$ and $\theta$. This problem class is related to active learning of a threshold function on the unit interval , and will be treated in detail in Section VI.

We now briefly discuss some of the lower bounds that arise from the techniques introduced in the paper. First, Theorem 1 in Section V implies a general lower bound of the form

on the number of oracle calls required to $\varepsilon$-minimize every function in a given class, where the exponent $\alpha>0$ depends on the geometry of the problem domain $\mathsf{X}$ and on the complexity of the instance space $\mathcal{F}$. For convex Lipschitz functions and noiseless first-order oracles (Example 1), or more generally for stochastic oracles that are sufficiently “informative” in a sense we make precise, this lower bound holds with $\alpha=1$ (cf. the discussion right after Theorem 1). This lower bound is known to be optimal in the noiseless case and in certain noisy scenarios when $n=1$ ; however, our techniques lead to a much more transparent proof of the bound.

For the noisy first-order oracle with zero-mean Gaussian noise of variance $\sigma^{2}$, we obtain lower bounds of the form

where the exponent $\alpha_{1}$ depends, as before, on the geometry of $\mathsf{X}$, on the complexity of $\mathcal{F}$, as well as on whether the oracle supplies full first-order information (function value and subgradient) or just the subgradient. The exponent $\alpha_{2}$ depends on the details of the function class $\mathcal{F}$. More specifically:

for $\mathcal{F}_{\rm Lip}$ (Example 2), we have $\alpha_{2}=2$ (Theorem 2 in Section V);

for $\mathcal{F}_{\rm SC}$ (Example 3), we have $\alpha_{2}=1$ (Theorem 3 in Section V).

The corresponding result for convex Lipschitz functions in $n=1$ can be found in , yet we obtain the optimal dependence on $n$ for higher dimensions. Our lower bound for strongly convex functions seems to be new; in particular, Nemirovski and Yudin only consider the noiseless case, while Agarwal et al. consider noisy first-order oracles, but with a different oracle model, which does not allow additive noise due to a coin-tossing construction. Ignoring the dependence on the dimension, we also obtain the error decay rate $\Omega(\sigma^{2}/t)$ for $\mathcal{F}_{\rm SC}$ when we restrict ourselves to anytime infinite-step algorithms (Theorem 5 in Section VI). To the best of our knowledge, such analysis does not appear anywhere else in the literature. The bounds of Eq. (7) essentially capture the fundamental limits of strongly convex programming in one dimension and can be easily deduced using our techniques (a sketch of the derivation is given in Section IV-A). We also derive new (and tighter) lower bounds on anytime algorithms for minimizing higher-order polynomials under a second-moment error criterion (Theorems 6 and 7 in Section VI).

Apart from “standard” optimization problems, our framework seamlessly captures several statistical problems with an optimization flavor. In particular, in Section V-D we look at information-based complexity of statistical estimation and sequential experimental design (Examples 4 and 5, respectively). Here we do not aim at obtaining tight rates for specific settings of interest, but rather show the connections to the techniques employed in statistics. Finally, we show in Section VI-C that our methodology leads to a particularly easy derivation of a lower bound for the active learning problem of Example 6. This bound was previously obtained in using a much more involved argument relying on a careful construction of a “difficult” subset of functions.

Overall, our main contributions are the development of a general framework that captures many diverse settings with optimization flavor, as well as a novel analysis that takes into account the effect of feedback upon the dynamics of the interaction between the algorithm and the oracle.

IV Setting the stage: optimization vs. hypothesis testing with feedback

We now lay down the foundations of our information-theoretic method for determining lower bounds on the information complexity of convex programming. The basic strategy is to show that the minimum number of oracle queries is constrained by the average rate at which each new query can reduce the algorithm’s uncertainty about the function being optimized.

$M\in\{0,\ldots,N-1\}$, which encodes the random choice of a problem instance in $\mathcal{F}^{\prime}$

$X^{T+1}\in\mathsf{X}^{T+1}$, where $X^{T}$ are the queries issued by $\mathcal{A}$ and $X_{T+1}$ is the candidate minimizer

$Y^{T}\in\mathsf{Y}^{T}$ are the responses of $\mathcal{O}$ to the queries issued by $\mathcal{A}$.

These variables describe the interaction between Nature, the algorithm, and the oracle, and thus have the causal ordering

for all $i\in\{0,\ldots,N-1\},A\in\mathcal{B}_{\mathsf{X}},B\in\mathcal{B}_{\mathsf{Y}}$. In other words, $M\to(X^{t-1},Y^{t-1})\to X_{t}$ and $(X^{t-1},Y^{t-1})\to(M,X_{t})\to Y_{t}$ are Markov chains for every $t$.

where the probability is w.r.t. the randomness in the oracle’s responses. Then, first of all,

In other words, a good algorithm should be able to obtain a nontrivial amount of information about the hypothesis $M$. On the other hand, by the data processing inequality, $I(M;\hat{M}_{T})\leq I(M;X^{T},Y^{T})$, and we will use statistical indistinguishability of $\{f_{i}\}$, as well as the structure of the oracle, to obtain an upper bound of the form

with some $\Psi_{2}(r,\varepsilon)<+\infty$. The two bounds are then combined to yield

To illustrate our method in action, we will sketch the derivation of the nontrivial part of the lower bound in (7), i.e., when $\varepsilon\in(0,1/2)$. Let

It is easy to see that $x^{*}_{0},x^{*}_{1}\in$. Consider two functions

A simple calculation shows that for any $x\in$ such that

we must have $f_{1}(x)-f^{*}_{1}=f_{1}(x)>\varepsilon$, and the same holds with the roles of $f_{0}$ and $f_{1}$ reversed. Thus, any $\varepsilon$-minimizer of $f_{0}$ fails to $\varepsilon$-minimize $f_{1}$, and vice versa.

Then it is not hard to show that, for $m\in\{0,1\}$,

In other words, the functions $f_{0}$ and $f_{1}$ are nearly indistinguishable from one another based on the outcome of a single query.

Now suppose that Nature selects an index $M\in\{0,1\}$ uniformly at random. Consider a $T$-step algorithm that $\varepsilon$-minimizes every function in the class $\mathcal{F}$ defined in (5) with probability at least $1-\delta$, where $\delta\in(0,1/2)$. Let $r=1$. Then Lemma 1 in Section IV-C can be used to show that the lower bound (14) holds with

where $h_{2}(\delta)\triangleq-\delta\log\delta-(1-\delta)\log(1-\delta)$ is the binary entropy function. On the other hand, using Lemmas 2 and 4, as well as Eq. (17), we can show that the upper bound (15) holds with

Hence, according to (16), any $T$-step algorithm that $\varepsilon$-minimizes every function in the class $\mathcal{F}$ of Eq. (5) with probability at least $1-\delta$ must satisfy

From this and from Proposition 1, we can obtain the lower bound $\Omega(\sigma^{2}/\varepsilon)$ of Eq. (7). The matching upper bound $O(\sigma^{2}/\varepsilon)$ is achieved by stochastic gradient descent .

IV-B Reduction to hypothesis testing with feedback

We now develop our information-theoretic methodology in the general setting of Section II-A.

Let us fix a problem class $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$. To set up our analysis, we first endow the instance space $\mathcal{F}$ with a “distance” $d(\cdot,\cdot)$ that has the following property: for any $x\in\mathsf{X}$ and any $\varepsilon>0$,

In other words, an $\varepsilon$-minimizer of a function cannot simultaneously be an $\varepsilon$-minimizer of a distant function. It is easy to construct a $d$ satisfying (18) for any particular class $\mathcal{F}$ of continuous functions, although such a $d$ need not be a metric. For example, if we consider the class

for some $\Theta\subset\mathsf{X}$, then $d(f_{\theta},f_{\theta^{\prime}})=\|\theta-\theta^{\prime}\|$ satisfies (18). Indeed, $\|\theta-\theta^{\prime}\|\geq 2\varepsilon$ and $\|x-\theta\|<\varepsilon$ imply $\|x-\theta^{\prime}\|>\varepsilon$ by the triangle inequality. For a general $\mathcal{F}$, we can also define

the distance-like function introduced in . This definition coincides with $d(f_{\theta},f_{\theta^{\prime}})=\|\theta-\theta^{\prime}\|$ for the parametric set $\mathcal{F}_{\Theta}$; however, (18) is the most general requirement. Note that we will often implicitly restrict our consideration to a subclass of $\mathcal{F}$ and define an appropriate $d$ on that subclass.

which simply selects that function in $\mathcal{F}^{\prime}$ for which the error of $X_{T+1}$ is the smallest. Since $X_{T+1}$ is $\sigma(X^{T},Y^{T})$-measurable, the estimator $\hat{M}_{T}$ is indeed a function only of the information available to $\mathcal{A}$ after time $T$.

IV-C Information bounds

The main object of interest will be the mutual information $I(M;\hat{M}_{T})$. We first show that any “good” $T$-step algorithm obtains a nonzero amount of information about $M$ at the end of its operation:

Fix some $r\geq 1$, $\delta\in(0,1/2)$, and $\varepsilon>0$. Suppose $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$ attains

Let $\mathcal{F}^{\prime}\subset\mathcal{F}$ be a finite set $\{f_{0},\ldots,f_{N-1}\}$ of functions, such that

Let $M$ be uniformly distributed on $\{0,1,\ldots,N-1\}$, and suppose that $\mathcal{A}$ is fed with the random problem instance $f_{M}\in\mathcal{F}^{\prime}$. If $N>4$, then the estimator $\hat{M}_{T}$ defined in (19) satisfies the bound

where $h_{2}(\delta)\triangleq-\delta\log\delta-(1-\delta)\log(1-\delta)$ is the binary entropy function.

In the sequel, we will consider only the cases when the set $\mathcal{F}^{\prime}$ is either “rich”, so that $N\gg 4$, or has only two elements, so $N=2$.

Consider an algorithm $\mathcal{A}$ with the claimed properties. Define, for each $i$, the event

We first show that the event $\{\hat{M}_{T}\neq i\}$ implies $E_{i}$. Indeed, if $E_{i}$ does not occur, then from the fact that $d(f_{i},f_{j})\geq 2\varepsilon^{1/r}$ for all $j\neq i$ and from (18) we deduce that

so it must be the case that $\hat{M}_{T}=i$. Therefore,

Now suppose that $N>4$. Then we can invoke the following version of Fano’s inequality :

Rearranging, we get (21). When $N=2$, we use a stronger form of Fano’s inequality (see, e.g., Section 2.10 in ):

Since $\delta\mapsto h_{2}(\delta)$ is monotone increasing on $[0,1/2]$, we get $h_{2}(\delta)\geq\log 2-I(M;\hat{M}_{T})$. Rearranging, we get (22). ∎

On the other hand, the amount of information $I(M;\hat{M}_{T})$ cannot be too large:

Any estimator $\hat{M}:\mathsf{X}^{T}\times\mathsf{Y}^{T}\to\{0,\ldots,N-1\}$ [and, in particular, the estimator $\hat{M}_{T}$ defined in (19)] satisfies

The terms $I(M;Y_{t}|X^{t},Y^{t-1})$ have analogues in the literature on information-theoretic experimental design (see, e.g., ). In that context, they represent the average reduction of uncertainty about the unknown variable $M$ after observing the experimental outcome $Y_{t}$ based on the design point $X_{t}=\mathcal{A}_{t}(X^{t-1},Y^{t-1})$.

where (24) is a consequence of the data processing inequality; (25) and (26) use the chain rule; and (27) uses the fact that $M\to(X^{t-1},Y^{t-1})\to X_{t}$ is a Markov chain. ∎

IV-D Refinement of the upper bounds

Lemmas 1 and 2 are the two main elements of our approach. In order to apply them, we need to get a handle on the conditional mutual information terms on the right-hand side of (23). The following two lemmas, whose proofs can be found in Appendix B, give us just the right tools for that:

Consider any estimator $\hat{M}:\mathsf{X}^{T}\times\mathsf{Y}^{T}\to\{0,\ldots,N-1\}$. Then, considering any realization of the oracle $\mathcal{O}$ in the form (8), we have the bound

where $U_{t}=\psi(f_{M},X_{t})$ is the output of the “deterministic part” of the oracle.

Lyapunov Function (LF) bound — This bound is useful for analyzing anytime algorithms. It relies on the idea that, with certain types of problem classes, the oracle responds with “pure noise” whenever the query point happens to hit upon a minimizer. In other words, there exists a probability measure $Q^{*}$ on $\mathsf{Y}$, such that

We apply the LF bounds in Section VI to the study of anytime algorithms.

(cf. [6, p. 1571]). Similarly, the “symmetrization trick” involving an independent copy of $M$ and an application of Jensen’s inequality, as in Eq. (30) above, is used often in the statistics literature (cf. and references therein). Our innovation consists in first performing a sequential decomposition of the mutual information $I(M;X^{T},Y^{T})$, carefully taking into account all the Markov structures that arise due to the causality constraints that must be obeyed by the algorithm, and then choosing an appropriate auxiliary measure for each time $t=1,\ldots,T$.

V Lower bounds for arbitrary algorithms

We now apply the lemmas of the preceding section to the problem of deriving lower bounds on the information-based complexity of several problem classes. These bounds hold for arbitrary finite-step or infinite-step algorithms.

Our first bound applies to any problem class. However, this generality comes at a price: the bound is nontrivial (i.e., tight) only in certain cases.

Consider a problem class $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$, with any realization of the oracle $\mathcal{O}$ in the form (8). Given any $\eta>0$, define the packing number

Then, for any $r\geq 1$, any $\varepsilon$ such that $N(\mathcal{F},d,\varepsilon^{1/r})>4$, and any $\delta\in(0,1/2)$, the following bounds hold:

where the supremum is over all random variables $U$ taking values in $\mathsf{U}_{\mathsf{X},\mathcal{F}}=\psi(\mathcal{F},\mathsf{X})$, and the mutual information is between $U$ and $Y=\Phi(U,W)$, cf. Eq. (8).

The number $C^{*}$ is the Shannon capacity of the random transformation $Y=\Phi(U,W)$ when its input is constrained to lie in the information space of the deterministic oracle $\psi$. When $C^{*}=\infty$, the bounds (33) and (34) simply say that $K^{(r)}_{\mathcal{P}}(\varepsilon,\delta)\geq 0$ and $K^{(r)}_{\mathcal{P}}(\varepsilon)\geq 0$.

Let $\mathcal{F}^{(r)}_{\varepsilon}=\{f_{0},\ldots,f_{N-1}\}\subset\mathcal{F}$, $N=N(\mathcal{F},d,\varepsilon^{1/r})$, be a maximal packing set in $\mathcal{F}$. Given $\delta\in(0,1/2)$, consider any $T$ and any algorithm $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$ such that $\Pr(\operatorname{err}^{r}_{\mathcal{A}}(T,f)\geq\varepsilon)\leq\delta$. Then we can apply Lemma 1 to get

On the other hand, from Lemma 3 and the definition of $C^{*}$,

Combining these two bounds, we get (33), while (34) follows after applying Proposition 1 with $\delta=1/3$. ∎

where $v_{n}=\operatorname{vol}(B^{n}_{2})$. Consider the subclass of $\mathcal{F}_{\rm Lip}$ consisting of all functions of the form $f_{\theta}(x)=\|x-\theta\|,\theta\in\Lambda_{\varepsilon}$. Then for any two distinct functions $f_{\theta},f_{\theta^{\prime}}$ we will have

so $N(\mathcal{F}_{\rm Lip},d,\varepsilon)\geq v^{-1}_{n}(1/\varepsilon)^{n}$. Theorem 1 then gives the following lower bound for any noisy oracle with $C^{*}<+\infty$:

For noiseless first-order oracles, the same lower bound follows from a binary search argument, and can be achieved using the (computationally infeasible) method of centers of gravity . In order to achieve this bound with a noisy oracle, an algorithm must pose queries that reduce the uncertainty by an amount that is independent of $\varepsilon$. This is possible with certain kinds of oracles .

V-B First-order oracles with Gaussian noise

If the oracle provides noisy first-order information, the above logarithmic lower bound can be tightened significantly. We now present lower bounds for two problem classes – convex Lipschitz functions (cf. Example 2) and strongly convex functions (cf. Example 3) – when the oracle supplies first-order information corrupted by additive white Gaussian noise. This is an oracle that, for a function $f$ and a query point $x$, responds with

We begin by particularizing the IR bound (31) to the oracles under consideration (the proof is given in Appendix B):

We can now address the complexity of minimizing Lipschitz convex functions over a compact domain (cf. Example 2):

Then for any $r\geq 1$, $\varepsilon\leq\left(s_{\mathsf{X}}\sqrt{n/8}\right)^{r}$, and $\delta\in(0,1/2)$, the following bounds hold:

By the Varshamov–Gilbert bound (see, e.g., Lemma 2.9 in ), there exists an $n/8$-packing of size $N>2^{n/8}\geq 4$ of the binary cube $\{-1,+1\}^{n}$ in the Hamming distance. In other words, there exists a subset $\{\xi_{0},\ldots,\xi_{N-1}\}$ of the vertices of $B^{n}_{\infty}$ with $N>2^{n/8}$, such that

Since \varepsilon\leq\big{(}s_{\mathsf{X}}\sqrt{n/8}\big{)}^{r} and $\{s_{\mathsf{X}}\xi_{i}\}^{N-1}_{i=0}\subset\mathsf{X}$, these functions lie in $\mathcal{F}_{\rm Lip}$, and each $f_{i}$ is uniquely minimized at $x^{*}_{i}=s_{\mathsf{X}}\xi_{i}$ with $f^{*}_{i}=0$. Moreover, upon defining

Next we will bound $I(M;\hat{M}_{T})$ from above. For any $x\in\mathsf{X}$ and any pair $i,j$, we have

Combining (39) and (40) and rearranging, we get (37). ∎

Upper bounds on stochastic gradient descent – an algorithm which only uses the subgradient information – for $r=1$ are of the form $O\left(G^{2}D^{2}_{\mathsf{X}}/\varepsilon^{2}\right)$, where $G^{2}$ is an upper bound on the expected squared norm of the noisy gradient . As we show below, this is matched by our lower bounds. Indeed, $G^{2}\propto n\sigma^{2}$ for the additive Gaussian noise with variance $\sigma^{2}$. For the unit sphere we thus obtain $\Omega(n\sigma^{2}/\varepsilon^{2})$; for the unit hypercube we obtain $\Omega\left(n^{2}\sigma^{2}/\varepsilon^{2}\right)$ for the SOG oracle:

Under the conditions of Theorem 2, we have

When the functions in $\mathcal{F}$ are strongly convex (cf. Example 3), rather than convex Lipschitz, the complexity of optimization will decrease:

Given $n$, construct the set $\{\xi_{0},\ldots,\xi_{N-1}\}\subset\{-1,+1\}^{n}$ as in the proof of Theorem 2 and define the functions

Since \varepsilon\leq\big{(}ns^{2}_{\mathsf{X}}/16)^{r},

Thus, the functions $f_{i}$ lie in $\mathcal{F}_{\rm SC}$, and each $f_{i}$ is uniquely minimized by $x^{*}_{i}$ with $f^{*}_{i}=0$. Moreover, upon defining

Now we will derive an upper bound on $I(M;\hat{M}_{T})$. For any $x\in\mathsf{X}$ and any pair $i,j$, we have

where the last step uses the definition of $D_{\mathsf{X}}$ and the triangle inequality. Thus,

Under the conditions of Theorem 3, we have

V-C Noisy oracles satisfying a moment bound

Our information-theoretic technique can be used to give a simpler derivation of the lower bounds obtained by Nemirovski and Yudin [1, Ch. 5] for Lipschitz convex functions and noisy first-order oracles satisfying a certain moment constraint.

(C2) There exist constants $\alpha>1,L>0$, such that

for all $f\in\mathcal{F},x\in\mathsf{X}$.

We will denote the class of all such oracles by $\Pi(\alpha,L)$.

There exists an oracle $\mathcal{O}\in\Pi(\alpha,L)$, such that the corresponding problem class $\mathcal{P}=(\mathsf{X},\mathcal{F}_{\rm Lip},\mathcal{O})$ satisfies

for all $\varepsilon\in(0,\min\{L/2^{1/\alpha},1\}),\delta\in(0,1/2)$ with some $c=c(\alpha,L)>0$.

It is an easy exercise to show that this oracle belongs to $\Pi(\alpha,L)$; moreover, on the set $\{f_{0},f_{1}\}$ this oracle can be realized in the form (8) with $\psi(f_{i},x)=(f_{i}(x),\nabla f_{i}(x))$, $i\in\{0,1\}$.

Consider an algorithm $\mathcal{A}$ that achieves (20) with $r=1$. Let $U_{t}=\psi(f_{M},X_{t})$. Then $I(U_{t};Y_{t}|X^{t},Y^{t-1})\leq I(U_{t};Y_{t}|X_{t})$ because $(X^{t},Y^{t-1})\to U_{t}\to Y_{t}$ is a Markov chain. Now, given $X_{t}=x_{t}$, $U_{t}$ can take only two values, namely $(-\xi^{\scriptscriptstyle\mathsf{T}}x_{t},-\xi)$ or $(\xi^{\scriptscriptstyle\mathsf{T}}x_{t},\xi)$. Thus, $H(U_{t}|X_{t})\leq\log 2$. Moreover, since the mutual information $I(A;B|C)$ is convex in $P_{B|A,C}$, we have

Summing over the $T$ rounds and using Lemma 2, we get

From Lemma 1, we have $I(M;\hat{M}_{T})\geq\log 2-h_{2}(\delta)$. Combining these bounds and rearranging, we get (43). ∎

The statement of Theorem 4 should be interpreted in the following sense (cf. also ): given $\mathsf{X}$ and $\mathcal{F}$ as above,

Thus, we have a lower bound which is robust relative to $\Pi(\alpha,L)$. However, this bound is sharp only for $\alpha\in(1,2]$ : for $\alpha\geq 2$, the correct bound is $\Omega(1/\varepsilon^{2})$. This can be easily seen from the results of the preceding section on the Gaussian first-order oracle.

V-D Statistical estimation and sequential experimental design

Finally, let us see how the problems of parametric statistical estimation (Example 4) and experimental design (Example 5) can be viewed through the lens of optimization.

Let us consider statistical estimation first. We will use the notation of Example 4. Typically, one considers the setting in which the statistician gets $T$ i.i.d. samples $Y_{1},\ldots,Y_{T}$ drawn from some $P_{\theta}$, where $\theta$ is unknown. The quantity of interest is the minimax risk

where the infimum is over all measurable estimators $\hat{\theta}_{T}:\mathsf{Y}^{T}\to\mathsf{X}$, and $f_{\theta}$ is an element of an appropriate class $\mathcal{F}$ of loss functions, such as (10) or (12).

Now, the output of any such estimator can be viewed as the final result of some algorithm $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$. Thus, we simply follow our general recipe and isolate a finite subset $\mathcal{F}^{\prime}=\{f_{\theta_{0}},\ldots,f_{\theta_{N-1}}\}$ such that, with a suitably defined “distance” $d(\cdot,\cdot)$ that satisfies (18), we have

Suppose that we can arrange things in such a way that the cardinality of such an $\mathcal{F}^{\prime}$ is independent of $\varepsilon$, but may still depend on $n$ and $r$: $N=N(r,n)$ (this is possible in many cases, cf. the proofs of Theorems 2 and 3). Then we simply apply the IR bound to get

for some $C(r,n)>0,\gamma>0$, we can invert (44) and obtain the minimax lower bound

Similar considerations apply to sequential experimental design as well (Example 5), except there we have a design strategy $\{\hat{X}_{t}:\mathsf{Y}^{t-1}\to\mathsf{X}\}^{T}_{t=1}$ and the estimator $\hat{\theta}_{T}:\mathsf{Y}^{T}\to\mathsf{X}$, where at time $t=1,\ldots,T$ we choose the design point $X_{t}=\hat{X}_{t}(Y^{t-1})$ and obtain a sample $Y_{t}\sim P_{\theta,X_{t}}$, and then at time $T+1$ we process all the samples to get the estimate $X_{T+1}=\hat{\theta}_{T}(Y^{T})$. The minimax risk is then

The connection to optimization is even more apparent than in the estimation setting, and the IR bound technique yields

Just as before, this bound can be inverted to get a lower bound on the minimax risk. Note, however, that what we have is a lower bound on the number of the design points needed to guarantee that the minimax risk is below $\varepsilon$.

VI Lower bounds for anytime algorithms

Conceptually, our use of the IR bounds is akin to the methods used in statistics to obtain minimax lower bounds through local entropy estimates and a device like the Assouad lemma (cf. and references therein). In both cases, in order to get the right rates it is essential to arrange things so that the size of the “packing” set $\mathcal{F}^{\prime}$ is independent of $\varepsilon$. However, one drawback of the IR bounds is that they do not take into account the dynamics of the algorithm, pertaining to the manner in which its expected error evolves with time. Instead, we must use uniform, worst-case bounds on the uncertainty remaining after each successive oracle call. However, it could be argued on practical grounds that the only optimization algorithms that are of any value are the ones whose performance gradually and monotonically improves with time, as more and more queries are issued — that is, anytime algorithms. In this section, we show that the LF bounds can be used to track the evolution of the mutual information over time. As a consequence, we will be able to derive upper bounds on the anytime exponent for certain problem classes.

We will show that the amount of information extracted by an anytime algorithm at each time step obeys a law of diminishing returns: as the queries $X_{t}$ approach the minimizer, the rate at which the algorithm can reduce its uncertainty about the objective function slows down. Moreover, assuming that the worst-case expected error of such an algorithm decays polynomially with time, we will obtain lower bounds on the rate of this decay. We will also show that, in some cases, insisting on the anytime property may mean that the algorithm will take longer to get to the point after which its expected error drops below some desired level. This seemingly strange conclusion reflects the fact that, without placing any restrictions on the algorithm’s trajectory, we are allowing “bizarre” (and not very practical) strategies that wander around the problem domain for a while, gathering information without much regard to how close they are to a minimizer, and then — boom! — produce an excellent solution. With such algorithms, it is certainly no surprise that they may hit upon a good solution more quickly than an “honest” anytime algorithm that must proceed incrementally and inexorably towards a minimizer.

In contrast to the local technique based on the IR bounds, our use of the LF bounds in this section can be thought of as a global technique . The main idea is as follows. Suppose we have an anytime algorithm whose worst-case expected errors decay at some rate $\varepsilon_{t}\to 0$. Then, for each $T$, we consider an $\varepsilon_{T}$-packing of the problem domain (with respect to a suitable metric, typically just the usual Euclidean norm $\|\cdot\|$), which will induce a packing of the function class $\mathcal{F}$. This packing will be of size $\Omega(\varepsilon^{-n}_{T})$. Since the algorithm does well on every single function in $\mathcal{F}$, it must necessarily do well on every function in this large packing set. Thus, if the objective function is drawn uniformly at random from this set, then combining the lower bound of Lemma 1 with the LF upper bound will result in a relation of the form

where $\gamma>0$ depends on the smoothness of the functions in $\mathcal{F}$. This relation must hold for all but finitely many values of $T$. The optimal rate is then derived by balancing the entropy $n\log\varepsilon^{-1}_{T}$ and the sum of diminishing mutual information terms.

Each $f\in\mathcal{F}_{\kappa,L}$ is $\kappa$-strongly convex (cf. Example 3).

For each $f$, the mapping $x\mapsto\nabla f(x)$ is $L$-Lipschitz:

Consider the noisy first-order oracle $Y=(f(x)+W,\nabla f(x)+Z)$ as in (35). Let $\{f_{0},\ldots,f_{N-1}\}\subset\mathcal{F}_{\kappa,L}$ be a finite set of functions such that $f^{*}_{0}=\ldots=f^{*}_{N-1}=c^{*}$ and $\nabla f_{i}(x^{*}_{i})=0$, where $x^{*}_{i}$ is the (unique) minimizer of $f_{i}$ on $\mathsf{X}$. Let $M$ denote the uniform random variable on $\{0,\ldots,N-1\}$. Then we have the following (the proof is in Appendix B):

At every time $t=1,2,\ldots$, any algorithm $\mathcal{A}\in\mathfrak{A}_{\infty}(\mathcal{P})$ satisfies

Moreover, if $\mathcal{A}$ is $1$-anytime (cf. Definition 6), then

Thus, the decay of the expected error in minimizing a strongly convex function is accompanied by the decay of the average information gain, and, moreover, the two quantities decay at the same rate. In other words, anytime algorithms for strongly convex programming obey a law of diminishing returns. Evidently, this phenomenon is due to the fact that, as the algorithm zeroes in on the minimizer, the signal-to-noise ratio keeps dropping because the mean-square error and the mean-square norm of the gradient both decrease as $O(\varepsilon_{t})$. Using Lemma 6 in conjunction with the information bounds of Section V, we establish the following upper bound on the anytime exponent of strongly convex programming problems:

Consider the problem class $\mathcal{P}=(\mathsf{X},\mathcal{F},\mathcal{O})$ with $\mathsf{X}=B^{n}_{\infty}$, $\mathcal{F}=\mathcal{F}_{\kappa,L}$ with $\kappa=1$ and $L\geq 1$, and the Gaussian first-order oracle (35). Then $\gamma_{\mathcal{P}}\leq 1$. In other words, on this problem class, $O(t^{-1})$ is the optimal error decay rate for all $1$-anytime algorithms whose errors decay polynomially with $t$.

Consider any algorithm $\mathcal{A}\in\mathfrak{A}_{\infty}(\mathcal{P})$ whose worst-case errors $\varepsilon_{t}\triangleq\overline{\operatorname{err}}_{\mathcal{A}}(t,\mathcal{F})$ satisfy

for some $\gamma\geq 0$. In other words, $\varepsilon_{t}=O(t^{-\gamma})$. By Markov’s inequality, we have, for every $T,$

Let us fix some $T$, let $\Lambda_{T}=\{\theta_{0},\ldots,\theta_{N-1}\}$ denote a maximal $2\sqrt{3\varepsilon_{T}}$-packing set in $\mathsf{X}$ (w.r.t. $\|\cdot\|$), and define

By volume counting, $N\geq v^{-1}_{n}(1/3\varepsilon_{T})^{n/2}$. We also have $d(f_{i},f_{j})=\frac{1}{2}\|\theta_{i}-\theta_{j}\|^{2}\geq 6\varepsilon_{T}$. By Lemma 1,

where $c_{n}=\frac{1}{3}\log\left(\frac{1}{3^{n}8v^{2}_{n}}\right)$. On the other hand, applying Lemma 6, we obtain

Combining (47) and (48), we see that the sequence $\{\varepsilon_{t}\}$ must satisfy the following inequalities:

where $c^{\prime}_{n}=\sigma^{2}c_{n}/(n+1)$. From Lemma C.1 we therefore conclude that there exists an infinite subsequence of times $1\leq t_{1}<t_{2}<\ldots$, such that $\varepsilon_{t_{j}}\geq ct^{-1}_{j}$ for some $c>0$. Since $\varepsilon_{t}=O(t^{-\gamma})$ by hypothesis, we must have $\gamma\leq 1$. ∎

The bound $\Omega(t^{-1})$ is tight and can be achieved by stochastic gradient descent . Note that the methods of Section V can be used to explicitly identify the dependence of the lower bound on the problem dimension $n$.

VI-B Comparison of IR and LF bounds

A natural question is whether LF bounds for anytime algorithms provide tighter lower bounds when compared to IR bounds without the anytime assumption. This is indeed the case, as we demonstrate through an example. Interestingly, the difference is not present for linear and quadratic functions, but appears for higher degree polynomials. Consider a simple set-up with $\mathsf{X}=$,

where $W,Z$ are mutually independent ${\mathcal{N}}(0,\sigma^{2})$ random variables.

On this problem class, for any $\varepsilon\leq 1$ and any $\delta\in(0,1/2)$ we have

By convexity of $x\mapsto x^{m}$ (recall that $m$ is even), we have for any $x,\theta,\theta^{\prime}\in\mathsf{X}$

Hence, the $d(\cdot,\cdot)$ defined in (50) satisfies (18). In particular, if we fix the functions

then $d(f_{0},f_{1})=2\varepsilon^{1/2}$. Let $M$ have uniform distribution on $\{0,1\}$. Consider now any algorithm $\mathcal{A}\in\mathfrak{A}_{T}(\mathcal{P})$ that attains $\operatorname{err}^{2}_{\mathcal{A}}(T,f_{\theta})<\varepsilon$ with probability at least $1-\delta$ for every $\theta\in\mathsf{X}$. Applying Lemma 1, we obtain

Likewise, applying the mean-value theorem to the function $x\mapsto x^{m-1}$, we get

Combining (51) and (52), we obtain (49). ∎

Consider the same problem class. Then $\gamma^{(2)}_{\mathcal{P}}\leq\frac{m}{m-1}$.

As before, consider any algorithm $\mathcal{A}\in\mathfrak{A}_{\infty}(\mathcal{P})$ whose worst-case errors $\varepsilon_{t}\triangleq\overline{\operatorname{err}}^{(2)}_{\mathcal{A}}(t,\mathcal{F})$ satisfy

for some $\gamma\geq 0$. Applying the same argument based on Markov’s inequality as in the proof of Theorem 5, we see that, for any $T$, $\mathcal{A}$ attains $\operatorname{err}^{2}_{\mathcal{A}}(T,f_{\theta})<3\varepsilon_{T}$ with probability at least $2/3$ on every $f_{\theta}\in\mathcal{F}$. Given $T$, let $\Lambda_{T}=\{\theta_{0},\ldots,\theta_{N-1}\}$ denote the largest finite subset of $\mathsf{X}=$, such that

A simple counting argument shows that $N\geq\left(\frac{1}{3\varepsilon_{T}}\right)^{1/2m}$. Moreover, the functions $f_{i}(x)\triangleq(x-\theta_{i})^{m},i=0,\ldots,N-1$, satisfy $d(f_{i},f_{j})\geq 2\sqrt{3\varepsilon_{T}}$ for $i\neq j$, where $d(\cdot,\cdot)$ is defined in (50).

where $c_{m}=\frac{1}{3}\log\left(\frac{1}{3^{1/m}8}\right)$. We will now combine this lower bound with an appropriate LF bound. Let $Q^{*}$ denote the bivariate normal distribution ${\mathcal{N}}(0,\sigma^{2}I_{2})$. Then, for every $i=0,\ldots,N-1$ we have

where in (53) we have used the concavity of the function $u\mapsto u^{(m-1)/m}$. Therefore, we conclude that the sequence $\{\varepsilon_{t}\}$ must satisfy

for all sufficiently large $T$. Applying Lemma C.1, we conclude that there exists an infinite subsequence of times $t_{1}<t_{2}<\ldots$, such that $\varepsilon_{t_{j}}\geq ct^{-m/(m-1)}_{j}$ for some constant $c>0$. Since $\varepsilon_{t}=O(t^{-\gamma})$ by hypothesis, we must have $\gamma\leq\frac{m}{m-1}$. ∎

For $m=2$, the two results indicate the same order of complexity, $T\succeq\varepsilon^{-1/2}$; however, for $m=4$ and larger, the bounds differ, giving $T\succeq\varepsilon^{-1/m}$ for arbitrary algorithms and $T\succeq\varepsilon^{(1-m)/m}$ for anytime algorithms, which is larger. We conclude that, in general, the LF bounding technique leads to tighter bounds for optimization algorithms which actually converge monotonically to the optimal solution.

VI-C Active learning

Our technique for analyzing anytime optimization algorithms can also be used to give a particularly simple derivation of the minimax lower bound for active learning of a threshold function on the unit interval . In general, active learning is more difficult than (convex) optimization. However, for the case below, we can apply the tools developed in this paper. The reason for including this example is twofold: first, to show that problems beyond convex optimization can be attacked with our information-theoretic method, and second to exhibit a problem with a noise model more complicated than those encountered so far in the paper.

There exists some $\theta\in$, such that $\eta(x)<1/2$ for $x<\theta$ and $\eta(x)\geq 1/2$ otherwise. In other words, the Bayes classifier $G^{*}(x)\triangleq{\bf 1}_{\{\eta(x)\geq 1/2\}}$ for this problem is of the form $G^{*}(x)=G_{\theta}(x)={\bf 1}_{\{x\geq\theta\}}$.

For some $0<c<C<1/2$ and $\kappa\in[1,\infty)$, we have

where the first inequality (known as the Tsybakov noise condition ) holds for all $x$ in a sufficiently small neighborhood of $\theta$.

Let $\Pi(\kappa,c,C)$ denote the class of all conditional probability distributions $P_{Z|X}$ satisfying these two conditions. We wish to determine the unknown threshold $\theta$ using an active strategy: at time $t$, we request a label $Z_{t}\in\{0,1\}$ at a point $X_{t}\in\mathsf{X}$, chosen as a function of the history $(X^{t-1},Z^{t-1})$. Given our query $X_{t}$, the label $Z_{t}$ is generated at random according to $P_{Z|X}(\cdot|X_{t})$. At time $t$, the candidate classifier is $G_{X_{t}}(x)={\bf 1}_{\{x\geq X_{t}\}}$. The performance of the strategy after $t$ time steps is measured by the excess risk relative to $G^{*}$:

where $\triangle$ denotes symmetric difference between sets. (The risk of a classifier $G:\mathsf{X}\to\{0,1\}$ is defined as $R(G)\triangleq\Pr(G(X)\neq Z)$, and the Bayes risk is $R(G^{*})\triangleq\inf_{G}R(G)$ .)

Castro and Nowak have shown that any active strategy will have excess risks of $\Omega(t^{-\kappa/(2\kappa-2)})$, and gave an explicit scheme that achieves the rate $O(t^{-\kappa/(2\kappa-2)})$. Their proof of the lower bound relies on an intricate construction of two distributions $P^{(1)}_{Z|X},P^{(2)}_{Z|X}\in\Pi(\kappa,c,C)$ that are close in a statistical sense, but far apart in the sense of their Bayes risks. We now show that the same lower bound can be derived using our machinery without any careful function tuning. To that end, we will cast this problem in the optimization setting, as alluded to in Example 6. Let $\mathsf{X}$ and $\mathcal{F}$ be as described there, and associate to each $P_{Z|X}\in\Pi(\kappa,c,C)$ a noisy oracle with $\mathsf{Y}=\{-1,+1\}$ and $P(Y=1|f,x)=P(Y=1|\theta,x)=\eta(x)$. With this correspondence in place, we can now prove the following: