Loom Notes

% ===========================================================================
%  Concentration of Measure  --  proof notes organized by engine
%  woven on LOOM.   compile:  xelatex main  (twice)  or  latexmk -xelatex main
%  How to fill: each section ships thesis / paradigm / cheat-sheet / theorem
%  statements + proof skeletons; replace the \TODO{...} and the skeleton stubs.
% ===========================================================================
\documentclass[cjk]{loom}   % [cjk] only so the pen name renders; all prose is English

% --- \block \trigger \TODO + booktabs/tabularx/L now come from loom.cls v0.2 ---
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Ent}{\operatorname{Ent}}
\DeclareMathOperator{\tr}{tr}

\runningthread{concentration of measure}

\begin{document}

\loomcover
  {Concentration of Measure}
  {Proof notes, organized by engine}
  {北极甜虾 (剑心犹在！)}
  {\today}

% ===========================================================================
\section*{Overview · the eight engines}
\addcontentsline{toc}{section}{Overview · the eight engines}
\warmth{0}

\begin{strand}
In one line: a function of many \emph{weakly dependent} variables is nearly
constant. Every concentration inequality is one \keyword{engine} for proving
this; they differ only in the structure they consume: independence, bounded
differences, convexity, or curvature and isoperimetry. Learn the engine before
the formula.
\end{strand}

\trigger{You want a small-probability bound on $f(X_1,\dots,X_n)$ deviating far from its mean/median.}
Ask yourself one question: \emph{which structure do I have?} Then reach for the engine below.

\block{Cheat-sheet: which engine to use}
\noindent\begin{tabularx}{\linewidth}{@{}l l L@{}}
\toprule
{\color{indigo}Engine} & {\color{indigo}Structure it eats} & \multicolumn{1}{l}{\color{indigo}Main tools / section} \\
\midrule
Cramér–Chernoff        & independence + MGF            & Laplace transform, optimize $\lambda$, rate function \;(§\ref{sec:chernoff}) \\
Sub-Gaussian / sub-exp.& \emph{shape} of the tail      & $\psi$-Orlicz norms, Bernstein \;(§\ref{sec:subgaussian}) \\
Bounded diff.\ / martingale & change one coordinate    & Azuma, McDiarmid \;(§\ref{sec:bdd}) \\
Variance / entropy     & tensorization                 & Efron–Stein, Herbst, log-Sobolev \;(§\ref{sec:entropy}) \\
Geometry / isoperimetry& metric \emph{and} measure     & sphere/Gaussian isoperimetry, Borell–TIS \;(§\ref{sec:geometry}) \\
Talagrand convex dist. & convexity + product space     & convex-distance inequality \;(§\ref{sec:talagrand}) \\
Matrix concentration   & spectrum + trace exponential  & Lieb, matrix Bernstein \;(§\ref{sec:matrix}) \\
Suprema / chaining     & metric entropy                & Dudley, generic chaining \;(§\ref{sec:chaining}) \\
\bottomrule
\end{tabularx}

\begin{strand}
Reading guide: §\ref{sec:chernoff}–§\ref{sec:subgaussian} are the trunk (the
continuation of Appendix A); read them until fluent. §\ref{sec:bdd}–§\ref{sec:entropy}
push ``sums'' to ``any bounded-difference function''.
§\ref{sec:geometry}–§\ref{sec:talagrand} are the geometric heart that gives
``\emph{measure} concentration'' its name. §\ref{sec:matrix}–§\ref{sec:chaining}
are two exits toward ML/TCS.
\end{strand}

\clearpage
{\small\tableofcontents}

\clearpage
% ===========================================================================
\input{sections/01-cramer-chernoff}
\input{sections/02-subgaussian}
\input{sections/03-bounded-differences}
\input{sections/04-entropy}
\input{sections/05-geometry}
\input{sections/06-talagrand}
\input{sections/07-matrix}
\input{sections/08-chaining}
\input{sections/09-hooks}

\end{document}