arXiv research

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 algorithms learn graph structures privately, matching best results.

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 estimates transport maps with nearly optimal error.

Paper solves outlier robust mean estimation near breakdown point.

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

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 framework reduces sum-of-squares proof degree, speeding up clustering and robust moment estimation.

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…

KSOS improves kernel learning for dynamical systems via global optimization.

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 …

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…

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

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

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

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

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

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…

Efficiently constructs prediction bands with minimal assumptions.

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…

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

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…

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

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

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

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…

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

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

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

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

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

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

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

Bayesian method synthesizes barrier certificates for unknown systems with latent states.

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

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…

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

Three algorithms improve starting solutions for clustering problems.

New estimator avoids overfitting in convex regression.

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

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

Christoffel function characterizes the corruption a bounded-degree certificate cannot remove in robust halfspace learning.

The Ward error sum of squares hierarchical clustering method has been very widely used since its first description by Ward in a 1963 publication. It has also been generalized in various ways. However there are different interpretations in the literature and there are different implementations of the Ward agglomerative …

Whilst there are many approaches to detecting changes in mean for a univariate time-series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging. For example, simple binary segmentation procedures do no…

The popular cubic smoothing spline estimate of a regression function arises as the minimizer of the penalized sum of squares $\sum_j(Y_j - μ(t_j))^2 + λ\int_a^b [μ"(t)]^2 dt$, where the data are $t_j,Y_j$, $j=1,..., n$. The minimization is taken over an infinite-dimensional function space, the space of all functions wi…

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

Algorithm learns Gaussian mixtures robust to outliers.