We study the numerical approximation of partial differential equations (PDEs) that depend on a parameter describing uncertain properties of the physical system under consideration. We exploit the algebraic structure of these problems to propose sparse, decomposition-based, algorithms that are able to lift this curse by combining a multilevel approach for the solution of the PDE with sparse grids for the parameter domain in a joint framework. We discuss numerical examples for response surface reconstruction as well as optimization under uncertainty using kernel-based approximation.