Autonomous systems are driven by dynamics, necessitating adapting learned models to new information. Linear models readily adapt, but deep models are essential to modern speech and perception. Thus, fundamental tradeoffs between complexity and statistical accuracy must be understood to facilitate autonomous adaptation. Motivated by this spectrum of possibility, and the fact that an infinite node one-layer Gaussian mixture model may identify any deep neural network, we characterize architectural/accuracy tradeoffs in nonparametric models. We first note that the update rules for kernel regression, Gaussian processes, and importance (Monte Carlo) sampling imply the curse of dimensionality: each new sample enters into the model with an associated weight. Then we propose compression framework that sparsifies both the algorithm sample path and its limit, providing an explicit tradeoff between memory and the radius of convergence: more accurate convergence requires greater memory. We then demonstrate that this approach facilitates stable and efficient training of nonlinear statistical models that outperform alternatives. We will also cover sample complexity characterizations of common reinforcement learning (RL) algorithms, i.e., policy gradient and actor-critic, in service of a framework to reduce the data requirements of recent blockbuster results and making RL applicable to real-time systems. In particular, we show that policy gradient and actor-critic inherit the convergence rates of non-convex stochastic search with appropriate use of Monte Carlo rollouts, and demonstrate that reward-shaping can improve the quality of limit points.
