Recovering Optimal Solution by Dual Random Projection
Random projection has been widely used in data classification. It maps high-dimensional data into a low dimensional space 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 solution to the optimization problem in the original 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 to the low-dimensional optimization problem to recover the solution to the original optimization problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution in the high dimensional space, provided that the data matrix is of low rank. We also examine the relationship between compressive sensing and the problem of recovering optimal solution using random projection.
Speaker Details
Dr. Rong Jin is a professor in the Department of Computer Science and Engineering at Michigan State University, and is currently lead the Seattle lab of Alibaba. His research is focused on statistical machine learning and its application to big data analysis. He has published over 200 technical papers, most in prestigious conferences (NIPS, ICML, KDD, SIGIR, CVPR, ICCV) and journals (TPAMI, JMLR, JML, and TKDD). Dr. Jin has served as area chair for NIPS 2013 and SIGIR 2008, and associate editor for TPAMI and ACM KDD. He received his Ph.D. in Computer Science from Carnegie Mellon University in 2003, NSF Career Award in 2006 and the best student paper award from COLT in 2012.
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Rong Jin
- Affiliation:
- Michigan State University
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-