Simon Shaolei Du 杜少雷

We studied when pretraining provably improves the performance of the downstream task. Based on our theory, we developed an active learning algorithm to select the most relevant pretraining data.

• Variance Alignment Score: A Simple But Tough-to-Beat Data Selection Method for Multimodal Contrastive Learning
  Yiping Wang*, Yifang Chen*, Wendan Yan, Kevin Jamieson, Simon S. Du

• Few-Shot Learning via Learning the Representation, Provably
  Simon S. Du*, Wei Hu*, Sham M. Kakade*, Jason D. Lee*, Qi Lei*
  International Conference on Learning Representations (ICLR) 2021
  

We develop algorithms to obtain optimal complexity guarantees for reinforcement learning. In particular, we showed the sample complexity can be independent of the planning horizon.

• Settling the Sample Complexity of Online Reinforcement Learning
  Zihan Zhang, Yuxin Chen, Jason D. Lee, Simon S. Du

• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
  Zihan Zhang, Xiangyang Ji, Simon S. Du
  Conference of Learning Theory (COLT) 2021
  

We proved the first set of global optimization and generalization guarantees for over-parameterized neural networks in the neural tanget kernel regime [Wikipedia]. Also see our [Blog] for a quick sumary. Recently, we found over-parameterization can exponentially slow down convergence.

• Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron
  Weihang Xu, Simon S. Du
  Conference of Learning Theory (COLT) 2023

• On Exact Computation with an Infinitely Wide Neural Net
  Sanjeev Arora*, Simon S. Du*, Wei Hu*, Zhiyuan Li*, Ruslan Salakhutdinov*, Ruosong Wang*
  Conference on Neural Information Processing Systems (NeurIPS) 2019
  

• Gradient Descent Finds Global Minima of Deep Neural Networks
  Simon S. Du*, Jason D. Lee*, Haochuan Li*, Liwei Wang*, Xiyu Zhai*
  International Conference on Machine Learning (ICML) 2019

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
  Sanjeev Arora*, Simon S. Du*, Wei Hu*, Zhiyuan Li*, Ruosong Wang*
  International Conference on Machine Learning (ICML) 2019

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
  Simon S. Du*, Xiyu Zhai*, Barnabás Póczos, Aarti Singh
  International Conference on Learning Representations (ICLR) 2019

We studied the necessary and sufficient conditions that permit efficient learning for reinforcement learning problems with a large state space.

• 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*
  International Conference on Machine Learning (ICML) 2021
  

• Provably efficient RL with Rich Observations via Latent State Decoding
  Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, John Langford
  International Conference on Machine Learning (ICML) 2019
  

• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
  Simon S. Du*, Sham M. Kakade*, Ruosong Wang*, Lin F. Yang*
  International Conference on Learning Representations (ICLR) 2020
  

We initiated the study on what dataset permits solving offline reinforcement learning problems. We also study MARL with function approximation that avoids the exponential dependency on the # of agents.

• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation
  Qiwen Cui, Kaiqing Zhang, Simon S. Du
  Conference of Learning Theory (COLT) 2023

• When are Offline Two-Player Zero-Sum Markov Games Solvable?
  Qiwen Cui, Simon S. Du
  Conference on Neural Information Processing Systems (NeurIPS) 2022