Use statistical physics ideas ("replica trick") to compute asymptotic value of $\inf_{\|w\| \le r} (1/n)\|Xw-y\|^2$ for random $X$ and $y$

Question

I'm trying to get my head around the "replica trick" and it's mathematically rigorous formulations (due to Talagrand, Parchenko, etc.). I was wondering to myself that a solution or insight for the problem below using ideas in the line of the aforementioned techniques would help me understand.

---

Let $n$ and $d$ be large positive integers with $n/d = \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ matrix with iid entries from $N(0,1/d)$ and $y$ be a $n$-dimensional vector with independent of $X$, iid entries drawn uniformly from $\{\pm 1\}$ (or from $N(0,1)$, if that helps). Finally, let $B_d(r)$ be the closed ball in $\mathbb R^d$ with radius $r \ge 0$, and defined a random variable $E \ge 0$ by $$ E := \inf_{\sigma \in B_d(r)} \|X\sigma-y\|^2 = n + \inf_{\sigma \in B_d(r)} \sigma^\top W \sigma - 2h^\top \sigma, $$

where $W := X^\top X \in \mathbb R^{d \times d}$ and $h \in X^\top y \in \mathbb R^d$.

Question. How can the "replica trick" (from statistical physics) or its modern mathematically rigorous reformulations be used to compute the asymptotic value of $E/n$ (when $n,d \to \infty$) ?

Note that if the $\inf$ was a $\sup$, then the problem would be an instance of the spherical Sherrington-Kirkpatrick (SK) model with external field. In the case where $W$ is symmetric with independent gaussian entries on and above the diagonal, this paper by A. Dembo & O. Zeitouni https://arxiv.org/pdf/1409.4606.pdf would give a solution to the problem (using concentration ideas which have something to do with replica trick or related ideas).

N.B. I understand concentration of measure and RMT well enough.

Answer 1

It turns out that the optimal value of the problem can be computed arbitrarily well using basic probability arguments. Of course, this post doesn't answer my question, since the only motivation of the question was understanding the "replica trick", but I thought I'd post it here as part of the discussion (too long for a comment).

---

By using the fact that $x \mapsto (1/2)\|x\|^2$ is invariant w.r.t to Fenchel-Legendre transformation, one computes

$$ \begin{split} \min_{w \in B_d(r)}\frac{1}{2}\|Xw-y\|^2 &= \min_{w \in B_d(r)}\sup_{u \in \mathbb R^n}u^\top (y-Xw) - \frac{1}{2}\|u\|^2\\ &= \sup_{u \in \mathbb R^n}u^\top y-\frac{1}{2}\|u\|^2 + \min_{w \in B_d(r)}u^\top Xw \\ &= \sup_{u \in \mathbb R^n} u^\top y - \frac{1}{2}\|u\|^2 - r\|X^\top u\|. \end{split} $$ Now, for any $\varepsilon \in (0, 1)$, we have $(1-\varepsilon)\|u\| \le \|X^\top u\| \le (1+\varepsilon)\|u\| $ w.p $1-e^{-\Omega(n\varepsilon^2)}$. This is more or less the Johnson-Lindenstrauss inquality.

Noting that $\sup_{u \in \mathbb R^n} u^\top y - \dfrac{1}{2}\|u\|^2 - r'\|u\| = \dfrac{1}{2}\left(\|y\|-r'\right)_+^2$ for any $r' \in \mathbb R$, and assuming for simplicity that the $y_i$'s are Rademacher, so that $\|y\| = \sqrt{n}$, we conclude that

$$ \left(1-\frac{(1+\varepsilon)r}{\sqrt{n}}\right)_+^2 \le \min_{w \in B_d(r)} \frac{1}{n}\|Xw-y\|^2 \le \left(1-\frac{(1-\varepsilon)r}{\sqrt{n}}\right)_+^2, $$ w.p $1-e^{-\Omega(n\varepsilon^2)}$.