Suppose $h^*=\left(1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{d}\right)$ and $h=h^*/\|h^*\|_1$.
Can someone see a way to approximate the following quantity for $d\approx 10^6$? The problem is to minimize the norm of a symmetric diagonal+rank1 matrix:
$$\operatorname{argmin}_\alpha \|I-\alpha \operatorname{diag} h + 2 \alpha^2 (\operatorname{diag} h)^2 +\alpha^2 (h\otimes h)\|$$
For $d=2000$ I can compute it using brute-force to be $\approx 1.48$ and the hypothesis is that it goes to $2$ as $d\to\infty$
Motivation: this gives optimal step size for SGD used to solve $0=wx_i$ where $x_i$ are drawn from Gaussian with eigenvalues $h$.