Counterexamples to the Low-Degree Conjecture

• URL: http://arxiv.org/abs/2004.08454v1
• Date: Fri, 17 Apr 2020 21:08:11 GMT
• Title: Counterexamples to the Low-Degree Conjecture
• Authors: Justin Holmgren, Alexander S. Wein
• Abstract summary: A conjecture of Hopkins posits that for certain high-dimensional hypothesis testing problems, no-time algorithm can outperform so-called "simple statistics" This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs.
• Score: 80.3668228845075
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.

Related papers

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
  A central problem in the theory of machine learning is whether it is possible to efficiently find a consistent hypothesis i.e. which has zero error. We show that the general idea of our algorithm can even be extended to the case of weakly convex hypotheses.
  arXiv  Detail & Related papers  (2021-05-10T23:00:02Z)
• Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron [21.356438315715888]
  We consider the symmetric binary perceptron model, a simple model of neural networks. We establish several conjectures for this model. Our proof technique relies on a dense counter-part of the small graph conditioning method.
  arXiv  Detail & Related papers  (2021-02-25T18:39:08Z)
• On a conjecture regarding quantum hypothesis testing [0.0]
  In the classical case, the best achievable symmetric error exponent is simply the the best achievable symmetric error exponent corresponding to the "worst case pair" The conjecture -- raised several years ago -- is that this remains true in the quantum case, too. I consider a new special case, which on one hand is as "asymmetrical" as possible, yet still analytically computable.
  arXiv  Detail & Related papers  (2020-11-05T18:31:28Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift [9.853329403413701]
  We show that a simple negative drift theorem for multiplicative drift scenarios can simplify existing analyses. We discuss in more detail Lehre's (PPSN 2010) emphnegative drift in populations method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms.
  arXiv  Detail & Related papers  (2020-05-02T15:10:09Z)

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.