Low-Rank Univariate Sum of Squares
Has No Spurious Local Minima
ICCOPT 2022

Chenyang Yuan (Joint with Benoı̂t Legat and Pablo Parrilo)MIT

Tuesday 26th July, 2022

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

1 / 14

Introduction
Semidefinite programming (SDP) is a powerful andexpressive convex optimization method
Positive semidefinite variable X ⪰ 0 + linear constraints
Solved in polynomial time with interior point methods(n ∼ 103 )Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

2 / 14

Introduction
Semidefinite programming (SDP) is a powerful andexpressive convex optimization method
Positive semidefinite variable X ⪰ 0 + linear constraints
Solved in polynomial time with interior point methods(n ∼ 103 )However: Success of deep learning shows that
Certain non-convex problems can be solved efficiently in practice with
first-order methods (n > 108 )Algorithms that scale linearly necessary for working with “big data”

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

2 / 14

Introduction
Semidefinite programming (SDP) is a powerful andexpressive convex optimization method
Positive semidefinite variable X ⪰ 0 + linear constraints
Solved in polynomial time with interior point methods(n ∼ 103 )However: Success of deep learning shows that
Certain non-convex problems can be solved efficiently in practice with
first-order methods (n > 108 )Algorithms that scale linearly necessary for working with “big data”
Can we apply these ideas to solving SDPs?

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

2 / 14

The Burer-Monteiro Method
Burer-Monteiro methods for solving SDPs factor PSD variable X = UU T , thenperform local optimization on non-convex unconstrained problem⟨Ai , X ⟩ = bi
X ⪰0

∀i

Feasible

Chenyang Yuan (MIT)X(⟨Ai , UU T ⟩ − bi )2

−→

min

⇐⇒

Optimum = 0

Ui

Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

3 / 14

The Burer-Monteiro Method
Burer-Monteiro methods for solving SDPs factor PSD variable X = UU T , thenperform local optimization on non-convex unconstrained problem⟨Ai , X ⟩ = bi
X ⪰0

∀i

Feasible

X(⟨Ai , UU T ⟩ − bi )2

−→

min

⇐⇒

Optimum = 0

Ui

May get stuck in local optimum (explicit counterexamples where second-order
critical point ̸= global minimum)

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

3 / 14

The Burer-Monteiro Method
Burer-Monteiro methods for solving SDPs factor PSD variable X = UU T , thenperform local optimization on non-convex unconstrained problem⟨Ai , X ⟩ = bi
X ⪰0

∀i

Feasible

X(⟨Ai , UU T ⟩ − bi )2

−→

min

⇐⇒

Optimum = 0

Ui

May get stuck in local optimum (explicit counterexamples where second-order
critical point ̸= global minimum)

OR

When is non-convexity benign?
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

3 / 14

The Burer-Monteiro Method
Burer-Monteiro methods for solving SDPs factor PSD variable X = UU T , thenperform local optimization on non-convex unconstrained problem⟨Ai , X ⟩ = bi
X ⪰0

∀i

Feasible

X(⟨Ai , UU T ⟩ − bi )2

−→

min

⇐⇒

Optimum = 0

Ui

May get stuck in local optimum (explicit counterexamples where second-order
critical point ̸= global minimum)

OR

When is non-convexity benign?
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

3 / 14

Related WorkSDP with m linear constraints, factorization X = UU ⊤ , where U ∈ Rn×r .

[BM05] Burer and Monteiro. “Local Minima and Convergence in Low-Rank Semidefinite Programming”. 2005.
[CM19] Cifuentes and Moitra. “Polynomial Time Guarantees for the Burer-Monteiro Method”. 2019.
[Bho+18] Bhojanapalli et al. “Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form”. 2018.
[GJZ17] Ge, Jin, and Zheng. “No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis”. 2017.
[BBV16] Bandeira, Boumal, and Voroninski. “On the low-rank approach for semidefinite programs arising in synchronization and community detection”.
2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
4 / 14

Related WorkSDP with m linear constraints, factorization X = UU ⊤ , where U ∈ Rn×r .
Second-order critical points =⇒ Global minima (non-convexity benign):r ≥ n [BM05] (explicit counterexamples exist for r = n − 1, m = n)√r ≳ m with smoothed analysis [CM19], determinant regularization [BM05]
or generic constraints [Bho+18]
r ≳ r ∗ , where r ∗ maximum possible rank of SDP solution (matrix sensing[GJZ17], rotational synchronization [BBV16])[BM05] Burer and Monteiro. “Local Minima and Convergence in Low-Rank Semidefinite Programming”. 2005.
[CM19] Cifuentes and Moitra. “Polynomial Time Guarantees for the Burer-Monteiro Method”. 2019.
[Bho+18] Bhojanapalli et al. “Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form”. 2018.
[GJZ17] Ge, Jin, and Zheng. “No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis”. 2017.
[BBV16] Bandeira, Boumal, and Voroninski. “On the low-rank approach for semidefinite programs arising in synchronization and community detection”.
2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
4 / 14

Related WorkSDP with m linear constraints, factorization X = UU ⊤ , where U ∈ Rn×r .
Second-order critical points =⇒ Global minima (non-convexity benign):r ≥ n [BM05] (explicit counterexamples exist for r = n − 1, m = n)√r ≳ m with smoothed analysis [CM19], determinant regularization [BM05]
or generic constraints [Bho+18]
r ≳ r ∗ , where r ∗ maximum possible rank of SDP solution (matrix sensing[GJZ17], rotational synchronization [BBV16])
Smaller r in factorization → less benign landscape[BM05] Burer and Monteiro. “Local Minima and Convergence in Low-Rank Semidefinite Programming”. 2005.
[CM19] Cifuentes and Moitra. “Polynomial Time Guarantees for the Burer-Monteiro Method”. 2019.
[Bho+18] Bhojanapalli et al. “Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form”. 2018.
[GJZ17] Ge, Jin, and Zheng. “No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis”. 2017.
[BBV16] Bandeira, Boumal, and Voroninski. “On the low-rank approach for semidefinite programs arising in synchronization and community detection”.
2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
4 / 14

Related WorkSDP with m linear constraints, factorization X = UU ⊤ , where U ∈ Rn×r .
Second-order critical points =⇒ Global minima (non-convexity benign):r ≥ n [BM05] (explicit counterexamples exist for r = n − 1, m = n)√r ≳ m with smoothed analysis [CM19], determinant regularization [BM05]
or generic constraints [Bho+18]
r ≳ r ∗ , where r ∗ maximum possible rank of SDP solution (matrix sensing[GJZ17], rotational synchronization [BBV16])
Smaller r in factorization → less benign landscapeCan we get do better if the SDP has special structure?
[BM05] Burer and Monteiro. “Local Minima and Convergence in Low-Rank Semidefinite Programming”. 2005.
[CM19] Cifuentes and Moitra. “Polynomial Time Guarantees for the Burer-Monteiro Method”. 2019.
[Bho+18] Bhojanapalli et al. “Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form”. 2018.
[GJZ17] Ge, Jin, and Zheng. “No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis”. 2017.
[BBV16] Bandeira, Boumal, and Voroninski. “On the low-rank approach for semidefinite programs arising in synchronization and community detection”.
2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
4 / 14

Sum of Squares Optimization
Given p(x), can we write it as a sum of squares?

p(x) =

Pr

i=1 ui (x)2

Certifies that p(x) ≥ 0, and can be formulated as a SDP:
p(x) = ⃗b(x)⊤ Q ⃗b(x),Q⪰0[Chu+16] Chua et al. “Gram spectrahedra”. 2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

5 / 14

Sum of Squares Optimization
Given p(x), can we write it as a sum of squares?

p(x) =

Pr

i=1 ui (x)2

Certifies that p(x) ≥ 0, and can be formulated as a SDP:
p(x) = ⃗b(x)⊤ Q ⃗b(x),Q⪰0

Q satisfying above constraints is called the Gram spectrahedron [Chu+16][Chu+16] Chua et al. “Gram spectrahedra”. 2016.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

5 / 14

Sum of Squares Optimization
Previous work: rank needed for benign non-convexity ∼ max rank of extreme
points of Gram spectrahedron
Can we do better?

[Sch22] Scheiderer. “Extreme points of Gram spectrahedra of binary forms”. 2022.
Image credit: Tae Roh and Lieven Vandenberghe. (2006) Discrete transforms, semidefinite programming and sum-of-squares representations of nonnegative
polynomials. SIAM J. on Optimization.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
6 / 14

Sum of Squares Optimization
Previous work: rank needed for benign non-convexity ∼ max rank of extreme
points of Gram spectrahedron
Can we do better?
Univariate (trigonometric) polynomials:

p(x) = a0 +2dX

ak cos(kx) x ∈ [0, 2π]

k=1Applications in signal processing, filter design andcontrol[Sch22] Scheiderer. “Extreme points of Gram spectrahedra of binary forms”. 2022.
Image credit: Tae Roh and Lieven Vandenberghe. (2006) Discrete transforms, semidefinite programming and sum-of-squares representations of nonnegative
polynomials. SIAM J. on Optimization.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
6 / 14

Sum of Squares Optimization
Previous work: rank needed for benign non-convexity ∼ max rank of extreme
points of Gram spectrahedron
Can we do better?
Univariate (trigonometric) polynomials:

p(x) = a0 +2dX

ak cos(kx) x ∈ [0, 2π]

k=1Applications in signal processing, filter design andcontrolGram spectrahedra has extreme points of all ranks: 2 ≤ r ≲√d [Sch22]

But always has rank-2 point! (Sum of 2 squares)[Sch22] Scheiderer. “Extreme points of Gram spectrahedra of binary forms”. 2022.
Image credit: Tae Roh and Lieven Vandenberghe. (2006) Discrete transforms, semidefinite programming and sum-of-squares representations of nonnegative
polynomials. SIAM J. on Optimization.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares
Tuesday 26th July, 2022
6 / 14

Contributions
Find sum of squares decomposition of p(x) by solving (equivalent to B-M):
min fp (u) = p(x) −u

Chenyang Yuan (MIT)2 2
i=1 ui (x)Pr

Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

7 / 14

Contributions
Find sum of squares decomposition of p(x) by solving (equivalent to B-M):
min fp (u) = p(x) −u

For any norm on polynomials, if fp (u) = 0,
decomposition of p(x).

Chenyang Yuan (MIT)2 2
i=1 ui (x)

Pr

P

2
i ui (x) is a sum of squares

Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

7 / 14

Contributions
Find sum of squares decomposition of p(x) by solving (equivalent to B-M):
min fp (u) = p(x) −u

For any norm on polynomials, if fp (u) = 0,
decomposition of p(x).

2 2
i=1 ui (x)

Pr

P

2
i ui (x) is a sum of squares

Theorem
For all nonnegative univariate polynomials p(x) ∈ R[x]2d and any r ≥ 2, if
u ∈ R[x]rd satisfies ∇fp (u) = 0 and ∇2 fp (u) ⪰ 0, then fp (u) = 0.

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

7 / 14

Contributions
Find sum of squares decomposition of p(x) by solving (equivalent to B-M):
min fp (u) = p(x) −u

For any norm on polynomials, if fp (u) = 0,
decomposition of p(x).

2 2
i=1 ui (x)

Pr

P

2
i ui (x) is a sum of squares

Theorem
For all nonnegative univariate polynomials p(x) ∈ R[x]2d and any r ≥ 2, if
u ∈ R[x]rd satisfies ∇fp (u) = 0 and ∇2 fp (u) ⪰ 0, then fp (u) = 0.

First-order methods find sum of squares decomposition(non-convexity benign)If we choose a suitable norm, ∇fp (u) can be computed inO(d log d) time using Fast Fourier Transforms (FFTs)
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

7 / 14

Proof Sketch
Define Sylvester map Au : R[x]rd → R[x]2d
Au (v) = A(u1 ,u2 ) ((v1 , v2 )) = u1 v1 + u2 v2

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

8 / 14

Proof Sketch
Define Sylvester map Au : R[x]rd → R[x]2d
Au (v) = A(u1 ,u2 ) ((v1 , v2 )) = u1 v1 + u2 v2Given an inner product ⟨·, ·⟩ on polynomials with associated norm ∥·∥:
fp (u) = u12 + u22 − p

2∇fp (u)(v) ∼ Au (v), u12 + u22 − p
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

8 / 14

Proof Sketch
Define Sylvester map Au : R[x]rd → R[x]2d
Au (v) = A(u1 ,u2 ) ((v1 , v2 )) = u1 v1 + u2 v2Given an inner product ⟨·, ·⟩ on polynomials with associated norm ∥·∥:
fp (u) = u12 + u22 − p

2∇fp (u)(v) ∼ Au (v), u12 + u22 − p
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥

Goal: For all u such that ∇fp (u)(v) = 0 and ∇2 fp (u)(v, v) ⪰ 0 for all v, showthat fp (u) = 0.

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

8 / 14

Proof Sketch
Define Sylvester map Au : R[x]rd → R[x]2d
Au (v) = A(u1 ,u2 ) ((v1 , v2 )) = u1 v1 + u2 v2Given an inner product ⟨·, ·⟩ on polynomials with associated norm ∥·∥:
fp (u) = u12 + u22 − p

2∇fp (u)(v) ∼ Au (v), u12 + u22 − p
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥

Goal: For all u such that ∇fp (u)(v) = 0 and ∇2 fp (u)(v, v) ⪰ 0 for all v, showthat fp (u) = 0.
To do so, for every p ∈ Σ[x]2d and u ∈ R[x]2d , find vi ∈ R[x]2d so that:∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi ) = − u12 + u22 − p

2= −fp (u)i=1Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

8 / 14

Geometric Interpretation∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi ) = − u12 + u22 − p

2= −fp (u)i=1

Our proof can be interpreted as finding a Positivstellensatz certificate of thiscondition for every u and p

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

9 / 14

Geometric Interpretation∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi ) = − u12 + u22 − p

2= −fp (u)i=1

Our proof can be interpreted as finding a Positivstellensatz certificate of thiscondition for every u and pp = σ(u)p ∈ Σ[x] | ∇2 fp (u) ⪰ 0{p ∈ R[x] | ∇fp (u) = 0}
Geometrically, we want to show that the only intersection between sets with zero
gradient and PSD hessian is when fp (u) = 0.

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

9 / 14

Geometric Interpretation∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi ) = − u12 + u22 − p

2= −fp (u)i=1

Our proof can be interpreted as finding a Positivstellensatz certificate of thiscondition for every u and pp = σ(u)p ∈ Σ[x] | ∇2 fp (u) ⪰ 0{p ∈ R[x] | ∇fp (u) = 0}
Geometrically, we want to show that the only intersection between sets with zero
gradient and PSD hessian is when fp (u) = 0.
For fixed u, these sets are convex (and can be represented by SDPs)!
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

9 / 14

Proof Sketch∇fp (u)(v) ∼ Au (v), u12 + u22 − p = 0
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥ ≥ 0− u12 + u22 − p2= ∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi )i=1

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

10 / 14

Proof Sketch∇fp (u)(v) ∼ Au (v), u12 + u22 − p = 0
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥ ≥ 0− u12 + u22 − p2= ∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi )i=1

Suppose u1 , u2 are coprime (true generically)

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

10 / 14

Proof Sketch∇fp (u)(v) ∼ Au (v), u12 + u22 − p = 0
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥ ≥ 0− u12 + u22 − p2= ∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi )i=1

Suppose u1 , u2 are coprime (true generically)Bézout’s lemma (Au is onto) =⇒ there exist v0 such that
Au (v0 ) = −(u12 + u22 − p) =⇒ ∇fp (u)(v0 ) = − u12 + u22 − p

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

2

Tuesday 26th July, 2022

10 / 14

Proof Sketch∇fp (u)(v) ∼ Au (v), u12 + u22 − p = 0
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥ ≥ 0− u12 + u22 − p2= ∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi )i=1

Suppose u1 , u2 are coprime (true generically)Bézout’s lemma (Au is onto) =⇒ there exist v0 such that2

Au (v0 ) = −(u12 + u22 − p) =⇒ ∇fp (u)(v0 ) = − u12 + u22 − pPSuppose u1 = u2 . If p(x) = 2 i si (x)2 , choose vi = (si , −si ), v0 = (−u1 , −u2 ):∇fp (u)(v0 ) = − u12 + u22 , u12 + u22 − pPk2i=1 ∇ fp (u)(vi , vi ) =Chenyang Yuan (MIT)p, u12 + u22 − p

Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

10 / 14

Proof Sketch∇fp (u)(v) ∼ Au (v), u12 + u22 − p = 0
2∇2 fp (u)(v, v) ∼ Av (v), u12 + u22 − p + ∥Au (v)∥ ≥ 0− u12 + u22 − p2= ∇fp (u)(v0 ) +kX∇2 fp (u)(vi , vi )i=1

Suppose u1 , u2 are coprime (true generically)Bézout’s lemma (Au is onto) =⇒ there exist v0 such that2

Au (v0 ) = −(u12 + u22 − p) =⇒ ∇fp (u)(v0 ) = − u12 + u22 − pPSuppose u1 = u2 . If p(x) = 2 i si (x)2 , choose vi = (si , −si ), v0 = (−u1 , −u2 ):∇fp (u)(v0 ) = − u12 + u22 , u12 + u22 − pPk2i=1 ∇ fp (u)(vi , vi ) =p, u12 + u22 − pMain technical result: how to interpolate between these two cases
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

10 / 14

Sampled Basis
Theorem holds for any inner product ⟨p(x), q(x)⟩ on polynomials, which should
we choose?

[LP04] Lofberg and Parrilo. “From Coefficients to Samples: A New Approach to SOS Optimization”. 2004.
[CP17] Cifuentes and Parrilo. “Sampling Algebraic Varieties for Sum of Squares Programs”. 2017.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

11 / 14

Sampled Basis
Theorem holds for any inner product ⟨p(x), q(x)⟩ on polynomials, which should
we choose?
Given p(x), q(x) of degree d, choose d + 1 points xk⟨p(x), q(x)⟩ =d+1
Xp(xk )q(xk ),2∥p(x)∥ =

k=1

d+1
X

p(xk )2

k=1
2

Valid inner product: when xk distinct, if ∥p(x)∥ = 0 then p(x) = 0.

[LP04] Lofberg and Parrilo. “From Coefficients to Samples: A New Approach to SOS Optimization”. 2004.
[CP17] Cifuentes and Parrilo. “Sampling Algebraic Varieties for Sum of Squares Programs”. 2017.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

11 / 14

Sampled Basis
Theorem holds for any inner product ⟨p(x), q(x)⟩ on polynomials, which should
we choose?
Given p(x), q(x) of degree d, choose d + 1 points xk⟨p(x), q(x)⟩ =d+1
Xp(xk )q(xk ),2∥p(x)∥ =

k=1

d+1
X

p(xk )2

k=1
2

Valid inner product: when xk distinct, if ∥p(x)∥ = 0 then p(x) = 0.
Sum of squares using a sampled/interpolation basis studied by [LP04] and [CP17].

[LP04] Lofberg and Parrilo. “From Coefficients to Samples: A New Approach to SOS Optimization”. 2004.
[CP17] Cifuentes and Parrilo. “Sampling Algebraic Varieties for Sum of Squares Programs”. 2017.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

11 / 14

Sampled Basis
Theorem holds for any inner product ⟨p(x), q(x)⟩ on polynomials, which should
we choose?
Given p(x), q(x) of degree d, choose d + 1 points xk⟨p(x), q(x)⟩ =d+1
Xp(xk )q(xk ),2∥p(x)∥ =

k=1

d+1
X

p(xk )2

k=1
2

Valid inner product: when xk distinct, if ∥p(x)∥ = 0 then p(x) = 0.
Sum of squares using a sampled/interpolation basis studied by [LP04] and [CP17].
How should we choose xk ?

[LP04] Lofberg and Parrilo. “From Coefficients to Samples: A New Approach to SOS Optimization”. 2004.
[CP17] Cifuentes and Parrilo. “Sampling Algebraic Varieties for Sum of Squares Programs”. 2017.
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

11 / 14

Numerical Implementation
Compute sum of squares decomposition ofdegree 4n trigonometric polynomial
p(x) = a0 +2dX

ak cos(kx) x ∈ [0, π]

k=1Using basis vectors evaluated at 4d + 1 points
Bk = [1, cos(xk ), . . . , cos(dxk )]kπ, k = 1, . . . , 4d + 1
xk =dMatrix-vector producted in ∇fp (U) computed by
FFT∇fp (U) = U ⊤ B Diag( U ⊤ Bk

2

− p(xk ))B ⊤Image credit: Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani. (2006) Algorithms
Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

12 / 14

Numerical Results

Compute sum of squares decomposition
for random trigonometric polynomial
Convergence rate for L-BFGS withrandom initialization

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

13 / 14

Numerical Results

Compute sum of squares decomposition
for random trigonometric polynomial
Convergence rate for L-BFGS withrandom initialization

Results (stop at 10−7 relative error in u):
Degree of p(x)10,00020,000100,000

200,000

1,000,000

Time (s)

6

9

53

160

1461

Iterations

530

632

1126

1375

2303

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

13 / 14

Conclusion
When does it make sense to solve non-convex formulations of convex problems?
In our setting we can prove that non-convexity does not hurt us
Near-linear time iteration cost with first-order methods in a benign landscape

Chenyang Yuan (MIT)Low-Rank Univariate Sum of Squares

Tuesday 26th July, 2022

14 / 14