Randomized Sketches of Convex Programs with Tangent-Cone Gaussian-Width Cost-Approximation and Privacy Mutual-Information Guarantees

⚠️ Curated Limitations & Negative Results

• Cost-Value Multiplicative Approximation vs. Statistical Parameter Estimation Under Noise: As analyzed in the companion paper Pilanci & Wainwright (2016, JMLR 17(53):1-38), Theorem 1 and Theorem 2 of Pilanci & Wainwright (2015) bound the worst-case optimization cost ratio f(x_hat) <= (1 + delta)^2 f(x^*) for a single joint sketch ||S(A x - y)||_2^2; when y = A x_0 + w contains additive noise with f(x^*) = O(n sigma^2), a single joint sketch of dimension m << n incurs O(delta ||A x^* - y||_2) residual-to-parameter cross-term error unless f(x^*) is small (as in noiseless compressed sensing, Corollary 4) or iterative Hessian sketching is used.
• Optimization Dimension in Vectorized Nuclear-Norm Matrix Sketching: As explicitly noted in Section 3.5 (p. 16), for weighted low-rank matrix approximation min_{|||X|||_nuc <= R} ||S y - S A vec(X)||_2^2 (Corollary 6), sketching reduces the measurement dimension from D = d_1 d_2 to m = O(r(d_1 + d_2)) for storage and privacy-sensitive optimization, but the matrix variable X itself remains d_1 x d_2 dimensional.
• Primary-Source Typographical Notes in Pilanci & Wainwright (2015, arXiv:1404.7203v1): Verified five self-correcting typographical details across the 37-page manuscript: (1) Section 2.2 (p. 4, Equation 6) writes the sub-Gaussian tail exponent as -n t^2 / (2 sigma^2) whereas Proposition 1 (p. 19) uses isotropic rows cov(s_i) = I_n (so that the 1/sqrt(m) normalization is applied inside S^T S / m); (2) Section 4.1 (p. 18, Equations 44-45) and Section 4.2 (p. 19, Lemma 3, Equation 47) omit the 1/m normalization factor on S^T S in (1/2)||S A e_hat||_2^2 and <u, (S^T S - I) v> (which is explicitly included in Lemma 1's definitions of Z_1(AK) and Z_2(AK) in Equations 41a-41b on p. 17); (3) In Section 4.2.2 (p. 20), Equation (51a) prints W(V) instead of W(U_+), the text below (51c) omits 1/sqrt(m) on 4 c_1 W(U_+), Equation (52) prints |u^T Q u| on the left-hand side instead of sup_{v in V_+} |u^T Q v| (and omits 1/sqrt(m), which is restored in Equation 55 on p. 21), and Equation (53) prints W(V) instead of W(U_+); (4) Section 3.6 (p. 17, Corollary 7, Equation 40) prints the unsquared operator norm |||A_g|||_op in the numerator instead of |||A_g|||_op^2 (needed to match the quadratic scaling of gamma_{k,G}^-(A) and to reduce to max_j ||a_j||_2^2 / gamma_k^-(A) in Equation 15 when |G| = d, M = 1); and (5) Section 5.2 (p. 25, Equation 65) writes Z(Y) = sup_{y in Y} |y^T (A^T S^T S A / m - I) y| with -I instead of -A^T A (corrected to R = A^T S^T S A / m - A^T A in the proof of Lemma 9 on pp. 26-27).
• All 37 pages of the full-text PDF of Pilanci & Wainwright (2014/2015, IEEE Trans. Inf. Theory 61(9):5096-5115, arXiv:1404.7203v1) were read. Constructed numerical checks in research/discovery/randomized-sketches-convex-programs-sharp-guarantees-boundaries.py verify (1) Lemma 1 deterministic tangent-cone error and cost approximation bounds (lhs error ratio 0.2739 <= 2 Z_2/Z_1 = 0.9340, f(x_hat) = 52.749 <= 183.528, approx ratio 1.0750) and Corollary 1 vanishing mutual information per symbol (0.4257 at n = 200 vs. 0.02128 at n = 4000), (2) Corollary 4 noiseless compressed sensing exact recovery via sketched denoising (error 1.669e-15), folded-noise denoising approximation ratio (1.7371), and Corollary 5 dual squared-hinge SVM simplex sketching approximation ratio (1.4377), and (3) Lemma 13 support-function inequality phi_1(X) <= 3 phi_0(X) across 90 random matrices (max ratio 1.9737 <= 2 <= 3) and Lemma 8 Equation (84) convex-hull difference quadratic-form bound across 50 random convex combinations.