Iterative Hessian Sketch for Constrained Least-Squares and Information-Theoretic Classical Sketching Lower Bounds

⚠️ Curated Limitations & Negative Results

• Multi-Pass Access to Matrix-Vector Products with A and A^T: Unlike single-pass classical sketching (S A, S y) which compresses the data in one pass at the expense of an O(n/m) variance inflation factor (Theorem 1), Iterative Hessian Sketch requires N = O(log n) rounds of computing exact residual gradients A^T(y - A x^t) and fresh sketch products S^{t+1} A (Section 2.4, Equation 24).
• Dependence of Tangent-Cone Gaussian Width on Restricted Eigenvalue and Self-Bounding Cone Conditions: For l_1-constrained and nuclear-norm-constrained regression (Corollaries 3-4, Lemma 7), the O(s log(ed/s)) and O(r(d_1 + d_2)) sketch-size bounds require the tuning parameter R to be binding at the true parameter (||x^*||_1 = R or |||X^*|||_1 = R) and scale inversely with the s-sparse or 2r-rank restricted eigenvalue gamma_s^-(A); moreover, randomized orthonormal system (ROS) sketches require an extra log^4(n) factor and the self-bounding cone property (Lemma 1(b), Definition 1).
• Primary-Source Typographical Notes in Pilanci & Wainwright (2016, arXiv:1411.0347v1): Verified four self-correcting typographical details across the 33-page manuscript: (1) Section 2.3 (p. 9, Equation 16) writes the single-step Hessian sketch objective as (1/2)||S A x||_2^2 - <A^T y, x> omitting the 1/m normalization (which is explicitly included in the IHS update Equation 24 on p. 12 and in Z_1(S), Z_2(S) in Equations 18a-18b on p. 10), and Appendix B (p. 25, Equation 37a) writes the classical-sketch optimality condition <A^T S^T (S A x_hat - y), x^{LS} - x_hat> >= 0 instead of the Hessian-sketch optimality condition <(1/m) A^T S^T S A x_hat - A^T y, x^{LS} - x_hat> >= 0 (while the immediately following display correctly uses the Hessian-sketch difference <(A^T A - (1/m) A^T S^T S A) x_hat, x^{LS} - x_hat> <= 0, omitting only the 1/m factor in I_n - S^T S below Equation 38); (2) Section 2.3 (p. 10, Equation 17) and Appendix D (p. 26, Equation 42) write 'v in R^d' instead of 'v in R^n' in the definition of the transformed tangent cone K^{LS} := {v in R^n | v = t A(x - x^{LS}) for some t >= 0 and x in C}, and Example 2 (p. 8) writes 'C = {x in R^n | ||x||_1 <= R}' instead of 'x in R^d'; (3) Lemma 1(a) (p. 11, Equation 22a) prints '1 - c_1 e^{-c_2 m delta^2}' with delta^2 instead of rho^2, and Corollary 4 (p. 20) prints 'm = c_0 rho^2 (|||A|||_op^2 / gamma_{2r}^-(A)) r(d_1 + d_2)' with rho^2 in the numerator instead of the denominator c_0 / rho^2; and (4) Appendix A.2 (p. 24, last two lines) prints E||x_hat - x^*||_2^2 instead of E||x_hat - x^*||_A^2 and writes delta = sigma^2 log(M/2) / (64 eta m) instead of delta^2 = sigma^2 log(M/2) / (64 eta m).
• All 33 pages of the full-text PDF of Pilanci & Wainwright (2014/2016, JMLR 17(53):1-38, arXiv:1411.0347v1) were read. Constructed numerical checks in research/discovery/iterative-hessian-sketch-constrained-least-squares-boundaries.py verify (1) Theorem 1 and Corollary 2 sub-optimality of single-shot classical sketching (prediction error 0.12728) vs. unconstrained IHS matching exact OLS (prediction error 0.04110 vs. 0.04089, OLS gap 3.819e-4 vs. 0.11647), (2) Proposition 1 and Theorem 2 exact per-step deterministic tangent-cone inequalities ||x^{t+1} - x^{LS}||_A <= (Z_2(S^{t+1})/Z_1(S^{t+1})) ||x^t - x^{LS}||_A across all 12 steps and cumulative product bound, and (3) Section 3.2 Corollary 3 geometric convergence of constrained IHS on l_1-ball sparse least squares (reducing gap from 1.41404 to 0.01169 in 5 rounds).