Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 10.6 — Frobenius oracle inequality for nuclear-norm regularized least squares

Disproved
WainwrightHDS.NucNorm.nuclear_norm_ls_frobenius_oracle_bound

by mikedeng1 · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationhigh-dimensional-statisticslow-rank-matrix-estimationnuclear-normstatistics

Let X1,…,Xn∈Rd1×d2X_1,\dots,X_n\in\mathbb R^{d_1\times d_2}X1​,…,Xn​∈Rd1​×d2​ be design matrices with observation operator [Xn(Θ)]i=⟨ ⁣⟨Xi,Θ⟩ ⁣⟩[\mathfrak X_n(\Theta)]_i=\langle\!\langle X_i,\Theta\rangle\!\rangle[Xn​(Θ)]i​=⟨⟨Xi​,Θ⟩⟩, let Θ∗∈Rd1×d2\Theta^*\in\mathbb R^{d_1\times d_2}Θ∗∈Rd1​×d2​ be arbitrary, and let the responses be y=Xn(Θ∗)+wy=\mathfrak X_n(\Theta^*)+wy=Xn​(Θ∗)+w for a noise vector w∈Rnw\in\mathbb R^nw∈Rn. Write d′=min⁡{d1,d2}d'=\min\{d_1,d_2\}d′=min{d1​,d2​} and σ1(Θ∗)≥⋯≥σd′(Θ∗)\sigma_1(\Theta^*)\ge\dots\ge\sigma_{d'}(\Theta^*)σ1​(Θ∗)≥⋯≥σd′​(Θ∗) for the singular values of Θ∗\Theta^*Θ∗. Suppose:

  1. (restricted strong convexity (10.17)) for constants κ>0\kappa>0κ>0 and c0>0c_0>0c0​>0,
∥Xn(Δ)∥222n  ≥  κ2∣∣∣Δ∣∣∣F2−c0 d1+d2n ∣∣∣Δ∣∣∣nuc2for all Δ∈Rd1×d2;\frac{\|\mathfrak X_n(\Delta)\|_2^2}{2n}\;\ge\;\frac{\kappa}{2}|||\Delta|||_F^2 - c_0\,\frac{d_1+d_2}{n}\,|||\Delta|||_{\mathrm{nuc}}^2\qquad\text{for all }\Delta\in\mathbb R^{d_1\times d_2};2n∥Xn​(Δ)∥22​​≥2κ​∣∣∣Δ∣∣∣F2​−c0​nd1​+d2​​∣∣∣Δ∣∣∣nuc2​for all Δ∈Rd1​×d2​;
  1. (the event G(λn)\mathbb G(\lambda_n)G(λn​)) λn>0\lambda_n>0λn​>0 and ∣∣∣1n∑i=1nwiXi∣∣∣2≤λn/2\big|\big|\big|\tfrac1n\sum_{i=1}^n w_iX_i\big|\big|\big|_2\le \lambda_n/2​​​n1​∑i=1n​wi​Xi​​​​2​≤λn​/2;
  2. Θ^\widehat\ThetaΘ is any optimal solution of the nuclear-norm regularized least-squares program (10.16),
Θ^∈arg⁡min⁡Θ∈Rd1×d2{12n∥y−Xn(Θ)∥22+λn∣∣∣Θ∣∣∣nuc}.\widehat\Theta\in\arg\min_{\Theta\in\mathbb R^{d_1\times d_2}}\Big\{\frac1{2n}\|y-\mathfrak X_n(\Theta)\|_2^2+\lambda_n|||\Theta|||_{\mathrm{nuc}}\Big\}.Θ∈argΘ∈Rd1​×d2​min​{2n1​∥y−Xn​(Θ)∥22​+λn​∣∣∣Θ∣∣∣nuc​}.

Then for every r∈{1,…,d′}r\in\{1,\dots,d'\}r∈{1,…,d′} with r≤κn128 c0(d1+d2)r\le \dfrac{\kappa n}{128\,c_0(d_1+d_2)}r≤128c0​(d1​+d2​)κn​,

∣∣∣Θ^−Θ∗∣∣∣F2  ≤  92 λn2κ2 r  +  1κ{2λn∑j=r+1d′σj(Θ∗)+32 c0(d1+d2)n[∑j=r+1d′σj(Θ∗)]2}.|||\widehat\Theta-\Theta^*|||_F^2 \;\le\; \frac92\,\frac{\lambda_n^2}{\kappa^2}\,r \;+\; \frac1\kappa\Big\{2\lambda_n\sum_{j=r+1}^{d'}\sigma_j(\Theta^*) + \frac{32\,c_0(d_1+d_2)}{n}\Big[\sum_{j=r+1}^{d'}\sigma_j(\Theta^*)\Big]^2\Big\}.∣∣∣Θ−Θ∗∣∣∣F2​≤29​κ2λn2​​r+κ1​{2λn​j=r+1∑d′​σj​(Θ∗)+n32c0​(d1​+d2​)​[j=r+1∑d′​σj​(Θ∗)]2}.

This oracle inequality splits the error into an estimation term, proportional to the target rank rrr, and an approximation term governed by the tail singular values of Θ∗\Theta^*Θ∗; it holds for every Θ∗\Theta^*Θ∗, not only low-rank ones, and rrr may be chosen to minimize the right-hand side. For Θ∗\Theta^*Θ∗ of rank rrr the tail vanishes and the bound becomes 92 rλn2/κ2\tfrac92\,r\lambda_n^2/\kappa^229​rλn2​/κ2 (10.19).

Formalization Note The statement is deterministic: conditioning on G(λn)\mathbb G(\lambda_n)G(λn​) is the hypothesis on www. There is no hypothesis n≥1n\ge1n≥1: with n=0n=0n=0 Lean's division gives x/0=0x/0=0x/0=0, and the restricted strong convexity hypothesis then fails for every Δ≠0\Delta\ne0Δ=0 (which exists because 1≤r≤d′1\le r\le d'1≤r≤d′), so the case is excluded by the other hypotheses.

Differences from the source:

  • reading: "conditioned on the event G(λ_n) = {|||(1/n)Σ w_i X_i|||₂ ≤ λ_n/2}" → deterministic hypothesis opNorm2 ((1/n)•Σ w_i•X_i) ≤ λ/2 on the vector w; reason: the proposition is a corollary of Theorem 9.19, which the book calls a deterministic result (p. 280); no probability law of w is involved
  • reading: c₀ "another universal constant of secondary importance" → an arbitrary real c₀ > 0 (a binder); reason: the stronger reading — the claim for every c₀ > 0 covers whatever value the universal constant has
  • encoding: r ≤ κn/(128c₀(d₁+d₂)) → 128·c₀·(d₁+d₂)·r ≤ κ·n in ℝ; reason: multiplied out by the positive number 128c₀(d₁+d₂) (c₀ > 0 and d₁ + d₂ ≥ 2 once r ≥ 1 exists); same instances
  • encoding: σ_j(Θ*), j = r+1, …, d' (1-based, sorted) → singVal j Θstar, j ∈ [r, min d₁ d₂) (0-based, Mathlib's sorted singularValues); reason: Lean convention; same instances
  • encoding: Θ̂ ∈ arg min of (10.16) → hypothesis ∀ Θ, lsNucObjective X y λ Θ̂ ≤ lsNucObjective X y λ Θ; reason: "any optimal solution" is any global minimizer; no existence or uniqueness is claimed
  • encoding: n ≥ 1 implicit → no binder; reason: at n = 0 Lean's x/0 = 0 makes the restricted strong convexity hypothesis false for every Δ ≠ 0, so n = 0 is excluded by the other hypotheses
  • encoding: indices i = 1..n, j₁ = 1..d₁, j₂ = 1..d₂ → Fin n, Fin d₁, Fin d₂ (0-based); λ_n → lam; reason: Lean convention; same instances
Preamble
import Mathlib
import Definitions.Def_WainwrightHDS_NucNorm_singVal
import Definitions.Def_WainwrightHDS_NucNorm_nucNorm
import Definitions.Def_WainwrightHDS_NucNorm_frobSq
import Definitions.Def_WainwrightHDS_NucNorm_opNorm2
import Definitions.Def_WainwrightHDS_NucNorm_obsOp
import Definitions.Def_WainwrightHDS_NucNorm_lsNucObjective
Formal statement
namespace WainwrightHDS.NucNorm

/-- **Proposition 10.6 — Frobenius oracle inequality for nuclear-norm regularized least squares.**
Wainwright, *High-Dimensional Statistics: A Non-Asymptotic Viewpoint*, Cambridge University
Press 2019, §10.2.2, p. 319 (PDF p. 339), Proposition 10.6, Eq. (10.18), with (10.16) and (10.17).

Observations `y = 𝔛_n(Θ*) + w` (10.3). Suppose `𝔛_n` satisfies restricted strong convexity
(10.17) with curvature `κ > 0` and constant `c₀ > 0`:
`‖𝔛_n(Δ)‖₂²/(2n) ≥ (κ/2)|||Δ|||_F² − c₀((d₁+d₂)/n)|||Δ|||_nuc²` for all `Δ`. On the event
`|||(1/n) Σ_i w_i X_i|||₂ ≤ λ_n/2`, every minimizer `Θ̂` of (10.16) with `λ_n > 0` satisfies, for every
`r ∈ {1, …, d'}` with `r ≤ κn/(128 c₀(d₁+d₂))`,
`|||Θ̂ − Θ*|||_F² ≤ (9/2)(λ_n²/κ²) r + (1/κ){2λ_n Σ_{j=r+1}^{d'} σ_j(Θ*) + (32c₀(d₁+d₂)/n)[Σ_{j=r+1}^{d'} σ_j(Θ*)]²}`.

Formalization Note: deterministic ("conditioned on the event" = hypothesis `hG` on `w`). `c₀` is
any positive real. The range of `r` is multiplied out: `128 c₀ (d₁+d₂) r ≤ κ n`. The tail
`Σ_{j=r+1}^{d'} σ_j(Θ*)` is `Σ_{j ∈ [r, min d₁ d₂)} singVal j Θ*` (0-based, sorted singular
values). No `0 < n` binder: for `n = 0` Lean reads `x / 0 = 0`, and then `hRSC` fails at any
`Δ ≠ 0` (and `1 ≤ r ≤ min d₁ d₂` gives such a `Δ`), so the hypotheses already exclude `n = 0`.
`λ_n` is `lam`. -/
theorem nuclear_norm_ls_frobenius_oracle_bound {n d₁ d₂ : ℕ}
    (X : Fin n → Matrix (Fin d₁) (Fin d₂) ℝ) (Θstar : Matrix (Fin d₁) (Fin d₂) ℝ)
    (w y : Fin n → ℝ) (hy : ∀ i, y i = obsOp X Θstar i + w i)
    (κ c₀ lam : ℝ) (hκ : 0 < κ) (hc₀ : 0 < c₀) (hlam : 0 < lam)
    (hRSC : ∀ Δ : Matrix (Fin d₁) (Fin d₂) ℝ,
      1 / (2 * (n : ℝ)) * ∑ i, (obsOp X Δ i) ^ 2 ≥
        κ / 2 * frobSq Δ - c₀ * (((d₁ : ℝ) + d₂) / n) * nucNorm Δ ^ 2)
    (hG : opNorm2 ((1 / (n : ℝ)) • ∑ i, w i • X i) ≤ lam / 2)
    (Θhat : Matrix (Fin d₁) (Fin d₂) ℝ)
    (hmin : ∀ Θ : Matrix (Fin d₁) (Fin d₂) ℝ, lsNucObjective X y lam Θhat ≤ lsNucObjective X y lam Θ)
    (r : ℕ) (hr₁ : 1 ≤ r) (hrd : r ≤ min d₁ d₂)
    (hrκ : 128 * c₀ * ((d₁ : ℝ) + d₂) * r ≤ κ * n) :
    frobSq (Θhat - Θstar) ≤
      9 / 2 * (lam ^ 2 / κ ^ 2) * r +
        1 / κ * (2 * lam * ∑ j ∈ Finset.Ico r (min d₁ d₂), singVal j Θstar +
          32 * c₀ * ((d₁ : ℝ) + d₂) / n *
            (∑ j ∈ Finset.Ico r (min d₁ d₂), singVal j Θstar) ^ 2) := by sorry

end WainwrightHDS.NucNorm
Source
Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge University Press 2019, doi:10.1017/9781108627771, §10.2.2, p. 319 (PDF p. 339), Proposition 10.6, Eq. (10.18); program (10.16) and condition (10.17), p. 319 (PDF p. 339); model (10.2)–(10.3), p. 312 (PDF p. 332)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me