688 citations · 1.5k across the 49 of their papers we have counts for
9 papers · 1 filter
Sparse Convolution for Approximate Sparse Instance
Xiaoxiao Li, Zhao Song, Guangyi Zhang
Computing the convolution of two vectors of dimension is one of the most important computational primitives in many fields. For the non-negative convolution scenari…
Faster Robust Tensor Power Method for Arbitrary Order
Yichuan Deng, Zhao Song, Junze Yin
Tensor decomposition is a fundamental method used in various areas to deal with high-dimensional data. \emph{Tensor power method} (TPM) is one of the widely-used techniques in the…
Solving Tensor Low Cycle Rank Approximation
Yichuan Deng, Yeqi Gao, Zhao Song
Large language models have become ubiquitous in modern life, finding applications in various domains such as natural language processing, language translation, and speech recogniti…
Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension
Yichuan Deng, Sridhar Mahadevan, Zhao Song
Large language models (LLMs) have shown their power in different areas. Attention computation, as an important subroutine of LLMs, has also attracted interests in theory. Recently…
Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
Jan van den Brand, Zhao Song, Tianyi Zhou
Large language models (LLMs) have made fundamental changes in human life. The attention scheme is one of the key components over all the LLMs, such as BERT, GPT-1, Transformers, GP…
An Over-parameterized Exponential Regression
Yeqi Gao, Sridhar Mahadevan, Zhao Song
Over the past few years, there has been a significant amount of research focused on studying the ReLU activation function, with the aim of achieving neural network convergence thro…
An Improved Sample Complexity for Rank-1 Matrix Sensing
Yichuan Deng, Zhihang Li, Zhao Song
Matrix sensing is a problem in signal processing and machine learning that involves recovering a low-rank matrix from a set of linear measurements. The goal is to reconstruct the o…
Solving Regularized Exp, Cosh and Sinh Regression Problems
Zhihang Li, Zhao Song, Tianyi Zhou
In modern machine learning, attention computation is a fundamental task for training large language models such as Transformer, GPT-4 and ChatGPT. In this work, we study exponentia…
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Yuzhou Gu, Zhao Song, Junze Yin +1
Given a matrix , the low rank matrix completion problem asks us to find a rank- approximation of as for …