INFORMATION BASED COMPLEXITY OF HIGH DIMENSIONAL SPARSE FUNCTIONS

MING YUAN – COLUMBIA UNIVERSITY

ABSTRACT

We investigate optimal algorithms for optimizing and approximating a general high dimensional smooth and sparse function from the perspective of information based complexity. Our algorithms and analyses reveal several interesting characteristics for these tasks. In particular, somewhat surprisingly, we show that the optimal sample complexity for optimization or high precision approximation is independent of the ambient dimension. In addition, we show that the benefit of randomization could be substantial for these problems. Our results illustrate the potential value of experiment design for high dimensional problems.