Tomoya Murata
Research Subjects
Tomoya Murata has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Taiji Suzuki
The University of Tokyo
8 shared publications - Iifan Tyou
Social Informatics Laboratories, NTT, Inc., Tokyo, Japan
2 shared publications - Kenta Niwa
NTT, Communication Science Laboratories, NTT Corporation, Tokyo, Japan
2 shared publications - Takumi Fukami
NTT Social Information Laboratories, NTT Corporation, Yokosuka, Japan
2 shared publications - Atsushi Nitanda
RIKEN Center for Advanced Intelligence Project Kyushu Institute of Technology
1 shared publication - Hiroshi Abe
Laboratory for Molecular Analysis of Higher Brain Function, RIKEN Center for Brain Science, Wako, Saitama, Japan
1 shared publication
Latest Publications
- Open Access
- 18 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 19 (15566013) , 5783-5797
DP-Norm: Differential Privacy Primal-Dual Algorithm for Decentralized Federated Learning
A novel algorithm is proposed for highly privacy-preserving decentralized federated learning (FL). Several studies have reported security risks in decentralized FL by reconstructing data even from model update differences. A common approach to overcome this issue is to use the diffusion process following differential privacy (DP), i.e., message passing between nodes is hidden by noise. However, this often makes the learning process unstable, leading to degraded results compared to without using DP diffusion process. In this paper, we propose a primal-dual DP algorithm with denoising normalization (DP-Norm) for less sensitivity to noise/interference, such as DP diffusion and heterogeneous data allocation. For DP-Norm, privacy analysis to determine minimal noise level and convergence analysis are conducted. Through image classification benchmark tests, we confirmed that DP-Norm performed close to the single-node reference score, even when statistically heterogeneous data was allocated on six nodes.
- 18 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 19 (15566013) , 5783-5797
Open AccessDP-Norm: Differential Privacy Primal-Dual Algorithm for Decentralized Federated Learning
A novel algorithm is proposed for highly privacy-preserving decentralized federated learning (FL). Several studies have reported security risks in decentralized FL by reconstructing data even from model update differences. A common approach to overcome this issue is to use the diffusion process following differential privacy (DP), i.e., message passing between nodes is hidden by noise. However, this often makes the learning process unstable, leading to degraded results compared to without using DP diffusion process. In this paper, we propose a primal-dual DP algorithm with denoising normalization (DP-Norm) for less sensitivity to noise/interference, such as DP diffusion and heterogeneous data allocation. For DP-Norm, privacy analysis to determine minimal noise level and convergence analysis are conducted. Through image classification benchmark tests, we confirmed that DP-Norm performed close to the single-node reference score, even when statistically heterogeneous data was allocated on six nodes.
- Open Access
- 25 December 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal and Information Processing over Networks
- Vol. 10, 94-107
A Localized Primal-Dual Method for Centralized/Decentralized Federated Learning Robust to Data Heterogeneity
Generalized Edge-Consensus Learning (G-ECL) is a primal-dual method to solve loss-sum minimization problems. We propose Local Generalized Edge-Consensus Learning (Local G-ECL) as an extension of previous G-ECL, aiming to be a decentralized/centralized FL algorithm robust to heterogeneous data sets with a large number of local updates. Our contributions are as follows: (C1) success in theoretical gradient norm convergence analysis nearly independently of data heterogeneity, and (C2) equivalency proof between our primal-dual Local G-ECL and a pure primal Stochastic Controlled Averaging (SCAFFOLD) algorithm in centralized settings, where the difference in the initial local model for each round is ignored. Numerical experiments using image classification tests validated that Local G-ECL is robust to heterogeneous data with a large number of local updates.
- 25 December 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal and Information Processing over Networks
- Vol. 10, 94-107
Open AccessA Localized Primal-Dual Method for Centralized/Decentralized Federated Learning Robust to Data Heterogeneity
Generalized Edge-Consensus Learning (G-ECL) is a primal-dual method to solve loss-sum minimization problems. We propose Local Generalized Edge-Consensus Learning (Local G-ECL) as an extension of previous G-ECL, aiming to be a decentralized/centralized FL algorithm robust to heterogeneous data sets with a large number of local updates. Our contributions are as follows: (C1) success in theoretical gradient norm convergence analysis nearly independently of data heterogeneity, and (C2) equivalency proof between our primal-dual Local G-ECL and a pure primal Stochastic Controlled Averaging (SCAFFOLD) algorithm in centralized settings, where the difference in the initial local model for each round is ignored. Numerical experiments using image classification tests validated that Local G-ECL is robust to heterogeneous data with a large number of local updates.
- Open Access
DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning
Differential private optimization for nonconvex smooth objective is considered. In the previous work, the best known utility bound is $\widetilde O(\sqrt{d}/(n\varepsilon_\mathrm{DP}))$ in terms of the squared full gradient norm, which is achieved by Differential Private Gradient Descent (DP-GD) as an instance, where $n$ is the sample size, $d$ is the problem dimensionality and $\varepsilon_\mathrm{DP}$ is the differential privacy parameter. To improve the best known utility bound, we propose a new differential private optimization framework called \emph{DIFF2 (DIFFerential private optimization via gradient DIFFerences)} that constructs a differential private global gradient estimator with possibly quite small variance based on communicated \emph{gradient differences} rather than gradients themselves. It is shown that DIFF2 with a gradient descent subroutine achieves the utility of $\widetilde O(d^{2/3}/(n\varepsilon_\mathrm{DP})^{4/3})$, which can be significantly better than the previous one in terms of the dependence on the sample size $n$. To the best of our knowledge, this is the first fundamental result to improve the standard utility $\widetilde O(\sqrt{d}/(n\varepsilon_\mathrm{DP}))$ for nonconvex objectives. Additionally, a more computational and communication efficient subroutine is combined with DIFF2 and its theoretical analysis is also given. Numerical experiments are conducted to validate the superiority of DIFF2 framework.Open AccessDIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning
Differential private optimization for nonconvex smooth objective is considered. In the previous work, the best known utility bound is $\widetilde O(\sqrt{d}/(n\varepsilon_\mathrm{DP}))$ in terms of the squared full gradient norm, which is achieved by Differential Private Gradient Descent (DP-GD) as an instance, where $n$ is the sample size, $d$ is the problem dimensionality and $\varepsilon_\mathrm{DP}$ is the differential privacy parameter. To improve the best known utility bound, we propose a new differential private optimization framework called \emph{DIFF2 (DIFFerential private optimization via gradient DIFFerences)} that constructs a differential private global gradient estimator with possibly quite small variance based on communicated \emph{gradient differences} rather than gradients themselves. It is shown that DIFF2 with a gradient descent subroutine achieves the utility of $\widetilde O(d^{2/3}/(n\varepsilon_\mathrm{DP})^{4/3})$, which can be significantly better than the previous one in terms of the dependence on the sample size $n$. To the best of our knowledge, this is the first fundamental result to improve the standard utility $\widetilde O(\sqrt{d}/(n\varepsilon_\mathrm{DP}))$ for nonconvex objectives. Additionally, a more computational and communication efficient subroutine is combined with DIFF2 and its theoretical analysis is also given. Numerical experiments are conducted to validate the superiority of DIFF2 framework. - Open Access
Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning
In recent centralized nonconvex distributed learning and federated learning, local methods are one of the promising approaches to reduce communication time. However, existing work has mainly focused on studying first-order optimality guarantees. On the other side, second-order optimality guaranteed algorithms, i.e., algorithms escaping saddle points, have been extensively studied in the non-distributed optimization literature. In this paper, we study a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), that combines the existing bias-variance reduced gradient estimator with parameter perturbation to find second-order optimal points in centralized nonconvex distributed optimization. BVR-L-PSGD enjoys second-order optimality with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order optimality. Particularly, the communication complexity is better than non-local methods when the local datasets heterogeneity is smaller than the smoothness of the local loss. In an extreme case, the communication complexity approaches to $\widetilde \Theta(1)$ when the local datasets heterogeneity goes to zero. Numerical results validate our theoretical findings.Open AccessEscaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning
In recent centralized nonconvex distributed learning and federated learning, local methods are one of the promising approaches to reduce communication time. However, existing work has mainly focused on studying first-order optimality guarantees. On the other side, second-order optimality guaranteed algorithms, i.e., algorithms escaping saddle points, have been extensively studied in the non-distributed optimization literature. In this paper, we study a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), that combines the existing bias-variance reduced gradient estimator with parameter perturbation to find second-order optimal points in centralized nonconvex distributed optimization. BVR-L-PSGD enjoys second-order optimality with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order optimality. Particularly, the communication complexity is better than non-local methods when the local datasets heterogeneity is smaller than the smoothness of the local loss. In an extreme case, the communication complexity approaches to $\widetilde \Theta(1)$ when the local datasets heterogeneity goes to zero. Numerical results validate our theoretical findings. - Open Access
Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning
While variance reduction methods have shown great success in solving large scale optimization problems, many of them suffer from accumulated errors and, therefore, should periodically require the full gradient computation. In this paper, we present a single-loop algorithm named SLEDGE (Single-Loop mEthoD for Gradient Estimator) for finite-sum nonconvex optimization, which does not require periodic refresh of the gradient estimator but achieves nearly optimal gradient complexity. Unlike existing methods, SLEDGE has the advantage of versatility; (i) second-order optimality, (ii) exponential convergence in the PL region, and (iii) smaller complexity under less heterogeneity of data. We build an efficient federated learning algorithm by exploiting these favorable properties. We show the first and second-order optimality of the output and also provide analysis under PL conditions. When the local budget is sufficiently large and clients are less (Hessian-)~heterogeneous, the algorithm requires fewer communication rounds then existing methods such as FedAvg, SCAFFOLD, and Mime. The superiority of our method is verified in numerical experiments.
Open AccessVersatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning
While variance reduction methods have shown great success in solving large scale optimization problems, many of them suffer from accumulated errors and, therefore, should periodically require the full gradient computation. In this paper, we present a single-loop algorithm named SLEDGE (Single-Loop mEthoD for Gradient Estimator) for finite-sum nonconvex optimization, which does not require periodic refresh of the gradient estimator but achieves nearly optimal gradient complexity. Unlike existing methods, SLEDGE has the advantage of versatility; (i) second-order optimality, (ii) exponential convergence in the PL region, and (iii) smaller complexity under less heterogeneity of data. We build an efficient federated learning algorithm by exploiting these favorable properties. We show the first and second-order optimality of the output and also provide analysis under PL conditions. When the local budget is sufficiently large and clients are less (Hessian-)~heterogeneous, the algorithm requires fewer communication rounds then existing methods such as FedAvg, SCAFFOLD, and Mime. The superiority of our method is verified in numerical experiments.
- 12 July 2021
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 63 (9) , 2513-2539
Sharp characterization of optimal minibatch size for stochastic finite sum convex optimization
- 12 July 2021
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 63 (9) , 2513-2539
Sharp characterization of optimal minibatch size for stochastic finite sum convex optimization
- Open Access
Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
Recently, local SGD has got much attention and been extensively studied in the distributed learning community to overcome the communication bottleneck problem. However, the superiority of local SGD to minibatch SGD only holds in quite limited situations. In this paper, we study a new local algorithm called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex distributed optimization. Algorithmically, our proposed bias and variance reduced local gradient estimator fully utilizes small second-order heterogeneity of local objectives and suggests randomly picking up one of the local models instead of taking the average of them when workers are synchronized. Theoretically, under small heterogeneity of local objectives, we show that BVR-L-SGD achieves better communication complexity than both the previous non-local and local methods under mild conditions, and particularly BVR-L-SGD is the first method that breaks the barrier of communication complexity $\Theta(1/\varepsilon)$ for general nonconvex smooth objectives when the heterogeneity is small and the local computation budget is large. Numerical results are given to verify the theoretical findings and give empirical evidence of the superiority of our method.Open AccessBias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
Recently, local SGD has got much attention and been extensively studied in the distributed learning community to overcome the communication bottleneck problem. However, the superiority of local SGD to minibatch SGD only holds in quite limited situations. In this paper, we study a new local algorithm called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex distributed optimization. Algorithmically, our proposed bias and variance reduced local gradient estimator fully utilizes small second-order heterogeneity of local objectives and suggests randomly picking up one of the local models instead of taking the average of them when workers are synchronized. Theoretically, under small heterogeneity of local objectives, we show that BVR-L-SGD achieves better communication complexity than both the previous non-local and local methods under mild conditions, and particularly BVR-L-SGD is the first method that breaks the barrier of communication complexity $\Theta(1/\varepsilon)$ for general nonconvex smooth objectives when the heterogeneity is small and the local computation budget is large. Numerical results are given to verify the theoretical findings and give empirical evidence of the superiority of our method. - Open Access
Gradient Descent in RKHS with Importance Labeling
Labeling cost is often expensive and is a fundamental limitation of supervised learning. In this paper, we study importance labeling problem, in which we are given many unlabeled data and select a limited number of data to be labeled from the unlabeled data, and then a learning algorithm is executed on the selected one. We propose a new importance labeling scheme that can effectively select an informative subset of unlabeled data in least squares regression in Reproducing Kernel Hilbert Spaces (RKHS). We analyze the generalization error of gradient descent combined with our labeling scheme and show that the proposed algorithm achieves the optimal rate of convergence in much wider settings and especially gives much better generalization ability in a small label noise setting than the usual uniform sampling scheme. Numerical experiments verify our theoretical findings.
Open AccessGradient Descent in RKHS with Importance Labeling
Labeling cost is often expensive and is a fundamental limitation of supervised learning. In this paper, we study importance labeling problem, in which we are given many unlabeled data and select a limited number of data to be labeled from the unlabeled data, and then a learning algorithm is executed on the selected one. We propose a new importance labeling scheme that can effectively select an informative subset of unlabeled data in least squares regression in Reproducing Kernel Hilbert Spaces (RKHS). We analyze the generalization error of gradient descent combined with our labeling scheme and show that the proposed algorithm achieves the optimal rate of convergence in much wider settings and especially gives much better generalization ability in a small label noise setting than the usual uniform sampling scheme. Numerical experiments verify our theoretical findings.
- Open Access
- 1 July 2020
- Published by International Joint Conferences on Artificial Intelligence
- p. 2839-2846
Spectral Pruning: Compressing Deep Neural Networks via Spectral Analysis and its Generalization Error
Electronic proceedings of IJCAI 2020
- 1 July 2020
- Published by International Joint Conferences on Artificial Intelligence
- p. 2839-2846
Open AccessSpectral Pruning: Compressing Deep Neural Networks via Spectral Analysis and its Generalization Error
Electronic proceedings of IJCAI 2020
- Open Access
Accelerated Sparsified SGD with Error Feedback
A stochastic gradient method for synchronous distributed optimization is studied. For reducing communication cost, we particularly focus on utilization of compression of communicated gradients. Several work has shown that {\it{sparsified}} stochastic gradient descent method (SGD) with {\it{error feedback}} asymptotically achieves the same rate as (non-sparsified) parallel SGD. However, from a viewpoint of non-asymptotic behavior, the compression error may cause slower convergence than non-sparsified SGD in early iterations. This is problematic in practical situations since early stopping is often adopted to maximize the generalization ability of learned models. For improving the previous results, we propose and theoretically analyse a sparsified stochastic gradient method with error feedback scheme combined with {\it{Nesterov's acceleration}}. It is shown that the necessary per iteration communication cost for maintaining the same rate as vanilla SGD can be smaller than non-accelerated methods in convex and even in nonconvex optimization problems. This indicates that our proposed method makes a better use of compressed information than previous methods. Numerical experiments are provided and empirically validates our theoretical findings.
Open AccessAccelerated Sparsified SGD with Error Feedback
A stochastic gradient method for synchronous distributed optimization is studied. For reducing communication cost, we particularly focus on utilization of compression of communicated gradients. Several work has shown that {\it{sparsified}} stochastic gradient descent method (SGD) with {\it{error feedback}} asymptotically achieves the same rate as (non-sparsified) parallel SGD. However, from a viewpoint of non-asymptotic behavior, the compression error may cause slower convergence than non-sparsified SGD in early iterations. This is problematic in practical situations since early stopping is often adopted to maximize the generalization ability of learned models. For improving the previous results, we propose and theoretically analyse a sparsified stochastic gradient method with error feedback scheme combined with {\it{Nesterov's acceleration}}. It is shown that the necessary per iteration communication cost for maintaining the same rate as vanilla SGD can be smaller than non-accelerated methods in convex and even in nonconvex optimization problems. This indicates that our proposed method makes a better use of compressed information than previous methods. Numerical experiments are provided and empirically validates our theoretical findings.