9 citations · 50 across the 16 of their papers we have counts for
17 papers
Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification
Lianke Qin, Zhao Song, Yuanyuan Yang
Deep learning has been widely used in many fields, but the model training process usually consumes massive computational resources and time. Therefore, designing an efficient neura…
Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration
Boyu Liu, Lianke Qin, Zhao Song +2
Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility…
Fast Attention Requires Bounded Entries
Josh Alman, Zhao Song
In modern machine learning, inner product attention computation is a fundamental task for training large language models such as Transformer, GPT-1, BERT, GPT-2, GPT-3 and ChatGPT.…
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
Josh Alman, Jiehao Liang, Zhao Song +2
Over the last decade, deep neural networks have transformed our society, and they are already widely applied in various machine learning applications. State-of-art deep neural netw…
Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability
Zhao Song, Yitan Wang, Zheng Yu +1
Sketching is one of the most fundamental tools in large-scale machine learning. It enables runtime and memory saving via randomly compressing the original large problem into lower…
A Sublinear Adversarial Training Algorithm
Yeqi Gao, Lianke Qin, Zhao Song +1
Adversarial training is a widely used strategy for making neural networks resistant to adversarial perturbations. For a neural network of width , input training data in …
A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework
Baihe Huang, Shunhua Jiang, Zhao Song +2
This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SD…
Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis
Alexander Munteanu, Simon Omlor, Zhao Song +1
A common method in training neural networks is to initialize all the weights to be independent Gaussian vectors. We observe that by instead initializing the weights into independen…
Fast Graph Neural Tangent Kernel via Kronecker Sketching
Shunhua Jiang, Yunze Man, Zhao Song +2
Many deep learning tasks have to deal with graphs (e.g., protein structures, social networks, source code abstract syntax trees). Due to the importance of these tasks, people turne…
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
Zhao Song, Lichen Zhang, Ruizhe Zhang
We consider the problem of training a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-paramet…
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
Tri Dao, Beidi Chen, Kaizhao Liang +4
Overparameterized neural networks generalize well but are expensive to train. Ideally, one would like to reduce their computational cost while retaining their generalization benefi…
Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures
Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
Conditional gradient methods (CGM) are widely used in modern machine learning. CGM's overall running time usually consists of two parts: the number of iterations and the cost of ea…
Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes
Aravind Reddy, Ryan A. Rossi, Zhao Song +6
In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbi…
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
Beidi Chen, Tri Dao, Eric Winsor +3
Recent advances in efficient Transformers have exploited either the sparsity or low-rank properties of attention matrices to reduce the computational and memory bottlenecks of mode…
Does Preprocessing Help Training Over-parameterized Neural Networks?
Zhao Song, Shuo Yang, Ruizhe Zhang
Deep neural networks have achieved impressive performance in many areas. Designing a fast and provable method for training neural networks is a fundamental question in machine lear…
Fast Sketching of Polynomial Kernels of Polynomial Degree
Zhao Song, David P. Woodruff, Zheng Yu +1
Kernel methods are fundamental in machine learning, and faster algorithms for kernel approximation provide direct speedups for many core tasks in machine learning. The polynomial k…
Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
Josh Alman, Timothy Chu, Gary Miller +3
In this paper, we develop a new technique which we call representation theory of the real hyperrectangle, which describes how to compute the eigenvectors and eigenvalues of certain…