The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

• URL: http://arxiv.org/abs/2205.09727v1
• Date: Thu, 19 May 2022 17:39:29 GMT
• Title: The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
• Authors: Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
• Abstract summary: This paper aims to make a rigorous connection between the different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness. Results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools.
• Score: 73.1090889521313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorous connection between the seemingly different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.

Related papers

• Estimating Shape Distances on Neural Representations with Limited Samples [5.959815242044236]
  We develop a rigorous statistical theory for high-dimensional shape estimation. We show that this estimator achieves lower bias than on neurals simulation data, particularly in high-dimensional settings.
  arXiv  Detail & Related papers  (2023-10-09T14:16:34Z)
• Energy Discrepancies: A Score-Independent Loss for Energy-Based Models [20.250792836049882]
  We propose a novel loss function called Energy Discrepancy (ED) which does not rely on the computation of scores or expensive Markov chain Monte Carlo. We show that ED approaches the explicit score matching and negative log-likelihood loss under different limits, effectively interpolating between both.
  arXiv  Detail & Related papers  (2023-07-12T19:51:49Z)
• Divergence Frontiers for Generative Models: Sample Complexity, Quantization Level, and Frontier Integral [58.434753643798224]
  Divergence frontiers have been proposed as an evaluation framework for generative models. We establish non-asymptotic bounds on the sample complexity of the plug-in estimator of divergence frontiers. We also augment the divergence frontier framework by investigating the statistical performance of smoothed distribution estimators.
  arXiv  Detail & Related papers  (2021-06-15T06:26:25Z)
• Physics-Guided Discovery of Highly Nonlinear Parametric Partial Differential Equations [29.181177365252925]
  Partial differential equations (PDEs) that fit scientific data can represent physical laws with explainable mechanisms. We propose a novel physics-guided learning method, which encodes observation knowledge and incorporates basic physical principles and laws. Experiments show that our proposed method is more robust against data noise, and can reduce the estimation error by a large margin.
  arXiv  Detail & Related papers  (2021-06-02T11:24:49Z)
• GELATO: Geometrically Enriched Latent Model for Offline Reinforcement Learning [54.291331971813364]
  offline reinforcement learning approaches can be divided into proximal and uncertainty-aware methods. In this work, we demonstrate the benefit of combining the two in a latent variational model. Our proposed metrics measure both the quality of out of distribution samples as well as the discrepancy of examples in the data.
  arXiv  Detail & Related papers  (2021-02-22T19:42:40Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Reintroducing Straight-Through Estimators as Principled Methods for Stochastic Binary Networks [85.94999581306827]
  Training neural networks with binary weights and activations is a challenging problem due to the lack of gradients and difficulty of optimization over discrete weights. Many successful experimental results have been achieved with empirical straight-through (ST) approaches. At the same time, ST methods can be truly derived as estimators in the binary network (SBN) model with Bernoulli weights.
  arXiv  Detail & Related papers  (2020-06-11T23:58:18Z)
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation [105.33409035876691]
  This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. We design a novel structured tensor low-rank norm tailored to MVSC. We show that the proposed method outperforms state-of-the-art methods to a significant extent.
  arXiv  Detail & Related papers  (2020-04-30T11:52:12Z)
• Community Detection and Stochastic Block Models [20.058330327502503]
  The geometric block model (SBM) is widely employed as a canonical model to study clustering and community detection. It provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in statistics and data science. This book surveys the recent developments that establish the fundamental limits for community detection in the SBM.
  arXiv  Detail & Related papers  (2017-03-29T17:21:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.