The supremum is 1-Lipschitz in the uniform norm

ProofIntermediate⏱ 15 minFoundationssupremumlipschitzuniform convergence

Problem

Let $g,h$ be bounded real functions on a set $T$ . Prove that

\Big|\sup_{t\in T}g(t) - \sup_{t\in T}h(t)\Big| \le \sup_{t\in T}\big|g(t)-h(t)\big| .

Then explain why this makes the quantity $Z = \sup_{f\in\Fcal}\big(R(f) - \hat R_n(f)\big)$ satisfy the bounded-differences condition with constants $c_i = 1/n$ when the loss is in $[0,1]$ .

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

Hints

Hints — 0 of 3 revealed

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
Equality in Jensen's inequality	Foundations	Proof	Beginner	15 min
Every norm is convex, and the operator norm is a supremum of linear functions	Optimization	Proof	Beginner	15 min
Lipschitz constants depend on the norm	Foundations	Numerical	Beginner	15 min
The excess risk decomposition for ERM	Learning Theory	Proof	Beginner	15 min
Bounding how far the adapted model moves	Fine-Tuning	Proof	Intermediate	30 min