 Optimal fixed step for quadratic gradient descent

For a fixed symmetric matrix and positive-definite matrix $A$, what positive step size minimizes the largest coordinate error multiplier over all eigenvector directions? Let $m={\lambda }_{\min }>0$ and $L={\lambda }_{\max }$. Since $|1-\eta \lambda |$ is a convex function of $\lambda$, its maximum over the eigenvalues occurs at an endpoint:Balance the two extremes by solving $1-\eta m=-(1-\eta L)$:Here $\kappa$ is the Euclidean norm condition number of $A$. This balance is optimal: for $\eta <{\eta }_{\ast }$ the endpoint $1-\eta m$ exceeds ${\rho }_{\ast }$, and for $\eta >{\eta }_{\ast }$ the endpoint $\eta L-1$ exceeds ${\rho }_{\ast }$. The optimal worst-case energy factor is ${\rho }_{\ast }^2$, rather than ${\rho }_{\ast }$. This optimizes a uniform one-step bound; a particular initial error supported on fewer eigenvectors can have a different best step size.

In the example $m=1$, $L=9$, so ${\eta }_{\ast }=0.2$ and ${\rho }_{\ast }^2=0.64$. Both eigenvalue directions attain that energy factor, making the displayed history exact. The smaller step size $0.1$ instead givesIts first step reaches $E_1=1.665$, below $4.16$ for $\eta =0.2$, but subsequent progress is limited by the first direction's energy factor $0.81$. By $k=5$, the energies are approximately $0.69736$ and $0.69793$, respectively; by $k=6$, the $0.2$ iteration is ahead. A better first step need not yield a faster long-run history.

As the condition number grows, ${\rho }_{\ast }$ approaches one: stability in the direction of the largest eigenvalue forces small movement along the smallest-eigenvalue direction. This is a precise reason to improve scaling or use a method such as the Conjugate gradient method, rather than merely increasing the step size. When $m=L$, choosing $\eta =1/m$ eliminates every error component in one step.