  We propose novel randomized optimization methods for high-dimensional convex
problems based on restrictions of variables to random subspaces. We consider
oblivious and data-adaptive subspaces and study their approximation properties
via convex duality and Fenchel conjugates. A suitable adaptive subspace can be
generated by sampling a correlated random matrix whose second order statistics
mirror the input data. We illustrate that the adaptive strategy can
significantly outperform the standard oblivious sampling method, which is
widely used in the recent literature. We show that the relative error of the
randomized approximations can be tightly characterized in terms of the spectrum
of the data matrix and Gaussian width of the dual tangent cone at optimum. We
develop lower bounds for both optimization and statistical error measures based
on concentration of measure and Fano's inequality. We then present the
consequences of our theory with data matrices of varying spectral decay
profiles. Experimental results show that the proposed approach enables
significant speed ups in a wide variety of machine learning and optimization
problems including logistic regression, kernel classification with random
convolution layers and shallow neural networks with rectified linear units.
