Iterative Sketching for Secure Coded Regression
- 4 April 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 148-161
Abstract
Linear regression is a fundamental and primitive problem in supervised machine learning, with applications ranging from epidemiology to finance. In this work, we propose methods for speeding up distributed linear regression. We do so by leveraging randomized techniques, while also ensuring security and straggler resiliency in asynchronous distributed computing systems. Specifically, we randomly rotate the basis of the system of equations and then subsample blocks, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the basis rotation corresponds to an encoded encryption in an approximate gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling servers in the centralized coded computing framework. This results in a distributive iterative stochastic approach for matrix compression and steepest descent.Keywords
All Related Versions
Funding Information
- Semiconductor Research Corporation (SRC), National Science Foundation (NSF-2246157, ECCS-2037304, DMS-2134248)
- SF CAREER Award (CCF-2236829)
- U.S. Army Research Office (W911NF-23-1-0343)
- U.S. ARO Early Career Award (W911NF-21-1-0242)
- Department of Energy (DE-NA0003921)
- Office of Naval Research (N00014-24-1-2164)
This publication has 69 references indexed in Scilit:
- Monte Carlo Simulation on the Stiefel Manifold via Polar ExpansionJournal of Computational and Graphical Statistics, 2021
- On block Gaussian sketching for the Kaczmarz methodNumerical Algorithms, 2020
- Block CUR: Decomposing Matrices Using Groups of Columns2019
- A novel image encryption scheme based on orthogonal matrix, skew tent map, and XOR operationNeural Computing and Applications, 2017
- A compression sensing and noise-tolerant image encryption scheme based on chaotic maps and orthogonal matricesNeural Computing and Applications, 2016
- Paved with good intentions: Analysis of a randomized block Kaczmarz methodLinear Algebra and its Applications, 2014
- Faster least squares approximationNumerische Mathematik, 2010
- The Fourier transform and its applications1995
- Block-iterative methods for consistent and inconsistent linear equationsNumerische Mathematik, 1980
- Gaussian elimination is not optimalNumerische Mathematik, 1969