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

Paper solves outlier robust mean estimation near breakdown point.

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 …

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

New algorithm estimates transport maps with nearly optimal error.

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

New perspective on Heegaard splittings using square complexes and combinatorial measurements.

New bounds on homological eigenvalues relate to Weil-Petersson length.

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

We consider the question of existence of ramified covers over P_1 matching certain prescribed ramification conditions. This problem has already been faced in a number of papers, but we discuss alternative approaches for an existence proof, involving elliptic curves and universal ramified covers with signature. We also …

New flag-no-square 4-manifolds discovered with unique triangulations.

We prove the Chern-Weil formula for SU(n+1)-singular connections over the complement of an embedded oriented surface in smooth four manifolds. The expression of the representation of a number as a sum of nonvanishing squares is given in terms of the representations of a number as a sum of squares. Using the number theo…

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 …

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

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…

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…

Improves accuracy of SMCI estimators without expanding sum regions.

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.

Counterexample shows Ito integrand needn't be locally square integrable.

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.

This letter presents an improved version of diffusion least mean ppower (LMP) algorithm for distributed estimation. Instead of sum of mean square errors, a weighted sum of mean square error is defined as the cost function for global and local cost functions of a network of sensors. The weight coefficients are updated b…

New proof of four squares theorem using projective geometry.

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 …

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

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

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

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…

KSOS improves kernel learning for dynamical systems via global optimization.

Cross validation residuals are well known for the ordinary least squares model. Here leave-M-out cross validation is extended to generalised least squares. The relationship between cross validation residuals and Cook's distance is demonstrated, in terms of an approximation to the difference in the generalised residual …

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…

Algorithm finds a subspace minimizing distances to inliers with outliers.

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

Three algorithms improve starting solutions for clustering problems.

We study the map degrees between quasitoric 4-manifolds. Our results rely on Theorems proved by Duan and Wang. We determine the set D (M, N) of all possible map degrees from M to N when M and N are certain quasitoric 4-manifolds. The obtained sets of integers are interesting, e. g. those representable as the sum of two…

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.

In this paper, we prove conformal positive mass theorems for asymptotically flat manifolds with charge. We apply conformal relations to show that if the conformal sum of scalar curvature is not less than the norm square of electric field and electric density, the sum of the mass will not less than the modulus of total …

GradaGrad adapts learning rate non-monotonically, overcoming AdaGrad's step size decrease.

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…