Federated Sufficient Dimension Reduction Through High-Dimensional Sparse Sliced Inverse Regression

Abstract

Federated learning has become a popular tool in the big data era nowadays. It trains a centralized model based on data from different clients while keeping data decentralized. In this paper, we propose a federated sparse sliced inverse regression algorithm for the first time. Our method can simultaneously estimate the central dimension reduction subspace and perform variable selection in a federated setting. We transform this federated high-dimensional sparse sliced inverse regression problem into a convex optimization problem by constructing the covariance matrix safely and losslessly. We then use a linearized alternating direction method of multipliers algorithm to estimate the central subspace. We also give approaches of Bayesian information criterion and holdout validation to ascertain the dimension of the central subspace and the hyper-parameter of the algorithm. We establish an upper bound of the statistical error rate of our estimator under the heterogeneous setting. We demonstrate the effectiveness of our method through simulations and real world applications.

Keywords

Federated learning / Sliced inverse regression / Sufficient dimension reduction / Variable selection / Mathematical Sciences / Statistics / Information and Computing Sciences / Artificial Intelligence and Image Processing

References

[1] Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2009). https://doi.org/10.1515/9781400830244

[2] Agrawal, S., Jia, R.: Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In: Advances in Neural Information Processing Systems, vol. 30, pp. 1184–1194. Curran Associates, Inc. (2017)

[3] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends® Mach. Learn. 3(1), 1–122 (2011). https://doi.org/10.1561/2200000016

[4] CaiZ, LiR, ZhuL. Online sufficient dimension reduction through sliced inverse regression. J. Mach. Learn. Res., 2020, 21101-25

[5] Caldas, S., Duddu, S.M.K., Wu, P., Li, T., Konečný, J., McMahan, H.B., Smith, V., Talwalkar, A.: Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01097 (2019)

[6] Chai, D., Wang, L., Fu, L., Zhang, J., Chen, K., Yang, Q.: Federated singular vector decomposition. arXiv preprint arXiv:2105.08925 (2021)

[7] ChenX, ZouC, CookRD. Coordinate-independent sparse sufficient dimension reduction and variable selection. Ann. Stat., 2010, 3863696-3723.

[8] Cheng, H., Cui, W., Jianjun, X.: Online sparse sliced inverse regression. arXiv preprint arXiv:2009.14615 (2021)

[9] CookRD, NiL. Sufficient dimension reduction via inverse regression. J. Am. Stat. Assoc., 2005, 100470410-428.

[10] CookRD. On the interpretation of regression plots. J. Am. Stat. Assoc., 1994, 89425177-189.

[11] CookRD. Save: a method for dimension reduction and graphics in regression. Commun. Stat. Theory Methods, 2000, 299–102109-2121.

[12] EatonML. A characterization of spherical distributions. J. Multivar. Anal., 1986, 202272-276.

[13] FangE, HeB-S, LiuH, YuanX. Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Program. Comput., 2015, 7: 149-187.

[14] GaoC, MaZ, ZhouH. Sparse cca: adaptive estimation and computational barriers. Ann. Stat., 2017, 45: 2074-2101.

[15] GrammenosA, Mendoza SmithR, CrowcroftJ, MascoloC. Federated principal component analysis. Adv. Neural Inf. Process. Syst., 2020, 33: 6453-6464

[16] HallP, LiK-C. On almost linearity of low dimensional projections from high dimensional data. Ann. Stat., 1993, 212867-889.

[17] Hsieh, K., Phanishayee, A., Mutlu, O., Gibbons, P.: The non-iid data quagmire of decentralized machine learning. In: International Conference on Machine Learning, pp. 4387–4398 (2020). PMLR

[18] HsingT, CarrollRJ. An asymptotic theory for sliced inverse regression. Ann. Stat., 1992, 2021040-1061.

[19] Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.: Advances and open problems in federated learning. Found. Trends® in Mach. Learn. 14(1–2), 1–210 (2021). https://doi.org/10.1561/2200000083

[20] Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S., Suresh, A.T.: Scaffold: Stochastic controlled averaging for federated learning. In: International Conference on Machine Learning, pp. 5132–5143 (2020). PMLR

[21] LiB, WangS. On directional regression for dimension reduction. J. Am. Stat. Assoc., 2007, 102479997-1008.

[22] Li, B.: Sufficient Dimension Reduction: Methods and Applications with R. Chapman and Hall/CRC Press, Boca Raton (2017). https://doi.org/10.1201/9781315119427

[23] LiK-C. On principal hessian directions for data visualization and dimension reduction: Another application of stein’s lemma. J. Am. Stat. Assoc., 1992, 874201025-1039.

[24] LiK-C. Sliced inverse regression for dimension reduction. J. Am. Stat. Assoc., 1991, 86414316-327.

[25] Li, L., Dennis Cook, R., Nachtsheim, C.J.: Model-free variable selection. J. Roy. Stat. Soc. B 67(2), 285–299 (2005). https://doi.org/10.1111/j.1467-9868.2005.00502.x

[26] LiL, YinX. Sliced inverse regression with regularizations. Biometrics, 2008, 641124-131.

[27] LiT, SahuAK, ZaheerM, SanjabiM, TalwalkarA, SmithV. Federated optimization in heterogeneous networks. Proc. Mach. Learn. Syst., 2020, 2: 429-450

[28] LinQ, ZhaoZ, LiuJS. Sparse sliced inverse regression via lasso. J. Am. Stat. Assoc., 2019, 1145281726-1739.

[29] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial Intelligence and Statistics, pp. 1273–1282 (2017). PMLR

[30] MeinshausenN, YuB. Lasso-type recovery of sparse representations for high-dimensional data. Ann. Stat., 2009, 371246-270.

[31] RavikumarP, WainwrightMJ, RaskuttiG, YuB. High-dimensional covariance estimation by minimizing l1-penalized log-determinant divergence. Electron. J. Stat., 2011, 5: 935-980.

[32] Redmond, M.: Communities and Crime. UCI Machine Learning Repository (2009)

[33] ShimodairaH. Improving predictive inference under covariate shift by weighting the log-likelihood function. J. Stat. Plan. Inference, 2000, 90: 227-244.

[34] TanKM, WangZ, ZhangT, LiuH, CookR. A convex formulation for high-dimensional sparse sliced inverse regression. Biometrika, 2018, 105: 769-782.

[35] Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2018). https://doi.org/10.1017/9781108231596

[36] Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 (2010). https://doi.org/10.1017/CBO9780511794308.006

[37] Vu, V.Q., Cho, J., Lei, J., Rohe, K.: Fantope projection and selection: A near-optimal convex relaxation of sparse pca. Adv. Neural Inf. Process. Syst. 26, vol. 26, pp. 2670–2678 (2013)

[38] Xia, Y., Tong, H., Li, W.K., Zhu, L.-X.: An adaptive estimation of dimension reduction space. J. Roy. Stat. Soc. B 64(3), 363–410 (2002). https://doi.org/10.1142/9789812836281_0023

[39] YangQ, LiuY, ChengY, KangY, ChenT, YuH. Federated learning. Synth. Lect. Artif. Intell. Mach. Learn., 2019, 1331-207

[40] YangSS. General distribution theory of the concomitants of order statistics. Ann. Stat., 1977, 55996-1002.

[41] Yeh, I.-C., Lien, C.-h: The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Syst. Appl. 36(2, Part 1), 2473–2480 (2009). https://doi.org/10.1016/j.eswa.2007.12.020

[42] YuanH, MaT. Federated accelerated stochastic gradient descent. Adv. Neural Inf. Process. Syst., 2020, 33: 5332-5344

[43] ZengP, ZhuY. An integral transform method for estimating the central mean and central subspaces. J. Multivar. Anal., 2010, 1011271-290.

[44] ZhangC-H. Nearly unbiased variable selection under minimax concave penalty. Ann. Stat., 2010, 382894-942.

[45] ZhangX, HongM, DhopleS, YinW, LiuY. Fedpd: a federated learning framework with adaptivity to non-iid data. IEEE Trans. Signal Process., 2021, 69: 6055-6070.

[46] ZhuL-P, ZhuL-X, FengZ-H. Dimension reduction in regressions through cumulative slicing estimation. J. Am. Stat. Assoc., 2010, 1054921455-1466.

[47] ZhuL-X, MiaoB-Q, PengH. On sliced inverse regression with high-dimensional covariates. J. Am. Stat. Assoc., 2006, 101474630-643.

[48] ZhuL-X, NgKW. Asymptotics of sliced inverse regression. Stat. Sin., 1995, 102: 727-736.

Funding

National Natural Science Foundation of China(71873128, 12171451)

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature