Research map / Learning theory and algorithms / Sample complexity
An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a generalized Franz-Parisi (GFP) hardness criterion that optimizes the overlap event under a group symmetry and proves it is equivalent to statistical query (SQ) hardness under a mild correlation assumption, yielding simplified and new SQ lower bounds.
Problem
Connecting the annealed Franz-Parisi hardness criterion (which is tied to low-degree lower bounds only for Gaussian additive models) with SQ lower bounds for statistical detection problems across a broader class of models.
Approach
Replace the Euclidean overlap event in the FP criterion with an optimized, group-invariant overlap event defined via likelihood-ratio correlations rho_G(u,v); under a mild pointwise/averaged correlation inequality, this GFP criterion is equivalent to SQ hardness.
Key results
- Main theorem: under the group-correlation assumption, SQ hardness (q,m) implies GFP hardness (Theta(q), Theta(m), O(1)) and GFP hardness implies SQ hardness (m^{Theta(m_IT)}, m^{1-o(1)}), so the two criteria coincide when m_IT = omega(log n).
- New SQ lower bounds are derived for mixed sparse linear regression and for alpha-slice convex truncation, the latter with sample size near n/alpha^2 up to log factors.
- An explicit two-point example is constructed where GFP hardness holds but FP hardness fails, showing the Euclidean overlap can be inadequate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize the overlap event subject to group invariance instead of fixing Euclidean overlap | Franz-Parisi hardness criterion · Detection tasks satisfying the paper's assumption | Scope of hardness characterization | Helped |
| Use the optimized overlap criterion instead of the original Euclidean-overlap FP criterion | Two-point-prior detection task · Two-point-prior detection task | Hardness characterization | Helped |
| Use GFP-to-SQ equivalence for mixed sparse linear regression | Mixed sparse linear regression · Conjecturally hard regime | SQ hardness | Helped |
| Apply the GFP-to-SQ framework to convex truncation | Convex truncation detection · α-Convex Truncation | SQ lower-bound sample complexity | Helped |
| Use the original Euclidean-overlap FP criterion instead of the optimized overlap | Two-point-prior detection task · Two-point-prior detection task | FP hardness | Hurt |
Surprising findings
- The FP criterion can be easy while GFP is hard: a constructed model satisfies the assumption and is FP-easy yet GFP-hard, hence SQ-hard.
Limitations
- Equivalence requires the group-correlation assumption and a non-trivial information-theoretic threshold m_IT growing with n.
- Bounds deteriorate with the group size |G|; infinite groups need an extra hypercontractivity assumption.
Experimental setup
Baselines: Franz-Parisi criterion (Bandeira et al. 2022) low-degree polynomial lower bounds
Builds on: Franz-Parisi criterion (Bandeira et al. 2022) low-degree polynomial lower bounds Brennan et al. SQ-LD equivalence
Closest papers by meaning
- The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics (NeurIPS 2022 · similarity 0.90)
- SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions (NeurIPS 2023 · similarity 0.86)
- Statistical Query Lower Bounds for List-Decodable Linear Regression (NeurIPS 2021 · similarity 0.85)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.85)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.83)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.