Rounding semidefinite relaxations of concave functionsof quadratic forms
Chenyang Yuan
Based on joint work with Pablo Parrilo
Toyota Research Institute

Friday 26th July, 2024

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

1 / 16

Introduction
How to find approximations to 3 seemingly unrelated problems:
Subspace approximation
Max-Cut
Permanent of PSD matrices

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

2 / 16

Introduction
How to find approximations to 3 seemingly unrelated problems:
Subspace approximation
Max-Cut
Permanent of PSD matrices
Goals:A unified framework to encompass and generalize these problems
Simple rounding analysis to obtain optimal approximation factors matching
lower-bounds

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

2 / 16

Introduction
How to find approximations to 3 seemingly unrelated problems:
Subspace approximation
Max-Cut
Permanent of PSD matrices
Goals:A unified framework to encompass and generalize these problems
Simple rounding analysis to obtain optimal approximation factors matching
lower-bounds
Bounding expectations of functions of Gaussians gives analysis for rounding
algorithms for optimization problems on the sphere

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

2 / 16

Subspace Approximation
Given a1 , . . . , am ∈ Rn and p ≥ 1. Find (n − d)-dimensional subspace V thatminimizes! p1mX
dist(ai , V )pi=1

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

3 / 16

Subspace Approximation
Given a1 , . . . , am ∈ Rn and p ≥ 1. Find (n − d)-dimensional subspace V thatminimizes! p1mX
dist(ai , V )pi=1

p = 2 equivalent to least squares,
polynomial-time solution via SVD.
p = ∞, minimize maximum distanceto V , NP-hard problem incomputational convex geometry.

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

3 / 16

Subspace Approximation SDP Relaxation

min
V

m
X
i=1

! p1
dist(ai , V )p

min
=

X

s.t.

m
X

! p1
(ai⊤ XX ⊤ ai )p/2

i=1

X ⊤ X = Id
X ∈ Rn×d[Gur+16] Guruswami et al. “Bypassing UGC from some optimal geometric inapproximability results”. 2016.
[DTV11] Deshpande, Tulsiani, and Vishnoi. “Algorithms and hardness for subspace approximation”. 2011.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere

Friday 26th July, 2024

4 / 16

Subspace Approximation SDP Relaxation

min
V

m
X

! p1
dist(ai , V )p

min
=

X

s.t.

i=1

m
X

! p1
(ai⊤ XX ⊤ ai )p/2

i=1

X ⊤ X = Id
X ∈ Rn×d

SDP relaxation via convex hull of feasible set (Fantope):
! p1
m
X
⊤
p/2
min
(ai Qai )
Q

s.t.

k=1

Tr(Q) = d
0 ⪯ Q ⪯ In

[Gur+16] Guruswami et al. “Bypassing UGC from some optimal geometric inapproximability results”. 2016.
[DTV11] Deshpande, Tulsiani, and Vishnoi. “Algorithms and hardness for subspace approximation”. 2011.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere

Friday 26th July, 2024

4 / 16

Subspace Approximation SDP Relaxation

min
V

m
X

! p1
dist(ai , V )p

min
=

X

s.t.

i=1

m
X

! p1
(ai⊤ XX ⊤ ai )p/2

i=1

X ⊤ X = Id
X ∈ Rn×d

SDP relaxation via convex hull of feasible set (Fantope):
! p1
m
X
⊤
p/2
min
(ai Qai )
Q

s.t.

k=1

Tr(Q) = d
0 ⪯ Q ⪯ In

Constant-factor approximation algorithm [DTV11] for p ≥ 1, 0 ≤ d ≤ n.
For d = 1 and p > 2, [Gur+16] shows that it is NP-hard to improve constant.
[Gur+16] Guruswami et al. “Bypassing UGC from some optimal geometric inapproximability results”. 2016.
[DTV11] Deshpande, Tulsiani, and Vishnoi. “Algorithms and hardness for subspace approximation”. 2011.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere

Friday 26th July, 2024

4 / 16

Max CutGiven A ≻ 0, the MaxCut problem is:max

x∈{±1}n⟨x, Ax⟩[BRS15] Briët, Regev, and Saket. “Tight hardness of the non-commutative Grothendieck problem”. 2015.
[Nes98] Nesterov. “Semidefinite relaxation and nonconvex quadratic optimization”. 1998.
[GW95] Goemans and Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. 1995.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere
Friday 26th July, 2024
5 / 16

Max CutGiven A ≻ 0, the MaxCut problem is:max

x∈{±1}n⟨x, Ax⟩For PSD A, we have a π2 -approximation by Nesterov [Nes98].
NP-hard to improve approximation constant. [BRS15][BRS15] Briët, Regev, and Saket. “Tight hardness of the non-commutative Grothendieck problem”. 2015.
[Nes98] Nesterov. “Semidefinite relaxation and nonconvex quadratic optimization”. 1998.
[GW95] Goemans and Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. 1995.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere
Friday 26th July, 2024
5 / 16

Max CutGiven A ≻ 0, the MaxCut problem is:max

x∈{±1}n⟨x, Ax⟩For PSD A, we have a π2 -approximation by Nesterov [Nes98].
NP-hard to improve approximation constant. [BRS15]
Can be improved to 0.878 [GW95] if A is graph Laplacian.

[BRS15] Briët, Regev, and Saket. “Tight hardness of the non-commutative Grothendieck problem”. 2015.
[Nes98] Nesterov. “Semidefinite relaxation and nonconvex quadratic optimization”. 1998.
[GW95] Goemans and Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. 1995.
Chenyang Yuan (Toyota Research Institute)
Rounding SDP relaxations on the sphere
Friday 26th July, 2024
5 / 16

Max Cut as Optimization on the SphereAn equivalent formulation over the sphere:
max n ⟨x, Ax⟩ = max

x∈{±1}

Chenyang Yuan (Toyota Research Institute)∥z∥2 =1

1

2

A2 z

Rounding SDP relaxations on the sphere.
1

Friday 26th July, 2024

6 / 16

Max Cut as Optimization on the SphereAn equivalent formulation over the sphere:1

max n ⟨x, Ax⟩ = max∥z∥2 =1x∈{±1}

2

A2 z

.
1

Using variational characterization ⟨x, Ax⟩ = maxy ∈Rn 2 ⟨x, y ⟩ − y , A−1 y :maxx∈{±1}n ,y ∈Rn

2 ⟨x, y ⟩ − y , A−1 y = maxn 2 ∥y ∥1 − y , A−1 yy ∈R1Substitute y = λA 2 z, where ∥z∥ = 1, λ ∈ R.
max∥z∥2 =1,λ∈R

Chenyang Yuan (Toyota Research Institute)1− λ2 = max

2λ A 2 z
1∥z∥2 =1

Rounding SDP relaxations on the sphere

1

2

A2 z

.
1

Friday 26th July, 2024

6 / 16

Max Cut as Optimization on the SphereAn equivalent formulation over the sphere:1

max n ⟨x, Ax⟩ = max∥z∥2 =1x∈{±1}

2

A2 z

.
1

Using variational characterization ⟨x, Ax⟩ = maxy ∈Rn 2 ⟨x, y ⟩ − y , A−1 y :maxx∈{±1}n ,y ∈Rn

2 ⟨x, y ⟩ − y , A−1 y = maxn 2 ∥y ∥1 − y , A−1 yy ∈R1Substitute y = λA 2 z, where ∥z∥ = 1, λ ∈ R.
max∥z∥2 =1,λ∈R

1− λ2 = max

2λ A 2 z
1∥z∥2 =1

1

2

A2 z

.
1

Generalized to matrix 2 → q norms when 0 < q <= 2 (MaxCut equivalent
to 2 → 1 norm).
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

6 / 16

Permanent of PSD Matrices
Permanent of a matrix per(A) =P Qn
σi=1 Ai,σ(i)#P-hard to compute in general, NP-hard to compute sign

[JSV04] Jerrum, Sinclair, and Vigoda. “A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries”. 2004.
[LSW] Linial, Samorodnitsky, and Wigderson. “A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents”.
[Ana+17] Anari et al. “Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices”. 2017.
[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

7 / 16

Permanent of PSD Matrices
Permanent of a matrix per(A) =P Qn
σi=1 Ai,σ(i)#P-hard to compute in general, NP-hard to compute signA ≥ 0: Counts bipartite perfect matchings
A ⪰ 0: Output probabilities of boson sampling experiment[JSV04] Jerrum, Sinclair, and Vigoda. “A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries”. 2004.
[LSW] Linial, Samorodnitsky, and Wigderson. “A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents”.
[Ana+17] Anari et al. “Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices”. 2017.
[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

7 / 16

Permanent of PSD Matrices
Permanent of a matrix per(A) =P Qn
σi=1 Ai,σ(i)#P-hard to compute in general, NP-hard to compute signA ≥ 0: Counts bipartite perfect matchings
A ⪰ 0: Output probabilities of boson sampling experiment
For A ≥ 0, (1 + ϵ) randomized approximation algorithm [JSV04], e −ndeterministic approximation algorithm [LSW].

[JSV04] Jerrum, Sinclair, and Vigoda. “A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries”. 2004.
[LSW] Linial, Samorodnitsky, and Wigderson. “A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents”.
[Ana+17] Anari et al. “Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices”. 2017.
[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

7 / 16

Permanent of PSD Matrices
Permanent of a matrix per(A) =P Qn
σi=1 Ai,σ(i)#P-hard to compute in general, NP-hard to compute signA ≥ 0: Counts bipartite perfect matchings
A ⪰ 0: Output probabilities of boson sampling experiment
For A ≥ 0, (1 + ϵ) randomized approximation algorithm [JSV04], e −ndeterministic approximation algorithm [LSW].
For A ⪰ 0, e −(1+γ)n approximation algorithm [Ana+17; YP21].
NP-hard to approximate better than e −γn , current-best approximation factore −(0.9999+γ)n [ENOG24].
[JSV04] Jerrum, Sinclair, and Vigoda. “A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries”. 2004.
[LSW] Linial, Samorodnitsky, and Wigderson. “A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents”.
[Ana+17] Anari et al. “Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices”. 2017.
[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

7 / 16

Approximating Permanents of PSD Matrices
Let A = V † V and vi be the columns of V
We study the following polynomial
optimization problem on the complex√(n − 1)-sphere of radius n, and its SDP relaxation:
ρ(A) ≡ max
2∥x∥ =nnY2|⟨x, vi ⟩|

i=1


n D
E
Y
Tr(X ) = nrel(A) ≡ max
X , vi vi† s.t.
X ⪰0
X
i=1

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

8 / 16

Product of Linear Forms and Permanent Approximation
Theorem ([YP21])
Let γ = 0.5772... be the Euler-Mascheroni constant. Then1e −γn rel(A) ≤ ρ(A) ≤ rel(A)[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

9 / 16

Product of Linear Forms and Permanent Approximation
Theorem ([YP21])
Let γ = 0.5772... be the Euler-Mascheroni constant. Then1e −γn rel(A) ≤ ρ(A) ≤ rel(A)Connection to permanent:
Theorem ([YP21])12e −n(1+γ) rel(A) ≤ e −n ρ(A) ≤ per(A) ≤ rel(A)Approximating permanent ←→ polynomial optimization over sphere[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

9 / 16

Product of Linear Forms and Permanent Approximation
Theorem ([YP21])
Let γ = 0.5772... be the Euler-Mascheroni constant. Then1e −γn rel(A) ≤ ρ(A) ≤ rel(A)Connection to permanent:
Theorem ([YP21])12e −n(1+γ) rel(A) ≤ e −n ρ(A) ≤ per(A) ≤ rel(A)Approximating permanent ←→ polynomial optimization over sphere(1) is tight for low-rank matrices, (2) is tight for high-rank matrices,[ENOG24] found arbitrage to improve approximation by 10−4 .
[YP21] Yuan and Parrilo. “Maximizing Products of Linear Forms, and the Permanent of Positive Semidefinite Matrices”. 2021.
[ENOG24] Ebrahimnejad, Nagda, and Oveis Gharan. “On approximability of the Permanent of PSD matrices”. 2024.
Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

9 / 16

A unified perspective
Given A1 , . . . , Ad ⪰ 0. Consider the image of the sphere {x ∈ Kn | ∥x∥ = 1}
under the map
A : Kn → Rd+
A(x) = (⟨x, A1 x⟩ , . . . , ⟨x, Ad x⟩)

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

10 / 16

A unified perspective
Given A1 , . . . , Ad ⪰ 0. Consider the image of the sphere {x ∈ Kn | ∥x∥ = 1}
under the map
A : Kn → Rd+
A(x) = (⟨x, A1 x⟩ , . . . , ⟨x, Ad x⟩)Im(A) is a non-convex set in Rd , convex hull given byconv(Im(A)) = {(⟨X , A1 ⟩ , . . . , ⟨X , Ad ⟩) | Tr(X ) = 1, X ⪰ 0}

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

10 / 16

A unified perspective
Given A1 , . . . , Ad ⪰ 0. Consider the image of the sphere {x ∈ Kn | ∥x∥ = 1}
under the map
A : Kn → Rd+
A(x) = (⟨x, A1 x⟩ , . . . , ⟨x, Ad x⟩)Im(A) is a non-convex set in Rd , convex hull given byconv(Im(A)) = {(⟨X , A1 ⟩ , . . . , ⟨X , Ad ⟩) | Tr(X ) = 1, X ⪰ 0}

How well does conv(Im(A)) approximate Im(A)?
What measure of approximation to use?

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

10 / 16

A unified perspective
We study the following relaxationXmax
f (⟨x, Ai x⟩)
∥x∥=1

i

relax

−→

max

Tr(X )=1, X ⪰0X

f (⟨X , Ai ⟩),iwhere Ai ⪰ 0 and f is concave

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

11 / 16

A unified perspective
We study the following relaxationXmax
f (⟨x, Ai x⟩)
∥x∥=1

i

relax

−→

max

Tr(X )=1, X ⪰0X

f (⟨X , Ai ⟩),iwhere Ai ⪰ 0 and f is concave
f (a) = ap for 0 ≤ p ≤ 1: Matrix 2 → p2 norm:
f (a) =√

a: MaxCut with PSD objective (ℓ1 norm)

f (a) = log a: Permanents and product of PSD forms (KL-divergence)

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

11 / 16

A unified perspective
We study the following relaxationXmax
f (⟨x, Ai x⟩)
∥x∥=1

i

relax

−→

max

Tr(X )=1, X ⪰0X

f (⟨X , Ai ⟩),iwhere Ai ⪰ 0 and f is concave
f (a) = ap for 0 ≤ p ≤ 1: Matrix 2 → p2 norm:
f (a) =√

a: MaxCut with PSD objective (ℓ1 norm)

f (a) = log a: Permanents and product of PSD forms (KL-divergence)f (a) = −ap for p ≥ 1: Subspace approximation for d = 1

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

11 / 16

A unified perspective
We study the following relaxationXmax
f (⟨x, Ai x⟩)
∥x∥=1

i

relax

−→

max

Tr(X )=1, X ⪰0X

f (⟨X , Ai ⟩),iwhere Ai ⪰ 0 and f is concave
f (a) = ap for 0 ≤ p ≤ 1: Matrix 2 → p2 norm:
f (a) =√

a: MaxCut with PSD objective (ℓ1 norm)

f (a) = log a: Permanents and product of PSD forms (KL-divergence)f (a) = −ap for p ≥ 1: Subspace approximation for d = 1
f (a) = −a log a: Entropy maximization of POVM (Reverse KL)

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

11 / 16

Summary of results
Rounding algorithm: Given optimum X ∗ = UU † , produce unit vector x̂ by:Sample x ∼ N(0, X ∗ )Normalize x̂ = x/ ∥x∥

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

12 / 16

Summary of results
Rounding algorithm: Given optimum X ∗ = UU † , produce unit vector x̂ by:Sample x ∼ N(0, X ∗ )Normalize x̂ = x/ ∥x∥f (a)Approximation

Factor (K = R)

Factor (K = C)ap

Multiplicative√
2p Γ (1/2 + p) / πΓ(1 + p)log aAdditive

γ + log 2γ−a log a

Additive2

1

Additional gains when we can bound the rank of SDP solution X ∗Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

12 / 16

Improved bounds for low-rank solutions
When f (a) = ap and the solution of X ∗ has rank r , approximation factor
αf (R) =r p Γ(r /2)Γ(1/2 + p)
2p Γ(1/2 + p)>
Γ(1/2)Γ(r /2 + p)
Γ(1/2)

αf (C) =r p Γ(r )Γ(1 + p)
> Γ(1 + p)
Γ(r + p)

ℝ

ℂ

ℝ

1.00

1.00

0.95

0.95

0.90

ℂ

0.90

0.85
0.85

0.2

0.4

0.6

0.8

1.0

Chenyang Yuan (Toyota Research Institute)

5

10

15

20

25

(b) αf (K) against r when p = 12(a) αf (K) against p when r → ∞Rounding SDP relaxations on the sphere

Friday 26th July, 2024

13 / 16

Rounding Analysis
max

∥x∥=1

X

log(⟨x, Ai x⟩)i

Chenyang Yuan (Toyota Research Institute)

relax

−→

max

Tr(X )=1, X ⪰0

Rounding SDP relaxations on the sphereXlog(⟨X , Ai ⟩),i

Friday 26th July, 2024

14 / 16

Rounding Analysis
max

∥x∥=1

X

log(⟨x, Ai x⟩)

i

relax

−→

max

Tr(X )=1, X ⪰0

Xlog(⟨X , Ai ⟩),iRounding algorithm: Given rank-r optimum X ∗ = UU † , produce x̂:Sample x ∼ N(0, X ∗ )Normalize x̂ = x/ ∥x∥

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

14 / 16

Rounding Analysis
max

∥x∥=1

X

relax

−→

log(⟨x, Ai x⟩)

imax

Tr(X )=1, X ⪰0

Xlog(⟨X , Ai ⟩),iRounding algorithm: Given rank-r optimum X ∗ = UU † , produce x̂:Sample x ∼ N(0, X ∗ )Normalize x̂ = x/ ∥x∥
Analyze:"E#
Xlog(⟨x̂, Ai x̂⟩) =i

Chenyang Yuan (Toyota Research Institute)XiEz∼N(0,I )
log z † U † Ai Uz − log z † U † Uz

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

14 / 16

Rounding Analysis
max

∥x∥=1

X

relax

−→

log(⟨x, Ai x⟩)

i

X

max

Tr(X )=1, X ⪰0log(⟨X , Ai ⟩),iRounding algorithm: Given rank-r optimum X ∗ = UU † , produce x̂:Sample x ∼ N(0, X ∗ )Normalize x̂ = x/ ∥x∥
Analyze:"E#
Xlog(⟨x̂, Ai x̂⟩) =i

Key Step: g (λ) = E log
E log z † U † Uz = E logiEz∼N(0,I )
log z † U † Ai Uz − log z † U † Uz

Pr

2
i=1 λi |zi | is a symmetric concave function

r
X
i=1

Chenyang Yuan (Toyota Research Institute)X!
λi |zi |2r≤ E log

1X 2
|zi |
r

!
= Hr −1 − γ − log(r )i=1Rounding SDP relaxations on the sphere

Friday 26th July, 2024

14 / 16

Main Technical Tool/Trick
Bounding functionPon a domain with symmetry, e.g. simplex∆r = {λ | λ ≥ 0, i λi = 1}
Maximum (minimum) of symmetric concave (convex) function on the simplex
achieved at center: λi = 1r .
Minumum (maximum) of symmetric concave (convex) function on the simplex
achieved at vertices: λ1 = 1, λ2 , . . . , λr = 0.

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

15 / 16

Conclusion

Summary:
Simple technique for obtaining tight bounds on expected values of concave
functions of Gaussian variables.
Tight analysis (NP-hard to improve) for Max-Cut, product of linear forms,
subspace approximation.

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

16 / 16

Conclusion

Summary:
Simple technique for obtaining tight bounds on expected values of concave
functions of Gaussian variables.
Tight analysis (NP-hard to improve) for Max-Cut, product of linear forms,
subspace approximation.
Questions:
Why do these tight approximation bounds depend on properties of Gaussianvariables, though they are not mentioned in the problem description?
Are there other classes of functions of Gaussian random variables for which we canobtain similarly tight approximation bounds?

Chenyang Yuan (Toyota Research Institute)

Rounding SDP relaxations on the sphere

Friday 26th July, 2024

16 / 16