arXiv research

Paper solves outlier robust mean estimation near breakdown point.

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 …

New algorithms learn graph structures privately, matching best results.

New algorithm estimates transport maps with nearly optimal error.

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

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

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

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

KSOS improves kernel learning for dynamical systems via global optimization.

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

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…

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

Efficiently constructs prediction bands with minimal assumptions.

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

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. …

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…

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

In a recent note [8], the author provides a counterexample to the global convergence of what his work refers to as "the DSOS and SDSOS hierarchies" for polynomial optimization problems (POPs) and purports that this refutes claims in our extended abstract [4] and slides in [3]. The goal of this paper is to clarify that …

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

This work improves graph inference using the degree-4 sum-of-squares hierarchy.

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

The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the {\it correct target clustering} of the samples according to which component distribution they were generated from. For a clustering pr…

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…

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

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…

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

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 …

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…

Algorithm learns Gaussian mixtures robust to outliers.

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…

New algorithm solves large cardinality-constrained clustering problems.

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…

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

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

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…

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

Privacy improves robustness in statistical estimation.

New method improves solving combinatorial optimization problems with smoothed policies.

Nearly all Gaussian points in high dimensions lie on a common ellipsoid.

In this paper we prove local analytic hypoellipticity for a degenerate sum of squares of complex vector fields generalizing those of Kohn in "Hypoellipticity and Loss of Derivatives". Kohn's article is to appear in the Annals of Mathematics with an appendix by Derridj and Tartakoff proving local analyticity in that cas…

We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a significantly lower number of constraints compared to popular MIP models based on cycle elimination constraint…

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 …

Three algorithms improve starting solutions for clustering problems.

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

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…

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

Triangular map is a recent construct in probability theory that allows one to transform any source probability density function to any target density function. Based on triangular maps, we propose a general framework for high-dimensional density estimation, by specifying one-dimensional transformations (equivalently co…

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