Distributed Sketching Methods for Privacy Preserving Regression
arXiv:2002.06538
Abstract
In this work, we study distributed sketching methods for large scale regression problems. We leverage multiple randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches. We consider random matrices including Gaussian, randomized Hadamard, uniform sampling and leverage score sampling in the distributed setting. Moreover, we propose a hybrid approach combining sampling and fast random projections for better computational efficiency. We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
References in corpus (7)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- EMNIST: an extension of MNIST to handwritten letters
- Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
- Occupy the Cloud: Distributed Computing for the 99%
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression
- Faster Least Squares Optimization
Cited by in corpus (3)
- Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
- Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
- Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality