Randomized Sketches of Convex Programs with Sharp Guarantees

Mert Pilanci; Martin J. Wainwright

Source-linked AI summary

Randomized Sketches of Convex Programs with Sharp Guarantees

Mert Pilanci, Martin J. Wainwright

arXiv:1404.7203v1Apr 29, 2014cs.ITcs.DSmath.OCstat.ML

TL;DR

Large-scale convex programs can be too costly to solve exactly, motivating lower-dimensional approximations with rigorous guarantees. This paper analyzes random projections of convex programs, proving approximation results tied to constraint geometry and extending them across sketching ensembles and applications. It also shows that privacy-sensitive optimization can retain δ-accuracy while reducing information about individual data points.

Problem
High-dimensional convex programs can have prohibitive computational and storage costs, while statistical estimation often involves large parameter dimensions and sample sizes.
Method
The paper analyzes random projections of matrices and vectors defining linear or quadratic convex programs over arbitrary convex constraint sets, using deterministic convex optimality arguments and probabilistic sketching analysis.
Results
The theory provides δ-approximation guarantees for sub-Gaussian and randomized orthogonal-system sketches, with projection dimensions governed by the Gaussian width of the constraint tangent cone.
Takeaways & Limitations
Random projection can reduce computation and storage across constrained quadratic, second-order cone, and semidefinite programs, while supporting privacy-sensitive optimization.
Takeaways & Limitations
Sub-Gaussian sketches require unstructured matrix-vector multiplications, while nuclear-norm matrix estimation may not yield substantial computational savings because the optimization space remains d1d2 dimensional.

Abstract

from arXiv · show

Random projection (RP) is a classical technique for reducing storage and computational costs. We analyze RP-based approximations of convex programs, in which the original optimization problem is approximated by the solution of a lower-dimensional problem. Such dimensionality reduction is essential in computation-limited settings, since the complexity of general convex programming can be quite high (e.g., cubic for quadratic programs, and substantially higher for semidefinite programs). In addition to computational savings, random projection is also useful for reducing memory usage, and has useful properties for privacy-sensitive optimization. We prove that the approximation ratio of this procedure can be bounded in terms of the geometry of constraint set. For a broad class of random projections, including those based on various sub-Gaussian distributions as well as randomized Hadamard and Fourier transforms, the data matrix defining the cost function can be projected down to the statistical dimension of the tangent cone of the constraints at the original solution, which is often substantially smaller than the original dimension. We illustrate consequences of our theory for various cases, including unconstrained and $\ell_1$-constrained least squares, support vector machines, low-rank matrix estimation, and discuss implications on privacy-sensitive optimization and some connections with de-noising and compressed sensing.

1 Introduction

The paper studies random-projection approximations for convex programs to reduce computational and storage costs while retaining rigorous solution-quality guarantees. It extends sketching beyond unconstrained least squares to broad constrained problems and privacy-sensitive optimization.

Motivation: Large-dimensional convex programs can be prohibitively expensive despite polynomial-time algorithms, motivating approximate methods with rigorous quality bounds.Quadratic programs may scale cubically, while second-order cone and semidefinite programs can be even more costly.
Approach: The proposed scheme randomly projects the matrices and vectors defining a quadratic objective, while allowing arbitrary convex constraint sets.This covers constrained or penalized least squares, second-order cone programs, and semidefinite programs.
Statistical estimation: Sketching is attractive for statistical estimation because large ambient dimensions and sample sizes can make exact convex optimization difficult.Relevant structures include sparse vectors, low-rank matrices, combinatorial sets, and algebraic sets.
Related work: The analysis generalizes unconstrained least-squares sketching to constrained quadratic programs and uses convex analysis, Banach space geometry, and empirical process theory for sharper guarantees.The paper also gives a unified view of least-squares sketching and compressed sensing.
Privacy: Random projection can support privacy-preserving optimization by storing sketched data with vanishingly small information about individual data points while retaining δ-accuracy.The theory identifies a trade-off between constraint-set complexity and mutual information, allowing arbitrary accuracy when the constraint set is sufficiently simple statistically.
Paper organization: The paper derives main results, concrete problem-specific corollaries, simulations, proofs, and a concluding discussion.The results include applications to several convex-program classes and computational settings.

2 Statement of main results

The paper formulates random-projection sketches for constrained quadratic programs and characterizes when the sketched solution is δ-optimal. The required sketch dimension depends on geometric complexity of the transformed tangent cone, with sub-Gaussian and randomized orthonormal systems offering different accuracy–computation trade-offs.

Problem formulation: The sketched problem projects the data matrix and vector into R^m, with m<n, to obtain a computationally simpler δ-optimal approximation.The original problem minimizes a quadratic objective over a convex set, and the sketch uses S∈R^m×n.
Geometric complexity: The tangent cone at x∗ captures feasible directions from the optimum, and its transformed version AK determines the relevant geometric complexity.The analysis measures AK∩S^(n−1) using Gaussian width and related complexity measures.
Sub-Gaussian projections: Sub-Gaussian sketches guarantee δ-optimality with probability at least 1−c1e^(−c2mδ^2) when m satisfies a bound involving the problem’s geometric complexity.The theorem applies to Gaussian, Bernoulli, and other sub-Gaussian ensembles.
Sub-Gaussian projections: The squared Gaussian width W^2(AK) scales with statistical dimension, so the projection can reach the problem’s effective degrees of freedom while preserving δ-optimality.This dimension may be substantially smaller than the ambient dimension.
Privacy-sensitive optimization: The same guarantees support privacy-sensitive optimization: under the stated sketch-size condition, SA solves the original program to δ-accuracy while retaining vanishing mutual information per symbol when W^2(AK)=o(n).The privacy conclusion is stated for fixed δ∈(0,1).
Randomized orthonormal systems: Randomized orthonormal systems reduce multiplication cost, but generally require a larger projection dimension because of an additional R^2(AK)+log n factor.Hadamard and Fourier constructions permit fast matrix-vector multiplication; specialized cone arguments can sometimes remove the extra factor.

3 Some concrete instantiations

The paper specializes its sketching guarantees across unconstrained and structured estimation problems, relating required projection dimensions to rank, sparsity, support-vector count, or group structure. Experiments broadly confirm that approximation improves as projection size increases, while sketching can also reduce storage and support privacy-sensitive optimization.

Unconstrained least squares: Unconstrained least squares admits sketch dimensions tied to rank(A), with exponentially high-probability guarantees for both sub-Gaussian and ROS sketches.ROS sketches have lower matrix-multiplication cost but incur an additional log^4(n) factor in the stated bound.
Unconstrained least squares: O(rank(A)d^2 log^4(n)/δ^2+nd log(rank(A)/δ^2)) operations suffice for ROS least-squares approximation, versus O(nd^2) for direct QR computation.
ℓ1-constrained least squares: When the optimal least-squares solution is sparse, ℓ1-constrained least squares can be sketched logarithmically in d while retaining δ-optimality with probability at least 1 −c1e−c2mδ2.
Compressed sensing and denoising: The denoising specialization guarantees exact noiseless recovery and δ-approximate noisy recovery under projection dimensions scaling with ∥x∗∥0 log d.The same result connects compressed-sensing error with denoising error through the best sparse approximation.
Support vector machine classification: For support vector machines, projection dimensions depend on the number of samples on the margin, and the sketched solution is δ-optimal with probability at least 1 −c1e−c2mδ2.Classification experiments show approximation error approaches one as α increases, consistently with the theory.
Low-rank and group-sparse estimation: The framework also provides δ-optimality guarantees for low-rank approximation and group-sparse least squares, with group-sparse bounds involving k log |G| + kM.For weighted low-rank approximation, sketching may reduce storage and aid privacy-sensitive optimization without substantial computational savings.

4 Proofs of main results

The proofs combine a deterministic convex-optimality argument with probabilistic bounds tailored to the sketching matrix. Both sub-Gaussian and randomized orthogonal-system analyses reduce δ-optimality to controlling variational quantities associated with the transformed tangent cone.

Main proof strategy: The proof has deterministic and probabilistic parts: convex optimality conditions first establish the error relation, then sketch-specific concentration bounds control the remaining terms.The probabilistic step differs between sub-Gaussian sketches and randomized orthogonal systems.
Main proof strategy: δ-optimality follows once the ratio Z2(AK)/Z1(AK) is controlled for the transformed tangent cone AK.The two quantities are deterministic for a fixed sketching matrix but random under randomized sketches.
Sub-Gaussian sketches: For sub-Gaussian sketches, separate lower and upper bounds on Z1(AK) and Z2(AK) complete the theorem when the projection dimension is sufficiently large.The bounds use empirical-process results for i.i.d. zero-mean σ-sub-Gaussian vectors.
Randomized orthogonal systems: The orthogonal-system analysis controls quadratic forms through set decompositions, projection geometry, and concentration over Rademacher randomness.The proof partitions the relevant set into V+ and V− and combines several bounds with high-probability guarantees.
Randomized orthogonal systems: For randomized orthogonal systems, analogous bounds on Z1(AK) and Z2(AK), expressed using S-Gaussian and Rademacher widths, complete the proof.The argument applies the two lemmas for projection size satisfying the theorem’s dimension bound.

5 Techniques for sharpening bounds

The paper sharpens randomized-orthogonal-system bounds by reducing supremum problems to finite coverings and exploiting structure in subspaces, ℓ1-induced cones, and nuclear-norm cones. The resulting arguments yield specialized projection-dimension guarantees tied to sparsity and rank geometry.

General sharpening scheme: Sharper bounds reduce supremum control over structured sets to finite maxima over ε-covers, followed by a JL-embedding argument.For subspaces, the discretization uses an ε-cover of AK ∩ S^(n−1) and controls the resulting maximum probabilistically.
Subspaces: For a subspace, the covering argument and JL embedding bound the quadratic-form supremum using the covering size and Gaussian width.The JL guarantee applies simultaneously to the fixed points in the cover.
General sharpening scheme: Lemma 8 generalizes the reduction by relating first and second set differences of structured sets to a convex comparison set.Its conditions include containment, convexity, and scaling relations for the relevant set differences and projections.
Nuclear-norm cones: For nuclear-norm regularization, the tangent cone at a rank-r optimum is handled analogously through rank-constrained geometry and Gaussian complexity.The randomized orthogonal-system guarantee uses a projection dimension involving r, d1, d2, and log^4(d1d2).
Nuclear-norm cones: The specialized lemmas complete the sharpened bounds by combining the structured-set estimates with the deterministic bound used earlier.The proof for the nuclear-norm case parallels the preceding argument.

6 Discussion

The paper concludes that random projections provide approximation guarantees for convex programs with arbitrary convex constraint sets, including sub-Gaussian sketches and structured randomized projections. The required projection dimension is governed by the geometry of the transformed tangent cone.

Discussion: The theory covers convex programs with linear or quadratic objectives and arbitrary convex constraint sets.Its guarantees provide projection-dimension lower bounds sufficient for δ-approximation of the original optimum.
Discussion: The main conclusion is that sketching can preserve δ-approximate optimization solutions when the projection dimension satisfies the derived lower bounds.The bounds are expressed through geometric complexity associated with the feasible-set structure.

A Technical details for Corollary 3

The appendix derives the second term in the sharpened bound by combining width estimates with a JL-embedding result and then invoking Theorem 2. The argument controls the relevant event and substitutes the resulting bounds into the theorem.

Derivation of the bound: The appendix obtains the second term in the bound as a corollary of Theorem 2 and earlier calculations for Corollary 3(a).The derivation starts from the previously established bounds and specializes them to the required width quantities.
Width estimates: The S-Gaussian width is analyzed using the Gaussian covariance induced by the randomized orthogonal sketch.The resulting calculation is combined with an upper bound on the Rademacher width.
Probability control: A JL-embedding theorem supplies a high-probability event when the projection dimension is sufficiently large, after which conditioning yields the needed bound.The stated dimension condition includes log^5(n) log(d), and the event complement is bounded probabilistically.

B Technical lemmas for Proposition 2

The appendix proves two technical lemmas that underlie Proposition 2.

The appendix contains proofs of Lemmas 6 and 7.
These lemmas are technical components of the paper’s proof strategy.
The results of the lemmas support Proposition 2.

B.1 Proof of Lemma 6

The proof of Lemma 6 bounds deviations and expectations using empirical-process concentration and Rademacher contraction, then combines the bounds through set inclusions.

Talagrand’s theorem is used to bound deviations of Z′0 above its expectation.
The proof defines a random vector from a randomly selected row and functions indexed by y ∈ Y.
Ledoux–Talagrand contraction bounds the relevant expectation for any ν ∈ G.
The final claim follows by combining inequalities based on the inclusions ν ∈ G1 and ν ∈ G2.

B.2 Proof of Lemma 7

The proof of Lemma 7 establishes concentration through distributional symmetry, convex Lipschitz functions, and control of the complementary event Gc.

For Rademacher vectors, each inner product ⟨si, y⟩ has the same distribution as ⟨ν, y⟩.
The proof separately controls the probability of the event Gc and analyzes the convex Lipschitz function g from equation (60).
The equality in distribution across indices enables a union-bound probability estimate.
A convex 1-Lipschitz function f is controlled using standard concentration results.
Jensen’s inequality and the unit-modulus construction of esij contribute to the remaining bound.

C Proof of Lemma 8

The proof of Lemma 8 bounds a quadratic form over Y1 by convex-hull arguments, an ε-cover of the boundary, and geometric inclusions.

The supremum over Y1 is bounded by the supremum over the closure of the convex hull of Y0.
Vectors in conv(Y0) are represented as convex combinations, extending the bound to its closure.
An ε-cover of ∂[Y0] approximates each boundary vector by a covered point plus a perturbation in ∂2[Y0].
The inclusions (67)(b) and (c), convexity, and the condition 9εα2 < 1/3 yield claim (68).

D A technical inclusion lemma

This technical section states an inclusion lemma and begins its proof by comparing support functions after reducing the matrix argument to diagonal form. The argument then isolates the largest diagonal entries and uses their ordering to continue the bound.

Lemma 13 states an inclusion involving the previously defined sets Y1(r) and Y0(r).
The notation clconv denotes the closed convex hull in the stated inclusion.
The proof introduces support functions φ0 and φ1 and reduces the goal to showing φ1(X) ≤ 3φ0(X) for every X ∈ S_d×d.
Unitary invariance of the Frobenius norm, nuclear norm, and rank permits taking X diagonal and restricting the optimization to diagonal matrices Δ.
The proof selects the indices of the ⌊r⌋ largest diagonal entries of X in absolute value, then compares every remaining entry with those selected entries.
The resulting ordering is used to rewrite the bound and continue the support-function comparison.