Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds

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