arXiv research

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

KSOS improves kernel learning for dynamical systems via global optimization.

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

New algorithm estimates transport maps with nearly optimal error.

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 method finds global minima using function evaluations and kernel approximations.

Motivated by the study of Hörmander's sums-of-squares operators and their generalizations, we define the convolution algebra of transverse distributions associated to a singular foliation. We prove that this algebra is represented as continuous linear operators on the spaces of smooth functions and generalized function…

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…

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.

Outlier detection methods have become increasingly relevant in recent years due to increased security concerns and because of its vast application to different fields. Recently, Pauwels and Lasserre (2016) noticed that the sublevel sets of the inverse Christoffel function accurately depict the shape of a cloud of data …

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

Paper solves outlier robust mean estimation near breakdown point.

The paper shows how multi-task learning in neural networks is similar to kernel regression and Hilbert spaces.

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

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 method improves solving combinatorial optimization problems with smoothed policies.

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

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

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…

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…

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…

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

Cluster analysis is an unsupervised learning strategy that can be employed to identify subgroups of observations in data sets of unknown structure. This strategy is particularly useful for analyzing high-dimensional data such as microarray gene expression data. Many clustering methods are available, but it is challengi…

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…

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.

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…

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

Three algorithms improve starting solutions for clustering problems.

High dimensional nonparametric regression is an inherently difficult problem with known lower bounds depending exponentially in dimension. A popular strategy to alleviate this curse of dimensionality has been to use additive models of \emph{first order}, which model the regression function as a sum of independent funct…

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

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

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

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…

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

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

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…

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

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

Algorithm learns Gaussian mixtures robust to outliers.

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…

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

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 …