For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $f:[0,1]\to\mathbb{R}$, $ %its empirical risk is $ $$ % R_n(f) = \frac1n\sum_{i=1}^n (f(X_i)-Y_i)^2$$ its true risk (w.r.t. $D$) is $$ R(f) = \mathbb{E}_D[(f(X)-Y)^2].$$ Define the minimax agnostic excess risk by $$ \Delta_n = \inf_{\hat f}\sup_D \mathbb{E}_D[ R(\hat f)-\inf_{f\in F_L}R(f)],$$ where the sup is over all distributions $D$ and the inf is over all estimators taking an $n$-point sample $(X_i,Y_i)$ to a function $\hat f:[0,1]\to\mathbb{R}$.

What is known about the behavior of $\Delta_n$? I was only able to find mimimax rates for additive -- rather than agnostic -- noise models.


1 Answer 1


Sasha Rakhlin kindly pointed me to: https://projecteuclid.org/euclid.bj/1486177384

where a rate of $n^{-2/3}$ is shown.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.