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...
share
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...
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...
research
∙
08/28/2023
Solving Attention Kernel Regression Problem via Pre-conditioner
Large language models have shown impressive performance in many tasks. O...
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...
research
∙
08/21/2023
Clustered Linear Contextual Bandits with Knapsacks
In this work, we study clustered contextual bandits where rewards and re...
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...
research
∙
08/16/2023
Convergence of Two-Layer Regression with Nonlinear Units
Large language models (LLMs), such as ChatGPT and GPT4, have shown outst...
research
∙
07/17/2023
Zero-th Order Algorithm for Softmax Attention Optimization
Large language models (LLMs) have brought about significant transformati...
research
∙
07/16/2023
Fast Quantum Algorithm for Attention Computation
Large language models (LLMs) have demonstrated exceptional performance a...
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...
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...
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...
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...
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...
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...
research
∙
06/04/2023
Sparse Convolution for Approximate Sparse Instance
Computing the convolution A ⋆ B of two vectors of dimension n is one of ...
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...
research
∙
06/01/2023
Faster Robust Tensor Power Method for Arbitrary Order
Tensor decomposition is a fundamental method used in various areas to de...
research
∙
05/27/2023
Federated Empirical Risk Minimization via Second-Order Method
Many convex optimization problems with important applications in machine...
research
∙
05/15/2023
Fast Submodular Function Maximization
Submodular functions have many real-world applications, such as document...
research
∙
05/15/2023
Fast and Efficient Matching Algorithm with Deadline Instances
Online weighted matching problem is a fundamental problem in machine lea...
research
∙
05/13/2023
Efficient Asynchronize Stochastic Gradient Algorithm with Structured Data
Deep learning has achieved impressive success in a variety of fields bec...
research
∙
05/08/2023
Differentially Private Attention Computation
Large language models (LLMs) have had a profound impact on numerous aspe...
research
∙
05/01/2023
An Iterative Algorithm for Rescaled Hyperbolic Functions Regression
Large language models (LLMs) have numerous real-life applications across...
research
∙
04/26/2023
PVP: Pre-trained Visual Parameter-Efficient Tuning
Large-scale pre-trained transformers have demonstrated remarkable succes...
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...
research
∙
04/20/2023
Attention Scheme Inspired Softmax Regression
Large language models (LLMs) have made transformed changes for human soc...
research
∙
04/13/2023
Solving Tensor Low Cycle Rank Approximation
Large language models have become ubiquitous in modern life, finding app...
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. ...
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 ...
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...
research
∙
03/29/2023
An Over-parameterized Exponential Regression
Over the past few years, there has been a significant amount of research...
research
∙
03/28/2023
Solving Regularized Exp, Cosh and Sinh Regression Problems
In modern machine learning, attention computation is a fundamental task ...
research
∙
03/22/2023
A General Algorithm for Solving Rank-one Matrix Sensing
Matrix sensing has many real-world applications in science and engineeri...
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...
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...
research
∙
03/08/2023
Streaming Kernel PCA Algorithm With Small Space
Principal Component Analysis (PCA) is a widely used technique in machine...
research
∙
02/26/2023
Fast Attention Requires Bounded Entries
In modern machine learning, inner product attention computation is a fun...
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 ...
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...
research
∙
01/17/2023
Faster Sinkhorn's Algorithm with Small Treewidth
Computing optimal transport (OT) distances such as the earth mover's dis...
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...
research
∙
12/10/2022
Adore: Differentially Oblivious Relational Database Operators
There has been a recent effort in applying differential privacy on memor...
research
∙
11/28/2022
A Faster k-means++ Algorithm
K-means++ is an important algorithm to choose initial cluster centers fo...
research
∙
11/27/2022
Dynamic Kernel Sparsifiers
A geometric graph associated with a set of points P= {x_1, x_2, ⋯, x_n }...
research
∙
11/26/2022
Faster Algorithm for Structured John Ellipsoid Computation
Computing John Ellipsoid is a fundamental problem in machine learning an...
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,...
research
∙
11/11/2022
A Faster Small Treewidth SDP Solver
Semidefinite programming is a fundamental tool in optimization and theor...
research
∙
11/03/2022