Exercises Notebook

Converted from exercises.ipynb for web reading.

Exercises: Rademacher Complexity

There are 10 exercises. Exercises 1-3 are mechanics, 4-6 are theory, and 7-10 connect the mathematics to AI systems.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import math

COLORS = {
    "primary":   "#0077BB",
    "secondary": "#EE7733",
    "tertiary":  "#009988",
    "error":     "#CC3311",
    "neutral":   "#555555",
    "highlight": "#EE3377",
}

def header(title):
    print("\n" + "=" * 72)
    print(title)
    print("=" * 72)

def check_true(condition, name):
    ok = bool(condition)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    assert ok, name

def check_close(value, target, tol=1e-8, name="value"):
    ok = abs(float(value) - float(target)) <= tol
    print(f"{'PASS' if ok else 'FAIL'} - {name}: got {float(value):.6f}, expected {float(target):.6f}")
    assert ok, name

def finite_class_bound(h_size, epsilon, delta):
    return (np.log(h_size) + np.log(1.0 / delta)) / epsilon

def hoeffding_gap(h_size, m, delta):
    return np.sqrt((np.log(2.0 * h_size) + np.log(1.0 / delta)) / (2.0 * m))

def bias_variance(y_hats, y_true, noise_var):
    mean_pred = np.mean(y_hats, axis=0)
    bias2 = np.mean((mean_pred - y_true) ** 2)
    variance = np.mean(np.var(y_hats, axis=0))
    return float(bias2), float(variance), float(noise_var)

def empirical_rademacher_linear(x, radius=1.0, trials=200):
    x = np.asarray(x, dtype=float)
    vals = []
    for _ in range(trials):
        sigma = np.random.choice([-1.0, 1.0], size=x.shape[0])
        vals.append(radius * abs(np.sum(sigma * x)) / x.shape[0])
    return float(np.mean(vals))

print("Helper functions ready.")

Exercise 1: fitting random noise as complexity (*)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 5

# Your Solution - Exercise 1
answer = None
print("Your answer placeholder:", answer)

Code cell 6

# Solution
header("Exercise 1: Rademacher Complexity")
h_size = 32
epsilon = 0.10
delta = 0.05
m = finite_class_bound(h_size, epsilon, delta)
check_true(m > 0, "finite-class sample bound is positive")
print("Required samples:", int(np.ceil(m)))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 2: data-dependent capacity (*)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 8

# Your Solution - Exercise 2
answer = None
print("Your answer placeholder:", answer)

Code cell 9

# Solution
header("Exercise 2: Rademacher Complexity")
y = np.array([1, 1, 0, 0, 1])
pred = np.array([1, 0, 0, 0, 1])
risk = float(np.mean(y != pred))
check_close(risk, 0.2, name="empirical 0-1 risk")
print("Risk:", risk)
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 3: why VC can be too coarse (*)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 11

# Your Solution - Exercise 3
answer = None
print("Your answer placeholder:", answer)

Code cell 12

# Solution
header("Exercise 3: Rademacher Complexity")
h_size = 16
m = 400
delta = 0.05
gap = hoeffding_gap(h_size, m, delta)
check_true(0 < gap < 1, "gap is on probability scale")
print("Gap bound:", round(gap, 4))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 4: random signs (**)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 14

# Your Solution - Exercise 4
answer = None
print("Your answer placeholder:", answer)

Code cell 15

# Solution
header("Exercise 4: Rademacher Complexity")
y_true = np.array([0.0, 1.0, 4.0])
y_hats = np.array([[0.0, 1.2, 3.8], [0.1, 0.9, 4.1], [-0.1, 1.1, 4.2]])
bias2, variance, noise = bias_variance(y_hats, y_true, 0.05)
check_true(bias2 >= 0 and variance >= 0, "bias and variance are nonnegative")
print("Bias^2, variance, noise:", round(bias2, 5), round(variance, 5), round(noise, 5))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 5: empirical complexity (**)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 17

# Your Solution - Exercise 5
answer = None
print("Your answer placeholder:", answer)

Code cell 18

# Solution
header("Exercise 5: Rademacher Complexity")
x = np.linspace(-1, 1, 20)
rad = empirical_rademacher_linear(x, radius=1.5, trials=100)
check_true(rad >= 0, "empirical Rademacher estimate is nonnegative")
print("Rademacher estimate:", round(rad, 5))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 6: Rademacher variables $\sigma_i$ (**)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 20

# Your Solution - Exercise 6
answer = None
print("Your answer placeholder:", answer)

Code cell 21

# Solution
header("Exercise 6: Rademacher Complexity")
h_size = 32
epsilon = 0.10
delta = 0.05
m = finite_class_bound(h_size, epsilon, delta)
check_true(m > 0, "finite-class sample bound is positive")
print("Required samples:", int(np.ceil(m)))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 7: empirical Rademacher complexity $\widehat{\mathfrak{R}}_S(\mathcal{H})$ (***)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 23

# Your Solution - Exercise 7
answer = None
print("Your answer placeholder:", answer)

Code cell 24

# Solution
header("Exercise 7: Rademacher Complexity")
y = np.array([1, 1, 0, 0, 1])
pred = np.array([1, 0, 0, 0, 1])
risk = float(np.mean(y != pred))
check_close(risk, 0.2, name="empirical 0-1 risk")
print("Risk:", risk)
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 8: expected Rademacher complexity (***)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 26

# Your Solution - Exercise 8
answer = None
print("Your answer placeholder:", answer)

Code cell 27

# Solution
header("Exercise 8: Rademacher Complexity")
h_size = 16
m = 400
delta = 0.05
gap = hoeffding_gap(h_size, m, delta)
check_true(0 < gap < 1, "gap is on probability scale")
print("Gap bound:", round(gap, 4))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 9: function classes (***)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 29

# Your Solution - Exercise 9
answer = None
print("Your answer placeholder:", answer)

Code cell 30

# Solution
header("Exercise 9: Rademacher Complexity")
y_true = np.array([0.0, 1.0, 4.0])
y_hats = np.array([[0.0, 1.2, 3.8], [0.1, 0.9, 4.1], [-0.1, 1.1, 4.2]])
bias2, variance, noise = bias_variance(y_hats, y_true, 0.05)
check_true(bias2 >= 0 and variance >= 0, "bias and variance are nonnegative")
print("Bias^2, variance, noise:", round(bias2, 5), round(variance, 5), round(noise, 5))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")

Exercise 10: loss-composed classes (***)

Compute or interpret a learning-theory quantity, then explain the AI relevance.

Code cell 32

# Your Solution - Exercise 10
answer = None
print("Your answer placeholder:", answer)

Code cell 33

# Solution
header("Exercise 10: Rademacher Complexity")
x = np.linspace(-1, 1, 20)
rad = empirical_rademacher_linear(x, radius=1.5, trials=100)
check_true(rad >= 0, "empirical Rademacher estimate is nonnegative")
print("Rademacher estimate:", round(rad, 5))
print("\nTakeaway: learning-theory calculations connect finite samples, class capacity, and future-risk claims.")