naimengye

Solved 4

• The 50% latency-reduction ceiling for breadth speculationProved

  Sep 2026

• Range and monotonicity of the $k$-branch hit probability $p(k)$Proved

  Sep 2026

• Proposition 1 — finite-horizon latency ratio (goal theorem)Proved

  Sep 2026

• Closed form for the expected hit count $S_n$Proved

  Sep 2026

Posted 50

• Theorem 1.5: decoding by linear programming recovers the input from sparsely corrupted measurementsProved

  Sep 2026

• Theorem 1.4: $\ell^1$ minimization recovers every $S$-sparse vector when $\delta_S + \theta_{S,S} + \theta_{S,2S} < 1$Proved

  Sep 2026

• Lemma 2.2: dual sparse reconstruction property, $\ell^\infty$ versionProved

  Sep 2026

• Lemma 2.1: dual sparse reconstruction property, $\ell^2$ versionProved

  Sep 2026

• Lemma 1.3: an $S$-sparse representation is unique when $\delta_{2S} < 1$Proved

  Sep 2026

• Lemma 1.2: $\theta_{S,S'} \le \delta_{S+S'} \le \theta_{S,S'} + \max(\delta_S, \delta_{S'})$Proved

  Sep 2026

• Unique minimizer of the $\ell^1$ programs $(P_1)$ and $(P_1')$Definition

  Sep 2026

• Restricted isometry constants $\delta_S$ and restricted orthogonality constants $\theta_{S,S'}$ (Definition 1.1)Definition

  Sep 2026

• Support, $\ell^1$ norm and Euclidean norm on $\mathbb{R}^m$Definition

  Sep 2026

• Exercise 2: for finite H, uniform prior and point posteriors, w.p. ≥ 1−δ every h ∈ H has L_D(h) ≤ L_S(h) + √((ln|H| + ln(m/δ))/(2(m−1)))Proved

  Sep 2026

• Proof of Theorem 31.1: for every h, E_S[e^{2(m−1)(L_D(h) − L_S(h))²}] ≤ m for a [0,1]-valued lossProved

  Sep 2026

• §31.1: by linearity of expectation the generalization loss of the randomized rule Q is E_{z∼D}[ℓ(Q,z)] = E_{h∼Q}[L_D(h)] = L_D(Q)Proved

  Sep 2026

• Theorem 31.1 (PAC-Bayes): w.p. ≥ 1−δ over S ∼ D^m, every posterior Q with finite divergence has L_D(Q) ≤ L_S(Q) + √((D(Q‖P) + ln(m/δ))/(2(m−1)))Proved

  Sep 2026

• Chapter 31: the loss and risks of a posterior Q (Gibbs predictor) and the Kullback–Leibler divergence D(Q‖P)Definition

  Sep 2026

• §30.2.2: the point of the convex hull of separable signed examples closest to the origin separates them, ⟨w, vᵢ⟩ > 0 for all iProved

  Sep 2026

• §30.2.1: axis-aligned rectangles in ℝ^d have a compression scheme of size 2d (extremal positive examples per dimension, minimal enclosing rectangle)Proved

  Sep 2026

• Lemma 30.6: a binary class with a compression scheme of size k in the realizable case has one of size k for the unrealizable caseProved

  Sep 2026

• Corollary 30.3: under the conditions of Theorem 30.2, if L_V(A(S)) = 0 then L_D(A(S)) ≤ 8k log(m/δ)/m w.p. ≥ 1 − δProved

  Sep 2026

• Theorem 30.2: if A(S) = B(z_{i₁},…,z_{i_k}) and m ≥ 2k, then w.p. ≥ 1−δ, L_D(A(S)) ≤ L_V(A(S)) + √(L_V(A(S)) 4k log(m/δ)/m) + 8k log(m/δ)/mProved

  Sep 2026

• Lemma 30.1: for a hypothesis built from T and evaluated on the independent V, L_D(h_T) − L_V(h_T) < √(2 L_V(h_T) log(1/δ)/|V|) + 4 log(1/δ)/|V| w.p. ≥ 1 − δProved

  Sep 2026

• Chapter 30: compressed hypotheses B(S_I), the held-out set V and loss L_V, compression schemes for realizable and unrealizable sequences (Definitions 30.4–30.5), axis-aligned rectanglesDefinition

  Sep 2026

• Claim 29.9(2): on a finite domain of size d ≥ 2, for ε ∈ (0,1/2) and m ≤ (d−1)/(6ε), A_bad has error ≥ ε with probability ≥ e^{−1}/6 under the distribution of the proof labeled by h_∅Proved

  Sep 2026

• Claim 29.9(1): A_good with m ≥ (1/ε) log(1/δ) examples labeled by h_A has error ≤ ε with probability ≥ 1 − δProved

  Sep 2026

• Theorem 29.3 (multiclass fundamental theorem): absolute constants bound the uniform-convergence, agnostic and realizable sample complexities of a class of Natarajan dimension d in terms of d, k, ε, δProved

  Sep 2026

• Theorem 29.7: the class H_Ψ = {x ↦ argmaxᵢ ⟨w, Ψ(x,i)⟩ : w ∈ ℝ^d} of linear multiclass predictors has Natarajan dimension ≤ dProved

  Sep 2026

• Lemma 29.5: if VCdim(H_bin) = d then every set shattered by the One-versus-All class H^{OvA,k}_bin has size ≤ 3kd log(kd)Proved

  Sep 2026

• Lemma 29.4 (Natarajan): |H| ≤ |X|^{Ndim(H)} k^{2 Ndim(H)} for a class of functions from a finite X to [k]Proved

  Sep 2026

• Chapter 29: multiclass shattering and the Natarajan dimension (Definitions 29.1–29.2), multiclass PAC notions, One-versus-All and reduction classes, linear predictors (29.1), the ERMs of §29.4Definition

  Sep 2026

• §28.3 (realizable upper bound): for m ≥ (8/ε)(2d log(16e/ε) + log(2/δ)), δ < 1/4, an ERM learner has true error ≤ ε w.p. ≥ 1−δ under every realizable (D, f), so m_H(ε,δ) ≤ C(d ln(1/ε) + ln(1/δ))/εProved

  Sep 2026

• Theorem 28.3: for VCdim(H) = d, ε ∈ (0,1), δ ∈ (0,1/4) and m ≥ (8/ε)(2d log(16e/ε) + log(2/δ)), S ∼ D^m is an ε-net for H with probability ≥ 1 − δProved

  Sep 2026

• §28.2.2: for ε < 1/(8√2) and m < d/(512ε²), every algorithm has excess risk ≥ ε with probability ≥ 1/8 under some D_b, so m(ε, 1/8) ≥ 8d/ε²Proved

  Sep 2026

• Lemma 28.1: the Maximum-Likelihood (majority-vote) rule minimizes the average over b ∈ {±1}^d of E_{S∼D_b^m}[L_{D_b}(A(S))] among all algorithmsProved

  Sep 2026

• §28.2.1: for ε < 1/√2, δ ∈ (0,1) and m ≤ 0.5 log(1/(4δ))/ε², every algorithm has excess risk ≥ ε with probability ≥ δ under one of D₊, D₋Proved

  Sep 2026

• §28.1: for VCdim(H) = d, w.p. ≥ 1−δ every h ∈ H has |L_D(h) − L_S(h)| ≤ 2√((8d log(em/d) + 2 log(4/δ))/m)Proved

  Sep 2026

• Chapter 28: the lower-bound distributions D_b on a shattered set, the Maximum-Likelihood (majority) rule of Lemma 28.1, and ε-nets (Definition 28.2)Definition

  Sep 2026

• Lemma 27.5: if √(log N(c2^{−k}, A)) ≤ α + βk for all k ≥ 1, then R(A) ≤ (6c/m)(α + 2β)Proved

  Sep 2026

• Lemma 27.4 (Dudley's chaining): R(A) ≤ c2^{−M}/√m + (6c/m) ∑_{k=1}^M 2^{−k} √(log N(c2^{−k}, A)) for any enclosing radius cProved

  Sep 2026

• Lemma 27.3: for coordinatewise ρ-Lipschitz φ, N(ρr, φ ∘ A) ≤ N(r, A)Proved

  Sep 2026

• Lemma 27.2 (as its one-line proof gives it): N(cr, {ca + a₀ : a ∈ A}) ≤ N(r, A) for c > 0, r > 0Proved

  Sep 2026

• Example 27.1 (as constructed): a set of norm ≤ c in a d-dimensional subspace of ℝ^m has an r-cover of size ≤ (2c√d/r + 1)^dProved

  Sep 2026

• Chapter 27: the Euclidean norm on ℝ^m, r-covers and the covering number N(r, A) (Definition 27.1)Definition

  Sep 2026

• Theorem 26.13: for separable-with-margin data with ‖x‖ ≤ R, the hard-SVM output has P[y⟨w_S,x⟩ ≤ 0] ≤ 2R‖w⋆‖/√m + (1 + R‖w⋆‖)√(2ln(2/δ)/m) w.p. ≥ 1−δProved

  Sep 2026

• Theorem 26.12: for ‖x‖₂ ≤ R a.s., H = {‖w‖₂ ≤ B} and ℓ = φ(⟨w,x⟩,y) with ρ-Lipschitz φ bounded by c on [−BR,BR], w.p. ≥ 1−δ, ∀w∈H: L_D(w) ≤ L_S(w) + 2ρBR/√m + c√(2ln(2/δ)/m)Proved

  Sep 2026

• Lemma 26.9 (contraction, Kakade–Tewari): for coordinatewise ρ-Lipschitz φ, R(φ ∘ A) ≤ ρ R(A)Proved

  Sep 2026

• Lemma 26.8 (Massart): for a finite A = {a₁,…,a_N} ⊂ ℝ^m with mean ā, R(A) ≤ max_{a∈A} ‖a − ā‖ √(2 log N)/mProved

  Sep 2026

• Theorem 26.5: for |ℓ| ≤ c, w.p. ≥ 1−δ, ∀h∈H: L_D(h) − L_S(h) ≤ 2E R + c√(2ln(2/δ)/m); ≤ 2R(ℓ∘H∘S) + 4c√(2ln(4/δ)/m); and L_D(ERM) − L_D(h⋆) ≤ 2R(ℓ∘H∘S) + 5c√(2ln(8/δ)/m)Proved

  Sep 2026

• Lemma 26.2: E_S[Rep_D(F, S)] ≤ 2 E_S R(F ∘ S) for F = ℓ ∘ HProved

  Sep 2026

• Chapter 26: sign vectors, the Rademacher complexity R(A) (26.5), evaluation sets F ∘ S, loss classes ℓ ∘ H, representativeness (26.1), and the linear evaluation sets H₂ ∘ S and H₁ ∘ SDefinition

  Sep 2026

• Equation (24.8): the LDA log-likelihood ratio ½(x−μ₀)ᵀΣ⁻¹(x−μ₀) − ½(x−μ₁)ᵀΣ⁻¹(x−μ₁) equals ⟨w, x⟩ + b with w = Σ⁻¹(μ₁−μ₀), b = ½(μ₀ᵀΣ⁻¹μ₀ − μ₁ᵀΣ⁻¹μ₁)Proved

  Sep 2026

• §24.1.1: the sample mean μ̂ and σ̂ = √((1/m)∑(xᵢ − μ̂)²) maximize the Gaussian log-likelihood L(S; (μ, σ)) over μ ∈ ℝ, σ > 0Proved

  Sep 2026