
NearOptimal TwoPass 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...
read it

Symmetric Boolean Factor Analysis with Applications to InstaHide
In this work we examine the security of InstaHide, a recently proposed s...
read it

Solving Tall Dense SDPs in the Current Matrix Multiplication Time
This paper introduces a new interior point method algorithm that solves ...
read it

Minimum Cost Flows, MDPs, and ℓ_1Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
read it

InstaHide's Sample Complexity When Mixing Two Private Images
Inspired by InstaHide challenge [Huang, Song, Li and Arora'20], [Chen, S...
read it

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
In this work, we examine the security of InstaHide, a scheme recently pr...
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 ...
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 ...
read it

TextHide: Tackling Data Privacy in Language Understanding Tasks
An unsolved challenge in distributed or federated learning is to effecti...
read it

InstaHide: Instancehiding Schemes for Private Distributed Learning
How can multiple distributed entities collaboratively train a shared dee...
read it

A Faster Interior Point Method for Semidefinite Programming
Semidefinite programs (SDPs) are a fundamental class of optimization pro...
read it

Generalized Leverage Score Sampling for Neural Networks
Leverage score sampling is a powerful technique that originates from the...
read it

An improved quantuminspired algorithm for linear regression
We give a classical algorithm for linear regression analogous to the qua...
read it

Breaking the nPass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching
Given a weighted bipartite graph with n vertices and m edges, the 𝑚𝑎𝑥𝑖𝑚𝑢...
read it

Bipartite Matching in Nearlylinear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)time randomized algorithm for maximum cardinali...
read it

Hyperbolic Polynomials I : Concentration and Discrepancy
Chernoff bound is a fundamental tool in theoretical computer science. It...
read it

Training (Overparametrized) Neural Networks in NearLinear Time
The slow convergence rate and pathological curvature issues of firstord...
read it

When is Particle Filtering Efficient for POMDP Sequential Planning?
Particle filtering is a popular method for inferring latent states in st...
read it

A robust multidimensional sparse Fourier transform in the continuous setting
Sparse Fourier transform (Sparse FT) is the problem of learning an unkno...
read it

Average Case Column Subset Selection for Entrywise ℓ_1Norm Loss
We study the column subset selection problem with respect to the entrywi...
read it

Faster Dynamic Matrix Inverse for Faster LPs
Motivated by recent Linear Programming solvers, we design dynamic data s...
read it

An Improved Cutting Plane Method for Convex Optimization, ConvexConcave Games and its Applications
Given a separation oracle for a convex set K ⊂R^n that is contained in a...
read it

Privacypreserving Learning via Deep Net Pruning
This paper attempts to answer the question whether neural network prunin...
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...
read it

Metalearning for mixed linear regression
In modern supervised learning, there are a large number of tasks, but ma...
read it

Overparameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
Adversarial training is a popular method to give neural nets robustness ...
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...
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...
read it

WaveFlow: A Compact Flowbased Model for Raw Audio
In this work, we present WaveFlow, a smallfootprint generative flow for...
read it

Efficient Symmetric Norm Regression via Linear Sketching
We provide efficient algorithms for overconstrained linear regression pr...
read it

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
We study the Kronecker product regression problem, in which the design m...
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 ...
read it

(Nearly) SampleOptimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
In this paper, we consider the extensively studied problem of computing ...
read it

Quadratic Suffices for Overparametrization via Matrix Chernoff Bound
We improve the overparametrization size over two beautiful results [Li ...
read it

Parallel Neural TexttoSpeech
In this work, we propose a nonautoregressive seq2seq model that convert...
read it

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Many convex problems in machine learning and computer science share the ...
read it

Efficient Modelfree Reinforcement Learning in Metric Spaces
Modelfree Reinforcement Learning (RL) algorithms such as Qlearning [Wa...
read it

Reducing approximate Longest Common Subsequence to approximate Edit Distance
Given a pair of strings, the problems of computing their Longest Common ...
read it

Stronger L2/L2 Compressed Sensing; Without Iterating
We consider the extensively studied problem of ℓ_2/ℓ_2 compressed sensin...
read it

Four Deviations Suffice for Rank 1 Matrices
We prove a matrix discrepancy bound that strengthens the famous Kadison...
read it

The Limitations of Adversarial Training and the BlindSpot Attack
The adversarial training procedure proposed by Madry et al. (2018) is on...
read it

Towards a Theoretical Understanding of HashingBased Neural Nets
Parameter reduction has been an important topic in deep learning due to ...
read it

Algorithmic Theory of ODEs and Sampling from Wellconditioned Logconcave Densities
Sampling logconcave functions arising in statistics and machine learning...
read it

Revisiting the Softmax Bellman Operator: Theoretical Properties and Practical Benefits
The softmax function has been primarily employed in reinforcement learni...
read it

A Convergence Theory for Deep Learning via OverParameterization
Deep neural networks (DNNs) have demonstrated dominating performance in ...
read it

Towards a ZeroOne Law for Entrywise Low Rank Approximation
There are a number of approximation algorithms for NPhard versions of l...
read it

On the Convergence Rate of Training Recurrent Neural Networks
Despite the huge success of deep learning, our understanding to how the ...
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...
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...
read it

Nonlinear Inductive Matrix Completion based on Onelayer Neural Networks
The goal of a recommendation system is to predict the interest of a user...
read it
Zhao Song
is this you? claim profile