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 …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Sum of Squares (SOS)”
SOS programming verifies MTW tensor non-negativity for optimal transport maps.
problem Verifying MTW tensor non-negativity for general cost functions is difficult.
method Sum-of-Squares (SOS) programming for verifying and approximating MTW non-negativity.
result SOS programming provides certificates and approximations of MTW non-negativity.
New tools in nonlinear random matrices improve understanding of the Sum of Squares hierarchy.
problem Improving the Sum of Squares (SoS) hierarchy's performance on average-case problems.
method Developed new tools in nonlinear random matrices and applied them to analyze the SoS hierarchy.
result Subexponential-time SoS lower bounds for various problems, offering evidence for the low-degree likelihood ratio hypothesis.
New framework reduces sum-of-squares proof degree, speeding up clustering and robust moment estimation.
problem Sum-of-squares proof optimization and faster algorithms for clustering and robust moment estimation.
method Introducing new variables to reduce the degree of sum-of-squares proofs.
result Significantly faster algorithms for clustering and robust moment estimation with the same statistical guarantees.
Sum-of-Squares lower bound shows NGCA requires more samples than known algorithms.
problem Finding a non-Gaussian direction in a high-dimensional dataset.
method Sum-of-Squares (SoS) framework to prove lower bounds.
result First super-constant degree SoS lower bound for NGCA.
This work improves graph inference using the degree-4 sum-of-squares hierarchy.
problem Recovering ground-truth binary labelings from corrupted edge observations.
method Apply the degree-4 sum-of-squares hierarchy to a quadratic combinatorial optimization problem.
result The solution of the dual problem is related to edge weights of Johnson and Kneser graphs.
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcs.DS
Polynomial-time algorithm estimates mean with bounded covariance using differential privacy.
problem Estimating mean of a d-variate distribution with differential privacy constraints.
method Sum of Squares (SoS) exponential mechanism for polynomial-time differentially private estimation.
result First polynomial-time algorithm with samples for mean estimation under pure differential privacy.
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…
New proof of four squares theorem using projective geometry.
problem Proving every natural number is a sum of four squares.
method Projective differential geometry and modular forms.
result A new geometric approach to Lagrange's theorem.
Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.
problem Efficiently learning from subgaussian distributions in high dimensions.
method Universal constant and polynomial sum of squares (SoS) approach.
result Proves subgaussian distributions are SoS-certifiably subgaussian.
Explicitly constructed 3XOR instances hard for Sum-of-Squares hierarchy.
problem Hard instances for Sum-of-Squares hierarchy.
method Based on high-dimensional expanders (LSV complexes), using cosystolic expansion and local isoperimetric inequality.
result Constructs explicit 3XOR instances hard for levels of Sum-of-Squares hierarchy.
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…
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/…
SDP Feasibility Problems and sos Representation Ranks for OT-FKM Type Isoparametric Polynomialsmath.DG
The paper studies SDP feasibility and sos ranks for specific polynomials.
problem Characterizing sos representations of nonnegative polynomials.
method Explicit SDP formulation based on Clifford systems.
result Quantitative rank bounds for sos representations, with rigidity.
Estimation is the computational task of recovering a hidden parameter associated with a distribution , given a measurement sampled from the distribution. High dimensional estimation problems arise naturally in statistics, machine learning, and complexity theory. Many high dimensional estimation problems ca…
New CRB derived for curved models using extrinsic geometry.
problem Estimate curved statistical families accurately.
method Vector generalization of CRB with curvature correction using SDP and SOS relaxations.
result Directional curvature correction provides more accurate estimation.
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 …
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…
Universal tester-learner for halfspaces over structured distributions.
problem Learning halfspaces over a wide class of structured distributions.
method Uses a fully polynomial tester-learner based on hypercontractivity and sum-of-squares (SOS) programs.
result Achieves error on any labeled distribution that the tester accepts.
New method uses SoS densities and α-divergences for efficient sequential transport maps.
problem Efficiently generating samples from approximated densities.
method Sequential transport maps using Sum-of-Squares (SoS) densities and α-divergences.
result Convex optimization problems with efficient semidefinite programming solutions.
New algorithms learn graph structures privately, matching best results.
problem Private learning of graph structures with multiple blocks.
method Sum-of-squares relaxation and exponential mechanism for score function.
result Matches statistical utility of previous best non-private methods.
Given a large data matrix , we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution , or instead contains a principal submatrix whose entries have marginal distribution . As …
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.
problem Estimating mean in presence of adversarial outliers.
method Sum-of-Squares approach to optimize error rate efficiently.
result Achieves optimal error rate for all ε ∈ [0, 1/2).
Algorithm learns Gaussian mixtures robust to outliers.
problem Efficiently learn high-dimensional Gaussian mixtures with outliers.
method Sum-of-Squares based proofs to algorithms approach.
result Polynomial time algorithm for -mixture with pairwise separated components.
Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Pointcs.DS
New algorithm estimates edge density of random graphs robustly, achieving optimal breakdown point.
problem Estimating edge density of Erdős-Rényi graphs under adversarial edge manipulation.
method Sum-of-Squares (SoS) hierarchy, constructing constant-degree certificates for concentration.
result First polynomial-time algorithm with optimal breakdown point and matching error guarantees.
New findings on tensor decomposition complexity, showing polynomial functions can estimate the largest component under certain conditions.
problem The complexity of tensor decomposition, especially for low-degree polynomials.
method Modeling a slightly larger component in a random tensor decomposition and using polynomial functions to estimate it.
result Polynomial functions can accurately estimate the largest component when but fail when .
New algorithm for batch list-decodable linear regression with stronger guarantees.
problem Efficiently list-decoding linear regression with a fraction of corrupted batches.
method Uses higher-order moments and Sum-of-Squares (SoS) certification to achieve better guarantees.
result Achieves substantially smaller minimum batch size and final error, with optimal list size.
Polynomial-time algorithm estimates edge density of random graphs with privacy and robustness.
problem Estimating edge density of random graphs while maintaining privacy and robustness.
method Sum-of-squares algorithm for robust edge density estimation and reduction from privacy to robustness.
result Optimal error rate up to logarithmic factors, matching theoretical lower bounds.
FF algorithm uses goodness as a measure of input quality, derived from likelihood-ratio tests.
problem Training each layer locally with a goodness measure.
method FF algorithm uses a likelihood-ratio test to define goodness, which is the sum of squared activations normalized between layers.
result The goodness measure is a sufficient statistic for a likelihood-ratio test, explaining the FF algorithm's performance.
New algorithm estimates transport maps with nearly optimal error.
problem Estimating smooth transport maps efficiently and accurately.
method Solving semi-dual formulation of optimal transport with kernel sums-of-squares.
result Statistical error on maps nearly matches minimax lower-bounds.
Paper introduces a new kernel model for PSD-valued functions with theoretical guarantees and applications.
problem Enforcing positive semi-definiteness (PSD) in function models with good performance and theoretical guarantees.
method Kernel sum-of-squares model for PSD-valued functions, extending previous models for non-negative scalar functions.
result The model constitutes a universal approximator of PSD functions and can represent any smooth and strongly convex function.
New perspective on Heegaard splittings using square complexes and combinatorial measurements.
problem Measuring obstructions to Heegaard splittings in 3-manifolds.
method Square complexes and Guirardel's core, augmented Heegaard diagrams.
result Augmented Heegaard diagrams provide a new way to describe Heegaard splittings with desirable properties.
MOY calculus in type Dmath.QA
Defines a new link invariant for type D webs.
problem Invariants for framed unoriented links in type D.
method Positive state sum for type D webs, derived from quantum so(2N) modules.
result Relates to Reshetikhin-Turaev's invariant.
New bounds on homological eigenvalues relate to Weil-Petersson length.
problem Bounding growth of homological eigenvalues for pseudo-Anosov automorphisms.
method Established inequality linking homological Jensen square sum to Weil-Petersson translation length.
result Homological Jensen square sum grows at most linearly with covering degree compared to Weil-Petersson translation length.
The paper develops sum-of-squares relaxations for computing -divergences.
problem Computing -divergences from non-centered covariance matrices.
method Sum-of-squares relaxations for convex optimization.
result Sum-of-squares relaxations make computations tractable.
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 …
On flag-no-square -manifoldsmath.GT
New flag-no-square 4-manifolds discovered with unique triangulations.
problem Identifying 4-manifolds with specific triangulation properties.
method Introduced star-connected-sum operation to preserve flag-no-square property; derived new constructions.
result Found non-aspherical flag-no-square 4-manifolds, answering a question by Przytycki and Swiatkowski.
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
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 in a cube, the mean sum of squared linking numbers and the mean sum of square…
FF algorithm uses goodness as a likelihood-ratio test for scalar normalization.
problem Training each layer locally with scalar goodness.
method FF algorithm uses a likelihood-ratio test with squared goodness as the sufficient statistic.
result The FF algorithm generalizes to anisotropic and heavy-tailed populations.
This book introduces linear models and their theories rigorously.
problem Understanding linear models and their theories.
method Explains linear models from three perspectives, introduces maximum likelihood estimation, and proves least squares is the best unbiased linear model.
result Least squares is the best unbiased linear model in terms of mean squared error.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscs.DS
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.
problem Private regression with Gaussian covariates under differential privacy constraints.
method Sum-of-Squares framework combined with robust estimators.
result Sample-optimal private regression algorithm with optimal error rates.
In many high-dimensional estimation problems the main task consists in minimizing a cost function, which is often strongly non-convex when scanned in the space of parameters to be estimated. A standard solution to flatten the corresponding rough landscape consists in summing the losses associated to different data poin…
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 incoherent, orthogonal components in from randomly observed entries of the tensor…
New algorithms learn from untrusted batches with improved efficiency.
problem Learning from untrusted batches with adversarial responses.
method Sum-of-Squares hierarchy applied to robust mean estimation.
result Reduces sample complexity to polylogarithmic in for most natural distributions.