PaperlayerView exact revision on arXiv

Source-linked AI summary

Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

Mert Pilanci, Martin J. Wainwright

arXiv:1411.0347v1math.OCcs.ITcs.LGstat.ML

TL;DR

The paper asks how to obtain accurate least-squares solutions under convex constraints when standard sketches approximate the data matrix and vector. It proves a lower bound for such classical sketches and introduces iterative Hessian sketching, achieving solution approximations with sketch size tied to statistical complexity and logarithmically many iterations. Empirical results report near-optimal estimators and better classification accuracy than the naive sketch in a facial-expression task.

  • Problem

    The paper studies solution approximation for constrained least-squares, where the minimizer itself matters more than the quadratic cost value, and examines limits of methods using only (SA, Sy).

  • Method

    The paper introduces iterative Hessian sketching, which uses multiple sketches of the data and iteratively refines the solution.

  • Results

    The classical sketch is sub-optimal for solution approximation when m ≪ n, while IHS produces near-optimal estimators and improves classification accuracy over the naive sketch in the reported face-expression experiment.

  • Takeaways & Limitations

    IHS uses sketch dimension proportional to the statistical dimension of the optimal solution and logarithmically many iterations to obtain ε-accurate solution approximations.

  • Takeaways & Limitations

    The paper’s discussion identifies extending iterative sketching beyond least-squares objectives, including ℓp regression, as further research.

Abstract

from arXiv · show

We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance measure between the approximate minimizer and the true minimizer (solution approximation). Focusing on the latter criterion, our first main result provides a general lower bound on any randomized method that sketches both the data matrix and vector in a least-squares problem; as a surprising consequence, the most widely used least-squares sketch is sub-optimal for solution approximation. We then present a new method known as the iterative Hessian sketch, and show that it can be used to obtain approximations to the original least-squares problem using a projection dimension proportional to the statistical complexity of the least-squares minimizer, and a logarithmic number of iterations. We illustrate our general theory with simulations for both unconstrained and constrained versions of least-squares, including $\ell_1$-regularization and nuclear norm constraints. We also numerically demonstrate the practicality of our approach in a real face expression classification experiment.

1 Introduction

The paper distinguishes solution approximation from cost approximation in constrained least-squares and shows that the classical sketch can be sub-optimal when the sketch dimension is much smaller than the sample size. It introduces iterative Hessian sketching, which uses multiple sketches and logarithmically many refinement rounds to achieve solution approximations tied to intrinsic problem complexity.

  • Sketching constrained least-squares: Randomized sketches reduce constrained least-squares to lower-dimensional problems by projecting (A, y) to (SA, Sy), enabling savings when m ≪ n.The sketched problem uses the m-dimensional matrix SA ∈ Rm×d.
  • Approximation criteria: Solution approximation evaluates the distance between the approximate and least-squares minimizers, unlike cost approximation, which evaluates the quadratic objective value.Relevant measures include the ℓ2-norm and prediction seminorm.
  • Limits of classical sketching: Matching the least-squares estimator’s accuracy can require an undesirable projection scaling when n ≫ d, undermining the goal of using m much smaller than n.The discussion motivates seeking a different sketching strategy for solution approximation.
  • Limits of classical sketching: m ≪ n makes the classical least-squares sketch sub-optimal for solution approximation, and this lower-bound conclusion applies broadly to constrained problems.Theorem 1 covers any estimator based only on (SA, Sy), including the standard sketching algorithm.
  • Iterative Hessian sketch: Iterative Hessian sketching obtains optimal solution approximations by repeatedly sketching the data and refining the solution over a logarithmic number of iterations.The method uses sketches (S1A, ..., SNA), with N chosen logarithmic in n; ε-accurate approximations require log(1/ε) steps.

2 Main results

The paper establishes that estimators using only the classical sketched pair (SA, Sy) are sub-optimal for solution approximation when m ≪ n, then introduces iterative Hessian sketching to achieve accurate approximations with complexity tied to the minimizer’s statistical complexity.

  • Classical sketch lower bound: Theorem 1 shows that any estimator based only on (SA, Sy) is sub-optimal for solution approximation when m ≪ n.The result applies to arbitrary measurable estimators and broad constrained least-squares problems.
  • Classical sketch lower bound: Matching the original least-squares estimator’s mean-squared error with the classical sketch can require m proportional to n, rather than proportional to rank(A) = d.This creates a gap between the computational savings of sketching and solution-approximation accuracy.
  • Constrained problems: The lower bound extends beyond unconstrained problems to sparse least-squares and matrix problems, while IHS uses dimensions scaling with the relevant statistical complexity.For sparse models, the IHS dimension scales as s log d + log(n); for matrix problems, it scales with r(d1 + d2) plus logarithmic factors.
  • Iterative Hessian sketch: IHS iteratively applies Hessian sketches to residual problems, reducing the distance to xLS by a factor ρ per iteration and producing geometric error decay.The construction uses the current iterate to form a problem whose solution is xLS − xt.
  • Iterative Hessian sketch: Corollary 1 gives an ε-accurate solution approximation with sketch size proportional to log(1/ε)W2(KLS), improving on the classical sketch’s ε^-2W2(KLS) scaling up to logarithmic factors.The guarantee applies to ROS and sub-Gaussian sketches, with some additional logarithmic terms omitted for sub-Gaussian sketches.
  • Computational and space complexity: For unconstrained least-squares, the resulting ε-accurate computation has complexity O(nd log(d) + d3) log(1/ε) and space O(d2); for sparse problems, the stated space is O(sd log(d)).The sparse complexity bound is O((nd log(s)+s2d log2(d)) log(1/ε)).

3 Consequences for concrete models

Across unconstrained and constrained least-squares models, IHS achieves the predicted accuracy with sketch dimensions tied to statistical complexity and geometric convergence over iterations.

  • Unconstrained least squares: m ≳ d/ρ^2 projections per round guarantee ρ-contractivity for unconstrained least-squares, yielding ε-accuracy in roughly log(1/ε)/log(1/ρ) iterations.The tolerance is chosen relative to the ordinary least-squares error when approximating x∗.
  • Unconstrained least squares: N = 4 IHS iterations with m = 6d achieve ∥x̂ − x∗∥A ≈ 0.11 across dimensions, while the classical sketch with M = 24d has roughly twice the error.The experiments use n = 100d and compare IHS with a classical sketch using the same total number of projections.
  • Low-rank matrix estimation: For nuclear-norm constrained matrix estimation, IHS matches the original solution’s error with sketch dimension scaling as {r(d1 + d2) + log(n)} log(n).The model assumes an unknown rank-r matrix and a nuclear-norm radius equal to the true matrix’s nuclear norm.

4 Discussion

The paper establishes that iterative Hessian sketching yields accurate solution approximations with sketch dimension tied to the optimum's statistical dimension, while empirical evaluations show near-optimal performance across constrained problems.

  • 4 Discussion: The sketch dimension per iteration need grow only proportionally to the Gaussian width of the tangent cone at the optimum.This Gaussian width measures the statistical dimension of the optimal solution.
  • 4 Discussion: log(1/ε) iterations guarantee an ε-accurate solution approximation with exponentially high probability.
  • 4 Discussion: IHS produces near-optimal estimators, while empirical evaluations reveal the sub-optimality of the classical sketch.
  • 4 Discussion: IHS tracks the unsketched solution's mean-squared error across row dimensions, whereas the classical sketch has essentially constant error.The nuclear-norm constrained simulation recovers a 20 × 20 matrix of rank r2 with m = 60.
  • 4 Discussion: IHS applied to a nuclear-norm constrained program produces classifiers with considerably better classification accuracy than the naive sketch.
  • 4 Discussion: Iterative sketching may also apply beyond least-squares objectives, including ℓp-norm regression.

A Proof of lower bounds

The lower-bound proof verifies its key condition for Gaussian, randomized orthonormal system, and weighted row-sampling sketches.

  • A Proof of lower bounds: The appendix verifies the lower-bound condition for three different types of sketches.
  • A Proof of lower bounds: Gaussian sketches use random matrices with independent Gaussian entries and an SVD-based analysis exploiting rotation invariance.
  • A Proof of lower bounds: ROS sketches use S = √nPHD, where P is a random picking matrix and H, D define the randomized orthonormal system.
  • A Proof of lower bounds: Weighted row sampling independently samples rows according to an α-balanced distribution.
  • A Proof of lower bounds: For independently sampled rows, row j is selected at least once with probability q_j = 1−(1−p_j)^m.
  • A Proof of lower bounds: The analysis uses p∞ = max_j∈[n] p_j and requires α-balanced row weights so that p∞ ≤ α.

A.2 Proof of Theorem 1

Theorem 1's proof constructs separated feasible instances, bounds their sketched-information divergence, and applies multiway testing arguments to derive the lower bound.

  • A.2 Proof of Theorem 1: A 1/2-packing of C0 in the seminorm ∥·∥A is rescaled as x_j = 4δz_j to construct separated feasible vectors.
  • A.2 Proof of Theorem 1: Conditionally on J = j, the sketched response follows N(SAx_j, σ2SST), while SA is also observed.
  • A.2 Proof of Theorem 1: The proof reduces worst-case mean-squared estimation error to a multiway testing problem over the index J.
  • A.2 Proof of Theorem 1: Fano's inequality lower-bounds the testing error using the mutual information I_S(Y; J), whose expectation is then upper-bounded.
  • A.2 Proof of Theorem 1: Convexity of Kullback–Leibler divergence is used to control divergences among the sketched Gaussian distributions.
  • A.2 Proof of Theorem 1: The sketch condition bounds the divergence by 32mηδ2/σ2, using ∥x_j−x_k∥A ≤ 8δ.
  • A.2 Proof of Theorem 1: Combining the testing and divergence bounds yields the lower bound (10), with the final step stated as 64ηm.

B Proof of Proposition 1

The proposition's proof combines optimality inequalities from the Hessian-sketch and original programs, then uses the resulting basic inequality to establish the claim.

  • B Proof of Proposition 1: Optimality and feasibility of bx and xLS for the Hessian sketch program provide the first inequality.
  • B Proof of Proposition 1: Optimality and feasibility of xLS and bx for the original least-squares program provide a second inequality.
  • B Proof of Proposition 1: Adding the two inequalities and simplifying produces the basic inequality used in the proof.
  • B Proof of Proposition 1: The basic inequality is combined with the definitions of Z1 and Z2 to complete the claim.

C Proof of Theorem 2

The proof rewrites the iterative update in terms of the error relative to xLS, bounds the resulting terms using optimality and sketch complexity, and combines these bounds to establish the contraction claim.

  • Iteration conclusion: Applying bound (39) successively to iterates 1 through N yields the claimed bounds (26a) and (26b).The theorem-level bounds follow by iterating the one-step result.
  • Error reformulation: The update is rewritten using Δ = bx − xLS, expressing the iteration through its error relative to the constrained least-squares solution.The notation abbreviates S_t+1 as S and x_t+1 as bx.
  • Optimality bounds: First-order optimality conditions for bx and xLS produce inequalities that are added to obtain a bound involving Δ.The proof introduces the shorthand Δ after combining the two optimality inequalities.
  • Sketch control: Because A(xLS − xt) is independent of the new sketch randomness and AΔ lies in K, the definition of Z2(S_t+1) controls the sketched term.This is the key independence and cone-membership step used in the iteration bound.
  • Combining bounds: A complementary lower bound is established and combined with the earlier bound (40) to prove claim (39).The two bounds identified as (41a) and (41b) are combined in this step.

D Maximum likelihood estimator and examples

This section develops a general upper bound for the error of the constrained least-squares estimate and applies it to the illustrative examples from Section 2.2.

  • Section overview: The section establishes a general upper bound on the error of the constrained least-squares estimate.The bound is then used in calculations for Examples 1 through 3.
  • Applications: The resulting bound and related results are used to work through Examples 1 through 3 from Section 2.2.

D.1 Upper bound on MLE

The constrained least-squares error is controlled by the localized complexity of a star-shaped error set, quantified through localized Gaussian widths and a fixed-point radius.

  • Error geometry: The accuracy of xLS as an estimate of x* depends on the size of a star-shaped set constructed from feasible parameter differences.For a fixed x*, the set contains scaled vectors A(x − x*) for feasible x and t in [0, 1].
  • Set construction: The set K* is defined for a given x*, and K is obtained by taking a union over all possible x* in C0.
  • Localized complexity: The complexity of these sets is measured using localized Gaussian widths of Θ intersected with an ℓ2 ball of radius ε.The Gaussian width is defined using a standard Gaussian vector g.
  • Complexity radius: The fixed-point quantity εℓ(Θ; σ) is defined as the smallest positive solution of the stated inequality for star-shaped Θ.The inequality is asserted for any σ > 0 and positive integer ℓ.
  • Error bound: Proposition 2 upper bounds the mean-squared error of the constrained least-squares estimate for any set C containing x*.The proof of this proposition is provided in Section D.3.

D.2 Detailed calculations for illustrative examples

The illustrative-example calculations use the normalized matrix notation eA = A/√n and derive an upper bound from Gaussian-width properties and Proposition 2.

  • Notation: The appendix calculations use the shorthand eA = A/√n throughout the illustrative examples.
  • Gaussian-width calculation: The Gaussian width of eA(x − x*) is evaluated using the fact that this vector lies in a subspace of dimension rank(A) = d.
  • Example bound: The resulting calculation yields the claimed upper bound (11a) as a consequence of Proposition 2.

D.2.2 Sparse vectors: Example 2

The proof derives bounds for sparse-vector and low-rank matrix settings using restricted isometry, Gaussian-width, norm-duality, and random-matrix arguments. These steps yield the stated upper and lower bounds through the cited propositions and theorem.

  • Sparse vectors: The RIP property of order 8s is used as a central condition in the sparse-vector argument.
  • Sparse vectors: For an s-sparse optimizer, the ℓ1 error is bounded by 2√s times the ℓ2 error over the feasible comparison set.
  • Sparse vectors: Gaussian-width comparisons and convex-hull inclusions control the relevant sparse-vector complexity and establish the claimed upper bound (12a).
  • Bounds: A reverse argument provides a universal lower bound involving s log, and Theorem 1 converts it into the stated lower bound.
  • Low-rank matrices: For rank-r matrix solutions, nuclear-norm error is related to Frobenius-norm error by a factor 2√r.
  • Low-rank matrices: A Gaussian covering argument applied to ATG, together with singular-value bounds, yields the stated upper bound (15a).

D.3 Proof of Proposition 2

The proposition’s proof controls estimation error through an auxiliary Gaussian process, concentration of measure, and the basic least-squares optimality inequality. A tail bound is then integrated to obtain the expected mean-squared-error bound.

  • The proof introduces εn = εn(K∗) and establishes a more general claim for every t ≥ εn.
  • Applying the lemma with u = √tεn and conditioning on the complementary event yields the desired error bound, which is integrated to obtain (44).
  • The least-squares basic inequality bounds the optimal residual by the noise energy, providing the starting point for the proposition’s error analysis.
  • The event B(u) is included in the event {Vn(u) ≥ 2u2} after rescaling a feasible error vector into star(C − x∗).
  • Vn(u) is Lipschitz in the Gaussian variables with constant L = σu√n, enabling a Gaussian concentration tail bound.
  • For u ≥ εn, Gaussian-width monotonicity and the definition of εn imply E[Vn(u)] ≤ εnu ≤ u2.
Loading 1411.0347v1…