b'Zhao Song'

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. ∙

research

∙ 10/22/2022

Quartic Samples Suffice for Fourier Interpolation

We study the problem of interpolating a noisy Fourier-sparse signal in t...

0 Zhao Song, et al. ∙

research

∙ 10/22/2022

Discrepancy Minimization in Input-Sparsity Time

A recent work of Larsen [Lar23] gave a faster combinatorial alternative ...

0 Yichuan Deng, et al. ∙

research

∙ 10/20/2022

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance

Projection maintenance is one of the core data structure tasks. Efficien...

0 Zhao Song, et al. ∙

research

∙ 10/15/2022

Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability

Sketching is one of the most fundamental tools in large-scale machine le...

0 Zhao Song, et al. ∙

research

∙ 10/15/2022

A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time

A coreset is a point set containing information about geometric properti...

0 Yichuan Deng, et al. ∙

research

∙ 10/08/2022

Dynamic Tensor Product Regression

In this work, we initiate the study of Dynamic Tensor Product Regression...

0 Aravind Reddy, et al. ∙

research

∙ 08/20/2022

An O(klog n) Time Fourier Set Query Algorithm

Fourier transformation is an extensively studied problem in many researc...

0 Yeqi Gao, et al. ∙

research

∙ 08/10/2022

A Sublinear Adversarial Training Algorithm

Adversarial training is a widely used strategy for making neural network...

0 Yeqi Gao, et al. ∙

research

∙ 08/09/2022

Training Overparametrized Neural Networks in Sublinear Time

The success of deep learning comes at a tremendous computational and ene...

0 Hang Hu, et al. ∙

research

∙ 08/08/2022

Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory

Kernel density estimation (KDE) stands out as a challenging task in mach...

0 Jiehao Liang, et al. ∙

research

∙ 08/07/2022

Federated Adversarial Learning: A Framework with Convergence Analysis

Federated learning (FL) is a trending training paradigm to utilize decen...

5 Xiaoxiao Li, et al. ∙

research

∙ 08/05/2022

Sublinear Time Algorithm for Online Weighted Bipartite Matching

Online bipartite matching is a fundamental problem in online algorithms....

0 Hang Hu, et al. ∙

research

∙ 07/19/2022

Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures

In this paper, we study the problem of speeding up a type of optimizatio...

0 Zhao Song, et al. ∙

research

∙ 06/26/2022

Bounding the Width of Neural Networks via Coupled Initialization – A Worst Case Analysis

A common method in training neural networks is to initialize all the wei...

0 Alexander Munteanu, et al. ∙

research

∙ 05/30/2022

Fast Distance Oracles for Any Symmetric Norm

In the Distance Oracle problem, the goal is to preprocess n vectors x_1,...

0 Yichuan Deng, et al. ∙

research

∙ 05/02/2022

Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction

We revisit the classical problem of band-limited signal reconstruction –...

0 Zhao Song, et al. ∙

research

∙ 04/23/2022

Smoothed Online Combinatorial Optimization Using Imperfect Predictions

Smoothed online combinatorial optimization considers a learner who repea...

0 Kai Wang, et al. ∙

research

∙ 04/15/2022

Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning

An ideal learned representation should display transferability and robus...

11 Mayee F. Chen, et al. ∙

Zhao Song

Featured Co-authors