<p>Sasha Rakhlin kindly pointed me to:
<a href="https://projecteuclid.org/euclid.bj/1486177384" rel="nofollow noreferrer">https://projecteuclid.org/euclid.bj/1486177384</a></p>

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

CC BY-SA 3.0
2017-03-26T15:32:37.697Z
2017-03-26T15:32:37.697Z
Aryeh
<p>For $L&gt;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}$.</p>

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

<machine-learning><lg.learning>
Minimax agnostic risk for Lipschitz functions
Aryeh
# Minimax agnostic risk for Lipschitz functions

(Asked by: username_0 on 2017-03-26)

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.

**Tags:** machine-learning, lg.learning


---

## 1 answers

### Answer by username_0 on 2017-03-26. Score: 0 | Accepted answer

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

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


---

