A General Framework for Computational Lower Bounds in Nontrivial Norm Approximation
This work addresses the challenge of certifying computational hardness in norm approximation for researchers in theoretical computer science and machine learning, providing evidence of a genuine barrier rather than technical limitations.
The paper tackles the problem of proving computational lower bounds for approximating nontrivial norms by introducing a framework that converts reverse detection-estimation gaps into hardness certifications, and applies it to show that approximating the spectral norm of symmetric tensors requires distortion at least p^{d/4-1/2}/polylog(p) under low-degree constraints, matching known upper bounds up to polylog factors.
In this note, we propose a general framework for proving computational lower bounds in norm approximation by leveraging a reverse detection--estimation gap. The starting point is a testing problem together with an estimator whose error is significantly smaller than the corresponding computational detection threshold. We show that such a gap yields a lower bound on the approximation distortion achievable by any algorithm in the underlying computational class. In this way, reverse detection--estimation gaps can be turned into a general mechanism for certifying the hardness of approximating nontrivial norms. We apply this framework to the spectral norm of order-$d$ symmetric tensors in $\mathbb{R}^{p^d}$. Using a recently established low-degree hardness result for detecting nonzero high-order cumulant tensors, together with an efficiently computable estimator whose error is below the low-degree detection threshold, we prove that any degree-$D$ low-degree algorithm with $D \le c_d(\log p)^2$ must incur distortion at least $p^{d/4-1/2}/\operatorname{polylog}(p)$ for the tensor spectral norm. Under the low-degree conjecture, the same conclusion extends to all polynomial-time algorithms. In several important settings, this lower bound matches the best known upper bounds up to polylogarithmic factors, suggesting that the exponent $d/4-1/2$ captures a genuine computational barrier. Our results provide evidence that the difficulty of approximating tensor spectral norm is not merely an artifact of existing techniques, but reflects a broader computational barrier.