Empirical risk minimization is optimal for the convex aggregation problem

الأصل · EN

Let F be a finite model of cardinality M and denote by conv(F) its convex hull. The problem of convex aggregation is to construct a procedure having a risk as close as possible to the minimal risk over conv(F). Consider the bounded regression model with respect to the squared risk denoted by R(·). If fₙERM-C denotes the empirical risk minimization procedure over conv(F), then we prove that for any x>0, with probability greater than 1-4(-x), R(fₙERM-C)≤∈ conv(F)R(f)+c₀ (ψₙ⁽ᶜ⁾(M),x/n), where c₀>0 is an absolute constant and ψₙ⁽ᶜ⁾(M) is the optimal rate of convex aggregation defined in (In Computational Learning Theory and Kernel Machines (COLT-2003) (2003) 303-313 Springer) by ψₙ⁽ᶜ⁾(M)=M/n when M≤ √n and ψₙ⁽ᶜ⁾(M)=√ (eM/√n)/n when M>√n.