No Access

Semi-supervised learning with summary statistics

Huihui Qin

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, P. R. China

E-mail Address: huihui.qin@connect.polyu.hk

Search for more papers by this author

and

Xin Guo

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, P. R. China

E-mail Address: x.guo@polyu.edu.hk

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219530519400037Cited by:1 (Source: Crossref)

This article is part of the issue:

Special Issue on Mathematics of Big Data: Deep Learning, Approximation and Optimization
Guest Editors: Charles Chui, Shao-Bo Lin and Yiming Ying

Abstract

Nowadays, the extensive collection and analyzing of data is stimulating widespread privacy concerns, and therefore is increasing tensions between the potential sources of data and researchers. A privacy-friendly learning framework can help to ease the tensions, and to free up more data for research. We propose a new algorithm, LESS (Learning with Empirical feature-based Summary statistics from Semi-supervised data), which uses only summary statistics instead of raw data for regression learning. The selection of empirical features serves as a trade-off between prediction precision and the protection of privacy. We show that LESS achieves the minimax optimal rate of convergence in terms of the size of the labeled sample. LESS extends naturally to the applications where data are separately held by different sources. Compared with the existing literature on distributed learning, LESS removes the restriction of minimum sample size on single data sources.

Keywords:

AMSC: 68T05, 68Q32, 41A25

References

1. F. Bauer, S. Pereverzev and L. Rosasco, On regularization algorithms in learning theory, J. Complexity 23(1) (2007) 52–72. Web of Science, Google Scholar
2. A. L. Bertozzi, X. Luo, A. M. Stuart and K. C. Zygalakis, Uncertainty quantification in graph-based classification of high dimensional data, SIAM/ASA J. Uncertain. Quantif. 6(2) (2018) 568–595. Google Scholar
3. R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Vol. 169 (Springer-Verlag, New York, 1997). Google Scholar
4. R. Bhatia and L. Elsner, The Hoffman–Wielandt inequality in infinite dimensions, Proc. Indian Acad. Sci. Math. Sci. 104(3) (1994) 483–494. Web of Science, Google Scholar
5. G. Blanchard and N. Krämer, Optimal learning rates for kernel conjugate gradient regression, in Advances in Neural Information Processing Systems eds. J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, Vol. 23 (Curran Associates Inc., 2010) pp. 226–234. Google Scholar
6. G. Blanchard and N. Krämer, Convergence rates of kernel conjugate gradient for random design regression, Anal. Appl. 14(6) (2016) 763–794. Link, Web of Science, Google Scholar
7. A. Caponnetto and E. De Vito, Optimal rates for the regularized least-squares algorithm, Found. Comput. Math. 7(3) (2007) 331–368. Web of Science, Google Scholar
8. X. Chang, S.-B. Lin and D.-X. Zhou, Distributed semi-supervised learning with kernel ridge regression, J. Mach. Learn. Res. 18 (2017) 1493–1514. Web of Science, Google Scholar
9. K. Chaudhuri, C. Monteleoni and A. D. Sarwate, Differentially private empirical risk minimization, J. Mach. Learn. Res. 12 (2011) 1069–1109. Web of Science, Google Scholar
10. R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal. 21(1) (2006) 5–30. Web of Science, Google Scholar
11. F. Cucker and D.-X. Zhou, Learning Theory: An Approximation Theory Viewpoint, Cambridge Monographs on Applied and Computational Mathematics, Vol. 24 (Cambridge University Press, Cambridge, 2007). Google Scholar
12. X. Guo, T. Hu, and Q. Wu, Distributed minimum error entropy algorithms, preprint (2019). Google Scholar
13. X. Guo and D.-X. Zhou, An empirical feature-based learning algorithm producing sparse approximations, Appl. Comput. Harmon. Anal. 32(3) (2012) 389–400. Web of Science, Google Scholar
14. Z.-C. Guo, S.-B. Lin and D.-X. Zhou, Learning theory of distributed spectral algorithms, Inverse Problems 33(7) (2017) 074009. Web of Science, Google Scholar
15. Z.-C. Guo, L. Shi and Q. Wu, Learning theory of distributed regression with bias corrected regularization kernel network, J. Mach. Learn. Res. 18(118) (2017) 1–25. Google Scholar
16. A. J. Hoffman and H. W. Wielandt, The variation of the spectrum of a normal matrix, Duke Math. J. 20 (1953) 37–39. Web of Science, Google Scholar
17. T. Hu, J. Fan, Q. Wu and D.-X. Zhou, Regularization schemes for minimum error entropy principle, Anal. Appl. (Singap.) 13(4) (2015) 437–455. Link, Web of Science, Google Scholar
18. T. Kato, Variation of discrete spectra, Comm. Math. Phys. 111(3) (1987) 501–504. Web of Science, Google Scholar
19. S.-B. Lin, X. Guo and D.-X. Zhou, Distributed learning with regularized least squares, J. Mach. Learn. Res. 18(92) (2017) 1–31. Google Scholar
20. S.-B. Lin and D.-X. Zhou, Distributed kernel-based gradient descent algorithms, Constr. Approx. 47(2) (2018) 249–276. Web of Science, Google Scholar
21. G. Little and J. B. Reade, Eigenvalues of analytic kernels, SIAM J. Math. Anal. 15(1) (1984) 133–136. Web of Science, Google Scholar
22. J. Liu, C. Yang, Y. Jiao and J. Huang, ssLasso: A summary-statistic-based regression using Lasso, preprint (2017). Google Scholar
23. I. Pinelis, Optimum bounds for the distributions of martingales in Banach spaces, Ann. Probab. 22(4) (1994) 1679–1706. Google Scholar
24. J. B. Reade, Eigenvalues of positive definite kernels. II, SIAM J. Math. Anal. 15(1) (1984) 137–142. Web of Science, Google Scholar
25. L. Shi, Distributed learning with indefinite kernels, Anal. Appl. (2019) 1–29. Link, Web of Science, Google Scholar
26. S. Smale and D.-X. Zhou, Learning theory estimates via integral operators and their approximations, Constr. Approx. 26(2) (2007) 153–172. Web of Science, Google Scholar
27. I. Steinwart and A. Christmann, Support Vector Machines, Information Science and Statistics (Springer, New York, 2008). Google Scholar
28. I. Steinwart, D. R. Hush and C. Scovel, Optimal rates for regularized least squares regression, in COLT 2009 — The 22nd Conf. Learning Theory, Montreal, Quebec, Canada, June 18–21 (2009), pp. 79–93. Google Scholar
29. G. Wahba, Spline Models for Observational Data, (SIAM, Philadelphia, 1990). Google Scholar
30. C. Wang and T. Hu, Online minimum error entropy algorithm with unbounded sampling, Anal. Appl. (Singap.) 17(2) (2019) 293–322. Link, Web of Science, Google Scholar
31. Y. Yao, L. Rosasco and A. Caponnetto, On early stopping in gradient descent learning, Constr. Approx. 26(2) (2007) 289–315. Web of Science, Google Scholar
32. T. Zhang, Effective dimension and generalization of kernel learning, in Advances in Neural Information Processing Systems (MIT Press, Cambridge, MA, 2002), pp. 454–461. Google Scholar
33. Y. Zhao, J. Fan and L. Shi, Learning rates for regularized least squares ranking algorithm, Anal. Appl. (Singap.) 15(6) (2017) 815–836. Link, Web of Science, Google Scholar
34. X. Zhu and M. Stephens, Bayesian large-scale multiple regression with summary statistics from genome-wide association studies, Ann. Appl. Stat. 11(3) (2017) 1561–1592. Web of Science, Google Scholar
35. L. Zwald and G. Blanchard, On the convergence of eigenspaces in kernel principal component analysis, in Advances in Neural Information Processing Systems (MIT Press, Cambridge, MA, 2006), pp. 1649–1656. Google Scholar
36. L. Zwald, G. Blanchard, P. Massart and R. Vert, Kernel projection machine: A new tool for pattern recognition, in Advances in Neural Information Processing Systems (MIT Press, Cambridge, MA, 2005), pp. 1649–1656. Google Scholar