Computational Complexity of Statistical Problems Workshop

I will discuss recent progress on the theory of Markov chain mixing times via the spectral independence framework. Through examples, I will describe intimate connections with statistical physics, the geometry of polynomials, and more. Finally, as an application, I will describe recent advances on our understanding of the uniform distribution over proper colorings of graphs.

I will discuss recent progress on the theory of Markov chain mixing times via the spectral independence framework. Through examples, I will describe intimate connections with statistical physics, the geometry of polynomials, and more. Finally, as an application, I will describe recent advances on our understanding of the uniform distribution over proper colorings of graphs.

I will introduce the cluster expansion, a classical tool from statistical physics used to prove absence of phase transition and describe the phase diagram of spin models on lattices. I'll then show how the cluster expansion can be applied in algorithmic and statistical settings to design efficient sampling algorithms and compute statistical indistinguishability thresholds.

We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian~\cite{FK01}. The previous best algorithms for this model succeed if the planted clique has size at least \(n^{2/3}\) in a graph with \(n\) vertices (Mehta, Mckenzie, Trevisan, 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching \(n^{1/2}\) -- the information-theoretic threshold in the semi-random model~\cite{steinhardt2017does} and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. Our algorithms are based on higher constant degree sum-of-squares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in \emph{unbalanced} bipartite Erdős--Rényi random graphs into algorithms for semi-random planted clique. The use of a higher-constant degree sum-of-squares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size \(k=o(n^2/3)\). We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree-polynomials model. The talk is based on a joint work with Rares-Darius Buhai and Pravesh K. Kothari.

In many problems in modern statistics and machine learning, it is often of interest to establish that a first order method on a non-convex risk function eventually enters a region of local strong convexity. In this talk, I will present an asymptotic comparison inequality, which we call the Sudakov-Fernique post-AMP inequality, which, in a certain class of problems involving a GOE matrix, is able to probe properties of an optimization landscape locally around the iterates of an approximate message passing (AMP) algorithm. As an example of its use, I will describe a new proof of a result in Celentano, Fan, Mei (2021), which establishes that the so-called TAP free energy in the Z2-synchronization problem is locally convex in the region to which AMP converges. As a consequence, the proof also confirms a conjecture of El Alaoui, Montanari, Sellke (2022) that their algorithm efficiently samples from the Sherrington-Kirkpatrick Gibbs measure throughout the "easy" regime.

The Gaussian mixture block model is a simple generative model for networks: to generate a sample, we associate each node with a latent feature vector sampled from a mixture of Gaussians, and we add an edge between nodes if and only if their feature vectors are sufficiently similar. The different components of the Gaussian mixture represent the fact that there may be several types of nodes with different distributions over features -- for example, in a social network each component represents the different attributes of a distinct community. In this talk I will discuss recent results on the performance of spectral clustering algorithms on networks sampled from high-dimensional Gaussian mixture block models, where the dimension of the latent feature vectors grows as the size of the network goes to infinity. Our results merely begin to sketch out the information-computation landscape for clustering in these models, and I will make an effort to emphasize open questions. Based on joint work with Shuangping Li.

In this talk, we will focus on beyond worst-case sequential prediction. In particular, we will focus on the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Traditional algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading to erroneous predictions, whereas, assuming fully adversarial data leads to very pessimistic bounds that are often vacuous in practice. To mitigate this, we will introduce a new model of sequential prediction that sits between the purely stochastic and fully adversarial settings by allowing the learner to abstain from making a prediction at no cost on adversarial examples. Assuming access to the marginal distribution on the non-adversarial examples, we will present a learner whose error scales with the VC dimension (mirroring the stochastic setting) of the hypothesis class, as opposed to the Littlestone dimension which characterizes the fully adversarial setting. Furthermore, we will design learners for certain special hypothesis classes including VC dimension 1 classes, which work even in the absence of access to the marginal distribution. We will conclude with several open questions and plausible connections of our framework with existing models. This is based on joint work with Steve Hanneke, Shay Moran, and Abhishek Shetty.

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples. This talk is based on joint work with Sam Hopkins, Gautam Kamath, and Mahbod Majid.

One form of rigorous evidence for computational hardness of statistical problems is low-degree lower bounds, i.e. provable failure of any algorithm that can be expressed as a low-degree multivariate polynomial in the observations. Inspired by sum-of-squares, low-degree lower bounds were first introduced in the context of distinguishing a "planted" distribution from an iid "null" distribution. I will give an overview of some new techniques that allow us to prove low-degree lower bounds in more complicated settings, including "planted-versus-planted" testing, estimation problems, and tensor decomposition.