An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

• URL: http://arxiv.org/abs/2608.02594v1
• Date: Mon, 03 Aug 2026 17:58:00 GMT
• Title: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
• Abstract summary: We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
• Score: 42.540924632302925
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.

Related papers

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Hypothesis Selection: A High Probability Conundrum [18.424488719261984]
  We present an algorithm for finding a hypothesis whose total variation distance to $P$ is comparable to that of the nearest hypothesis in $mathcalH$.<n>We also study hypothesis selection in three alternative settings, resolving or making progress on several open questions from prior works.
  arXiv  Detail & Related papers  (2025-09-03T21:44:48Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  It is shown for the first time that this assumption is not required for convergence and finer results.<n>Rates of convergence are obtained for the standard algorithm and for estimates obtained via the averaging technique of Polyak and Ruppert.<n>Results from numerical experiments illustrate that $beta_theta$ may be large due to a combination of multiplicative noise and Markovian memory.
  arXiv  Detail & Related papers  (2024-05-28T05:11:05Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  We show that in fact $tildeO(fracdepsilon+frac1epsilon2)$ data points are also sufficient. We further generalize the result and show that a similar upper bound holds for all convex bodies.
  arXiv  Detail & Related papers  (2023-11-09T14:29:25Z)
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
  The proximal gradient method (PSGD) is one of the state-of-the-art approaches for composite-type problems.<n>In this paper, we present a simple variant of PSGD based on Robinsons map.
  arXiv  Detail & Related papers  (2023-05-10T01:12:11Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  Decentralized optimization problem $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n.
  arXiv  Detail & Related papers  (2022-10-25T11:37:11Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  We consider linear prediction with a convex Lipschitz loss, or more generally, convex optimization problems of generalized linear form. We show that in this setting, early iteration stopped Gradient Descent (GD), without any explicit regularization or projection, ensures excess error at most $epsilon$. But instead of uniform convergence in a norm ball, which we show can guarantee suboptimal learning using $Theta (1/epsilon4)$ samples, we rely on uniform convergence in a distribution-dependent ball.
  arXiv  Detail & Related papers  (2022-02-27T09:41:43Z)
• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
  The paper concerns the $d$-dimensional recursion approximation, $$theta_n+1= theta_n + alpha_n + 1 f(theta_n, Phi_n+1) The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3) An example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometrical
  arXiv  Detail & Related papers  (2021-10-27T13:38:25Z)
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence [0.0]
  This paper recasts Fast Incremental Expectation Maximization (FIEM) and other incremental EM type algorithms in the em Approximation within EM framework. We provide nonasymptotic bounds for the convergence in expectation as a function of the number of examples $n$ and of the maximal number of iterations $kmax$.
  arXiv  Detail & Related papers  (2020-12-29T09:11:42Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.