2024/11/04 by César Sabater, Nicolas, Julien, Mohamed Maouche +6 · 2 citations
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Privacy-Preserving Technologies in Data #Random Matrices and Applications #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2411.01931
openalex publication_date 2024/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The randomized power method has gained significant interest due to its simplicity and efficient handling of large-scale spectral analysis and recommendation tasks. However, its application to large datasets containing personal information (e.g., web interactions, search history, personal tastes) raises critical privacy problems. This paper addresses these issues by proposing enhanced privacy-preserving variants of the method. First, we propose a variant that reduces the amount of the noise required in current techniques to achieve Differential Privacy (DP). More precisely, we refine the privacy analysis so that the Gaussian noise variance no longer grows linearly with the target rank, achieving the same DP guarantees with strictly less noise. Second, we adapt our method to a decentralized framework in which data is distributed among multiple users. The decentralized protocol strengthens privacy guarantees with no accuracy penalty and a low computational and communication overhead. Our results include the provision of tighter convergence bounds for both the centralized and decentralized versions, and an empirical comparison with previous work using real recommendation datasets.