124 citations · 276 across the 23 of their papers we have counts for
24 papers
Adore: Differentially Oblivious Relational Database Operators
Lianke Qin, Rajesh Jayaram, Elaine Shi +3
There has been a recent effort in applying differential privacy on memory access patterns to enhance data privacy. This is called differential obliviousness. Differential oblivious…
Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning
Mayee F. Chen, Daniel Y. Fu, Avanika Narayan +4
An ideal learned representation should display transferability and robustness. Supervised contrastive learning (SupCon) is a promising method for training accurate models, but prod…
On Convergence of Federated Averaging Langevin Dynamics
Wei Deng, Qian Zhang, Yi-An Ma +2
We propose a federated averaging Langevin algorithm (FA-LD) for uncertainty quantification and mean predictions with distributed clients. In particular, we generalize beyond normal…
Evaluating Gradient Inversion Attacks and Defenses in Federated Learning
Yangsibo Huang, Samyak Gupta, Zhao Song +2
Gradient inversion attack (or input recovery from gradient) is an emerging threat to the security and privacy preservation of Federated learning, whereby malicious eavesdroppers or…
Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We formulate the value function estim…
FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
Baihe Huang, Xiaoxiao Li, Zhao Song +1
Federated Learning (FL) is an emerging learning scheme that allows different distributed clients to train deep neural networks together without data sharing. Neural networks have b…
Symmetric Sparse Boolean Matrix Factorization and Applications
Sitan Chen, Zhao Song, Runzhou Tao +1
In this work, we study a variant of nonnegative matrix factorization where we wish to find a symmetric factorization of a given input matrix into a sparse, Boolean matrix. Formally…
InstaHide's Sample Complexity When Mixing Two Private Images
Baihe Huang, Zhao Song, Runzhou Tao +3
Training neural networks usually require large numbers of sensitive training data, and how to protect the privacy of training data has thus become a critical topic in deep learning…
On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
Sitan Chen, Xiaoxiao Li, Zhao Song +1
In this work, we examine the security of InstaHide, a scheme recently proposed by [Huang, Song, Li and Arora, ICML'20] for preserving the security of private datasets in the contex…
MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
Xiaoxiao Li, Yangsibo Huang, Binghui Peng +2
To address the issue that deep neural networks (DNNs) are vulnerable to model inversion attacks, we design an objective function, which adjusts the separability of the hidden data…
TextHide: Tackling Data Privacy in Language Understanding Tasks
Yangsibo Huang, Zhao Song, Danqi Chen +2
An unsolved challenge in distributed or federated learning is to effectively mitigate privacy risks without slowing down training or reducing accuracy. In this paper, we propose Te…
InstaHide: Instance-hiding Schemes for Private Distributed Learning
Yangsibo Huang, Zhao Song, Kai Li +1
How can multiple distributed entities collaboratively train a shared deep net on their private data while preserving privacy? This paper introduces InstaHide, a simple encryption o…
Generalized Leverage Score Sampling for Neural Networks
Jason D. Lee, Ruoqi Shen, Zhao Song +2
Leverage score sampling is a powerful technique that originates from theoretical computer science, which can be used to speed up a large number of fundamental questions, e.g. linea…
Privacy-preserving Learning via Deep Net Pruning
Yangsibo Huang, Yushan Su, Sachin Ravi +3
This paper attempts to answer the question whether neural network pruning can be used as a tool to achieve differential privacy without losing much data utility. As a first step to…
Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
Yi Zhang, Orestis Plevrakis, Simon S. Du +3
Adversarial training is a popular method to give neural nets robustness against adversarial perturbations. In practice adversarial training leads to low robust training loss. Howev…
Sketching Transformed Matrices with Applications to Natural Language Processing
Yingyu Liang, Zhao Song, Mengdi Wang +2
Suppose we are given a large matrix that cannot be stored in memory but is in a disk or is presented in a data stream. However, we need to compute a matrix decomposit…
Meta-learning for mixed linear regression
Weihao Kong, Raghav Somani, Zhao Song +2
In modern supervised learning, there are a large number of tasks, but many of them are associated with only a small amount of labeled data. These include data from medical image pr…
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, Zhao Song
We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by nonnegative mixing weights summing to , and unknown…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
Zhao Song, Xin Yang
We improve the over-parametrization size over two beautiful results [Li and Liang' 2018] and [Du, Zhai, Poczos and Singh' 2019] in deep learning theory.
Four Deviations Suffice for Rank 1 Matrices
Rasmus Kyng, Kyle Luh, Zhao Song
We prove a matrix discrepancy bound that strengthens the famous Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any independent scalar random variables $ξ_1, \l…
Towards a Theoretical Understanding of Hashing-Based Neural Nets
Yibo Lin, Zhao Song, Lin F. Yang
Parameter reduction has been an important topic in deep learning due to the ever-increasing size of deep neural network models and the need to train and run them on resource limite…
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
Rasmus Kyng, Zhao Song
Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables [Borcea, Branden, Liggett JAMS 09]. Recently, these distribution…
Nearly Optimal Dynamic -Means Clustering for High-Dimensional Data
Wei Hu, Zhao Song, Lin F. Yang +1
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to o…