In[]:=
deploy
Sat 30 Dec 2023 10:37:14
Convergence of w - α x<w, x> in probability
Convergence of w - α x<w, x> in probability
If x is Gaussian or normalized Gaussian, for which values of α does iteration converge?Top-level summary:“Multiplicative Convergence + Kaczmarz” section of Notes: Optimization- NIntegrate to find variance:forum-variance-multiplicative.nb- stats.SE (Mathuss): Range of α such that converges almost surely post - solution takes matrix logarithms, but the matrix is singular- 1D, explicit plot of expectation (user293787): Tricky `FindRoot/NExpectation` problem post - explicit characterization using Central Limit Theorem for logs- 2D case (Anthony Quas mathoverflow): “Range of 𝑎 such that” - explicit formula - open questions: mathoverflow: https://mathoverflow.net/questions/443143/when-is-prod-i-0-infty-i-x-i-x-it-0-for-isotropic-gaussian-x-i stats.SE: https://stats.stackexchange.com/questions/610099/asymptotic-behavior-of-prod-i-1s-1-alpha-x2-i2-for-gaussian-x-i dsp.SE: https://dsp.stackexchange.com/questions/87091/for-which-values-of-step-size-is-lms-filter-stable Speeding up batchStep: https://mathematica.stackexchange.com/q/282590/217 Normalized isotropic Gaussian:- critical α in in : https://mathematica.stackexchange.com/questions/272484/speeding-up-computation-of-gaussian-integral- 4th moments https://mathematica.stackexchange.com/questions/272672/computing-expectation-of-fracx-12-x-22-x-4-for-gaussian-x- density of eigenvalues for Isotropic: https://mathoverflow.net/questions/443119/density-of-eigenvalues-of-empirical-covariance-matrix-of-vectors-uniform-on-the
d
R
Stochastic divergence
Stochastic divergence
Clear[x,y,a,rv];norm2[x_]=Total[x*x];(*Returnsstandardnormaldensityinvariablesx[1],x[2],...,x[d]*)normalDensity[d_]:=Module[{xvec,dist},Clear[x];xvec=Array[x,d];dist=If[d==1,NormalDistribution[],MultinormalDistribution[IdentityMatrix[d]]];If[d==1,PDF[dist,First@xvec],PDF[dist,xvec]]];findLearningRate[d_]:=xvec=Array[x,d];pdf=normalDensity[d];scaling=Ifd==1,1,;rv[a_]=scaling2Log[Abs[1-anorm2[xvec]]];bounds={#,-∞,∞}&/@xvec;obj[a_?NumericQ]:=Chop[NIntegrate@@Join[{pdf*rv[a]},bounds]];a/.FindRoot[obj[a]==-Log[d]/d,{a,2.2}];Quiet[Print[StringForm["d=``, =``",1,findLearningRate[1]]];Print[StringForm["d=``, =`` (should be 0.937087)",2,findLearningRate[2]]];Print[StringForm["d=``, =`` (probably incorrect)",3,findLearningRate[3]]];]
2
x[1]
norm2[xvec]
α
max
α
max
α
max
d=1, =2.42125
α
max
d=2, =0.918611
α
max
d=3, =0.551258
α
max
In[]:=
SeedRandom[1,Method->"MKL"];B=100001;numSteps=100;d=2;W=ConstantArray[1,{B,d}];batchStepNormal[W_,α_]:=Module[{X},X=RandomVariate[NormalDistribution[],{B,d}];W-MapThread[α#2#1.#2&,{W,X}]];(*stepsxBxd*)meanRowNorm[row_]:=Mean[&/@row];medianRowNorm[row_]:=Median[&/@row];a=0.9186110732490;a=0.93;trajectories=NestList[batchStepNormal[#,a]&,W,numSteps];ListPlot[medianRowNorm/@trajectories,PlotLabel->StringForm["a=``",a],AxesLabel->{"steps","median ||w"}]
2
Norm[#]
2
Norm[#]
2
||
Out[]=
In[]:=
SeedRandom[1,Method->"MKL"];B=100001;numSteps=100;d=2;W=ConstantArray[1,{B,d}];batchStepNormal[W_,α_]:=Module[{X},X=RandomVariate[NormalDistribution[],{B,d}];W-MapThread[α#2#1.#2&,{W,X}]];(*stepsxBxd*)meanRowNorm[row_]:=Mean[&/@row];medianRowNorm[row_]:=Median[&/@row];a=0.9186110732490;a=0.94;trajectories=NestList[batchStepNormal[#,a]&,W,numSteps];ListPlot[medianRowNorm/@trajectories,PlotLabel->StringForm["a=``",a],AxesLabel->{"steps","median ||w"}]
2
Norm[#]
2
Norm[#]
2
||
Out[]=
Critical step size
Critical step size
Refactored from Mathematica forum
Refactored from Mathematica forum
Monotonic vs Asymptotic convergence
Monotonic vs Asymptotic convergence
Covariance of projected Gaussian
Covariance of projected Gaussian