Recovering the Optimal Solution by Dual Random Projection

Abstract

Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance of using random projection, in this work, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original optimization problem in the high-dimensional space based on the solution learned from the subspace spanned by random projections. We present a simple algorithm, termed Dual Random Projection, that uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is of low rank or can be well approximated by a low rank matrix.

The 26th Annual Conference on Learning Theory (COLT 2013)

References in corpus (4)

• Is margin preserved after random projection?
• Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
• A Simple Algorithm for Semi-supervised Learning with Improved Generalization Error Bound
• A short note on the tail bound of Wishart distribution

Cited by in corpus (17)

• Fine-Grained Visual Categorization via Multi-stage Metric Learning
• Theory of Dual-sparse Regularized Randomized Reduction
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
• A New Analysis of Compressive Sensing by Stochastic Proximal Gradient Descent
• Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Improved Subsampled Randomized Hadamard Transform for Linear SVM
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Compressed and Penalized Linear Regression
• Sketching in Bayesian High Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors
• Random Projections for Linear Support Vector Machines
• High-Dimensional Optimization in Adaptive Random Subspaces
• Similarity Learning via Adaptive Regression and Its Application to Image Retrieval
• Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees
• Sparse Learning for Large-scale and High-dimensional Data: A Randomized Convex-concave Optimization Approach
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery
• Stable Sparse Subspace Embedding for Dimensionality Reduction