In this talk, we consider the problem of learning with random feature models (RFMs), two-layer neural networks, as well as kernel methods. Leveraging tools from information-based complexity (IBC), we establish a dual equivalence between approximation and estimation, and then apply it to study the learning of functions within the preceding function spaces. To showcase the efficacy of our duality framework, we delve into two important but under-explored problems: Random feature learning beyond kernel regime and the $L^\inf$ learning of reproducing kernel Hilbert space. To establish the aforementioned duality, we introduce a type of IBC, termed I-complexity, to measure the complexity of a function class. Notably, I-complexity offers a tight characterization of learning in noiseless settings, yields lower bounds comparable to Le Cam's in noisy settings, and is versatile in deriving upper bounds. Our duality framework holds potential for broad applications in learning analysis across more scenarios.
