Computational Complexity of Statistical Problems Workshop

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.

Approximate message passing (AMP) is a family of iterative algorithms that are known to optimally solve many high-dimensional statistics optimization problems. In this talk, I will explain how to simulate a broad class of AMP algorithms in polynomial time using "local statistics hierarchy" semidefinite programs (SDPs), with the added benefit of robustness: the SDPs work even in the strong contamination model, when an unknown (but bounded) subset of the input data is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for problems where AMP is known to succeed. Based on joint work with Misha Ivkov.

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.

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.