pith. sign in

arxiv: 2605.25303 · v2 · pith:COVSR3J5new · submitted 2026-05-24 · 💻 cs.DS · cs.LG· math.ST· stat.ML· stat.TH

Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications

Samuel B. Hopkins , Stefan Tiegel This is my paper

Pith reviewed 2026-06-29 23:13 UTC · model grok-4.3

classification 💻 cs.DS cs.LGmath.STstat.MLstat.TH
keywords 2 to q normapproximation algorithmssum of squaresrobust estimationhypercontractivitymatrix normsclustering
0
0 comments X

The pith

Polynomial-time algorithms approximate the 2 to q norm better than the d to the 1/4 spectral baseline by polynomial factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives the first polynomial-time algorithms for approximating the 2 to q norm of a matrix that improve on the simple spectral guarantee of d to the 1/4 by polynomial amounts. For the case q equals 4 this produces a d to the 1/8 approximation factor. The same techniques also produce sum-of-squares certificates for the norm. These certificates yield improved algorithms for robust mean estimation, covariance estimation, regression, and clustering, provided only that the input satisfies a bound on its q-th moment. A reader would care because the norm directly encodes several long-standing problems in optimization and statistics, and prior polynomial-time methods either matched the baseline or required stronger assumptions on the data.

Core claim

We give polynomial-time multiplicative approximation algorithms for the 2 to q norm when q is greater than 2. These algorithms beat the baseline d to the 1/4 factor by polynomial amounts; the special case q equals 4 achieves a d to the 1/8 approximation. We also construct sum-of-squares certificates for the norm. The certificates directly imply improved algorithms for robust mean and covariance estimation, robust regression, and clustering when the data satisfies only a bound on its q-th moment.

What carries the argument

Sum-of-squares certificates for the 2 to q norm that certify improved approximation factors without extra assumptions on the matrix.

If this is right

  • Robust mean estimation algorithms improve under q-moment bounds.
  • Robust covariance estimation algorithms improve under q-moment bounds.
  • Robust regression algorithms improve under q-moment bounds.
  • Clustering algorithms improve under q-moment bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The sum-of-squares approach might extend to give polynomial improvements for related problems such as small set expansion.
  • Similar certificates could apply to other hypercontractive quantities arising in quantum information.
  • The algorithms could be tested on synthetic matrices with known norms to measure the practical gap between d to the 1/8 and d to the 1/4.

Load-bearing premise

The input matrix satisfies a bound on its q-th moment.

What would settle it

An explicit family of matrices X in R to the n by d with q equals 4 for which the algorithm returns a value more than a constant factor worse than d to the 1/8 times the true 2 to q norm.

read the original abstract

The $2 \rightarrow q$ norm of a matrix $X \in \mathbb{R}^{n \times d}$ is defined as $\lVert X \rVert_{2 \rightarrow q} = \sup_{\lVert v \rVert_2 = 1} \lVert Xv \rVert_q$. We give polynomial-time multiplicative approximation algorithms for this norm when $q > 2$ (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what approximation factors we can achieve for this problem in polynomial time, even though such approximations have significant downstream consequences. Barak, Brand\~{a}o, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than $2^{\sqrt{\log n}}$, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a $d^{1/4}$-approximation as a baseline. We give, to the best of our knowledge, the first polynomial-time approximation algorithm beating this baseline by polynomial factors. For the important special case of $q = 4$ it achieves a $d^{1/8}$-approximation. All previous algorithms required additional assumptions on $X$, or only surpassed the baseline for small values of $n$. Moreover, we construct sum-of-squares certificates for the $2 \rightarrow q$ norm. This directly implies improved algorithms for robust mean and covariance estimation, robust regression, and clustering, when the data only satisfies a bound on its $q$-th moment.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper presents polynomial-time multiplicative approximation algorithms for the 2→q norm of an n×d matrix (sup over unit v of ||Xv||_q) when q>2. For the case q=4 it achieves a d^{1/8}-approximation, improving polynomially on the d^{1/4} spectral baseline without extra assumptions on X. The work also constructs sum-of-squares certificates for the norm, which are used to obtain improved algorithms for robust mean/covariance estimation, robust regression, and clustering under a q-th moment bound on the data.

Significance. If the algorithmic claims and SOS constructions hold, the result supplies the first polynomial-factor improvement over the long-standing spectral baseline for this norm, which is connected to Small Set Expansion, Best Separable State, and other problems. The explicit SOS certificates are a concrete strength that directly yields downstream robust estimation algorithms under only a moment bound; this is a clear advance over prior work that either required stronger assumptions or only improved the baseline for small n.

minor comments (3)
  1. [Abstract] The abstract states that the algorithm 'beats this baseline by polynomial factors' but does not specify the degree of the polynomial or the dependence on n and d; adding this detail would strengthen the claim.
  2. The definition of the 2→q norm uses sup over ||v||_2=1; it would help to clarify whether the algorithm returns a vector achieving the approximation or only the norm value.
  3. [Introduction] The manuscript cites Barak et al. (FOCS'12) for the 2^{√log n} hardness; a brief comparison of the new approximation factor against this hardness threshold in the introduction would aid context.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a new polynomial-time algorithm achieving a d^{1/8}-approximation for the 2→q norm (q=4) that improves on the independent spectral d^{1/4} baseline, along with SOS certificates for downstream robust estimation tasks under a q-moment bound. The hardness result 2^{\sqrt{\log n}} is cited from external prior work (Barak et al., FOCS'12) as context rather than contradicted or reduced to. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described claims; the derivation chain relies on independent algorithmic constructions and certificates that do not reduce to the inputs by construction. This is the expected honest non-finding for a paper whose central result is an explicit algorithmic improvement with external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Central algorithmic claim rests on an unspecified construction whose details are absent from the abstract. Applications rest on the domain assumption of a q-moment bound on the data.

axioms (1)
  • domain assumption Input data satisfies a bound on its q-th moment.
    Explicitly stated as the condition under which the SOS certificates yield improved robust estimation and clustering algorithms.

pith-pipeline@v0.9.1-grok · 5884 in / 1321 out tokens · 32572 ms · 2026-06-29T23:13:26.342138+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 3 canonical work pages · 3 internal anchors

  1. [1]

    563--572

    Sanjeev Arora, Boaz Barak, and David Steurer, Subexponential algorithms for unique games and related problems, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563--572

    2010

  2. [2]

    2, 535--561

    Rados aw Adamczak, Alexander Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann, Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, Journal of the American Mathematical Society 23 (2010), no. 2, 535--561

    2010

  3. [3]

    307--326

    Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications, Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012, pp. 307--326

    2012

  4. [4]

    1629--1642

    Mitali Bafna, Boaz Barak, Pravesh K Kothari, Tselil Schramm, and David Steurer, Playing unique games on certified small-set expanders, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1629--1642

    2021

  5. [5]

    1008--1019

    Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani, Weak decoupling, polynomial folds and approximate optimization over the sphere, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 1008--1019

    2017

  6. [6]

    1, 132--155

    Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani, Inapproximability of matrix norms, SIAM Journal on Computing 52 (2023), no. 1, 132--155

    2023

  7. [7]

    1295--1303

    Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, and Xuandi Ren, Inapproximability of finding sparse vectors in codes, subspaces, and lattices, 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2025, pp. 1295--1303

    2025

  8. [8]

    Fernando GSL Brandao and Aram W Harrow, Estimating operator norms using covering nets, arXiv preprint arXiv:1509.05065 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  9. [9]

    Punyashloka Biswal, Hypercontractivity and its applications, arXiv preprint arXiv:1101.2913 (2011)

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  10. [10]

    Boaz Barak, Jonathan A Kelner, and David Steurer, Rounding sum-of-squares relaxations, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, pp. 31--40

    2014

  11. [11]

    102--115

    Ainesh Bakshi and Adarsh Prasad, Robust linear regression: Optimal rates in polynomial time, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 102--115

    2021

  12. [12]

    Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, arXiv preprint arXiv:1404.5236 (2014)

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  13. [13]

    497--511

    Aditya Bhaskara and Aravindan Vijayaraghavan, Approximating matrix p-norms, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2011, pp. 497--511

    2011

  14. [14]

    Moses Charikar, Jacob Steinhardt, and Gregory Valiant, Learning from untrusted data, Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, 2017, pp. 47--60

    2017

  15. [15]

    1689--1700

    Ilias Diakonikolas, Samuel B Hopkins, Ankit Pensia, and Stefan Tiegel, Sos certifiability of subgaussian distributions and its algorithmic applications, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, pp. 1689--1700

    2025

  16. [16]

    Ilias Diakonikolas and Daniel M Kane, Algorithmic high-dimensional robust statistics, Cambridge university press, 2023

    2023

  17. [17]

    655--664

    Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robust estimators in high dimensions without the computational intractability, 57th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2016, pp. 655--664

    2016

  18. [18]

    999--1008

    , Being robust (in high dimensions) can be practical, International Conference on Machine Learning, PMLR, 2017, pp. 999--1008

    2017

  19. [19]

    4703--4763

    Ilias Diakonikolas, Daniel M Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas, Robust sparse mean estimation via sum of squares, Conference on Learning Theory, PMLR, 2022, pp. 4703--4763

    2022

  20. [20]

    1262--1275

    Ilias Diakonikolas, Daniel M Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian, Clustering mixture models in almost-linear time via list-decodable mean estimation, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1262--1275

    2022

  21. [21]

    Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 73--84

    2017

  22. [22]

    Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan, Tester-learners for halfspaces: Universal algorithms, Advances in Neural Information Processing Systems 36 (2023), 10145--10169

    2023

  23. [23]

    Suprovat Ghoshal and Euiwoong Lee, On lifting integrality gaps to sseh hardness for globally constrained csps, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023, pp. 26--36

    2023

  24. [24]

    3, 2080--2092

    Larry Guth, Dominique Maldague, and John Urschel, Estimating the matrix pq norm, SIAM Journal on Matrix Analysis and Applications 46 (2025), no. 3, 2080--2092

    2025

  25. [25]

    1021--1034

    Samuel B Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1021--1034

    2018

  26. [26]

    1649--1682

    , How hard is robust mean estimation?, Conference on learning theory, PMLR, 2019, pp. 1649--1682

    2019

  27. [27]

    1, 1--43

    Aram W Harrow and Ashley Montanaro, Testing product states, quantum merlin-arthur games and tensor optimization, Journal of the ACM (JACM) 60 (2013), no. 1, 1--43

    2013

  28. [28]

    2, 423--468

    Aram W Harrow, Anand Natarajan, and Xiaodi Wu, Limitations of semidefinite programs for separable states and entangled games, Communications in Mathematical Physics 366 (2019), no. 2, 423--468

    2019

  29. [29]

    1420--1430

    Adam Klivans, Pravesh K Kothari, and Raghu Meka, Efficient algorithms for outlier-robust regression, Conference On Learning Theory, PMLR, 2018, pp. 1420--1430

    2018

  30. [30]

    1035--1046

    Pravesh K Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum of squares, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1035--1046

    2018

  31. [31]

    665--674

    Kevin A Lai, Anup B Rao, and Santosh Vempala, Agnostic estimation of mean and covariance, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 665--674

    2016

  32. [32]

    1-3, 141--160

    Yu Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization methods and software 9 (1998), no. 1-3, 141--160

    1998

  33. [33]

    245--254

    Prasad Raghavendra, Optimal algorithms and inapproximability results for every csp?, Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, pp. 245--254

    2008

  34. [34]

    755--764

    Prasad Raghavendra and David Steurer, Graph expansion and the unique games conjecture, Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 755--764

    2010

  35. [35]

    631--640

    Prasad Raghavendra, David Steurer, and Prasad Tetali, Approximations for the isoperimetric and spectral profile of graphs and related parameters, Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 631--640

    2010

  36. [36]

    Prasad Raghavendra, David Steurer, and Madhur Tulsiani, Reductions between expansion problems, 2012 IEEE 27th Conference on Computational Complexity, IEEE, 2012, pp. 64--73

    2012

  37. [37]

    Jacob Steinhardt, Moses Charikar, and Gregory Valiant, Resilience: A criterion for learning in the presence of arbitrary outliers, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2018, pp. 45--1

    2018

  38. [38]

    374--393

    David Steurer and Stefan Tiegel, Sos degree reduction with applications to clustering and robust moment estimation, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 374--393

    2021

  39. [39]

    Daureen Steinberg, Computation of matrix norms with applications to robust optimization, Research thesis, Technion-Israel University of Technology 2 (2005)

    2005

  40. [40]

    Roman Vershynin, Approximating the moments of marginals of high-dimensional distributions

  41. [41]

    47, Cambridge university press, 2018

    , High-dimensional probability: An introduction with applications in data science, vol. 47, Cambridge university press, 2018

    2018

  42. [42]

    2, 315--323

    Yi Yu, Tengyao Wang, and Richard J Samworth, A useful variant of the davis--kahan theorem for statisticians, Biometrika 102 (2015), no. 2, 315--323

    2015