arXiv research

New algorithms learn graph structures privately, matching best results.

Estimation is the computational task of recovering a hidden parameter $x$ associated with a distribution $D_x$, given a measurement $y$ sampled from the distribution. High dimensional estimation problems arise naturally in statistics, machine learning, and complexity theory. Many high dimensional estimation problems ca…

New framework reduces sum-of-squares proof degree, speeding up clustering and robust moment estimation.

Paper solves outlier robust mean estimation near breakdown point.

Polynomial-time algorithm estimates edge density of random graphs with privacy and robustness.

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new …

New algorithms recover signals robustly against outliers and heavy-tailed noise.

We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-$3$ tensor $T$ of the form $T = τ\cdot v_0^{\otimes 3} + A$, where $τ\geq 0$ is a signal-to-noise ratio, $v_0$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover th…

Efficiently estimates prediction error in regression with Gaussian covariates under privacy constraints.

New algorithm estimates transport maps with nearly optimal error.

We obtain the first polynomial-time algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown 3-tensor with $r$ incoherent, orthogonal components in $\mathbb R^n$ from $r\cdot \tilde O(n^{1.5})$ randomly observed entries of the tensor…

Polynomial-time algorithm estimates mean with bounded covariance using differential privacy.

The paper develops sum-of-squares relaxations for computing $f$-divergences.

Three algorithms improve starting solutions for clustering problems.

Algorithm estimates mixtures of arbitrary Gaussians robustly in presence of corruptions.

New method clusters non-spherical Gaussian mixtures with fewer samples and time.

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also sho…

In the noisy tensor completion problem we observe $m$ entries (whose location is chosen uniformly at random) from an unknown $n_1 \times n_2 \times n_3$ tensor $T$. We assume that $T$ is entry-wise close to being rank $r$. Our goal is to fill in its missing entries using as few observations as possible. Let $n = \max(n…

Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to $n^{\lfloor p/2 \rfloor}$ for a $p$-th order tensor in $\mathbb{R}^{n^p}$. Previously no efficient algorithm can decompose 3rd order ten…

Hilbert's 17th problem asks that whether every nonnegative polynomial can be a sum of squares of rational functions. It has been answered affirmatively by Artin. However, the question as to whether a given nonnegative polynomial is a sum of squares of polynomials is still a central question in real algebraic geometry. …

New algorithm learns mixtures of any constant number of Gaussians robustly.

We study the problem of high-dimensional sparse mean estimation in the presence of an $ε$-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for rob…

Two spectral clustering methods for multi-layer networks are analyzed and compared.

Algorithm learns Gaussian mixtures robust to outliers.

New algorithms improve privacy in statistical estimation by making them robust.

Sum-of-Squares lower bound shows NGCA requires more samples than known algorithms.

Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.

This note optimizes distributions using kernel mean embeddings with a new parameterization.

SOS programming verifies MTW tensor non-negativity for optimal transport maps.

In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear …

This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the {\em Sparse Principal Component Analysis} (Sparse PCA) problem, and the family of {\em Sum-of-Squares} (SoS, aka Lasserre/…

New algorithms learn from untrusted batches with improved efficiency.

Paper introduces a new kernel model for PSD-valued functions with theoretical guarantees and applications.

New tools in nonlinear random matrices improve understanding of the Sum of Squares hierarchy.

New method finds global minima using function evaluations and kernel approximations.

This work addresses privacy in Bayesian estimation, achieving near-optimal error rates.

New algorithm finds corrupted vertices in graphs with few queries.

We study tensor completion in the agnostic setting. In the classical tensor completion problem, we receive $n$ entries of an unknown rank-$r$ tensor and wish to exactly complete the remaining entries. In agnostic tensor completion, we make no assumption on the rank of the unknown tensor, but attempt to predict unknown …

Robustly clusters mixtures of Gaussians even with outliers.

In order to model entanglements of polymers in a confined region, we consider the linking numbers and writhes of cycles in random linear embeddings of complete graphs in a cube. Our main results are that for a random linear embedding of $K_n$ in a cube, the mean sum of squared linking numbers and the mean sum of square…

For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (ap…

Privacy improves robustness in statistical estimation.

Minimum sum-of-squares clustering (MSSC) is a widely used clustering model, of which the popular K-means algorithm constitutes a local minimizer. It is well known that the solutions of K-means can be arbitrarily distant from the true MSSC global optimum, and dozens of alternative heuristics have been proposed for this …

New algorithm estimates edge density of random graphs robustly, achieving optimal breakdown point.

New method certifies anti-concentration for various non-Gaussian distributions.

In this paper, we generalize the Cao-Yau's gradient estimate for the sum of squares of vector fields up to higher step under assumption of the generalized curvature-dimension inequality. With its applications, by deriving a curvature-dimension inequality, we are able to obtain the Li-Yau gradient estimate for the CR he…

We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than $1/2$ fraction of examples. For any $α< 1$, our algorithm takes as input a sample $\{(x_i,y_i)\}_{i \leq n}$ of $n$ linear equations where $αn$ of the equations satisfy $y_i = \l…

Explicitly constructed 3XOR instances hard for Sum-of-Squares hierarchy.