b'Zhao Song'

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...
02/22/2021 ∙ by Lijie Chen, et al. ∙ 0 ∙ share

read it
Symmetric Boolean Factor Analysis with Applications to InstaHide

In this work we examine the security of InstaHide, a recently proposed s...
02/02/2021 ∙ by Sitan Chen, et al. ∙ 0 ∙ share

read it
Solving Tall Dense SDPs in the Current Matrix Multiplication Time

This paper introduces a new interior point method algorithm that solves ...
01/20/2021 ∙ by Baihe Huang, et al. ∙ 0 ∙ share

read it
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...
01/14/2021 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
InstaHide's Sample Complexity When Mixing Two Private Images

Inspired by InstaHide challenge [Huang, Song, Li and Arora'20], [Chen, S...
11/24/2020 ∙ by Baihe Huang, et al. ∙ 0 ∙ share

read it
On InstaHide, Phase Retrieval, and Sparse Matrix Factorization

In this work, we examine the security of InstaHide, a scheme recently pr...
11/23/2020 ∙ by Sitan Chen, et al. ∙ 0 ∙ share

read it
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 ...
11/04/2020 ∙ by Josh Alman, et al. ∙ 0 ∙ share

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

To address the issue that deep neural networks (DNNs) are vulnerable to ...
10/22/2020 ∙ by Xiaoxiao Li, et al. ∙ 4 ∙ share

read it
TextHide: Tackling Data Privacy in Language Understanding Tasks

An unsolved challenge in distributed or federated learning is to effecti...
10/12/2020 ∙ by Yangsibo Huang, et al. ∙ 7 ∙ share

read it
InstaHide: Instance-hiding Schemes for Private Distributed Learning

How can multiple distributed entities collaboratively train a shared dee...
10/06/2020 ∙ by Yangsibo Huang, et al. ∙ 5 ∙ share

read it
A Faster Interior Point Method for Semidefinite Programming

Semidefinite programs (SDPs) are a fundamental class of optimization pro...
09/21/2020 ∙ by Haotian Jiang, et al. ∙ 0 ∙ share

read it
Generalized Leverage Score Sampling for Neural Networks

Leverage score sampling is a powerful technique that originates from the...
09/21/2020 ∙ by Jason D. Lee, et al. ∙ 0 ∙ share

read it
An improved quantum-inspired algorithm for linear regression

We give a classical algorithm for linear regression analogous to the qua...
09/15/2020 ∙ by András Gilyén, et al. ∙ 0 ∙ share

read it
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 𝑚𝑎𝑥𝑖𝑚𝑢...
09/13/2020 ∙ by S. Cliff Liu, et al. ∙ 0 ∙ share

read it
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...
09/03/2020 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
Hyperbolic Polynomials I : Concentration and Discrepancy

Chernoff bound is a fundamental tool in theoretical computer science. It...
08/21/2020 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
Training (Overparametrized) Neural Networks in Near-Linear Time

The slow convergence rate and pathological curvature issues of first-ord...
06/20/2020 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
When is Particle Filtering Efficient for POMDP Sequential Planning?

Particle filtering is a popular method for inferring latent states in st...
06/10/2020 ∙ by Simon S. Du, et al. ∙ 1 ∙ share

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

Sparse Fourier transform (Sparse FT) is the problem of learning an unkno...
05/13/2020 ∙ by Yaonan Jin, et al. ∙ 0 ∙ share

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

We study the column subset selection problem with respect to the entrywi...
04/16/2020 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
Faster Dynamic Matrix Inverse for Faster LPs

Motivated by recent Linear Programming solvers, we design dynamic data s...
04/16/2020 ∙ by Shunhua Jiang, et al. ∙ 0 ∙ share

read it
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...
04/08/2020 ∙ by Haotian Jiang, et al. ∙ 0 ∙ share

read it
Privacy-preserving Learning via Deep Net Pruning

This paper attempts to answer the question whether neural network prunin...
03/04/2020 ∙ by Yangsibo Huang, et al. ∙ 18 ∙ share

read it
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...
02/23/2020 ∙ by Yingyu Liang, et al. ∙ 0 ∙ share

read it
Meta-learning for mixed linear regression

In modern supervised learning, there are a large number of tasks, but ma...
02/20/2020 ∙ by Weihao Kong, et al. ∙ 6 ∙ share

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

Adversarial training is a popular method to give neural nets robustness ...
02/16/2020 ∙ by Yi Zhang, et al. ∙ 11 ∙ share

read it
Solving Tall Dense Linear Programs in Nearly Linear Time

In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...
02/06/2020 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

We consider the problem of learning a mixture of linear regressions (MLR...
12/16/2019 ∙ by Sitan Chen, et al. ∙ 0 ∙ share

read it
WaveFlow: A Compact Flow-based Model for Raw Audio

In this work, we present WaveFlow, a small-footprint generative flow for...
12/03/2019 ∙ by Wei Ping, et al. ∙ 0 ∙ share

read it
Efficient Symmetric Norm Regression via Linear Sketching

We provide efficient algorithms for overconstrained linear regression pr...
10/04/2019 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

We study the Kronecker product regression problem, in which the design m...
09/29/2019 ∙ by Huaian Diao, et al. ∙ 8 ∙ share

read it
Total Least Squares Regression in Input Sparsity Time

In the total least squares problem, one is given an m × n matrix A, and ...
09/27/2019 ∙ by Huaian Diao, et al. ∙ 0 ∙ share

read it
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless

In this paper, we consider the extensively studied problem of computing ...
09/24/2019 ∙ by Vasileios Nakos, et al. ∙ 0 ∙ share

read it
Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound

We improve the over-parametrization size over two beautiful results [Li ...
06/09/2019 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
Parallel Neural Text-to-Speech

In this work, we propose a non-autoregressive seq2seq model that convert...
05/21/2019 ∙ by Kainan Peng, et al. ∙ 0 ∙ share

read it
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Many convex problems in machine learning and computer science share the ...
05/11/2019 ∙ by Yin Tat Lee, et al. ∙ 0 ∙ share

read it
Efficient Model-free Reinforcement Learning in Metric Spaces

Model-free Reinforcement Learning (RL) algorithms such as Q-learning [Wa...
05/01/2019 ∙ by Zhao Song, et al. ∙ 8 ∙ share

read it
Reducing approximate Longest Common Subsequence to approximate Edit Distance

Given a pair of strings, the problems of computing their Longest Common ...
04/10/2019 ∙ by Aviad Rubinstein, et al. ∙ 0 ∙ share

read it
Stronger L2/L2 Compressed Sensing; Without Iterating

We consider the extensively studied problem of ℓ_2/ℓ_2 compressed sensin...
03/07/2019 ∙ by Vasileios Nakos, et al. ∙ 0 ∙ share

read it
Four Deviations Suffice for Rank 1 Matrices

We prove a matrix discrepancy bound that strengthens the famous Kadison-...
01/20/2019 ∙ by Rasmus Kyng, et al. ∙ 0 ∙ share

read it
The Limitations of Adversarial Training and the Blind-Spot Attack

The adversarial training procedure proposed by Madry et al. (2018) is on...
01/15/2019 ∙ by Huan Zhang, et al. ∙ 22 ∙ share

read it
Towards a Theoretical Understanding of Hashing-Based Neural Nets

Parameter reduction has been an important topic in deep learning due to ...
12/26/2018 ∙ by Yibo Lin, et al. ∙ 0 ∙ share

read it
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Sampling logconcave functions arising in statistics and machine learning...
12/15/2018 ∙ by Yin Tat Lee, et al. ∙ 0 ∙ share

read it
Revisiting the Softmax Bellman Operator: Theoretical Properties and Practical Benefits

The softmax function has been primarily employed in reinforcement learni...
12/02/2018 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
A Convergence Theory for Deep Learning via Over-Parameterization

Deep neural networks (DNNs) have demonstrated dominating performance in ...
11/09/2018 ∙ by Zeyuan Allen-Zhu, et al. ∙ 0 ∙ share

read it
Towards a Zero-One Law for Entrywise Low Rank Approximation

There are a number of approximation algorithms for NP-hard versions of l...
11/04/2018 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
On the Convergence Rate of Training Recurrent Neural Networks

Despite the huge success of deep learning, our understanding to how the ...
10/29/2018 ∙ by Zeyuan Allen-Zhu, et al. ∙ 0 ∙ share

read it
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees

Strongly Rayleigh distributions are a class of negatively dependent dist...
10/19/2018 ∙ by Rasmus Kyng, et al. ∙ 0 ∙ share

read it
Solving Linear Programs in the Current Matrix Multiplication Time

This paper shows how to solve linear programs of the form _Ax=b,x≥0 c^ x...
10/18/2018 ∙ by Michael B. Cohen, et al. ∙ 0 ∙ share

read it
Nonlinear Inductive Matrix Completion based on One-layer Neural Networks

The goal of a recommendation system is to predict the interest of a user...
05/26/2018 ∙ by Kai Zhong, et al. ∙ 0 ∙ share

read it

Zhao Song

Featured Co-authors