mlsanityData to 14 Oct 2026

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

arXiv 2605.25303 ↗First posted 24 May 2026cs.DS cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

The 2 rightarrow q norm of a matrix X ∈ ℝn × d is defined as lVert X rVert2 rightarrow q = suplVert v rVert2 = 1 lVert Xv rVertq. 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~ao, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than 2^√log n, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a d1/4-approximation as a baseline. For the important special case of q = 4, prior work of Guth, Maldague, and Urschel (SIAM Matrix Analysis and Applications'25) can be combined with known sparsification techniques to give a d1/6-approximation. We improve over these results by polynomial factors, giving a d1/8-approximation. 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 45 references that are in the map. First posted on arXiv 24 May 2026.

Builds on

23 of 45 references.

References · 23

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  4. 2016Learning from Untrusted Datacited by 90
  5. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  6. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  7. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  8. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  9. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  10. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  11. 2015Simple, Efficient, and Neural Algorithms for Sparse Codingcited by 37
  12. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
11 more
  1. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  2. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  3. 2019How Hard Is Robust Mean Estimation?cited by 16
  4. 2014Sum-of-squares proofs and the quest toward optimal algorithmscited by 12
  5. 2013Rounding Sum-of-Squares Relaxationscited by 11
  6. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  7. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  8. 2018Towards Learning Sparsely Used Dictionaries with Arbitrary Supportscited by 2
  9. 2015Estimating operator norms using covering netscited by 1
  10. 2023On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPscited by 1
  11. 2024Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Latticescited by 1

Built on by

Not cited yet.