
-
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...
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 ℓ_1-Regression 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: Instance-hiding 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 quantum-inspired algorithm for linear regression
We give a classical algorithm for linear regression analogous to the qua...
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 𝑚𝑎𝑥𝑖𝑚𝑢...
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...
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 Near-Linear Time
The slow convergence rate and pathological curvature issues of first-ord...
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 multi-dimensional 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 ℓ_1-Norm 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, Convex-Concave Games and its Applications
Given a separation oracle for a convex set K ⊂R^n that is contained in a...
read it
-
Privacy-preserving 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
-
Meta-learning for mixed linear regression
In modern supervised learning, there are a large number of tasks, but ma...
read it
-
Over-parameterized 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 Flow-based Model for Raw Audio
In this work, we present WaveFlow, a small-footprint 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) Sample-Optimal 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 Over-parametrization via Matrix Chernoff Bound
We improve the over-parametrization size over two beautiful results [Li ...
read it
-
Parallel Neural Text-to-Speech
In this work, we propose a non-autoregressive 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 Model-free Reinforcement Learning in Metric Spaces
Model-free Reinforcement Learning (RL) algorithms such as Q-learning [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 Blind-Spot Attack
The adversarial training procedure proposed by Madry et al. (2018) is on...
read it
-
Towards a Theoretical Understanding of Hashing-Based Neural Nets
Parameter reduction has been an important topic in deep learning due to ...
read it
-
Algorithmic Theory of ODEs and Sampling from Well-conditioned 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 Over-Parameterization
Deep neural networks (DNNs) have demonstrated dominating performance in ...
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...
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 One-layer Neural Networks
The goal of a recommendation system is to predict the interest of a user...
read it