Cover Image

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Siyu, Misiakiewicz, Theodor, Zadik, Ilias, Zhang, Peiyuan
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Statistical Mechanics Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
by: Tsirkas, Konstantinos, et al.
Published: (2026)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

On the Hardness of Learning One Hidden Layer Neural Networks
by: Li, Shuchen, et al.
Published: (2024)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

A non-asymptotic theory of Kernel Ridge Regression: deterministic equivalents, test error, and GCV estimator
by: Misiakiewicz, Theodor, et al.
Published: (2024)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
by: Zhao, Haimeng, et al.
Published: (2025)

Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis
by: Latourelle-Vigeant, Hugo, et al.
Published: (2026)

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
by: Diakonikolas, Ilias, et al.
Published: (2024)

Review and Prospect of Algebraic Research in Equivalent Framework between Statistical Mechanics and Machine Learning Theory
by: Watanabe, Sumio
Published: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
by: Hu, Fangjun, et al.
Published: (2026)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime
by: Hu, Hong, et al.
Published: (2024)

Transfer Learning Beyond Bounded Density Ratios
by: Kalavasis, Alkis, et al.
Published: (2024)

Learning single-index models via harmonic decomposition
by: Joshi, Nirmit, et al.
Published: (2025)

Stochastic thermodynamics of computation
by: Wolpert, David H.
Published: (2019)

Learning High-dimensional Gaussians from Censored Data
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
by: Wein, Alexander S.
Published: (2025)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

Causal Discovery under Latent Class Confounding
by: Mazaheri, Bijan, et al.
Published: (2023)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Low degree conjecture implies sharp computational thresholds in stochastic block model
by: Ding, Jingqiu, et al.
Published: (2025)

Lower Bounds on the Size of Markov Equivalence Classes
by: Jahn, Erik, et al.
Published: (2025)

Statistics of Min-max Normalized Eigenvalues in Random Matrices
by: Nakada, Hyakka, et al.
Published: (2025)

Laws of thermodynamics for exponential families
by: Balsubramani, Akshay
Published: (2025)

Susceptibilities and Patterning: A Primer on Linear Response in Bayesian Learning
by: Elliott, Chris, et al.
Published: (2026)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
by: Lou, Mengqi, et al.
Published: (2025)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
by: Bresler, Guy, et al.
Published: (2025)

When does Gaussian equivalence fail and how to fix it: Non-universal behavior of random features with quadratic scaling
by: Wen, Garrett G., et al.
Published: (2025)

Near-Optimal Learning and Planning in Separated Latent MDPs
by: Chen, Fan, et al.
Published: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

Information-Geometric Decomposition of Generalization Error in Unsupervised Learning
by: Kim, Gilhan
Published: (2026)

A Bayesian Proof and Interpretation of Talagrand's Majorizing Measure Theorem
by: Zadik, Ilias
Published: (2026)

Sliding down the stairs: how correlated latent variables accelerate learning with neural networks
by: Bardone, Lorenzo, et al.
Published: (2024)

A renormalization-group inspired lattice-based framework for piecewise generalized linear models
by: Chang, Joshua C.
Published: (2026)

Information-Theoretic Bounds and Task-Centric Learning Complexity for Real-World Dynamic Nonlinear Systems
by: Bulusu, Sri Satish Krishna Chaitanya, et al.
Published: (2025)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

Efficient witnessing and testing of magic in mixed quantum states
by: Haug, Tobias, et al.
Published: (2025)

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
by: Gao, Xun, et al.
Published: (2021)