Expected error does not give a high-probability guarantee

ProofAdvanced⏱ 30 minSGDhigh probabilitymarkovtightness

Theory: SGD — Convergence Under Every Standard Assumption →

Problem

Suppose $\E[f(x_T)-f^\star]\le\epsilon$ . Show that the best general tail bound is $\P(f(x_T)-f^\star>s)\le\epsilon/s$ and that it is attained. Compute the $\epsilon$ needed for a $99\%$ guarantee at accuracy $s$ , and the resulting increase in $T$ under the $1/\sqrt T$ rate.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Markov and Chebyshev are attained	High-Dim Probability	Proof	Foundation	15 min
When is the union bound tight?	Probability	Proof	Foundation	15 min
Tightness of the descent lemma	Foundations	Proof	Beginner	15 min
Mini-batching and the compute budget	SGD	Numerical	Intermediate	30 min
Reading the Robbins–Monro conditions off the proof	SGD	Proof	Intermediate	30 min