This thesis addresses the significant gap in understanding the finite-sample performance of algorithms for learning nonlinear systems, specifically Volterra series, where existing literature predominantly relies on asymptotic analysis. We develop a novel framework termed Directional Probabilistic Excitation (dPE) to provide rigorous performance guarantees for Linear-In-Parameter models under mild assumptions on input excitation and system stability. Explicit, non-asymptotic complexity bounds are derived for learning Volterra series using Ordinary Least Squares, revealing that the minimal sample size scales linearly with the combinatorial model $D$ dimension, while the estimation error decays at a rate of $\mathcal{O}(\sqrt{D/N})$ under sub-Gaussian noise conditions. Furthermore, we demonstrate that this framework applies to polynomial NARMAX models via regularized least-squares, quantifying the additional statistical cost imposed by feedback loops and dependent noise. Numerical simulations validate the theoretical bounds, illustrating the critical influence of input excitation, noise robustness, and the curse of dimensionality on convergence rates. Ultimately, this work bridges the sharp finite-sample theory of linear systems with the expressive power of nonlinear Volterra models, offering a foundational statistical framework for fading memory nonlinear dynamical system learning.