Distributed function estimation: adaptation using minimal communication. (English) Zbl 07671981
Summary: We investigate whether in a distributed setting, adaptive estimation of a smooth function at the optimal rate is possible under minimal communication. It turns out that the answer depends on the risk considered and on the number of servers over which the procedure is distributed. We show that for the \(L_{\infty}\)-risk, adaptively obtaining optimal rates under minimal communication is not possible. For the \(L_2\)-risk, it is possible over a range of regularities that depends on the relation between the number of local servers and the total sample size.
MSC:
| 62G20 | Asymptotic properties of nonparametric inference |
| 62G05 | Nonparametric estimation |
| 62G10 | Nonparametric hypothesis testing |
| 94A15 | Information theory (general) |
Keywords:
divide-and-conquer methods; minimax rates; adaptation; communication constraints; Besov spaces; nonparametric estimationReferences:
| [1] | L. P. Barnes, Y. Han, and A. Ozgur, Learning distributions from their samples under com-munication constraints. 2019, arXiv:1902.02890v1 |
| [2] | H. Battey, J. Fan, H. Liu, J. Lu, and Z. Zhu, Distributed testing and estimation under sparse high dimensional models. Ann. Statist. 46 (2018), no. 3, 1352-1382 Zbl 1392.62060 MR 3798006 · Zbl 1392.62060 |
| [3] | L. Birgé, An alternative point of view on Lepski’s method. In State of the art in probability and statistics (Leiden, 1999), pp. 113-133, IMS Lecture Notes Monogr. Ser. 36, Inst. Math. Statist., Beachwood, OH, 2001 Zbl 1373.62142 MR 1836557 |
| [4] | M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff, Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In STOC’16 -Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Com-puting, pp. 1011-1020, ACM, New York, 2016 Zbl 1373.68235 MR 3536632 · Zbl 1373.68235 |
| [5] | A. D. Bull, Honest adaptive confidence bands and self-similar functions. Electron. J. Stat. 6 (2012), 1490-1516 Zbl 1295.62049 MR 2988456 · Zbl 1295.62049 |
| [6] | A. D. Bull and R. Nickl, Adaptive confidence sets in L 2 . Probab. Theory Related Fields 156 (2013), no. 3-4, 889-919 Zbl 1273.62105 MR 3078289 · Zbl 1273.62105 |
| [7] | T. T. Cai and M. G. Low, An adaptation theory for nonparametric confidence intervals. Ann. Statist. 32 (2004), no. 5, 1805-1840 Zbl 1056.62060 MR 2102494 · Zbl 1056.62060 |
| [8] | T. T. Cai and H. Wei, Distributed gaussian mean estimation under communication con-straints: Optimal rates and communication-efficient algorithms. 2020, arXiv:2001.08877 |
| [9] | T. T. Cai and H. Wei, Distributed nonparametric function estimation: Optimal rate of con-vergence and cost of adaptation. Ann. Statist. 50 (2022), no. 2, 698-725 Zbl 1486.62099 MR 4404917 · Zbl 1486.62099 |
| [10] | A. Carpentier, Testing the regularity of a smooth signal. Bernoulli 21 (2015), no. 1, 465-488 Zbl 1320.94021 MR 3322327 · Zbl 1320.94021 |
| [11] | A. Cohen, I. Daubechies, and P. Vial, Wavelets on the interval and fast wavelet transforms. Appl. Comput. Harmon. Anal. 1 (1993), no. 1, 54-81 Zbl 0795.42018 MR 1256527 · Zbl 0795.42018 |
| [12] | J. C. Duchi and M. J. Wainwright, Distance-based and continuum Fano inequalities with applications to statistical estimation. 2013, arXiv:1311.2669 |
| [13] | E. Giné and R. Nickl, Confidence bands in density estimation. Ann. Statist. 38 (2010), no. 2, 1122-1170 Zbl 1183.62062 MR 2604707 · Zbl 1183.62062 |
| [14] | E. Giné and R. Nickl, Mathematical foundations of infinite-dimensional statistical models. Camb. Ser. Stat. Probab. Math., 40, Cambridge Univ. Press, New York, 2016 Zbl 1358.62014 MR 3588285 · Zbl 1358.62014 |
| [15] | W. Härdle, G. Kerkyacharian, D. Picard, and A. Tsybakov, Wavelets, approximation, and statistical applications. Lect. Notes Stat. 129, Springer, New York, 1998 · Zbl 0899.62002 |
| [16] | Y. I. Ingster and I. A. Suslina, Nonparametric goodness-of-fit testing under Gaussian mod-els. Lect. Notes Stat. 169, Springer, New York, 2003 Zbl 1013.62049 MR 1991446 |
| [17] | A. Kleiner, A. Talwalkar, P. Sarkar, and M. I. Jordan, A scalable bootstrap for massive data. J. R. Stat. Soc. Ser. B. Stat. Methodol. 76 (2014), no. 4, 795-816 Zbl 07555464 MR 3248677 · Zbl 07555464 |
| [18] | J. D. Lee, Q. Liu, Y. Sun, and J. E. Taylor, Communication-efficient sparse regression. J. Mach. Learn. Res. 18 (2017), Paper No. 5 Zbl 1434.62157 MR 3625709 · Zbl 1434.62157 |
| [19] | D. Picard and K. Tribouley, Adaptive confidence interval for pointwise curve estimation. Ann. Statist. 28 (2000), no. 1, 298-335 Zbl 1106.62331 MR 1762913 · Zbl 1106.62331 |
| [20] | J. Robins and A. van der Vaart, Adaptive nonparametric confidence sets. Ann. Statist. 34 (2006), no. 1, 229-253 Zbl 1091.62039 MR 2275241 · Zbl 1091.62039 |
| [21] | J. D. Rosenblatt and B. Nadler, On the optimality of averaging in distributed statistical learning. Inf. Inference 5 (2016), no. 4, 379-404 Zbl 1426.68241 MR 3609865 · Zbl 1426.68241 |
| [22] | J. Rousseau and B. Szabo, Asymptotic frequentist coverage properties of Bayesian credi-ble sets for sieve priors. Ann. Statist. 48 (2020), no. 4, 2155-2179 Zbl 1471.62350 MR 4134790 · Zbl 1471.62350 |
| [23] | B. Szabó, A. W. van der Vaart, and J. H. van Zanten, Frequentist coverage of adaptive nonparametric Bayesian credible sets. Ann. Statist. 43 (2015), no. 4, 1391-1428 Zbl 1317.62040 MR 3357861 · Zbl 1317.62040 |
| [24] | B. Szabó and H. van Zanten, An asymptotic analysis of distributed nonparametric meth-ods. J. Mach. Learn. Res. 20 (2019), Paper No. 87 Zbl 1434.68457 MR 3960941 · Zbl 1434.68457 |
| [25] | Distributed function estimation: Adaptation using minimal communication 199 |
| [26] | B. Szabó and H. van Zanten, Adaptive distributed methods under communication con-straints. Ann. Statist. 48 (2020), no. 4, 2347-2380 Zbl 1455.62097 MR 4134798 · Zbl 1455.62097 |
| [27] | B. Szabó, L. Vuursteen, and H. van Zanten, Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication. IEEE Trans. Inf. Theory 68 (2022), no. 6, 4070-4084 Zbl 07555916 MR 4433269 · Zbl 1505.94025 |
| [28] | B. Szabó, L. Vuursteen, and H. van Zanten, Optimal high-dimensional and nonparametric distributed testing under communication constraints. 2022, arXiv:2202.00968 |
| [29] | A. Zaman and B. Szabó, Distributed nonparametric estimation under communication con-straints. 2022, arXiv:2204.10373 |
| [30] | Y. Zhang, J. C. Duchi, M. I. Jordan, and M. J. Wainwright, Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NeurIPS 2013 -Advances in Neural Information Processing Systems 26, pp. 2328-2336, Curran Associates, Inc., 2013 |
| [31] | Y. Zhang, J. C. Duchi, and M. J. Wainwright, Communication-efficient algorithms for statistical optimization. In NeurIPS 2012 -Advances in Neural Information Processing Systems 25, pp. 1502-1510, Curran Associates, Inc., 2012 |
| [32] | Y. Zhu and J. Lafferty, Distributed nonparametric regression under communication con-straints. In ICML 2018 -Proceedings of the 35th International Conference on Machine Learning, pp. 6004-6012, Proceedings of Machine Learning Research 80, PMLR, 2018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
