From polynomial to deep neural network approximation in high dimensions approximating multi-dimensional functions from pointwise samples is a ubiquitous task in data science and scientific computing. This task is made intrinsically difficult by the presence of four contemporary challenges: (i) the target function is usually defined over a high- or infinite-dimensional domain; (ii) generating samples can be very expensive; (iii) samples are corrupted by unknown sources of errors; (iv) the target function might take values in a function space. In this talk, we will show how these challenges can be substantially overcome thanks to the ``blessings" of sparsity and Monte Carlo sampling. \\ \\ First, we will consider the case of sparse polynomial approximation via compressed sensing. Focusing on the case where the target function is smooth (e.g., holomorphic), but possibly highly anisotropic, we will show how to obtain sample complexity bounds only mildly affected by the curse of dimensionality, near-optimal accuracy guarantees, stability to unknown errors corrupting the data, and rigorous convergence rates of algebraic and exponential type. Then, we will illustrate how the mathematical toolkit of sparse polynomial approximation via compressed sensing can be employed to obtain a practical existence theorem for Deep Neural Network (DNN) approximation of high-dimensional Hilbert-valued functions. This result shows not only the existence of a DNN with desirable approximation properties, but also how to compute it via a suitable training procedure in order to achieve best-in-class performance guarantees. We will conclude by discussing open research questions. \\ \\ The presentation is based on joint work with Ben Adcock, Casie Bao, Nick Dexter, Sebastian Moraga, and Clayton G. Webster.