Purpose
The target object is
\[
L(Q)
=
\inf_g
\mathbb E\!\left[
\left\|Z-g(\operatorname{ReLU}(QZ))\right\|^2
\right].
\]
Your existing notes already cover the algebraic prerequisites:
- expectation,
- covariance,
- independence,
- finite second moments,
- norms, traces, and outer products.
This guide covers only the remaining load-bearing material:
- measurable spaces, measurable maps, generated sigma-algebras, and laws;
- conditional expectation, tower property, and conditional variance;
- conditional expectation as an orthogonal projection in (L^2), hence the MMSE theorem.
Primary reading
Use:
Nima Moshayedi, Lectures on Probability Theory, University of Zurich
https://arxiv.org/pdf/2010.16280
The page numbers below refer to the printed page numbers in the notes.
Level 2 — Conditional expectation
Read only:
- Chapter 3, §2.2, Discrete construction, pp. 80–82.
- Chapter 3, §2.3 through Theorem 2.18, General construction and basic properties, pp. 82–84.
- Theorem 2.29, Tower property, p. 86.
Skip on the first pass:
- the Radon–Nikodym construction;
- transition kernels;
- martingales.
You should leave this level knowing that
\[
\mathbb E[X\mid\mathcal G]
\]
is a (G)-measurable random variable satisfying
\[
\mathbb E[X1_G]
=
\mathbb E[\mathbb E[X\mid\mathcal G]1_G]
\qquad
\text{for every }G\in\mathcal G,
\]
and that, for (HG),
\[
\mathbb E[\mathbb E[X\mid\mathcal G]\mid\mathcal H]
=
\mathbb E[X\mid\mathcal H].
\]
Level 3 — (L^2) geometry and MMSE
Read only:
- Chapter 3, §1, (L^2(,F,P)) as a Hilbert space, pp. 73–75.
- Chapter 3, §1.2, Orthogonal projection, pp. 78–79.
- Definitions 2.12 and 2.15 and Remarks 2.13–2.14, pp. 82–83.
- The first two paragraphs of §4.1.2, pp. 90–91, emphasizing the distinction between:
- projection onto all ((A))-measurable functions;
- projection onto the much smaller linear span of the observed variables.
You should leave this level able to prove
\[
\mathbb E\|Z-g(A)\|^2
=
\mathbb E\|Z-\mathbb E[Z\mid A]\|^2
+
\mathbb E\|\mathbb E[Z\mid A]-g(A)\|^2.
\]
This identity is the actual reason conditional expectation is the MMSE decoder.
Optional terse reference
For a compact formal reference:
Matija Vidmar, Probability with Measure
https://arxiv.org/pdf/2604.01685
Relevant sections:
- §1.1, measurable sets;
- §1.3, measurable maps and generated sigma-fields;
- §3.3, conditioning.
Do not use this as the first exposition unless you prefer definition-dense notes.
How to use the quiz
Do three passes.
- Closed-notes pass: attempt every question without reading the answer key.
- Open-notes repair pass: repair incomplete definitions and proofs.
- Compression pass: rewrite each starred proof in at most ten lines without omitting assumptions.
Each ordinary question is worth (2) points:
- (0): absent, materially false, or circular;
- (1): right idea but missing a required definition, assumption, or proof step;
- (2): correct and explicit.
A starred question is load-bearing. A zero on any starred question means the corresponding level is not yet secure, regardless of total score.
Part II — Conditional expectation
Question 10 ★ — Definition
Let (XL^1) and let (GF) be a sub-sigma-algebra.
State the defining properties of
\[
Y=\mathbb E[X\mid\mathcal G].
\]
Include the sense in which (Y) is unique.
Question 11 — Finite partition calculation
Let
\[
\Omega=\{1,2,3,4\},
\]
with probabilities
\[
(0.1,0.2,0.3,0.4),
\]
and let
\[
X=(2,-1,4,0)
\]
on these four outcomes.
Let
\[
\mathcal G
=
\sigma(\{1,2\},\{3,4\}).
\]
Compute (E[XG]) as a random variable on ().
Question 12 ★ — Verify from the definition
For your answer to Question 11, verify explicitly that
\[
\mathbb E[X1_G]
=
\mathbb E[\mathbb E[X\mid\mathcal G]1_G]
\]
for every (GG).
Question 15 ★ — Tower property
Let
\[
\mathcal H\subseteq\mathcal G\subseteq\mathcal F
\]
and (XL^1).
State and prove
\[
\mathbb E[\mathbb E[X\mid\mathcal G]\mid\mathcal H]
=
\mathbb E[X\mid\mathcal H].
\]
Use the defining property of conditional expectation, not an informal averaging argument.
Question 16 ★ — Law of total variance
For (XL^2), prove
\[
\operatorname{Var}(X)
=
\mathbb E[\operatorname{Var}(X\mid\mathcal G)]
+
\operatorname{Var}(\mathbb E[X\mid\mathcal G]).
\]
Define
\[
\operatorname{Var}(X\mid\mathcal G)
=
\mathbb E[(X-\mathbb E[X\mid\mathcal G])^2\mid\mathcal G].
\]
Identify exactly where the cross term vanishes.
Question 17 — Vector version
For (ZL^2(;R^d)), prove
\[
\operatorname{Cov}(Z)
=
\mathbb E[\operatorname{Cov}(Z\mid\mathcal G)]
+
\operatorname{Cov}(\mathbb E[Z\mid\mathcal G]).
\]
All quantities are matrices. State what expectation of a random matrix means.
Question 18 ★ — Trace of conditional covariance
Let
\[
m=\mathbb E[Z\mid\mathcal G].
\]
Prove
\[
\operatorname{tr}(\operatorname{Cov}(Z\mid\mathcal G))
=
\mathbb E[\|Z-m\|^2\mid\mathcal G].
\]
Then prove
\[
\mathbb E[
\operatorname{tr}(\operatorname{Cov}(Z\mid\mathcal G))
]
=
\mathbb E\|Z-m\|^2.
\]
Do not remove the conditional expectation in the first identity.
Question 20 — Scalar Gaussian ReLU
Let
\[
Z\sim\mathcal N(0,1),
\qquad
A=\operatorname{ReLU}(Z).
\]
You may use
\[
\mathbb E[Z\mid Z\le 0]
=
-\sqrt{\frac{2}{\pi}},
\qquad
\operatorname{Var}(Z\mid Z\le 0)
=
1-\frac{2}{\pi}.
\]
Compute (E[ZA]) and the MMSE.
Question 21 — Conditioning on a continuously distributed observation
Explain why the notation
\[
\mathbb E[Z\mid A=a]
\]
cannot generally be defined by the elementary formula
\[
\frac{\mathbb E[Z1_{\{A=a\}}]}{\mathbb P(A=a)}
\]
when (A) is continuous.
Explain why
\[
\mathbb E[Z\mid A]
=
\mathbb E[Z\mid\sigma(A)]
\]
remains well-defined.
Question 22 — Sparse nonnegative scalar
Let
\[
Z=
\begin{cases}
0,&\text{with probability }1-p,\\
X,&\text{with probability }p,
\end{cases}
\qquad
X\sim\operatorname{Exp}(1),
\]
and let (A=(Z)).
Compute (E[ZA]) and the MMSE.
Part III — (L^2) geometry and MMSE
Question 23 ★ — (L^2) as an inner-product space
Define
\[
L^2(\Omega,\mathcal F,\mathbb P)
\]
and its inner product and norm.
Why are random variables that are equal almost surely treated as the same element of (L^2)?
Question 24 — The observable subspace
For a sub-sigma-algebra (G), define
\[
L^2(\Omega,\mathcal G,\mathbb P).
\]
Prove it is a linear subspace of (L^2(,F,P)).
State the additional property needed before the orthogonal projection theorem applies.
Question 25 ★ — Projection theorem
State the orthogonal projection theorem for a closed linear subspace (M) of a Hilbert space (H).
Give both equivalent characterizations of the projection (P_Mx):
- closest point;
- orthogonality of the residual.
Question 26 ★ — Conditional expectation is the projection
Let (XL^2).
Prove that
\[
m=\mathbb E[X\mid\mathcal G]
\]
satisfies
\[
\mathbb E[(X-m)V]=0
\]
for every (VL^2(,G,P)).
First prove it for indicator functions, then simple functions, then general (V).
Question 27 ★ — Pythagorean risk decomposition
Let
\[
Z\in L^2(\Omega;\mathbb R^d),
\qquad
m=\mathbb E[Z\mid\mathcal G],
\]
and let (T) be any square-integrable (G)-measurable random vector.
Prove
\[
\mathbb E\|Z-T\|^2
=
\mathbb E\|Z-m\|^2
+
\mathbb E\|m-T\|^2.
\]
Expand the square and prove that the cross term is exactly zero.
Question 28 ★ — MMSE decoder
Set
\[
A=\operatorname{ReLU}(QZ).
\]
Using Questions 7 and 27, prove
\[
\inf_g
\mathbb E\|Z-g(A)\|^2
=
\mathbb E\|Z-\mathbb E[Z\mid A]\|^2.
\]
State:
- the admissible class of (g);
- the integrability condition;
- the sense in which the minimizer is unique.
Question 30 ★ — Exact recoverability
Prove the equivalence
\[
L(Q)=0
\]
if and only if
\[
Z\text{ is }\sigma(A)\text{-measurable},
\]
if and only if there exists a measurable (g) such that
\[
Z=g(A)
\qquad\text{a.s.}
\]
Explain why this is an almost-sure recoverability statement, not necessarily a statement that the deterministic map
\[
z\mapsto\operatorname{ReLU}(Qz)
\]
is globally injective on all of (R^d).
Question 31 ★ — Arbitrary decoder versus linear decoder
Explain the difference between minimizing over:
\[
g(A)\quad\text{for every measurable }g
\]
and minimizing over:
\[
BA+b.
\]
Give a concrete example in which the MMSE decoder is nonlinear and therefore cannot be represented by an affine decoder.
Question 32 ★ — Gaussian rotational invariance
Assume
\[
Z\sim\mathcal N(0,I_d)
\]
and (QO(d)).
Prove that (L(Q)) is independent of (Q).
Your proof must use:
- (Y=QZN(0,I_d));
- preservation of Euclidean norm by (Q);
- a bijection between decoders for (Z) and decoders for (Y).
Bridge problems toward the privileged-basis proof
These are not prerequisites. They test whether you can now begin the actual problem.
Bridge 1 — Identity basis for nonnegative latents
Assume
\[
Z\in[0,\infty)^d
\qquad\text{a.s.}
\]
Prove
\[
L(I)=0.
\]
The sparsity and exponential assumptions are irrelevant for this step. Explain why.
Bridge 2 — Why one collision is insufficient
Someone argues:
I found (zz’) such that [ (Qz) = (Qz’). ] Therefore (L(Q)>0).
Give at least three reasons this argument is incomplete.
Bridge 3 — Correct positivity criterion
State a rigorous condition, in terms of conditional covariance, sufficient and necessary for
\[
L(Q)>0.
\]
Then state a more concrete sufficient condition involving a positive-probability set of observations.
Bridge 4 — Forty-five-degree sparse case
Let (d=2) and
\[
Q
=
\frac{1}{\sqrt 2}
\begin{bmatrix}
1&-1\\
1&1
\end{bmatrix}.
\]
Let (Z_1,Z_2) be independent sparse nonnegative exponential variables.
Write
\[
A=\operatorname{ReLU}(QZ)
\]
coordinatewise.
Identify a region of latent space on which one ReLU coordinate is zero and the other reveals only (Z_1+Z_2).
Formulate a rigorous route to proving that the conditional distribution of (Z) on this region has nonzero variance. You do not need to complete all measure-theoretic details, but you must identify exactly what must be proved.
Readiness criterion
There are (32) main questions, for (64) points.
You are ready to begin the privileged-basis proof when:
- total score is at least (52/64);
- no starred question receives (0);
- Questions 27–30 can be reproduced without notes;
- you can explain in one paragraph why the problem is fundamentally about the conditional spread of ReLU fibres under the law of (Z).
The answer key is a separate file. Do not open it until completing the closed-notes pass.