1 citations · 4 across the 9 of their papers we have counts for
10 papers
Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
Zhao Song, Lichen Zhang
Randomized sketch-and-solve algorithms accelerate overconstrained regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the…
Sublinear Time Quantum Algorithm for Attention Approximation
Zhao Song, Jianfei Xue, Jiahao Zhang +1
Given the query, key and value matrices , the attention module is defined as where wi…
A Unified Scheme of ResNet and Softmax
Zhao Song, Weixin Wang, Junze Yin
Large language models (LLMs) have brought significant changes to human society. Softmax regression and residual neural networks (ResNet) are two important techniques in deep learni…
Streaming Semidefinite Programs: Passes, Small Space and Fast Runtime
Zhao Song, Mingquan Ye, Lichen Zhang
We study the problem of solving semidefinite programs (SDP) in the streaming model. Specifically, constraint matrices and a target matrix , all of size together…
Solving Attention Kernel Regression Problem via Pre-conditioner
Zhao Song, Junze Yin, Lichen Zhang
The attention mechanism is the key to large language models, and the attention matrix serves as an algorithmic and computational bottleneck for such a scheme. In this paper, we def…
Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Yuzhou Gu, Zhao Song, Lichen Zhang
Quadratic programming is a ubiquitous prototype in convex programming. Many machine learning problems can be formulated as quadratic programming, including the famous Support Vecto…
Efficient Algorithm for Solving Hyperbolic Programs
Yichuan Deng, Zhao Song, Lichen Zhang +1
Hyperbolic polynomials is a class of real-roots polynomials that has wide range of applications in theoretical computer science. Each hyperbolic polynomial also induces a hyperboli…
Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation
Zhao Song, Mingquan Ye, Junze Yin +1
Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix $M \in \mathbb{R}^{n \times n…
Federated Empirical Risk Minimization via Second-Order Method
Song Bian, Zhao Song, Junze Yin
Many convex optimization problems with important applications in machine learning are formulated as empirical risk minimization (ERM). There are several examples: linear and logist…
Convex Minimization with Integer Minima in Time
Haotian Jiang, Yin Tat Lee, Zhao Song +1
Given a convex function on with an integer minimizer, we show how to find an exact minimizer of using calls to a separation oracle and $O(n^4…