Given the computational cost and technical expertise required to train machine learning
models, users may delegate the task of learning to a service provider. Delegation of learning …

These notes survey and explore an emerging method, which we call the low-degree
method, for understanding statistical-versus-computational tradeoffs in high-dimensional …

Inference problems with conjectured statistical-computational gaps are ubiquitous
throughout modern statistics, computer science, statistical physics and discrete probability …

A precise high-dimensional asymptotic theory for boosting and minimum-l1-norm
interpolated classifiers Page 1 The Annals of Statistics 2022, Vol. 50, No. 3, 1669–1695 …

Computational barriers to estimation from low-degree polynomials Page 1 The Annals of
Statistics 2022, Vol. 50, No. 3, 1833–1858 https://doi.org/10.1214/22-AOS2179 © Institute of …

Researchers currently use a number of approaches to predict and substantiate information-
computation gaps in high-dimensional statistical estimation problems. A prominent …

In the group testing problem, which goes back to the work of Dorfman (1943), we aim to
identify a small set of $ k\sim n^\theta $ infected individuals out of a population size $ n …

Abstract The Random Geometric Graph (RGG) is a random graph model for network data
with an underlying spatial representation. Geometry endows RGGs with a rich dependence …

We study the computational cost of recovering a unit-norm sparse principal component x∈
R n planted in a random matrix, in either the Wigner or Wishart spiked model (observing …

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be
viewed as a random constraint satisfaction problem with a high degree of connectivity. The …