Gradient Descent and the Silver Ratio

This notebook verifies the algebraic identities in Section 3.2 of the paper
​“Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization”
​by Jason M. Altschuler and Pablo A. Parrilo [ https://arxiv.org/abs/2309.16530 ]

​
Definitions and relations

In[]:=
(*Silverratio*)​​rho=1+Sqrt[2];​​​​(*SilverStepsizeforiterationn=2^k-1,fromequation(2.1)*)​​an=1+rho^(k-1);​​​​(*Silverconvergenceratefromequation(1.4)*)​​r=k1/(1+Sqrt[4rho^(2k)-3]);​​rk=r[k];(*r_k*)​​rk1=r[k+1];(*r_{k+1}*)​​​​(*Sparsecorrectionsinequation(3.7)*)​​d12=rk1(rho);​​d13=rk1(1-rho^k);​​d21=rk1(rho^k);​​d23=rk1(2rho-Sqrt[2]rho^(k+1));​​d31=rk1(1+rho^(k-1)-1/(2rk));​​d32=rk1(1/(2rk1)-(1+2rho)/(2rk));​​​​(*ThethreematricesinLemma3.7*)​​EE=rk1{{-2rho,(1+2*rho)an-1/(2rk),0,0},​​{0,1/(4rk^2)-(1+2*rho)an^2,0,0},​​{0,0,2rho,1/(2rk1)-(1+2rho)/(2*rk)},​​{0,0,0,(1+2*rho)/(4rk^2)-1/(4*rk1^2)}};​​​​S={{0,(d21+d31),0,-d12},​​{0,-(d13+d31+d21+d12),-d21,d12+d21},​​{0,0,0,(d12+d32)},​​{0,0,0,-(d12+d21+d23+d32)}};​​​​L=rhork1{{-2,2+rho^(k-1),0,1},​​{0,-1-rho^k-2rho^(k-1),rho^(k-1),-1-rho^(k-1)},​​{0,0,2,-1},​​{0,0,0,1-rho^k}};

Verify identity

In[]:=
DD=S+L-EE;​​Simplify[DD]//MatrixForm
Out[]//MatrixForm=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

​