Worst-Case Proximal Denoising Normalized Mean-Squared Error and Subdifferential Mean-Squared Distance

For any proper continuous convex function $f : \mathbb{R}^n \to \mathbb{R}$, signal $x_0 \in \mathbb{R}^n$, tuning multiplier $\lambda \ge 0$, noise scale $\sigma > 0$, and noise realization $v \in \mathbb{R}^n$, the regularized proximal denoiser $x^*(\sigma\lambda, \sigma v) = \arg\min_x \{\frac{1}{2}\|x_0 + \sigma v - x\|_2^2 + \sigma\lambda f(x)\}$ satisfies the deterministic point-wise bound $\|x^*(\sigma\lambda, \sigma v) - x_0\|_2 \le \operatorname{dist}(\sigma v, \sigma\lambda\partial f(x_0))$ via nonexpansiveness of proximal mappings applied to the first-order subdifferential support function $\hat{f}_{x_0}(x) = f(x_0) + \sup_{s \in \partial f(x_0)} \langle s, x - x_0\rangle \le f(x)$ (Lemma 5.1, Eqs. 5.1-5.6, pp. 12-13). Taking expectations over $v \sim \mathcal{N}(0, I_n)$ and using local Lipschitz continuity of $f$ to control the directional derivative limit as $\sigma \to 0^+$ (Lemmas 5.2-5.3, Proposition 5.2, pp. 13-16) yields the exact worst-case identity $\sup_{\sigma > 0} \frac{\mathbb{E}[\|x^*(\sigma\lambda, \sigma v) - x_0\|_2^2]}{\sigma^2} = \lim_{\sigma \to 0^+} \frac{\mathbb{E}[\|x^*(\sigma\lambda, \sigma v) - x_0\|_2^2]}{\sigma^2} = \mathbf{D}(\lambda\partial f(x_0)) := \mathbb{E}[\operatorname{dist}(v, \lambda\partial f(x_0))^2]$ (Theorem 1.1, Eq. 2.7, p. 4). Moreover, when $0 \notin \partial f(x_0)$, the constrained denoiser $x^c(\sigma v) = \arg\min_{f(x) \le f(x_0)} \|x_0 + \sigma v - x\|_2^2$ satisfies $\|x^c(\sigma v) - x_0\|_2 \le \operatorname{dist}(\sigma v, \operatorname{cone}(\partial f(x_0))) = \|\Pi_{T_f(x_0)}(\sigma v)\|_2$ point-wise and $\sup_{\sigma > 0}\frac{\mathbb{E}[\|x^c(\sigma v) - x_0\|_2^2]}{\sigma^2} = \lim_{\sigma \to 0^+} \frac{\mathbb{E}[\|x^c(\sigma v) - x_0\|_2^2]}{\sigma^2} = \mathbf{D}(\operatorname{cone}(\partial f(x_0))) = \inf_{\lambda \ge 0} \mathbf{D}(\lambda\partial f(x_0))$ (Theorem 3.1, Eqs. 3.1-3.3, p. 6; Appendix B Lemma B.1, pp. 27-29).

For any proper convex function $f$ and $x_0 \in \mathbb{R}^n$, the conic subdifferential distance $\mathbf{D}(\operatorname{cone}(\partial f(x_0)))$ and the squared Gaussian width $\mathbf{S}(T_f(x_0) \cap \mathcal{B}^n) := (\mathbb{E}[\sup_{u \in T_f(x_0) \cap \mathcal{B}^n} \langle u, g\rangle])^2$ satisfy the universal additive sandwiching $0 \le \mathbf{D}(\operatorname{cone}(\partial f(x_0))) - \mathbf{S}(T_f(x_0) \cap \mathcal{B}^n) \le 1$ (Proposition 6.1, Eq. 6.1, p. 16; Lemma C.1, p. 29), and tighter multiplicative bounds $\frac{\min_{\lambda \ge 0} \mathbf{D}(\lambda\partial f(x_0))}{\mathbf{S}(T_f(x_0) \cap \mathcal{B}^n)} \le 1 + \frac{2}{\sqrt{k^3 / n}}$ for the $\ell_1$ norm at a $k$-sparse vector in $\mathbb{R}^n$ (Eq. 6.2) and $\le 1 + \frac{2}{\sqrt{r^3 d}}$ for the nuclear norm at a rank-$r$ matrix in $\mathbb{R}^{d \times d}$ (Eq. 6.3, Lemmas C.2-C.3, pp. 29-30). Furthermore, for norms whose subdifferential decomposes over orthogonal subspaces $T$ and $T^\perp$ as $\partial f(x_0) = \{e + w : w \in \partial f_{T^\perp}(0), \|w\|_2 \le R_{x_0}\}$ with $e \in T$ ($\|e\|_2 \ge L_{x_0}^{-1}$) and radial convexity along $T^\perp$, the gap between ray-scaled subdifferential distance and the full cone satisfies $0 \le \min_{\lambda \ge 0} \mathbf{D}(\lambda\partial f(x_0)) - \mathbf{D}(\operatorname{cone}(\partial f(x_0))) \le 2\pi R_{x_0}^2 L_{x_0}^2 + 2\sqrt{2\pi}\,R_{x_0} L_{x_0} \sqrt{\mathbf{D}(\operatorname{cone}(\partial f(x_0)))} + 1$ (Proposition 6.2, p. 17; Lemma C.4, p. 30).

In noisy linear inverse problems $y = A x_0 + \sigma v \in \mathbb{R}^m$ with i.i.d. standard Gaussian $A \in \mathbb{R}^{m \times n}$ and $v \sim \mathcal{N}(0, I_m)$, the tangent-cone projected LASSO $\hat{x} = \arg\min_{x - x_0 \in T_{\mathcal{C}}(x_0)} \|y - A x\|_2$ (which bounds the constrained LASSO error via $\|x^* - x_0\|_2 \le 2\|\hat{x} - x_0\|_2$, Lemma 7.1, Eq. 7.3) undergoes a sharp phase transition governed solely by $\mathbf{D} = \mathbf{D}(T_{\mathcal{C}}(x_0)^*) = \mathbf{D}(\operatorname{cone}(\partial f(x_0)))$: in the asymptotic regime $n \to \infty$ with $|m - \mathbf{D}| / \sqrt{m} \to \infty$, the normalized estimation error $\eta_{\text{LASSO}} = \lim_{\sigma \to 0} \frac{\|\hat{x} - x_0\|_2^2}{\sigma^2}$ and normalized optimal cost $F_{\text{LASSO}} = \lim_{\sigma \to 0} \frac{\|y - A\hat{x}\|_2^2}{\sigma^2}$ converge in probability to $\eta_{\text{LASSO}} = \frac{\mathbf{D}}{m - \mathbf{D}}$ and $F_{\text{LASSO}} = m - \frac{\mathbf{D}}{m - \mathbf{D}}$ when $m > \mathbf{D}$, whereas for $m < \mathbf{D}$ recovery fails with $\eta_{\text{LASSO}} = \infty$ and $F_{\text{LASSO}} = 0$ (Theorem 3.3, Eqs. 3.8-3.9, pp. 7-8; Proposition 7.1, Eqs. 7.5-7.9, pp. 18-19).