arXiv research

Paper studies statistical-computational trade-offs in tensor PCA and related problems.

Greedy training of recursive partitioning estimators faces a computational barrier when the true function doesn't satisfy a specific property.

Lower bounds show density estimation requires linear samples or query time.

We study the generalization properties of ridge regression with random features in the statistical learning framework. We show for the first time that $O(1/\sqrt{n})$ learning bounds can be achieved with only $O(\sqrt{n}\log n)$ random features rather than $O({n})$ as suggested by previous results. Further, we prove fa…

This article is the rejoinder for the paper "Probabilistic Integration: A Role in Statistical Computation?" to appear in Statistical Science with discussion. We would first like to thank the reviewers and many of our colleagues who helped shape this paper, the editor for selecting our paper for discussion, and of cours…

Sobolev quantities (norms, inner products, and distances) of probability density functions are important in the theory of nonparametric statistics, but have rarely been used in practice, partly due to a lack of practical estimators. They also include, as special cases, $L^2$ quantities which are used in many applicatio…

Statistical-computational gap found in aligning multiple Gaussian graphs.

New algorithms learn multi-index models via harmonic analysis, achieving statistical and computational trade-offs.

Improved statistical computation through efficient matrix sampling.

Random Fourier features (RFF) represent one of the most popular and wide-spread techniques in machine learning to scale up kernel algorithms. Despite the numerous successful applications of RFFs, unfortunately, quite little is understood theoretically on their optimality and limitations of their performance. Only recen…

New methods solve tensor-on-tensor regression with unknown rank, revealing benefits of over-parameterization.

New insights link diverse statistical problems via secret leakage planted clique.

New computational lower bounds for clustering and related problems.

Noise Sensitivity Exponent controls statistical-computational gaps in learning.

Paper proposes efficient methods for high-order clustering in tensor block models.

New method improves approximate inference for Bayesian models.

New method uses almost orthonormal bases to prove low-degree lower bounds in complex statistical models.

A research frontier has emerged in scientific computation, wherein numerical error is regarded as a source of epistemic uncertainty that can be modelled. This raises several statistical challenges, including the design of statistical methods that enable the coherent propagation of probabilities through a (possibly dete…

Paper connects free-energy and low-degree hardness in high-dimensional statistics.

Develops methods to estimate high rank tensors from noisy data.

Optimal design for multinomial logit models improves assortment selection efficiency.

Survey on using low-degree polynomials to assess statistical tasks complexity.

EFI automates statistical inference for big data.

Missing data imputation (MDI) is a fundamental problem in many scientific disciplines. Popular methods for MDI use global statistics computed from the entire data set (e.g., the feature-wise medians), or build predictive models operating independently on every instance. In this paper we propose a more general framework…

New study shows limits of low-degree algorithms in finding large independent sets in sparse hypergraphs.

How should statistical procedures be designed so as to be scalable computationally to the massive datasets that are increasingly the norm? When coupled with the requirement that an answer to an inferential question be delivered within a certain time budget, this question has significant repercussions for the field of s…

Estimation under missing data shows computational and statistical limits for Gaussian data.

The paper tackles optimal level set estimation in crowdsourcing and tournaments.

New algorithm recovers sparse binary vectors from generalized linear measurements efficiently.

First DP algorithm for Wasserstein barycenters on private data.

Recent advances in cryptography promise to enable secure statistical computation on encrypted data, whereby a limited set of operations can be carried out without the need to first decrypt. We review these homomorphic encryption schemes in a manner accessible to statisticians and machine learners, focusing on pertinent…

This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detection-recovery gap and a universality principle for these gaps. A main feature of our approach is to ma…

Estimates isotonic functions under unknown permutations, achieving optimal statistical and computational efficiency.

A statistical framework for removing unwanted data domains in machine learning.

Deep learning identifies functional primitives in stroke rehabilitation.

New method explains computational barriers in high-dimensional statistical models.

Study potential computational gaps in symmetric binary perceptrons using fl-RDT.

Efficiently transforms Gaussian data to simulate various target distributions.

ParK efficiently solves kernel ridge regression for large datasets.

Unified approach to tensor PCA and related problems using tensor cumulants.

In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique (PC) con…

New insights into binary perceptron reveal phase transitions and algorithmic thresholds.

This paper connects ultrametric overlap gap properties to parametric RDT for symmetric binary perceptrons.

New insights into statistical and computational limits for mixed sparse linear regression.

New data structure identifies close match from multiple distributions.

TSCI estimates treatment effects using machine learning and data-adaptive methods for invalid instruments.

Bayesian nonparametrics adapt model complexity to diverse datasets.

We provide a general framework for characterizing the trade-off between accuracy and robustness in supervised learning. We propose a method and define quantities to characterize the trade-off between accuracy and robustness for a given architecture, and provide theoretical insight into the trade-off. Specifically we in…