b'Zhao Song'

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

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

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

Zhao Song, et al. ∙

research

∙ 04/23/2022

Smoothed Online Combinatorial Optimization Using Imperfect Predictions

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

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

Mayee F. Chen, et al. ∙

research

∙ 04/07/2022

Speeding Up Sparsification using Inner Product Search Data Structures

We present a general framework that utilizes different efficient data st...

Zhao Song, et al. ∙

research

∙ 02/24/2022

A Dynamic Fast Gaussian Transform

The Fast Gaussian Transform (FGT) enables subquadratic-time multiplicati...

Baihe Huang, et al. ∙

research

∙ 12/14/2021

Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time

We consider the problem of training a multi-layer over-parametrized neur...

Zhao Song, et al. ∙

research

∙ 12/09/2021

On Convergence of Federated Averaging Langevin Dynamics

We propose a federated averaging Langevin algorithm (FA-LD) for uncertai...

Wei Deng, et al. ∙

research

∙ 12/04/2021

Fast Graph Neural Tangent Kernel via Kronecker Sketching

Many deep learning tasks have to deal with graphs (e.g., protein structu...

Shunhua Jiang, et al. ∙

research

∙ 11/30/2021

Evaluating Gradient Inversion Attacks and Defenses in Federated Learning

Gradient inversion attack (or input recovery from gradient) is an emergi...

Yangsibo Huang, et al. ∙

research

∙ 11/30/2021

Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models

Overparameterized neural networks generalize well but are expensive to t...

Beidi Chen, et al. ∙

research

∙ 11/30/2021

Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures

Conditional gradient methods (CGM) are widely used in modern machine lea...

Anshumali Shrivastava, et al. ∙

research

∙ 11/20/2021

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

Longest common subsequence (𝖫𝖢𝖲) is a classic and central problem in com...

Aviad Rubinstein, et al. ∙

research

∙ 11/04/2021

An Interpretable Graph Generative Model with Heterophily

Many models for graphs fall under the framework of edge-independent dot ...

Sudhanshu Chanpuriya, et al. ∙

research

∙ 10/28/2021

Scatterbrain: Unifying Sparse and Low-rank Attention Approximation

Recent advances in efficient Transformers have exploited either the spar...

Beidi Chen, et al. ∙

research

∙ 10/09/2021

Does Preprocessing Help Training Over-parameterized Neural Networks?

Deep neural networks have achieved impressive performance in many areas....

Zhao Song, et al. ∙

research

∙ 08/21/2021

Fast Sketching of Polynomial Kernels of Polynomial Degree

Kernel methods are fundamental in machine learning, and faster algorithm...

Zhao Song, et al. ∙

research

∙ 05/18/2021

Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing

We present the first provable Least-Squares Value Iteration (LSVI) algor...

Anshumali Shrivastava, et al. ∙

research

∙ 05/11/2021

FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis

Federated Learning (FL) is an emerging learning scheme that allows diffe...

Baihe Huang, et al. ∙

research

∙ 02/22/2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

For a directed graph G with n vertices and a start vertex u_ start, we w...

Lijie Chen, et al. ∙

research

∙ 02/02/2021

Symmetric Boolean Factor Analysis with Applications to InstaHide

In this work we examine the security of InstaHide, a recently proposed s...

Sitan Chen, et al. ∙

research

∙ 01/20/2021

Solving Tall Dense SDPs in the Current Matrix Multiplication Time

This paper introduces a new interior point method algorithm that solves ...

Baihe Huang, et al. ∙

research

∙ 01/14/2021

Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances

In this paper we provide new randomized algorithms with improved runtime...

Jan van den Brand, et al. ∙

research

∙ 11/24/2020

InstaHide's Sample Complexity When Mixing Two Private Images

Inspired by InstaHide challenge [Huang, Song, Li and Arora'20], [Chen, S...

Baihe Huang, et al. ∙

research

∙ 11/23/2020

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization

In this work, we examine the security of InstaHide, a scheme recently pr...

Sitan Chen, et al. ∙

research

∙ 11/04/2020

Algorithms and Hardness for Linear Algebra on Geometric Graphs

For a function 𝖪 : ℝ^d×ℝ^d→ℝ_≥ 0, and a set P = { x_1, …, x_n}⊂ℝ^d of n ...

Josh Alman, et al. ∙

research

∙ 10/22/2020

MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery

To address the issue that deep neural networks (DNNs) are vulnerable to ...

Xiaoxiao Li, et al. ∙

research

∙ 10/12/2020

TextHide: Tackling Data Privacy in Language Understanding Tasks

An unsolved challenge in distributed or federated learning is to effecti...

Yangsibo Huang, et al. ∙

research

∙ 10/06/2020

InstaHide: Instance-hiding Schemes for Private Distributed Learning

How can multiple distributed entities collaboratively train a shared dee...

Yangsibo Huang, et al. ∙

research

∙ 09/21/2020

A Faster Interior Point Method for Semidefinite Programming

Semidefinite programs (SDPs) are a fundamental class of optimization pro...

Haotian Jiang, et al. ∙

research

∙ 09/21/2020

Generalized Leverage Score Sampling for Neural Networks

Leverage score sampling is a powerful technique that originates from the...

Jason D. Lee, et al. ∙

research

∙ 09/15/2020

An improved quantum-inspired algorithm for linear regression

We give a classical algorithm for linear regression analogous to the qua...

András Gilyén, et al. ∙

research

∙ 09/13/2020

Breaking the n-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching

Given a weighted bipartite graph with n vertices and m edges, the 𝑚𝑎𝑥𝑖𝑚𝑢...

S. Cliff Liu, et al. ∙

research

∙ 09/03/2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...

Jan van den Brand, et al. ∙

research

∙ 08/21/2020

Hyperbolic Polynomials I : Concentration and Discrepancy

Chernoff bound is a fundamental tool in theoretical computer science. It...

Zhao Song, et al. ∙

research

∙ 06/20/2020

Training (Overparametrized) Neural Networks in Near-Linear Time

The slow convergence rate and pathological curvature issues of first-ord...

Jan van den Brand, et al. ∙

research

∙ 06/10/2020

When is Particle Filtering Efficient for POMDP Sequential Planning?

Particle filtering is a popular method for inferring latent states in st...

Simon S. Du, et al. ∙

research

∙ 05/13/2020

A robust multi-dimensional sparse Fourier transform in the continuous setting

Sparse Fourier transform (Sparse FT) is the problem of learning an unkno...

Yaonan Jin, et al. ∙

research

∙ 04/16/2020

Average Case Column Subset Selection for Entrywise ℓ_1-Norm Loss

We study the column subset selection problem with respect to the entrywi...

Zhao Song, et al. ∙

research

∙ 04/16/2020

Faster Dynamic Matrix Inverse for Faster LPs

Motivated by recent Linear Programming solvers, we design dynamic data s...

Shunhua Jiang, et al. ∙

research

∙ 04/08/2020

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

Given a separation oracle for a convex set K ⊂R^n that is contained in a...

Haotian Jiang, et al. ∙

research

∙ 03/04/2020

Privacy-preserving Learning via Deep Net Pruning

This paper attempts to answer the question whether neural network prunin...

Yangsibo Huang, et al. ∙

research

∙ 02/23/2020

Sketching Transformed Matrices with Applications to Natural Language Processing

Suppose we are given a large matrix A=(a_i,j) that cannot be stored in m...

Yingyu Liang, et al. ∙

research

∙ 02/20/2020

Meta-learning for mixed linear regression

In modern supervised learning, there are a large number of tasks, but ma...

Weihao Kong, et al. ∙

research

∙ 02/16/2020

Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality

Adversarial training is a popular method to give neural nets robustness ...

Yi Zhang, et al. ∙

research

∙ 02/06/2020

Solving Tall Dense Linear Programs in Nearly Linear Time

In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...

Jan van den Brand, et al. ∙

research

∙ 12/16/2019

Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

We consider the problem of learning a mixture of linear regressions (MLR...

Sitan Chen, et al. ∙

research

∙ 12/03/2019

WaveFlow: A Compact Flow-based Model for Raw Audio

In this work, we present WaveFlow, a small-footprint generative flow for...

Wei Ping, et al. ∙

research

∙ 10/04/2019

Efficient Symmetric Norm Regression via Linear Sketching

We provide efficient algorithms for overconstrained linear regression pr...

Zhao Song, et al. ∙

Zhao Song

Featured Co-authors