Ruosong Wang

Ruosong Wang

I am currently a fifth year Ph.D. student at Carnegie Mellon University (2017-Present). I am extremely fortunate to be advised by Ruslan Salakhutdinov. I have broad interest in the theory and applications of modern machine learning, including reinforcement learning in particular.

In Summer 2020, I interned at Microsoft Research, New York and worked with Sham M. Kakade on reinforcement learning.

In Summer 2019, I visited Princeton University and worked with Sanjeev Arora on deep learning theory.

I did my undergraduate study in Yao Class (2013-2017), Tsinghua University, where I worked closely with Jian Li, Pingzhong Tang and Ran Duan.

During my undergraduate I visited University of Michigan in Spring 2016 and worked with Seth Pettie on distributed computing.

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

Publications

(*alphabetic author order, **equal contribution)

Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
Yuanzhi Li*, Ruosong Wang*, Lin F. Yang*
FOCS 2021
arXiv

An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
Yuanhao Wang, Ruosong Wang, Sham M. Kakade
NeurIPS 2021 (Oral)
arXiv

Instabilities of Offline RL with Pre-Trained Neural Representation
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, Sham M. Kakade
ICML 2021
arXiv

Bilinear Classes: A Structural Framework for Provable Generalization in RL
Simon S. Du*, Sham M. Kakade*, Jason D. Lee*, Shachar Lovett*, Gaurav Mahajan*, Wen Sun*, Ruosong Wang*
ICML 2021
arXiv

What are the Statistical Limits of Offline RL with Linear Function Approximation?
Ruosong Wang, Dean Foster, Sham M. Kakade
ICLR 2021 (Spotlight)
Selected for oral presentation in NeurIPS 2020 Offline Reinforcement Learning Workshop
arXiv

Optimism in Reinforcement Learning with Generalized Linear Function Approximation
Yining Wang, Ruosong Wang, Simon Shaolei Du, Akshay Krishnamurthy
ICLR 2021
arXiv

Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang
NeurIPS 2020
arXiv

Is Long Horizon RL More Difficult Than Short Horizon RL?
Ruosong Wang**, Simon S. Du**, Lin F. Yang**, Sham M. Kakade
NeurIPS 2020
arXiv

On Reward-Free Reinforcement Learning with Linear Function Approximation
Ruosong Wang, Simon S. Du, Lin F. Yang, Ruslan Salakhutdinov
NeurIPS 2020
arXiv

Planning with General Objective Functions: Going Beyond Total Rewards
Ruosong Wang**, Peilin Zhong**, Simon S. Du, Ruslan Salakhutdinov, Lin F. Yang
NeurIPS 2020

Agnostic Q-learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity
Simon S. Du*, Jason D. Lee*, Gaurav Mahajan*, Ruosong Wang*
NeurIPS 2020
arXiv

Provably Efficient Exploration for RL with Unsupervised Learning
Fei Feng, Ruosong Wang, Wotao Yin, Simon S. Du, Lin F. Yang
NeurIPS 2020 (Spotlight)
arXiv

Preference-based Reinforcement Learning with Finite-Time Guarantees
Yichong Xu, Ruosong Wang, Lin F. Yang, Aarti Singh, Artur Dubrawski
NeurIPS 2020 (Spotlight)
arXiv

Nearly Linear Row Sampling Algorithm for Quantile Regression
Yi Li*, Ruosong Wang*, Lin F. Yang*, Hanrui Zhang*
ICML 2020
arXiv

Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Simon S. Du*, Sham M. Kakade*, Ruosong Wang*, Lin F. Yang*
ICLR 2020 (Spotlight)
Selected as a Late-Breaking Paper in NeurIPS 2019 Deep Reinforcement Learning Workshop
arXiv

Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
Sanjeev Arora*, Simon S. Du*, Zhiyuan Li*, Ruslan Salakhutdinov*, Ruosong Wang*, Dingli Yu*
ICLR 2020 (Spotlight)
arXiv

Tight Bounds for the Subspace Sketch Problem with Applications
Yi Li*, Ruosong Wang*, David P. Woodruff*
SODA 2020
SIAM Journal on Computing, 50(4), 1287-1335, 2021
arXiv

The Communication Complexity of Optimization
Santosh S. Vempala*, Ruosong Wang*, David P. Woodruff*
SODA 2020
Invited to Highlights of Algorithms (HALG) 2020
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 (Spotlight)
arXiv Code

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

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

Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song*, Ruosong Wang*, Lin F. Yang*, Hongyang Zhang*, Peilin Zhong*.
NeurIPS 2019
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.
TA for 15-451/651: Algorithms, Fall 2020.

Conference Reviewing

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