Note on impossible robust loss

Yaroslav Bulatov

June 10, 2007

Suppose we want a loss function such that minimizing that loss on n + 1 datapoints produces the mean of the smallest n datapoints. A loss function R×R → R that is differentiable almost everywhere will not be able to do this.

Suppose we pick some arbitrary numbers b and m̂< b ∈ R, and construct a dataset where x_{i} < b for i ∈ [1,n], x_{n+1} ≥ b and mean of x_{1},...,x_{n} is m̂. Our loss function would have to satisfy

argmin_{m}∑_{i=1}^{n} f(m,x_{i}) + f(m,x_{n+1} ) = m̂ ∀x_{n+1} ≥ b

Assume our loss function f(a,b) is differentiable everywhere, then the following would have to be true

∑_{i=1}^{n} \frac{∂}{∂m}f(m̂,x_{i}) + \frac{∂}{∂m}f(m̂,x_{n+1} ) = 0 ∀x_{n+1} ≥ b

Because m̂ is an arbitrary number < b and x_{n+1} is an arbitrary number ≥ b, this shows that

\frac{∂}{∂x}f(x,y) = C ∀x < b,y ≥ b

For some constant C. Since b was arbitrary, this is the same as

\frac{∂}{∂x}f(x,y) = C ∀x ≤ y

This means that changing the position of any point lying above the true minimizer has no effect on the position of the minimum, so minimizer of that loss function can’t be the mean of smallest n numbers.

If our function is instead differentiable only on some set dense in the domain of the loss function, then possible m̂and x_{n+1} will be restricted to some dense set, and we’ll get result of the form

\frac{∂}{∂x}f(x,y) = C ∀x < y,(x,y) ∈ B

Where B is some dense set in the domain. Here also, small changes in points greater than current minimum will not affect the minimum, so it can’t be the mean of smallest n numbers.