Computational and Statistical Tradeoffs via Convex Relaxation

Introduction

The rapid growth in the size and scope of datasets in science and technology has created a need for novel foundational perspectives on data analysis that blend computer science and statistics. That classical perspectives from these fields are not adequate to address emerging problems in ‘‘Big Data’’ is apparent from their sharply divergent nature at an elementary level---in computer science, the growth of the number of data points is a source of ‘‘complexity’’ that must be tamed via algorithms or hardware, whereas in statistics, the growth of the number of data points is a source of ‘‘simplicity’’ in that inferences are generally stronger and asymptotic results can be invoked. In classical statistics, where one considers the increase in inferential accuracy as the number of data points grows, there is little or no consideration of computational complexity. Indeed, if one imposes the additional constraint---prevalent in real-world applications---that a certain level of inferential accuracy be achieved within a limited time budget, classical theory provides no guidance as to how to design an inferential strategy. Note that classical statistics contains a branch known as sequential analysis that does discuss methods that stop collecting data points after a target error level has been reached (see, e.g., ), but this is different from the computational complexity guarantees (the number of steps that a computational procedure requires) that are our focus. In classical computer science, practical solutions to large-scale problems are often framed in terms of approximations to idealized problems, but even when such approximations are sought, they are rarely expressed in terms of the coin of the realm of the theory of inference—the statistical risk function. Thus there is little or no consideration of the idea that computation can be simplified in large datasets because of the enhanced inferential power in the data. In general, in computer science, datasets are not viewed formally as a resource on a par with time and space (such that the more of the resource the better).

On intuitive grounds it is not implausible that strategies can be designed that yield monotonically improving risk as data accumulate, even in the face of a time budget. In particular, if an algorithm simply ignores all future data once a time budget is exhausted, then statistical risk will not increase (under various assumptions that may not be desirable in practical applications). Alternatively, one might allow linear growth in the time budget (for example, in a real-time setting), and attempt to achieve such growth via a subsampling strategy where some fraction of the data are dropped. Executing such a strategy may be difficult, however, in that the appropriate fraction depends on the risk function and thus on a mathematical analysis that may be difficult to carry out. Moreover, subsampling is a limited strategy for controlling computational complexity. More generally, one would like to consider some notion of “algorithm weakening,” where as data accumulate one can back off to simpler algorithmic strategies that nonetheless achieve a desired risk. The challenge is to do this in a theoretically sound manner.

To develop a notion of “algorithm weakening” that combines computational and statistical considerations, we consider estimation procedures for which we can characterize the computational benefits as well as the loss in estimation performance due to the use of weaker algorithms. Reflecting the fact that the space of all algorithms is poorly understood, we retain the focus on convex optimization from high-dimensional statistics, but we consider parameterized hierarchies of optimization procedures in which a form of algorithm weakening is obtained by employing successively weaker outer approximations to convex sets. Such convex relaxations have been widely used to give efficient approximation algorithms for intractable problems in computer science . As we will discuss, a precise characterization of both the estimation performance and the computational complexity of employing a particular relaxation of a convex set can be obtained by appealing to convex geometry and to results on the complexity of solving convex programs. Specifically, the tighter relaxations in these families offer better approximation quality (and in our context better estimation performance) but such relaxations are computationally more complex. On the other hand the weaker relaxations are computationally more tractable, and they can provide the same estimation performance as the tighter ones but with access to more data. In this manner, convex relaxations provide a principled mechanism to weaken inference algorithms in order to reduce the runtime in processing larger datasets.

To demonstrate explicit tradeoffs in high-dimensional, large-scale inference, we focus for simplicity and concreteness on estimation in sequence models :

In order to estimate $\mathbf{x}^{\ast}$, we consider the following natural shrinkage estimator given by a projection of the sample mean $\bar{\mathbf{y}}$ onto a convex set $\mathcal{C}$ that is an outer approximation to $\mathcal{S}$, i.e., $\mathcal{S}\subset\mathcal{C}$:

We study the estimation performance of a family of shrinkage estimators $\{\hat{\mathbf{x}}_{n}(\mathcal{C}_{i})\}$ that employ as the convex constraint one of a sequence of convex outer approximations $\{\mathcal{C}_{i}\}$ with $\mathcal{C}_{1}\supset\mathcal{C}_{2}\supset\cdots\supset\mathcal{S}$. Given the same number of samples, using a weaker relaxation such as $\mathcal{C}_{1}$ leads to an estimator with a larger risk than would result from using a tighter relaxation such as $\mathcal{C}_{2}$. On the other hand, given access to more data samples the weaker approximations provide the same estimation guarantees as the tighter ones. In settings in which computing a weaker approximation is more tractable than computing a tighter one, a natural computation/sample tradeoff arises. We characterize this tradeoff in a number of stylized examples, motivated by problems such as collaborative filtering, learning an ordering of a collection of random variables, and inference in networks.

More broadly, this paper highlights the role of computation in estimation by jointly studying both the computational and the statistical aspects of high-dimensional inference. Such an understanding is particularly of interest in modern inferential tasks in data-rich settings. Further, an observation from our examples on time-data tradeoffs is that in many contexts one does not need too many extra data samples in order to go from a computationally inefficient estimator based on a tight relaxation to an extremely efficient estimator based on a weaker relaxation. Consequently, in application domains in which obtaining more data is not too expensive it may be preferable to acquire more data with the upshot being that the computational infrastructure can be relatively less sophisticated.

We should note that we investigate only one algorithm weakening mechanism, namely convex relaxation, and one class of statistical estimation problems, namely denoising in a high-dimensional sequence model. There is reason to believe, however, that the principles described in this paper are relevant more generally. Convex-optimization-based procedures are employed in a variety of large-scale data analysis tasks , and it is likely to be interesting to explore hierarchies of convex relaxations in such tasks. In addition, there are a number of potentially interesting mechanisms beyond convex relaxation for weakening inference procedures such as dimensionality reduction or other forms of data quantization, and approaches based on clustering or coresets. We discuss these and other research directions in the Conclusions.

A number of papers have considered computational and sample complexity tradeoffs in the setting of learning binary classifiers. Specifically, several authors have described settings under which speedups in running time of a classifier learning algorithm are possible given a substantial increase in dataset size . In contrast, in the denoising setup considered in this paper, several of our examples of time-data tradeoffs demonstrate significant computational speedups with just a constant factor increase in dataset size. Another attempt in the binary classifier learning setting, building on earlier work on classifier learning in data-rich problems , has shown that modest improvements in runtime (of constant factors) may be possible with access to more data by employing the stochastic gradient descent method . Time-data tradeoffs have also been characterized in Boolean network training from time series data , but the computational speedups offered there are from exponential-time algorithms to slightly faster but still exponential-time algorithms. Two recent papers have considered time-data tradeoffs in sparse principal component analysis (PCA) and in biclustering, in which a sparse rank-one matrix is corrupted by noise and the objective is to recover the support of the matrix. We also study time-data tradeoffs in the estimation of a sparse rank-one matrix, but from a denoising perspective. In our discussion of Example 3 below we discuss the differences between our problem setup and these latter two papers. As a general contrast to all these previous results, a major contribution of the present paper is the demonstration of the efficacy of convex relaxation as a powerful algorithm weakening mechanism for processing massive datasets in a broad range of settings.

Paper outline

The main sections of this paper proceed in the following sequence. The next section describes a framework for formally stating results on time-data tradeoffs. Then we provide some background on convex optimization and relaxations of convex sets. Following this we investigate in detail the denoising problem (1), and characterize the risk obtained when one employs a convex programming estimator of the type (2). Subsequently, we give several examples of time-data tradeoffs in concrete denoising problems. Finally, we conclude with a discussion of directions for further research.

Formally Stating Time-Data Tradeoffs

One can informally view an estimation algorithm that achieves a risk of $\epsilon(p)$ by processing $n(p)$ samples with runtime $t(p)$ as a point on a two-dimensional plot such as Figure 1, with one axis representing the runtime and the other representing the sample complexity. To be precise the axes in the plot index functions (of $p$) that represent runtime and number of samples, but we do not emphasize such formalities and rather use these plots to provide a useful qualitative comparison of inference algorithms. In Figure 1, procedure A requires fewer samples than procedure C to achieve the same error, but this reduction in sample complexity comes at the expense of a larger runtime. Procedure B has both a larger sample complexity and a larger runtime than procedure C, and thus it is strictly dominated by procedure C.

Given an error function $\epsilon(p)$, there is a lower bound on the number of samples $n(p)$ required to achieve this error using any computational procedure (i.e., no constraints on $t(p)$)—such information-theoretic or minimax risk lower bounds correspond to “vertical lines” in the plot in Figure 1. Characterizing these fundamental limits on sample complexity has been a traditional focus in the estimation theory literature with a fairly complete set of results available in many settings. One can imagine asking for similar lower bounds on the computational side, corresponding to “horizontal” lines in the plot in Figure 1—given a desired risk $\epsilon(p)$ and access to an unbounded number of samples, what is a non-trivial lower bound on the runtime $t(p)$ of any inference algorithm that achieves a risk of $\epsilon(p)$? Such complexity-theoretic lower bounds are significantly harder to obtain, and they remain a central open problem in computational complexity theory.

This research landscape informs the qualitative nature of the statements on time-data tradeoffs we make in this paper. First, we will not attempt to prove combined lower bounds—as is traditionally done in the characterization of tradeoffs between physical quantities—involving $n(p)$ and $t(p)$ jointly; this is because obtaining a lower bound just on $t(p)$ remains a substantial challenge. Hence, our time-data tradeoff results on the use of more efficient algorithms for larger datasets refer to a reduction in the upper bounds on runtimes of estimation procedures with increases in dataset size. Second, in any setting in which there is a computational cost associated with touching each data sample and in which the samples are exchangeable, there is a sample threshold beyond which it is computationally more efficient to throw away excess data samples than to process them in any form. This observation suggests that there is a “floor,” as in Figure 1 with procedures $E,F,G$ and $H$, beyond which additional data do not lead to a reduction in runtime. Precisely characterizing this sample threshold is in general very hard as it depends on difficult-to-obtain computational lower bounds for estimation tasks and also on the particular space of estimation algorithms that one may employ. We will comment further on this point when we consider concrete examples of time-data tradeoffs.

In order to formally state our results concerning time-data tradeoffs, we define a resource class constrained by runtime and sample complexity as follows.

Convex Relaxation

In this section we describe the particular algorithmic toolbox on which we focus, namely convex programs. Convex optimization methods offer a powerful framework for statistical inference due to the broad class of estimators that can be effectively modeled as convex programs. Further the theory of convex analysis is useful both for characterizing the statistical properties of convex programming based estimators as well as for developing methods to compute such estimators efficiently. Most importantly from our viewpoint, convex optimization methods provide a principled and general framework for algorithm weakening based on relaxations of convex sets. We briefly discuss the key ideas from this literature that are relevant to this paper in this section. A central notion to the geometric viewpoint adopted in this section is that of a convex cone, which is a convex set that is closed under nonnegative linear combinations.

Convex programs refer to a class of optimization problems in which we seek to minimize a convex function over a convex constraint set . For example linear programming and semidefinite programming are two prominent subclasses in which linear functions are minimized over constraint sets given by affine spaces intersecting the nonnegative orthant (in linear programming) and the positive semidefinite cone (in semidefinite programming). Roughly speaking convex programs are tractable to solve computationally if the convex objective function can be computed efficiently, and if membership in the convex constraint sets can be certified efficiently More precisely, one requires an efficient separation oracle that responds YES if the point is in the convex set, and otherwise provides a hyperplane that separates the point from the convex set.; we will informally refer to this latter operation as computing the convex constraint set. It is then clear that the main computational bottleneck associated with solving convex programs of the form (2) is the efficiency of computing the constraint sets.

Such a representation of $\mathcal{C}$ is called a $\mathcal{K}$-representation.

Informally, if $\mathcal{K}$ is the nonnegative orthant (or the semidefinite cone) we will refer to the resulting representations as LP representations (or SDP representations), following commonly used terminology in the literature. A virtue of conic representations of convex sets based on the orthant or the semidefinite cone is that these representations lead to a numerical recipe for solving convex optimization problems of the form (2) via a natural associated barrier penalty . The computational complexity of these procedures is polynomial in the dimension of the cone and we discuss runtimes for specific instances in our discussion of concrete examples of time-data tradeoffs.

The $p$-dimensional simplex is an example of an LP representable set:

The elliptope, or the set of correlation matrices, in the space of $m\times m$ symmetric matrices is defined as follows:

Hierarchies of Convex Relaxations

In many cases of interest, convex sets may not have tractable representations. Lifted representations in such cases have lifting dimensions that are super-polynomially large in the dimension of the original convex set, and thus the associated numerical techniques lead to intractable computational procedures that have super-polynomial runtime with respect to the dimension of the original set. A prominent example of a convex set that is difficult to compute is the cut polytope:

Rank-one signed matrices and their convex combinations are of interest in collaborative filtering and clustering problems (see the section on time-data tradeoffs). There is no known tractable representation of the cut polytope—lifted linear or semidefinite representations have lifting dimensions that are super-polynomial in size. Such computational issues have led to a large literature on approximating intractable convex sets by tractable ones. For the purposes of this paper, and following the dominant trend in the literature, we focus on outer approximations. For example, the elliptope (5) is an outer relaxation of the cut polytope, and it has been employed in approximation algorithms for intractable combinatorial optimization problems such as finding the maximum-weight cut in a graph . More generally, one can imagine a hierarchy of increasingly tighter approximations $\{\mathcal{C}_{i}\}$ of a convex set $\mathcal{C}$ as follows:

There exist several mechanisms for deriving such hierarchies, and we describe three frameworks here.

These outer conic approximations are obtained by taking certain derivatives of the hyperbolic polynomial used to define the original cone $\mathcal{K}$—see for more details. One then constructs a hierarchy of approximations $\{\mathcal{C}_{i}\}$ to $\mathcal{C}$ by replacing the cone $\mathcal{K}$ in the representation of $\mathcal{C}$ by the family of conic approximations $\{\mathcal{K}_{i}\}$. From (3) and (7) it is clear that the $\{\mathcal{C}_{i}\}$ so defined satisfy $\mathcal{C}\subseteq\cdots\subseteq\mathcal{C}_{3}\subseteq\mathcal{C}_{2}\subseteq\mathcal{C}_{1}$.

The important point in these three frameworks is that the family of approximations $\{\mathcal{C}_{i}\}$ obtained in each case is ordered both by approximation quality as well as by computational complexity; that is, the weaker approximations in the hierarchy are also the ones that are more tractable to compute. This observation leads to an algorithm weakening mechanism that is useful for processing larger datasets more coarsely. As demonstrated concretely in the next section, the estimator (2) based on a weaker approximation to $\mathcal{C}$ can provide the same statistical performance as one based on a stronger approximation to $\mathcal{C}$ provided the former estimator is evaluated with more data. The upshot is that the first estimator is more tractable to compute than the second. Thus, we obtain a technique for reducing the runtime required to process a larger dataset.

Estimation via Convex Optimization

In this section we investigate the statistical properties of the estimator (2) for the denoising problem (1). The signal set $\mathcal{S}$ in (1) differs based on the application of interest. For example $\mathcal{S}$ may be the set of sparse vectors in a fixed basis, which could correspond to the problem of denoising sparse vectors in wavelet bases . The signal set $\mathcal{S}$ may be the set of low-rank matrices, which leads to problems of collaborative filtering . Finally, $\mathcal{S}$ may be a set of permutation matrices corresponding to rankings over a collection of items. Our analysis in this section is general, and is applicable to these and other settings (see the section on time-data tradeoffs for concrete examples). In some denoising problems, one is interested in noise models other than Gaussian. We comment on the performance of the estimator (2) in settings with non-Gaussian noise, although we primarily focus on the Gaussian case for simplicity.

The normal cone $N_{\mathcal{C}}(\mathbf{a})$ at $\mathbf{a}$ with respect to the convex set $\mathcal{C}$ is the polar cone of the tangent cone $T_{\mathcal{C}}(\mathbf{a})$:

Thus, the normal cone consists of vectors that form an obtuse angle with every vector in the tangent cone $T_{\mathcal{C}}(\mathbf{x})$. Both the tangent and normal cones are convex cones.

A key quantity that will appear in our error bounds is the following notion of the “complexity” or “size” of a tangent cone:

where the expectation is with respect to $\mathbf{g}\sim\mathcal{N}(0,I_{p\times p})$.

This quantity is closely related to the Gaussian complexity of a set which consists of no squaring of the term inside the expectation. The Gaussian squared-complexity shares many properties in common with the Gaussian complexity, and we describe those that are relevant to this paper in the next subsection. Specifically, we discuss methods to estimate this quantity for sets $\mathcal{D}$ that have some structure.

Note that the basic structure of the error bound provided by the estimator (2) in fact holds for an arbitrary distribution on the noise $\mathbf{z}$ with the Gaussian squared-complexity suitably modified. However, we focus for the rest of this paper on the Gaussian case, $\mathbf{z}\sim\mathcal{N}(0,I_{p\times p})$.

Properties and Computation of Gaussian Squared-Complexity

In a recent paper , sharp upper bounds on the Gaussian complexities of normalized cones have been established for families of cones of interest in a class of linear inverse problems. The (square of the) Gaussian complexity can be upper bounded by the Gaussian squared-complexity $g(\mathcal{D})$ via Jensen’s inequality:

where $\mathbf{g}$ is a standard normal vector. In fact most of these bounds in were obtained by bounding $g(\mathcal{D})$ and thus they are directly relevant to our setting. In the rest of this section we present the bounds on $g(\mathcal{D})$ from that will be used in this paper, deferring to that paper for proofs in most cases. In some cases the proofs do require modifications with respect to their counterparts in , and for these cases we give full proofs in the Supplementary Information.

Therefore we have the following result as a simple corollary.

Next we state a result for low-rank matrices and the nuclear norm ball.

Next we state and prove a result that allows us to estimate Gaussian squared-complexities of general cones. The bound is based on the volume of the dual of the cone of interest, and the proof involves an appeal to Gaussian isoperimetry . A similar result on Gaussian complexities of cones (without the square) was proved in , but that result does not directly imply our statement and we therefore give a complete self-contained proof in the Supplementary Information. The volume of a cone is assumed to be normalized (between zero and one) so we consider the relative fraction of a unit Euclidean sphere that is covered by a cone:

Time-Data Tradeoffs

For $\mathbf{x}^{\ast}\in\mathcal{S}$ and with $\mathcal{S}\subseteq\mathcal{C}$, if

Proof: The result follows by a rearrangement of the terms in the bound in Proposition 4. $\square$

This corollary states that if we have access to a dataset with $n$ samples, then we can use any convex constraint set $\mathcal{C}$ such that the term on the right-hand-side in the corollary is smaller than $n$. Recalling that larger constraint sets $\mathcal{C}$ lead to larger tangent cones $T_{\mathcal{C}}$, we observe that if $n$ is large one can potentially use very weak (and computationally inexpensive) relaxations and still obtain a risk of $1$. This observation, combined with the important point that the hierarchies of convex relaxations described previously are simultaneously ordered both by approximation quality and by computational tractability, allows us to realize a time-data tradeoff by using convex relaxation as an algorithm weakening mechanism. See Figure 2 for a simple demonstration.

Example 1: Denoising Signed Matrices

We consider the problem of recovering signed matrices corrupted by noise:

Example 2: Ordering Variables

The matrix $M$ here is to be viewed as a covariance matrix. Thus, the corresponding denoising problem (1) is that we wish to estimate a covariance matrix in the absence of knowledge of the ordering of the underlying variables. In a real-world scenario one might wish to consider covariance matrices $M$ that belong to some class of banded matrices and then construct $\mathcal{S}$ as done here, but we stick with the case of a fixed $M$ for simplicity. Further, the noise in a practical setting is better modeled as coming from a Wishart distribution—again, we focus on the Gaussian case for simplicity.

Example 3: Sparse PCA and Network Activity Identification

In addition to sparse PCA, such signal sets are also of interest in identifying activity in noisy networks , as well as in related combinatorial optimization problems such as the planted clique problem . In the sparse PCA context, Amini and Wainwright study time-data tradeoffs by investigating the sample complexities of two procedures, a simple one based on thresholding and a more sophisticated one based on semidefinite programming. Kolar et al. investigate the sample complexities of a number of procedures ranging from a combinatorial search method, thresholding, and sparse SVD. We note that the time-data tradeoffs studied in these two papers relate to the problem of learning the support of the leading sparse eigenvector; in contrast in our setup the objective is to simply denoise an element of $\mathcal{S}$. Further while the Gaussian noise setting is of interest in some of these domains, in a more realistic sparse PCA problem (such as the one considered in ) the noise is Wishart rather than Gaussian as considered here. Nevertheless, we stick with our stylized problem setting as it provides some useful insights on time-data tradeoffs. Finally, the size of the block $k\in\{1,\dots,\sqrt{p}\}$ depends on the application of interest and it is typically far from the extremes $1$ and $\sqrt{p}$—we will consider the case $k\sim p^{1/4}$ for concreteness. This setting is an interesting threshold case in the planted clique context where $k=p^{1/4}$ is the square-root of the number of nodes $\sqrt{p}$ of the graph represented by $M$ (viewed as an adjacency matrix).

Example 4: Estimating Matchings

As our final example, we consider signals that represent the set of all perfect matchings in the complete graph. A matching is any subset of edges of a graph such that no node of the graph is incident to more than one edge in the subset, and a perfect matching is a subset of edges in which every node is incident to exactly one edge in the subset. Graph matchings arise in a range of inference problems such as in chemical structure analysis and in network monitoring . Letting $M$ be the adjacency matrix of some perfect matching in the complete graph on $\sqrt{p}$ nodes, our signal set in this case is defined as follows:

A tractable relaxation of the perfect matching polytope is a hypersimplex , obtained by taking the convex hull of all $\sqrt{p}\times\sqrt{p}$ matrices consisting of $\sqrt{p}$ ones and the other entries being equal to zero. We scale this hypersimplex by a factor of $p^{1/4}$ so that the elements of $\mathcal{S}$ are on the boundary. The hypersimplex is also a vertex-transitive polytope like the perfect matching polytope, but with about ${p\choose\sqrt{p}}$ entries. Hence from Corollary 10 and from Corollary 11, we have that $n=c_{2}\sqrt{p}\log(p)$ samples will provide a risk-$1$ estimate. Further, projecting onto the hypersimplex is a very efficient operation based on sorting and has a runtime of $\mathcal{O}(p\log(p))$. Consequently the total runtime of this procedure is $c_{2}p^{1.5}\log(p)+\mathcal{O}(p\log(p))$.

Some Observations

A curious observation that we may take away from these examples is that it is possible to obtain substantial speedups computationally with just a constant factor increase in the size of the dataset. This suggests that in settings in which obtaining additional data is inexpensive, it may be more economical to procure more data and employ a more basic computational infrastructure rather than to process limited data using powerful and expensive computers.

Conclusions

In this paper we considered the problem of reducing the computational complexity of an inference task as one has access to larger datasets. The traditional goal in the theory of statistical inference is to understand the tradeoff in an estimation problem between the amount of data available and the risk attainable via some class of procedures. In an age of plentiful data in many settings and computational resources being the principal bottleneck, we believe that an increasingly important objective is to investigate the tradeoffs between computational and sample complexities. As one pursues this line of thinking, it becomes clear that a central theme must be the ability to weaken an inference procedure as one has access to larger datasets. Accordingly, we proposed convex relaxation as an algorithm weakening mechanism, and we investigated its efficacy in a class of denoising tasks. Our results suggest that such methods are especially effective in achieving time-data tradeoffs in high-dimensional parameter estimation.

We close our discussion by outlining some exciting future research directions. As algorithm weakening is central to the viewpoint described in this paper, it should come as no surprise that several of the directions listed below involve interaction with important themes in computer science.

In many massive data problems, one is presented with a stream of input data rather than a large fixed dataset, and an estimate may be desired after a fixed amount of time independent of the rate of the input stream. In such a setting an alternative viewpoint to the one presented in this paper might be more appropriate. Specifically, rather than keeping the risk fixed, one would keep the runtime fixed and trade off the risk with the rate of the input stream. One can imagine algorithm weakening mechanisms, dependent on the rate of the data stream, in which the initial data points are processed using sophisticated algorithms and subsequent samples are processed more coarsely. Understanding the tradeoffs in such a setting is of interest in a range of applications.

Alternative algorithm weakening mechanisms

The notion of weakening an inference algorithm is key to realizing a time-data tradeoff. While convex relaxation methods provide a powerful and general approach, a number of other weakening mechanisms are potentially relevant. For example, processing data more coarsely by quantization, dimension reduction, and clustering may be natural in some contexts. Coresets, which originated in the computational geometry community, summarize a large set of points via a small collection (see, for example, and the references therein), and they could also provide a powerful algorithm weakening mechanism. Finally, we would like to mention a computer hardware concept that has implications for massive data analysis. A recent approach to designing computer chips is premised on the idea that many tasks do not require extremely accurate computation . If one is willing to tolerate small, random errors in arithmetic computations (e.g., addition, multiplication), it may be possible to design chips that consume less power and are faster than traditional, more accurate chips. Translated to a data analysis context, such design principles may provide a hardware-based algorithm weakening mechanism.

Measuring quality of approximation of convex sets

In the mathematical optimization and theoretical computer science communities, relaxations of convex sets have provided a powerful toolbox for designing approximation algorithms for intractable problems, most notably those arising in combinatorial optimization. The manner in which the quality of a relaxation translates to the quality of an approximation algorithm is usually quantified based on the integrality gap between the original convex set and its approximation . However, the quantity of interest in a statistical inference context in characterizing the quality of approximations is based on ratios of Gaussian squared-complexities of tangent cones. These two quantifications can be radically different—indeed, several of the relaxations presented in our time-data tradeoff examples that are useful in an inferential setting would provide poor performance in a combinatorial optimization context. More broadly, those examples demonstrate that weak relaxations frequently provide as good estimation performance as tighter ones with just an increase of a constant factor in the number of data samples. This observation suggests a potentially deeper result along the following lines—many computationally intractable convex sets for which there exist no tight efficiently-computable approximations as measured by integrality gap can nonetheless be well-approximated by computationally tractable convex sets, if the quality of approximation is measured based on statistical inference objectives.

Acknowledgments

This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under contract/grant number W911NF-11-1-0391. We are grateful to Pablo Parrilo, Benjamin Recht, and Parikshit Shah for many insightful conversations. We would also like to thank Alekh Agarwal, Emmanuel Candès, James Saunderson, Leonard Schulman, and Martin Wainwright for helpful questions and discussions.

References

Supplementary Information

Letting $R_{1}$ and $R_{2}$ denote orthogonal subspaces that contain $Q_{1}$ and $Q_{2}$, i.e., $Q_{1}\subseteq R_{1}$ and $Q_{2}\subseteq R_{2}$, and letting $\boldsymbol{\delta}^{(1)}=\mathcal{P}_{R_{1}}(\boldsymbol{\delta}),\boldsymbol{\delta}^{(2)}=\mathcal{P}_{R_{2}}(\boldsymbol{\delta}),\hat{\boldsymbol{\delta}}^{(1)}_{n}(\mathcal{C})=\mathcal{P}_{R_{1}}(\hat{\boldsymbol{\delta}}_{n}(\mathcal{C})),\hat{\boldsymbol{\delta}}^{(2)}_{n}(\mathcal{C})=\mathcal{P}_{R_{2}}(\hat{\boldsymbol{\delta}}_{n}(\mathcal{C}))$ denote the projections of $\boldsymbol{\delta},\hat{\boldsymbol{\delta}}_{n}(\mathcal{C})$ onto $R_{1},R_{2}$, we can rewrite the above reformulated optimization problem as:

This bound can be established following the same sequence of steps as in the proof of Proposition 4. Combining the two bounds on $\hat{\boldsymbol{\delta}}^{(1)}_{n}(\mathcal{C})$ and $\hat{\boldsymbol{\delta}}^{(2)}_{n}(\mathcal{C})$, one can then check that

Taking expectations concludes the proof. $\square$

Proof of Proposition 9

Proof of Lemma 2: Consider the following definition of a spherical cap, parametrized by height $h$:

We can thus obtain bounds on the solid angle of a spherical cap via bounds on its height. The following result from relates the volume of a spherical cap to its height:

Continuing with the proof of Lemma 2, note that for $\tfrac{2}{\sqrt{p}}\leq h\leq 1$

Choosing $h=\sqrt{\tfrac{2\log\left(\tfrac{1}{4\mu}\right)}{p-1}}$ we have $\tfrac{2}{\sqrt{p}}\leq h\leq 1$ based on the assumption $\mu\in\left(\tfrac{1}{4}\exp\{-p/20\},\tfrac{1}{4e^{2}}\right)$. Consequently, we can apply Lemma 3 with this value of $h$ combined with (10) to conclude that

Using the bound $\sin^{-1}(h)\leq\tfrac{\pi}{2}h$, we obtain the desired bound. $\square$

From here onward, we focus exclusively on bounding the integral.

Let $\tau(\psi)$ denote the volume of a spherical cap subtending a solid angle of $\psi$ radians. Recall that $\psi$ is a quantity between $0$ and $\pi$. As in Lemma 2 let $\psi(\mu)$ denote the solid angle of a spherical cone subtending a solid angle of $\mu$. Since the Euclidean distance between points on a sphere is always smaller than the geodesic distance, we have that $\bar{\mu}(V;s)\geq\tau(\psi(\mu)+s)$. Further, we have the following explicit formula for $\tau(\psi)$ :

where $\omega_{p}=\int_{0}^{\pi}\sin^{p-1}(v)dv$ is the normalization constant. Combining these latter two observations, we can bound the integral in (11) as:

Next we change the order of integration to obtain:

We now appeal to the inequalities $\omega_{p}^{-1}\leq\sqrt{p-1}/2$ and $\sin(x)\leq\exp(-(x-\tfrac{\pi}{2})^{2}/2)$ for $x\in[0,\pi]$ to obtain

Performing a change of variables with $a=\sqrt{p-1}(v-\tfrac{\pi}{2})$, we have

Here the inequality was obtained by suitably changing the limits of integration. We now employ Lemma 2 to obtain the final bound:

Here the final bound holds because $\mu<1/4e^{2}$ and $p\geq 12$. $\square$