1. A computer-implemented method for solving fast nonlinear regression and classification problems comprising: sketching an input data and output data using sparse embedding matrices and structured random matrices; utilizing structure in the data to accelerate sketching, said structure is a Vandermonde matrix form; and solving a regression problem on the sketched data, a hardware processor performing one or more said sketching, structure utilizing and problem solving.