384 citations · 1.1k across the 22 of their papers we have counts for
24 papers
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
Yuanzhi Li, Ruosong Wang, Lin F. Yang
Recently there is a surge of interest in understanding the horizon-dependence of the sample complexity in reinforcement learning (RL). Notably, for an RL environment with horizon l…
An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
Yuanhao Wang, Ruosong Wang, Sham M. Kakade
A fundamental question in the theory of reinforcement learning is: suppose the optimal -function lies in the linear span of a given dimensional feature mapping, is sample-ef…
Bilinear Classes: A Structural Framework for Provable Generalization in RL
Simon S. Du, Sham M. Kakade, Jason D. Lee +4
This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function a…
Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang
Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory f…
Nearly Linear Row Sampling Algorithm for Quantile Regression
Yi Li, Ruosong Wang, Lin Yang +1
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm w…
Preference-based Reinforcement Learning with Finite-Time Guarantees
Yichong Xu, Ruosong Wang, Lin F. Yang +2
Preference-based Reinforcement Learning (PbRL) replaces reward values in traditional reinforcement learning by preferences to better elicit human opinion on the target objective, e…
Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
Fei Feng, Ruosong Wang, Wotao Yin +2
Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems [tang2017exploration,bellemare2016unifying], w…
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
Simon S. Du, Jason D. Lee, Gaurav Mahajan +1
The current paper studies the problem of agnostic -learning with function approximation in deterministic systems where the optimal -function is approximable by a function in…
Optimism in Reinforcement Learning with Generalized Linear Function Approximation
Yining Wang, Ruosong Wang, Simon S. Du +1
We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity a…
Enhanced Convolutional Neural Tangent Kernels
Zhiyuan Li, Ruosong Wang, Dingli Yu +4
Recent research shows that for training with loss, convolutional neural networks (CNNs) whose width (number of channels in convolutional layers) goes to infinity correspon…
Continuous Control with Contexts, Provably
Simon S. Du, Ruosong Wang, Mengdi Wang +1
A fundamental challenge in artificial intelligence is to build an agent that generalizes and adapts to unseen environments. A common strategy is to build a decoder that takes the c…
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
Sanjeev Arora, Simon S. Du, Zhiyuan Li +3
Recent research shows that the following two models are equivalent: (a) infinitely wide neural networks (NNs) trained under l2 loss by gradient descent with infinitesimally small l…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Simon S. Du, Sham M. Kakade, Ruosong Wang +1
Modern deep learning methods provide effective means to learn good representations. However, is a good representation itself sufficient for sample efficient reinforcement learning?…
The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator toge…
Dimensionality Reduction for Tukey Regression
Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff
We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function has …
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
Simon S. Du, Kangcheng Hou, Barnabás Póczos +3
While graph kernels (GKs) are easy to train and enjoy provable theoretical guarantees, their practical performances are limited by their expressive power, as the kernel function of…
On Exact Computation with an Infinitely Wide Neural Net
Sanjeev Arora, Simon S. Du, Wei Hu +3
How well does a classic deep net architecture like AlexNet or VGG19 classify on a standard dataset such as CIFAR-10 when its width --- namely, number of channels in convolutional l…
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
Sanjeev Arora, Simon S. Du, Wei Hu +2
Recent works have cast some light on the mystery of why deep nets fit any data and generalize despite being very overparametrized. This paper analyzes training and generalization f…
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
Lijie Chen, Ruosong Wang
The polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times. As observed in [Alman and Williams, S…
Tight Bounds for Oblivious Subspace Embeddings
Ruosong Wang, David P. Woodruff
An oblivious subspace embedding is a distribution over matrices such that for any fixed matrix , $$\Pr_Π[\textrm{for all }x, \ \|Ax\|_p \l…
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Lijie Chen, Anupam Gupta, Jian Li +2
We study the combinatorial pure exploration problem Best-Set in stochastic multi-armed bandits. In a Best-Set instance, we are given arms with unknown reward distributions, as…
Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie +2
Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), n…
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang +2
Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph with vertices and …