Proof of Thm 31 (p. 37) — margin tail: w.p. ≥ (1 − γ)/2, ⟨w, yx⟩ ≤ (a_n/γ)‖w‖₁

Let $0<\tau\le\tfrac12$, $0\le b\le1$ and $\gamma>0$. Let $m\in\mathbb R^d$ with $|m_i|\le b$ for all $i$, and let $\theta^\star$ follow the product law $\rho_m$ on $\{\pm1\}^d$ with independent coordinates of means $\mathbb E[\theta^\star_i]=m_i$. Given $\theta^\star$, let $(x,y)$ be a fresh sample from the $(\theta^\star,\tau)$-Bernoulli model. Then for every $w\in\mathbb R^d$, with $a=2\tau b$,

In the proof of Theorem 31 this is applied conditionally on the sample set $S$: given $S$, the posterior of $\theta^\star$ is a product law whose coordinate means satisfy $|\mathbb E[\theta^\star_i\mid S]|\le b=15\tau\sqrt{2n\log(4d/\gamma)}$, so $a=a_n=30\tau^2\sqrt{2n\log(4d/\gamma)}$ is the page's shorthand. The statement here is the general product-law form that the argument uses.

Formalization Note The probability is the finite sum $\sum_\theta\rho_m(\theta)\sum_{(x,y)}P_{\theta,\tau}(x,y)\,\mathbf 1[\cdot]$. $\|w\|_1=\sum_i|w_i|$. The bound $b\le1$ (with $\tau\le\tfrac12$) makes $\rho_m$ a probability law and $a\le1$.