688 citations · 1.5k across the 49 of their papers we have counts for
9 papers · 1 filter
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Yin Tat Lee, Zhao Song, Santosh S. Vempala
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamil…
A Convergence Theory for Deep Learning via Over-Parameterization
Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a…
Towards a Zero-One Law for Column Subset Selection
Zhao Song, David P. Woodruff, Peilin Zhong
There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank- matrix minimizing the sum of absolute values of differ…
On the Convergence Rate of Training Recurrent Neural Networks
Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
How can local-search methods such as stochastic gradient descent (SGD) avoid bad local minima in training multi-layer neural networks? Why can they fit random labels even given non…
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
This paper shows how to solve linear programs of the form with variables in time where is the e…
Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
Kai Zhong, Zhao Song, Prateek Jain +1
The goal of a recommendation system is to predict the interest of a user in a given item by exploiting the existing set of ratings as well as certain user/item features. A standard…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…
Towards Fast Computation of Certified Robustness for ReLU Networks
Tsui-Wei Weng, Huan Zhang, Hongge Chen +5
Verifying the robustness property of a general Rectified Linear Unit (ReLU) network is an NP-complete problem [Katz, Barrett, Dill, Julian and Kochenderfer CAV17]. Although finding…
Learning Long Term Dependencies via Fourier Recurrent Units
Jiong Zhang, Yibo Lin, Zhao Song +1
It is a known fact that training recurrent neural networks for tasks that have long term dependencies is challenging. One of the main reasons is the vanishing or exploding gradient…