Survey on using low-degree polynomials to assess statistical tasks complexity.
problem Understanding the complexity of statistical tasks using polynomial functions.
method Applying low-degree polynomials to measure the complexity of statistical tasks, including detection, recovery, and estimation.
result Low-degree polynomials provide a framework to predict and explain statistical-computational tradeoffs.
New findings on computational limits for estimating hidden structures.
problem Estimating hidden structures in noisy data.
method Use of low-degree polynomials as a restricted model of computation.
result Established low-degree hardness of recovery problems for easy detection problems.
Study disproves conjecture about low-degree polynomials in hypothesis testing.
problem Conjecture about limitations of polynomial-time algorithms in hypothesis testing.
method Used counterexamples to refute the conjecture and modified the conjecture to rule out the counterexample.
result Disproved conjecture about limitations of low-degree polynomials in hypothesis testing.
New evidence shows computational barriers in graphon estimation using low-degree polynomials.
problem Estimating graphons efficiently and accurately.
method Low-degree polynomials to analyze computational limits.
result Low-degree polynomial estimators cannot significantly outperform USVT in graphon estimation.
New work shows FP potential monotonicity equals low-degree polynomial estimators limits.
problem Establishing a precise mathematical relationship between statistical physics and polynomial estimators limits.
method Analyzing Gaussian additive models (GAMs) to show FP potential monotonicity equals low-degree polynomial estimators limits.
result For a broad family of Gaussian additive models, the power of low-degree polynomials is equivalent to the monotonicity of the annealed FP potential.
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
The paper explores how low-degree polynomials can detect shuffled linear regression models.
problem Detecting multivariate shuffled linear regression models from independent Gaussian random matrices.
method Investigates the effectiveness of low-degree polynomial algorithms for distinguishing the model from independent Gaussian random matrices.
result Establishes a phase transition phenomenon in the performance of low-degree polynomial algorithms for distinguishing the model.
Study efficient estimation of hidden subspaces in Gaussian Multi-index models.
problem Estimating hidden subspaces in Gaussian Multi-index models with low-dimensional projections.
method Introduced the generative leap exponent and developed an agnostic sequential estimation procedure using spectral U-statistics.
result Achieved optimal sample complexity of $n=Θ(d^{1 \vee \k/2})$ for efficient estimation.
New study shows low-degree polynomial algorithms struggle at clause densities close to Fix's.
problem Finding satisfying assignments in random k-SAT formulas at high clause densities.
method Analysis of low-degree polynomial algorithms and a new many-way overlap gap property.
result No efficient algorithms can find satisfying assignments at clause densities close to Fix's.
Paper proves first non-trivial PTF testing lower bounds for NGCA.
problem Proving lower bounds against PTF tests is challenging.
method Developed tools to prove PTF testing lower bounds for NGCA.
result First non-trivial PTF testing lower bounds for NGCA.
Study shows computational and statistical gaps in Gaussian Single-Index Models.
problem Statistical and computational trade-offs in high-dimensional regression problems.
method Analysis of SQ and LDP frameworks, partial-trace algorithm.
result Computational algorithms require significantly more samples than information-theoretic limits.
Detects dense subhypergraphs in random hypergraphs using low-degree polynomials.
problem Detecting a planted dense subhypergraph in a random hypergraph model.
method Degree-n^o(1) polynomials of adjacency tensor entries.
result Thresholds for detection in different density regimes.
Low-degree method fails to predict robust subspace recovery problem.
problem Predicting computational tractability of robust subspace recovery problem.
method Low-degree polynomial framework, anti-concentration properties.
result Low-degree method fails to predict computational tractability of robust subspace recovery problem even up to high degree.
New algorithms learn multi-index models via harmonic analysis, achieving statistical and computational trade-offs.
problem Learning multi-index models with unknown projections of input data.
method Exploiting the equivariance of the problem under the orthogonal group, we derive lower bounds and construct spectral algorithms based on harmonic tensor unfolding.
result Achieve statistical and computational trade-offs between sample and runtime complexity.
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
New findings on tensor decomposition complexity, showing polynomial functions can estimate the largest component under certain conditions.
problem The complexity of tensor decomposition, especially for low-degree polynomials.
method Modeling a slightly larger component in a random tensor decomposition and using polynomial functions to estimate it.
result Polynomial functions can accurately estimate the largest component when r ≪ n 3 / 2 r \ll n^{3/2} r ≪ n 3/2 but fail when r ≫ n 3 / 2 r \gg n^{3/2} r ≫ n 3/2 . New findings show that common optimization algorithms struggle with random problems.
problem Finding near-optimal solutions to random optimization problems.
method Low-degree polynomials, Boolean circuits, and Langevin dynamics.
result These algorithms fail to produce nearly optimal solutions with high probability.
Gradient Descent with Projection learns low-degree polynomials efficiently.
problem Learning low-degree spherical polynomials with neural networks.
method Over-parameterized two-layer neural network with Gradient Descent with Projection.
result Achieves nearly minimax optimal sample complexity and risk bound.
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
Study shows it's impossible to count communities without finding them.
problem Determining the number and sizes of communities in random graph models.
method Hypothesis testing between models with different community structures, using low-degree polynomial framework.
result Testing between two different planted distributions is as hard as finding the communities.
New algorithm learns PTFs with noisy data efficiently.
problem Learning low-degree PTFs with noisy data efficiently.
method Structural result and novel robust Chow vector estimation.
result PAC learns PTFs with nasty noise using efficient samples.
Study on estimating Gaussian mean with missing data in high dimensions.
problem Estimating Gaussian mean in high dimensions with missing data due to realizable contamination.
method Statistical Query model, Low-Degree Polynomials, PTF tests, and algorithms.
result Established information-computation gap and developed efficient algorithms.
Sublinear algorithms detect cliques in graphs with high probability.
problem Detecting a planted clique in random graphs efficiently.
method Non-adaptive low-degree polynomial queries of adjacency matrix entries.
result Sublinear time detection is possible for a specific range of clique sizes.
New method for estimating sparse means in noisy data.
problem Estimating the mean of a sparse distribution in the presence of outliers.
method Difference-of-Pairs Filtering technique for list-decodable sparse mean estimation.
result First sample and computationally efficient algorithm for list-decodable sparse mean estimation.
Paper explores limits of high-order clustering with planted structures.
problem Statistical and computational limits of high-order clustering with planted structures.
method Developed methods for detection and recovery of clusters, identified signal-to-noise ratio boundaries.
result Sharp boundaries of signal-to-noise ratio for statistical and computational feasibility.
Paper proposes a robust LPR method using similarity kernels.
problem Outliers and high-leverage points affect traditional LPR's accuracy.
method Integrates predictor and response variables in weighting mechanism using a conditional density kernel.
result Lower empirical bias compared to iterative robust LOWESS.
This article describes a multivariate polynomial regression method where the uncertainty of the input parameters are approximated with Gaussian distributions, derived from the central limit theorem for large weighted sums, directly from the training sample. The estimated uncertainties can be propagated into the optimal…
Unified approach to tensor PCA and related problems using tensor cumulants.
problem Statistical inference on invariant distributions, particularly tensor PCA.
method Definition and analysis of tensor cumulants to unify and extend previous results.
result Unified explanation of hardness and subexponential-time algorithms for tensor PCA.
New findings show transfer learning is possible even when density ratios are unbounded.
problem Transfer learning under unbounded density ratios.
method Low-degree polynomial estimators, general transfer inequality over R n \mathbb{R}^n R n . result Non-trivial transfer learning possible under mild assumptions, including log-concave measures.
New insights into statistical and computational limits for mixed sparse linear regression.
problem Recovering two sparse signals from noisy linear measurements.
method Analysis of low-degree polynomials and a simple thresholding algorithm.
result Identification of a smooth information-computation tradeoff and order-optimality of the thresholding algorithm.
Study on detecting and recovering hidden dense cycles in random graphs.
problem Detecting and recovering hidden dense cycles in random graphs.
method Information-theoretic analysis of thresholds for detection and recovery.
result Characterization of information-theoretic thresholds for detection and recovery.
New algorithm achieves optimal clustering for sparse centers with high dimensions.
problem Statistical and computational limits of clustering sparse centers with high dimensions.
method Sparse clustering algorithm based on sparse PCA.
result Achieves minimax optimal misclustering rate under certain conditions.
New algorithms find half-optimal independent sets in sparse graphs.
problem Finding large independent sets in sparse random graphs.
method Low-degree polynomial algorithms.
result Low-degree polynomial algorithms can find independent sets of half-optimal size.
New method explains computational barriers in high-dimensional statistical models.
problem Understanding detection-recovery gaps in high-dimensional inference.
method Combining algorithmic contiguity and cross-validation reduction to obtain conditional computational lower bounds.
result Mild control of low-degree advantage is sufficient to explain computational barriers for recovery.
New local-search methods close the gap in sparse tensor PCA.
problem Sparse tensor PCA underperforms compared to other methods.
method Proposes new local-search methods including greedy and random-threshold variants.
result Proves local-search methods close the gap to best known polynomial-time procedures.
Detection of dense cycles in graphs reveals a gap between easy detection and hard recovery.
problem Detecting and recovering dense cycles in Erdős-Rényi graphs.
method Characterization of computational thresholds for detection and recovery using low-degree polynomial algorithms.
result A gap exists between the detection and recovery thresholds for certain parameter regimes.
Let f : S d − 1 × S d − 1 → S f:\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}\to\mathbb{S} f : S d − 1 × S d − 1 → S be a function of the form f ( x , x ′ ) = g ( ⟨ x , x ′ ⟩ ) f(\mathbf{x},\mathbf{x}') = g(\langle\mathbf{x},\mathbf{x}'\rangle) f ( x , x ′ ) = g (⟨ x , x ′ ⟩) for g : [ − 1 , 1 ] → R g:[-1,1]\to \mathbb{R} g : [ − 1 , 1 ] → R . We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate $f…
High-dimensional kernel regression struggles due to rotational invariance.
problem Kernel ridge regression struggles in high dimensions due to rotational invariance.
method Analysis of kernel properties and their impact on high-dimensional data.
result Lower bound on generalization error for high-dimensional kernel regression.
Improved agnostic learning time via Gaussian surface area analysis.
problem Learning polynomial threshold functions under Gaussian marginals.
method Improvement of polynomial degree required for approximation.
result Near optimal bounds on agnostic learning complexity.
We study the problem of high-dimensional sparse mean estimation in the presence of an ε ε ε -fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for rob…
BPR matches NN accuracy in crop classification while being more transparent.
problem Lack of auditability and alignment with domain knowledge in neural networks for high-dimensional climate data.
method Bagged polynomial regression with random projections (BPR), averaging many low-degree polynomial models.
result BPR matches neural networks in accuracy but is more transparent.
We show how to efficiently project a vector onto the top principal components of a matrix, without explicitly computing these components. Specifically, we introduce an iterative algorithm that provably computes the projection using few calls to any black-box routine for ridge regression. By avoiding explicit principal …
Study reveals limits of detecting local geometry in random graphs.
problem Detecting local geometry in random graphs with hidden communities.
method Introduced model and used information-theoretic and computational limits to investigate detection.
result Detection threshold determined at d = Θ ~ ( k 2 ∨ k 6 / n 3 ) d = \widetildeΘ(k^2 \vee k^6/n^3) d = Θ ( k 2 ∨ k 6 / n 3 ) for fixed p p p . Optimized Franz-Parisi criterion matches SQ lower bounds for various statistical models.
problem Understanding computational hardness in statistical inference.
method Proposed and refined Franz-Parisi criterion, established equivalence with SQ lower bounds.
result Optimized Franz-Parisi criterion is equivalent to Statistical Query (SQ) lower bounds.
Optimizes ICA performance in high dimensions with computational constraints.
problem Statistical optimality and computational tractability in ICA.
method Characterization of optimal sample complexity, development of computationally tractable estimates.
result Optimal sample complexity is linear in dimensionality, quadratic with low-degree polynomial algorithms.
There has been a large amount of interest, both in the past and particularly recently, into the power of different families of universal approximators, e.g. ReLU networks, polynomials, rational functions. However, current research has focused almost exclusively on understanding this problem in a worst-case setting, e.g…
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least d Ω ( 1 / ε ) d^{Ω(1/ε)} d Ω ( 1/ ε ) for learning mixtures of bounded covariance Gaussians. New lower bounds show challenges in clustering in moderate dimensions.
problem Clustering points from mixtures of isotropic Gaussians in moderate dimensions.
method Established low-degree polynomial lower bounds and developed a novel non-spectral algorithm.
result New lower bounds reveal a 'non-parametric rate' in moderate dimensions.