b'Zhao Song'

research

∙ 09/14/2023

Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?

A rising trend in theoretical deep learning is to understand why deep le...

0 Lianke Qin, et al. ∙

research

∙ 09/14/2023

A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time

Large language models (LLMs) have played a pivotal role in revolutionizi...

0 Yeqi Gao, et al. ∙

research

∙ 09/10/2023

Streaming Semidefinite Programs: O(√(n)) Passes, Small Space and Fast Runtime

We study the problem of solving semidefinite programs (SDP) in the strea...

0 Zhao Song, et al. ∙

research

∙ 08/28/2023

Solving Attention Kernel Regression Problem via Pre-conditioner

Large language models have shown impressive performance in many tasks. O...

0 Zhao Song, et al. ∙

research

∙ 08/23/2023

How to Protect Copyright Data in Optimization of Large Language Models?

Large language models (LLMs) and generative AI have played a transformat...

0 Timothy Chu, et al. ∙

research

∙ 08/21/2023

Clustered Linear Contextual Bandits with Knapsacks

In this work, we study clustered contextual bandits where rewards and re...

0 Yichuan Deng, et al. ∙

research

∙ 08/21/2023

GradientCoin: A Peer-to-Peer Decentralized Large Language Models

Since 2008, after the proposal of a Bitcoin electronic cash system, Bitc...

0 Yeqi Gao, et al. ∙

research

∙ 08/16/2023

Convergence of Two-Layer Regression with Nonlinear Units

Large language models (LLMs), such as ChatGPT and GPT4, have shown outst...

0 Yichuan Deng, et al. ∙

research

∙ 07/17/2023

Zero-th Order Algorithm for Softmax Attention Optimization

Large language models (LLMs) have brought about significant transformati...

0 Yichuan Deng, et al. ∙

research

∙ 07/16/2023

Fast Quantum Algorithm for Attention Computation

Large language models (LLMs) have demonstrated exceptional performance a...

0 Yeqi Gao, et al. ∙

research

∙ 07/15/2023

A Nearly-Linear Time Algorithm for Structured Support Vector Machines

Quadratic programming is a fundamental problem in the field of convex op...

0 Yuzhou Gu, et al. ∙

research

∙ 07/13/2023

Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification

Deep learning has been widely used in many fields, but the model trainin...

0 Lianke Qin, et al. ∙

research

∙ 07/05/2023

In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trick

Large language models (LLMs) have brought significant and transformative...

0 Yeqi Gao, et al. ∙

research

∙ 06/24/2023

H_2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models

Large Language Models (LLMs), despite their recent impressive accomplish...

0 Zhenyu Zhang, et al. ∙

research

∙ 06/07/2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Weighted low rank approximation is a fundamental problem in numerical li...

0 Zhao Song, et al. ∙

research

∙ 06/06/2023

Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis

Many machine learning algorithms require large numbers of labeled data t...

0 Xiang Chen, et al. ∙

research

∙ 06/04/2023

Sparse Convolution for Approximate Sparse Instance

Computing the convolution A ⋆ B of two vectors of dimension n is one of ...

0 Xiaoxiao Li, et al. ∙

research

∙ 06/04/2023

A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models

Large Language Models have become popular for their remarkable capabilit...

0 Ritwik Sinha, et al. ∙

research

∙ 06/01/2023

Faster Robust Tensor Power Method for Arbitrary Order

Tensor decomposition is a fundamental method used in various areas to de...

0 Yichuan Deng, et al. ∙

research

∙ 05/27/2023

Federated Empirical Risk Minimization via Second-Order Method

Many convex optimization problems with important applications in machine...

0 Song Bian, et al. ∙

research

∙ 05/15/2023

Fast Submodular Function Maximization

Submodular functions have many real-world applications, such as document...

0 Lianke Qin, et al. ∙

research

∙ 05/15/2023

Fast and Efficient Matching Algorithm with Deadline Instances

Online weighted matching problem is a fundamental problem in machine lea...

0 Zhao Song, et al. ∙

research

∙ 05/13/2023

Efficient Asynchronize Stochastic Gradient Algorithm with Structured Data

Deep learning has achieved impressive success in a variety of fields bec...

0 Zhao Song, et al. ∙

research

∙ 05/08/2023

Differentially Private Attention Computation

Large language models (LLMs) have had a profound impact on numerous aspe...

0 Yeqi Gao, et al. ∙

research

∙ 05/01/2023

An Iterative Algorithm for Rescaled Hyperbolic Functions Regression

Large language models (LLMs) have numerous real-life applications across...

0 Yeqi Gao, et al. ∙

research

∙ 04/26/2023

PVP: Pre-trained Visual Parameter-Efficient Tuning

Large-scale pre-trained transformers have demonstrated remarkable succes...

0 Zhao Song, et al. ∙

research

∙ 04/26/2023

The Closeness of In-Context Learning and Weight Shifting for Softmax Regression

Large language models (LLMs) are known for their exceptional performance...

0 Shuai Li, et al. ∙

research

∙ 04/20/2023

Attention Scheme Inspired Softmax Regression

Large language models (LLMs) have made transformed changes for human soc...

0 Yichuan Deng, et al. ∙

research

∙ 04/13/2023

Solving Tensor Low Cycle Rank Approximation

Large language models have become ubiquitous in modern life, finding app...

0 Yichuan Deng, et al. ∙

research

∙ 04/10/2023

Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension

Large language models (LLMs) have shown their power in different areas. ...

0 Yichuan Deng, et al. ∙

research

∙ 04/07/2023

Convex Minimization with Integer Minima in O(n^4) Time

Given a convex function f on ℝ^n with an integer minimizer, we show how ...

0 Haotian Jiang, et al. ∙

research

∙ 04/05/2023

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models

Large language models (LLMs) have made fundamental changes in human life...

0 Jan van den Brand, et al. ∙

research

∙ 03/29/2023

An Over-parameterized Exponential Regression

Over the past few years, there has been a significant amount of research...

0 Yeqi Gao, et al. ∙

research

∙ 03/28/2023

Solving Regularized Exp, Cosh and Sinh Regression Problems

In modern machine learning, attention computation is a fundamental task ...

0 Zhihang Li, et al. ∙

research

∙ 03/22/2023

A General Algorithm for Solving Rank-one Matrix Sensing

Matrix sensing has many real-world applications in science and engineeri...

0 Lianke Qin, et al. ∙

research

∙ 03/13/2023

An Improved Sample Complexity for Rank-1 Matrix Sensing

Matrix sensing is a problem in signal processing and machine learning th...

0 Yichuan Deng, et al. ∙

research

∙ 03/10/2023

A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph

Graph-based algorithms have demonstrated state-of-the-art performance in...

1 Anshumali Shrivastava, et al. ∙

research

∙ 03/08/2023

Streaming Kernel PCA Algorithm With Small Space

Principal Component Analysis (PCA) is a widely used technique in machine...

0 Yichuan Deng, et al. ∙

research

∙ 02/26/2023

Fast Attention Requires Bounded Entries

In modern machine learning, inner product attention computation is a fun...

0 Josh Alman, et al. ∙

research

∙ 02/21/2023

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Given a matrix M∈ℝ^m× n, the low rank matrix completion problem asks us ...

0 Yuzhou Gu, et al. ∙

research

∙ 02/01/2023

A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee

Given a matrix A∈ℝ^n× d and a vector b∈ℝ^n, we consider the regression p...

0 Zhao Song, et al. ∙

research

∙ 01/17/2023

Faster Sinkhorn's Algorithm with Small Treewidth

Computing optimal transport (OT) distances such as the earth mover's dis...

0 Zhao Song, et al. ∙

research

∙ 12/21/2022

Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations

In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resol...

0 Lianke Qin, et al. ∙

research

∙ 12/10/2022

Adore: Differentially Oblivious Relational Database Operators

There has been a recent effort in applying differential privacy on memor...

0 Lianke Qin, et al. ∙

research

∙ 11/28/2022

A Faster k-means++ Algorithm

K-means++ is an important algorithm to choose initial cluster centers fo...

0 Jiehao Liang, et al. ∙

research

∙ 11/27/2022

Dynamic Kernel Sparsifiers

A geometric graph associated with a set of points P= {x_1, x_2, ⋯, x_n }...

0 Yichuan Deng, et al. ∙

research

∙ 11/26/2022

Faster Algorithm for Structured John Ellipsoid Computation

Computing John Ellipsoid is a fundamental problem in machine learning an...

0 Zhao Song, et al. ∙

research

∙ 11/25/2022

Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing

Over the last decade, deep neural networks have transformed our society,...

0 Josh Alman, et al. ∙

research

∙ 11/11/2022

A Faster Small Treewidth SDP Solver

Semidefinite programming is a fundamental tool in optimization and theor...

0 Yuzhou Gu, et al. ∙

research

∙ 11/03/2022

A Convergence Theory for Federated Average: Beyond Smoothness

Federated learning enables a large amount of edge computing devices to l...

5 Xiaoxiao Li, et al. ∙

Zhao Song

Featured Co-authors