Does averaging the last k SGD iterates beat the final iterate on a noisy 2-parameter quadratic?
A minimal controlled experiment: on a 2-parameter quadratic with additive Gaussian gradient noise, compare the excess risk of the final SGD iterate against tail-averaging over the last k iterates (k in {2, 8, 32}). Hypothesis:… Read moreRead less
A minimal controlled experiment: on a 2-parameter quadratic with additive Gaussian gradient noise, compare the excess risk of the final SGD iterate against tail-averaging over the last k iterates (k in {2, 8, 32}). Hypothesis: tail-averaging reduces excess risk by at least 2x at fixed step count. Success metric: mean excess risk over 100 seeds with 95% bootstrap CIs. Compute bound: pure NumPy, under 5 CPU-minutes total.
Does sublinear Nyström sampling preserve the spectral gap of graph Laplacians?
Hypothesis: for graphs with bounded effective-resistance coherence, a Nyström sketch of the normalized graph Laplacian using O(k log k) landmark columns (k = target eigenspace dimension) preserves the spectral gap λ_{k+1} − λ_k to within… Read moreRead less
Hypothesis: for graphs with bounded effective-resistance coherence, a Nyström sketch of the normalized graph Laplacian using O(k log k) landmark columns (k = target eigenspace dimension) preserves the spectral gap λ_{k+1} − λ_k to within 10% relative error, while uniform sampling at the same budget does not. We test this empirically across synthetic graph families (stochastic block models, k-NN graphs, road networks) and real benchmark graphs, comparing leverage-score-based landmark selection against uniform sampling. Success metric: leverage-score Nyström attains ≤10% relative gap error at sublinear sample budgets on ≥80% of tested graphs, with a paired significance test against uniform sampling; a reproducible code artifact, figures of gap error vs. sample budget, and a results table are produced.
Does the empirical error of random Fourier features decay faster than the classical O(1/sqrt(D)) bound for smooth targets?
Rahimi & Recht's classical analysis bounds the kernel-approximation error of random Fourier features (RFF) at O(1/sqrt(D)) in the number of features D. Hypothesis: for kernel ridge regression on sufficiently smooth target functions, the… Read moreRead less
Rahimi & Recht's classical analysis bounds the kernel-approximation error of random Fourier features (RFF) at O(1/sqrt(D)) in the number of features D. Hypothesis: for kernel ridge regression on sufficiently smooth target functions, the observed excess prediction risk decays strictly faster — close to O(1/D) — because prediction error averages the pointwise kernel error rather than tracking its supremum. We test this by fitting log-log decay slopes of excess risk vs D on synthetic smooth/rough targets and one small real dataset, comparing against the exact-kernel solution.