Distributed Sketching Methods for Privacy Preserving Regression

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.

• Publication year

  2020

• Venue

  arXiv.org

• Publication date

  2020-02-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2002.06538
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Faster Least Squares Optimization

  2019cited by this paper
• Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise

  2018cited by this paper
• EMNIST: an extension of MNIST to handwritten letters

  2017influential reference
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging

  2017cited by this paper
• Occupy the cloud: distributed computing for the 99%

  2017cited by this paper
• Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression

  2015cited by this paper
• Iterative Hessian Sketch: Fast and Accurate Solution Approximation for Constrained Least-Squares

  2014cited by this paper
• Randomized sketches of convex programs with sharp guarantees

  2014cited by this paper
• Differentially Private Distributed Optimization

  2014influential reference
• Sketching as a Tool for Numerical Linear Algebra

  2014cited by this paper
• OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

  2012cited by this paper
• The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

  2012cited by this paper
• Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

  2011cited by this paper
• Compressed and Privacy-Sensitive Sparse Regression

  2009cited by this paper
• Faster least squares approximation

  2007cited by this paper
• Compressed Regression

  2007cited by this paper
• Our Data, Ourselves: Privacy Via Distributed Noise Generation

  2006cited by this paper
• All Invariant Moments of the Wishart Distribution

  2004cited by this paper
• Parallel and distributed computation

  1989cited by this paper
• Stat260/cs294: Randomized Algorithms for Matrices and Data

  year unknowncited by this paper

• The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning

  2023cites this paper
• Privacy-Utility Tradeoff of OLS with Random Projections

  2023cites this paper
• Manufacturing Data Privacy Protection System for Secure Predictive Maintenance

  2022cites this paper
• Orthonormal Sketches for Secure Coded Regression

  2022cites this paper
• Personalized Federated Learning towards Communication Efficiency, Robustness and Fairness

  2022cites this paper
• Dynamic Network-Assisted D2D-Aided Coded Distributed Learning

  2021cites this paper
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality

  2021cites this paper
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

  2020cites this paper
• Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds

  2020cites this paper
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization

  2020cites this paper
• Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares Using Random Projections

  2020cites this paper