Data-Driven Optimization: A Reproducing Kernel Hilbert Space Approach

We present two methods, based on regression in reproducing kernel Hilbert spaces, for solving an optimization problem with uncertain parameters for which we have historical data, including auxiliary data. The first method approximates the objective function and the second approximates the optimizer. We provide finite sample guarantees and prove asymptotic optimality for both methods. Computational experiments suggest that at least the second method overcomes a curse of dimensionality that afflicts existing methods, extrapolates better to unseen data, and achieves a many-fold decrease in sample complexity even for small dimensions.