Ruosong Wang

I am currently a third-year Ph.D. student at Carnegie Mellon University. I am extremely fortunate to be advised by Ruslan Salakhutdinov. I have broad interest in the theory and applications of machine learning, including deep learning, reinforcement learning and non-convex optimization. I did my undergraduate study in Yao Class, Tsinghua University, where I worked closely with Jian Li, Pingzhong Tang and Ran Duan. During my undergraduate I spent a happy semester at University of Michigan, working with Seth Pettie on distributed computing.

Email: ruosongw [at] andrew [dot] cmu [dot] edu.

Publications

Note: Authors in all these papers are ordered alphabetically.

Tight Bounds for the Subspace Sketch Problem with Applications
Yi Li, Ruosong Wang, David P. Woodruff
SODA 2020 (to appear)
arXiv

The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
SODA 2020 (to appear)
arXiv

On Exact Computation with an Infinitely Wide Neural Net
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang.
NeurIPS 2019 (to appear)
Spotlight Presentation
arXiv

Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang.
NeurIPS 2019 (to appear)
arXiv

Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabas Poczos, Ruosong Wang, Keyulu Xu.
NeurIPS 2019 (to appear)
arXiv

Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, Peilin Zhong.
NeurIPS 2019 (to appear)
arXiv

Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang.
ICML 2019
arXiv

Dimensionality Reduction for Tukey Regression
Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff.
ICML 2019
arXiv

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
Lijie Chen, Ruosong Wang.
ITCS 2019
arXiv

Tight Bounds for $\ell_p$ Oblivious Subspace Embeddings
Ruosong Wang, David P. Woodruff.
SODA 2019
Invited to the special issue of ACM Transactions on Algorithms for SODA 2019
arXiv

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang and Tianyi Zhang.
SWAT 2018
arXiv

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang
COLT 2017
arXiv

Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
STOC 2017
ACM Transactions on Algorithms 15(4), Article 49, 2019
arXiv

Efficient Near-optimal Algorithms for Barter Exchange
Zhipeng Jia, Pingzhong Tang, Ruosong Wang, Hanrui Zhang
AAMAS 2017
PDF

k-Regret Minimizing Set: Efficient Algorithms and Hardness
Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, Wei Zhan
ICDT 2017
Best Newcomer Award
PDF

Bounded Rationality of Restricted Turing Machines
Lijie Chen, Pingzhong Tang, Ruosong Wang
AAAI 2017
PDF

Teaching

TA for 15-750 Graduate Algorithms, Spring 2019.

Conference Reviewing

NeurIPS (2018, 2019), ICML (2019), ICLR (2019, 2020), COLT (2018, 2019), AISTATS (2020), FOCS (2019), AAAI (2020), UAI (2019), ISIT (2019).