arXiv research

Statistical-computational gap found in aligning multiple Gaussian graphs.

Noise Sensitivity Exponent controls statistical-computational gaps in learning.

New computational lower bounds for clustering and related problems.

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.

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

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

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

Develops methods to estimate high rank tensors from noisy data.

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

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…

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

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

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.

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

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…

We consider the weakly supervised binary classification problem where the labels are randomly flipped with probability $1- α$. Although there exist numerous algorithms for this problem, it remains theoretically unexplored how the statistical accuracies and computational efficiency of these algorithms depend on the degr…

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

Improved statistical computation through efficient matrix sampling.

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

Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.

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

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

Efficiently transforms Gaussian data to simulate various target distributions.

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

Develops a new tensor model for clustering with degree correction.

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

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 proposes efficient methods for high-order clustering in tensor block models.

New algorithm clusters Gaussian mixtures with unknown covariance efficiently.

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

QAOA matches classical tensor power iteration in spiked tensor model recovery.

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…

Optimal design for multinomial logit models improves assortment selection efficiency.

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…

The pair-matching problem appears in many applications where one wants to discover good matches between pairs of entities or individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and obs…

Paper develops inference methods for low-rank tensors without debiasing.

We study the fundamental tradeoffs between computational tractability and statistical accuracy for a general family of hypothesis testing problems with combinatorial structures. Based upon an oracle model of computation, which captures the interactions between algorithms and data, we establish a general lower bound tha…

New lower bounds show sparse recovery is hard even with multiple preconditioners.

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…

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…

Deep learning identifies functional primitives in stroke rehabilitation.

ParK efficiently solves kernel ridge regression for large datasets.

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…