Differentially Private Random Block Coordinate Descent
This work addresses privacy concerns in machine learning optimization for sensitive data, representing an incremental improvement over existing differentially private coordinate descent methods.
The paper tackles the problem of data privacy in coordinate descent methods by proposing a differentially private random block coordinate descent algorithm that selects multiple coordinates with varying probabilities using sketch matrices. The result is an algorithm that generalizes existing private methods while preserving utility guarantees and achieving better utility through importance sampling, leading to improved convergence rates.
Coordinate Descent (CD) methods have gained significant attention in machine learning due to their effectiveness in solving high-dimensional problems and their ability to decompose complex optimization tasks. However, classical CD methods were neither designed nor analyzed with data privacy in mind, a critical concern when handling sensitive information. This has led to the development of differentially private CD methods, such as DP-CD (Differentially Private Coordinate Descent) proposed by Mangold et al. (ICML 2022), yet a disparity remains between non-private CD and DP-CD methods. In our work, we propose a differentially private random block coordinate descent method that selects multiple coordinates with varying probabilities in each iteration using sketch matrices. Our algorithm generalizes both DP-CD and the classical DP-SGD (Differentially Private Stochastic Gradient Descent), while preserving the same utility guarantees. Furthermore, we demonstrate that better utility can be achieved through importance sampling, as our method takes advantage of the heterogeneity in coordinate-wise smoothness constants, leading to improved convergence rates.