Optimal Error Drop

Worst case distribution for single-step error drop with greedy step size:

Δ=

2

ϕ

δ

.For single step loss drop, see https://www.wolframcloud.com/obj/yaroslavvb/nn-linear/forum-step1-minimizer.nb

Background:
- https://math.stackexchange.com/questions/4640077/largest-k-such-that-k-operatornametr-h2-c-le-operatornametr-h-c2
- https://mathematica.stackexchange.com/questions/280116/computing-c-that-minimizes-left-sum-i-h-i-c-i-right2-sum-i-h-i2-c-i

In[]:=

findMin[hvec_]:=Clear[c];d=Length[hvec];cvec=Array[c,d];poscons=Thread[cvec>=0];cons=poscons~Join~{Tr[cvec]==1};sol=Minimize

2

Tr[hvec*cvec]

Tr[hvec*hvec*cvec]

,And@@cons,cvec;Print["C=",DiagonalMatrix[cvec/.sol[[2]]]//MatrixForm];sol[[1]];h={1,1,1,10};H=DiagonalMatrix[h];Print["H=",H//MatrixForm];Print["k=",findMin[h]]emax[H_]:=Max[Eigenvalues[H]];emin[H_]:=Min[Eigenvalues[H]];k[H_]:=

2

emin[H]

emax[H]

;Print["user1551 bound: ",k[H]]Print"Frederik bound: ",

4emin[H]emax[H]

2

(emin[H]+emax[H])



H=

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	10

C=

39 176	0	0	0
0	7 16	0	0
0	0	1 4	0
0	0	0	1 11

k=

40

121

user1551 bound:

1

100

Frederik bound:

40

121

Sanity check with random C’s

In[]:=

randomMin[hvec_]:=d=Length[hvec];cvec=RandomVariate[NormalDistribution[],d];cvec=cvec*cvec;cvec=cvecTotal[cvec];

2

Tr[hvec*cvec]

Tr[hvec*hvec*cvec]

;Min[Table[randomMin[h],{10000}]]>40/121.Min[Table[randomMin[h],{10000}]]40/121.

Out[]=

True

Out[]=

0.330579

Out[]=

0.330579