Lee Jones

Title:  Finite sample minimax estimation, fusion in machine learning, and overcoming the curse of dimensionality

Abstract:

A minimax approach is described for learning the value of an unknown function f(x) at a query point xo based on knowledge of
the function's values ( with possible noise added) at given points {xj}.  As a result optimal accuracy bounds, based on assumptions about the behavior of f(x), may be determined for several new and old algorithms for learning f(xo).

Empirical evidence indicates that averaging the learned estimate of f(xo) from many different algorithms ( estimates) often leads to increased accuracy - as with random subspace methods, random forests and varying  kernel covariances. Furthermore, when statistically analyzed, different algorithms are often estimating different conditional expectations of the corresponding  response variable.  A  method (fusion) is presented for optimally combining the estimates from a given set (ensemble) of such algorithms and obtaining an accuracy bound on such combination. The approach is to introduce  information-theoretic concepts relating accuracy
bounds of  an aggregate estimate to the degree of conditioning of the aggregate estimate.

The minimax approach allows the fusion procedure to account for the possibility of spurious features causing ( with a known high
probability) only a small number of  algorithms to overfit.  When a large number of the algorithms  are highly predictive  the fusion estimate remains accurate and the curse of dimensionality may be avoided.

(Research supported by the Norbert Wiener Center (NWC) and the Submillimeter-Wave Technology Laboratory (STL).)