arXiv research

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

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

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…

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

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…

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 tools in nonlinear random matrices improve understanding of the Sum of Squares hierarchy.

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

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…

We propose an estimator for the mean of a random vector in $\mathbb{R}^d$ that can be computed in time $O(n^4+n^2d)$ for $n$ i.i.d.~samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we mak…

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

Survey on using low-degree polynomials to assess statistical tasks complexity.

Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.

New algorithms learn from untrusted batches with improved efficiency.

New algorithms learn graph structures privately, matching best results.

Paper improves variational inference on Boolean hypercube using quantum methods.

Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we con…

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

We discuss the relation between knot polynomials and the KP hierarchy. Mainly, we study the scaling 1-hook property of the coloured Alexander polynomial: $\mathcal{A}^\mathcal{K}_R(q)=\mathcal{A}^\mathcal{K}_{[1]}(q^{\vert R\vert})$ for all 1-hook Young diagrams $R$. Via the Kontsevich construction, it is reformulated …

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

Lasso method applied to polynomial models with hierarchy constraints.

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

This study shows the moment-SOS hierarchy converges in polynomial optimization over product of spheres.

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 develop fast spectral algorithms for tensor decomposition that match the robustness guarantees of the best known polynomial-time algorithms for this problem based on the sum-of-squares (SOS) semidefinite programming hierarchy. Our algorithms can decompose a 4-tensor with $n$-dimensional orthonormal components in the…

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…

Given a large data matrix $A\in\mathbb{R}^{n\times n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix $A_{{\sf Q},{\sf Q}}$ whose entries have marginal distribution $A_{ij}\sim P_1\neq P_0$. As …

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

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

Maximum A posteriori Probability (MAP) inference in graphical models amounts to solving a graph-structured combinatorial optimization problem. Popular inference algorithms such as belief propagation (BP) and generalized belief propagation (GBP) are intimately related to linear programming (LP) relaxation within the She…

Paper proves BGW tau-function can be represented as Q-polynomials.

We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors $\boldsymbol x \in \mathbb R^d$, $r$ hidden units with weights $\{\boldsymbol w_i\}_{1\le i \le r}$ and output $y\in \mathbb R$, i.e., $y=\sum_{i=1}^r σ( \boldsymbol w_i…

Efficient algorithm for tensor PCA with improved time complexity.

Proves a formula for Kontsevich-Witten tau-function using Schur Q-polynomials.

Algorithm learns Gaussian mixtures robust to outliers.

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m \geq n$) from examples of the form \[ y = Ax + e, \] where $x$ is a random vector in $\mathbb R^m$ with at most $τm$ nonzero coordinates, and $e$ is a random noise vector in …

New integrable deformations for topological hierarchies from Frobenius manifolds.

We introduce two families of soliton hierarchies: the twisted hierarchies associated to symmetric spaces. The Lax pairs of these two hierarchies are Laurent polynomials in the spectral variable. Our constructions gives a hierarchy of commuting flows for the generalized sine-Gordon equation (GSGE), which is the Gauss-Co…

The paper studies SDP feasibility and sos ranks for specific polynomials.

New algorithm estimates transport maps with nearly optimal error.

The modified Korteweg-de Vries hierarchy (mKdV) is derived by imposing isometry and isoenergy conditions on a moduli space of plane loops. The conditions are compared to the constraints that define Euler's elastica. Moreover, the conditions are shown to be constraints on the curvature and other invariants of the loops …

New algorithm for robust regression with subgaussian error bound.

New algorithm recovers sparse signals from linearly sparse dictionaries efficiently.

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

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…

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

Algorithm distinguishes Gaussian mixtures from pure Gaussians in quasi-polynomial time.