Lipschitz constants depend on the norm

NumericalBeginner⏱ 15 minFoundationslipschitznormsdimension dependence

Problem

For each of the following functions on $\R^d$ , compute the smallest Lipschitz constant with respect to $\|\cdot\|_2$ and with respect to $\|\cdot\|_\infty$ .

$f(x) = \max_i x_i$
$f(x) = \sum_i x_i$
$f(x) = \|x\|_2$
$f(x) = \frac1d\sum_i x_i$

State which constants grow with $d$ and explain the consequence for concentration bounds.

Compute the requested quantities and say what they mean. A number without an interpretation is not an answer.

Hints

Hints — 0 of 2 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
Bounding how far the adapted model moves	Fine-Tuning	Proof	Intermediate	30 min
The supremum is 1-Lipschitz in the uniform norm	Foundations	Proof	Intermediate	15 min
Mirror descent on the simplex beats Euclidean projection abyss	Advanced Optimization	Proof	Graduate	1 hour