Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data. (English) Zbl 1499.35598
Summary: We study the consistency of Lipschitz learning on graphs in the limit of infinite unlabeled data and finite labeled data. Previous work has conjectured that Lipschitz learning is well-posed in this limit, but is insensitive to the distribution of the unlabeled data, which is undesirable for semi-supervised learning. We first prove that this conjecture is true in the special case of a random geometric graph model with kernel-based weights. Then we go on to show that on a random geometric graph with self-tuning weights, Lipschitz learning is in fact highly sensitive to the distribution of the unlabeled data, and we show how the degree of sensitivity can be adjusted by tuning the weights. In both cases, our results follow from showing that the sequence of learned functions converges to the viscosity solution of an \(\infty\)-Laplace-type equation and studying the structure of the limiting equation.
MSC:
| 35R02 | PDEs on graphs and networks (ramified or polygonal spaces) |
| 35D40 | Viscosity solutions to PDEs |
| 35J60 | Nonlinear elliptic equations |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
Keywords:
partial differential equations; viscosity solutions; graph-based semi-supervised learning; Lipschitz learning; consistency; continuum limits; maximum principleReferences:
| [1] | G. Aronsson, M. Crandall, and P. Juutinen, A tour of the theory of absolutely minimizing functions, Bull. Amer. Math. Soc. (N.S.), 41 (2004), pp. 439-505. · Zbl 1150.35047 |
| [2] | E. N. Barron, R. R. Jensen, and C. Wang, The Euler equation and absolute minimizers of \(L^\infty\) functionals, Arch. Ration. Mech. Anal., 157 (2001), pp. 255-283. · Zbl 0979.49003 |
| [3] | S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, Oxford, UK, 2013. · Zbl 1279.60005 |
| [4] | O. Bousquet, S. Boucheron, and G. Lugosi, Introduction to statistical learning theory, in Advanced Lectures on Machine Learning, Springer, Berlin, Heidelberg, 2004, pp. 169-207. · Zbl 1120.68428 |
| [5] | J. Calder, The game theoretic p-Laplacian and semi-supervised learning with few labels, Nonlinearity, 32 (2018), pp. 301-330. · Zbl 1408.35048 |
| [6] | J. Calder, S. Esedoḡlu, and A. O. Hero, A PDE-based approach to nondominated sorting, SIAM J. Numer. Anal., 53 (2015), pp. 82-104, https://doi.org/10.1137/130940657. · Zbl 1330.65158 |
| [7] | J. Calder and D. Slepcev, Properly-Weighted Graph Laplacian for Semi-supervised Learning, preprint, https://arxiv.org/abs/1810.04351, 2018. |
| [8] | O. Chapelle, B. Scholkopf, and A. Zien, Semi-supervised Learning, MIT Press, Cambridge, MA, 2006. |
| [9] | S. Choi, Y. J. Kim, S. Briceno, and D. Mavris, Prediction of weather-induced airline delays based on machine learning algorithms, in Proceedings of the 2016 IEEE/AIAA 35th Digital Avionics Systems Conference (DASC), 2016, pp. 1-6. |
| [10] | M. G. Crandall, H. Ishii, and P.-L. Lions, User’s guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.), 27 (1992), pp. 1-67. · Zbl 0755.35015 |
| [11] | A. El Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright, and M. I. Jordan, Asymptotic behavior of \(\ell_p\)-based Laplacian regularization in semi-supervised learning, in Proceedings of the 29th Annual Conference on Learning Theory, 2016, pp. 879-906. |
| [12] | L. C. Evans, Partial Differential Equations, Grad. Stud. Math. 19, American Mathematical Society, Providence, RI, 1998. · Zbl 0902.35002 |
| [13] | M. Flores, J. Calder, and G. Lerman, Algorithms for \(\ell_p\)-Based Semi-supervised Learning on Graphs, preprint, https://arxiv.org/abs/1901.05031, 2019. |
| [14] | E. W. Frees, Estimating densities of functions of observations, J. Amer. Statist. Assoc., 89 (1994), pp. 517-525. · Zbl 0798.62051 |
| [15] | E. Giné and D. M. Mason, On local U-statistic processes and the estimation of densities of functions of several sample variables, Ann. Statist., 35 (2007), pp. 1105-1145. · Zbl 1175.60017 |
| [16] | M. Hein, J.-Y. Audibert, and U. von Luxburg, Graph Laplacians and their convergence on random neighborhood graphs, J. Mach. Learn. Res., 8 (2007), pp. 1325-1368. · Zbl 1222.68215 |
| [17] | M. Hein, J.-Y. Audibert, and U. von Luxburg, From graphs to manifolds-weak and strong pointwise consistency of graph Laplacians, in Proceedings of the International Conference on Computational Learning Theory, Springer, Berlin, Heidelberg, 2005, pp. 470-485. · Zbl 1095.68097 |
| [18] | J. Illian, A. Penttinen, H. Stoyan, and D. Stoyan, Statistical Analysis and Modelling of Spatial Point Patterns, John Wiley & Sons, Chichester, UK, 2008. · Zbl 1197.62135 |
| [19] | H. Ishii and P. Loreti, Limits of solutions of p-Laplace equations as p goes to infinity and related variational problems, SIAM J. Math. Anal., 37 (2005), pp. 411-437, https://doi.org/10.1137/S0036141004432827. · Zbl 1134.35307 |
| [20] | R. Jensen, Uniqueness of Lipschitz extensions: Minimizing the sup norm of the gradient, Arch. Rational Mech. Anal., 123 (1993), pp. 51-74. · Zbl 0789.35008 |
| [21] | P. Juutinen, Minimization Problems for Lipschitz Functions via Viscosity Solutions, Dissertation, University of Jyväskulä, Jyväskulä, Finland, 1998. · Zbl 0902.35037 |
| [22] | R. Kyng, A. Rao, S. Sachdeva, and D. A. Spielman, Algorithms for Lipschitz learning on graphs, in Proceedings of the 28th Conference on Learning Theory, 2015, pp. 1190-1223. |
| [23] | Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, Gradient-based learning applied to document recognition, Proc. IEEE, 86 (1998), pp. 2278-2324. |
| [24] | M. Lewicka and J. J. Manfredi, Game theoretical methods in PDEs, Boll. Unione Mat. Ital., 7 (2014), pp. 211-216. · Zbl 1322.35139 |
| [25] | P. Lindqvist, Notes on the p-Laplace Equation, 2017. · Zbl 1421.35002 |
| [26] | U. von Luxburg and O. Bousquet, Distance-based classification with Lipschitz functions, J. Mach. Learn. Res., 5 (2003/04), pp. 669-695. · Zbl 1222.68326 |
| [27] | J. J. Manfredi, A. Oberman, and A. P. Sviridov, Nonlinear elliptic partial differential equations and p-harmonic functions on graphs, Differential Integral Equations, 28 (2015), pp. 79-102. · Zbl 1349.35382 |
| [28] | B. Nadler, N. Srebro, and X. Zhou, Semi-supervised learning with the graph Laplacian: The limit of infinite unlabelled data, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2009, pp. 1330-1338. |
| [29] | A. Oberman, A convergent difference scheme for the infinity Laplacian: Construction of absolutely minimizing Lipschitz extensions, Math. Comp., 74 (2005), pp. 1217-1230. · Zbl 1094.65110 |
| [30] | A. Oberman, Finite difference methods for the infinity Laplace and p-Laplace equations, J. Comput. Appl. Math., 254 (2013), pp. 65-80. · Zbl 1290.65098 |
| [31] | Y. Peres, O. Schramm, S. Sheffield, and D. Wilson, Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc., 22 (2009), pp. 167-210. · Zbl 1206.91002 |
| [32] | Y. Peres and S. Sheffield, Tug-of-war with noise: A game-theoretic view of the p-Laplacian, Duke Math. J., 145 (2008), pp. 91-120. · Zbl 1206.35112 |
| [33] | J. J. Rebollo and H. Balakrishnan, Characterization and prediction of air traffic delays, Transp. Res. Part C Emerg. Technol., 44 (2014), pp. 231-241. |
| [34] | S. Sheffield and C. K. Smart, Vector-valued optimal Lipschitz extensions, Comm. Pure Appl. Math., 65 (2012), pp. 128-154. · Zbl 1233.35068 |
| [35] | Z. Shi, S. Osher, and W. Zhu, Weighted nonlocal Laplacian on interpolation from sparse data, J. Sci. Comput., 73 (2017), pp. 1164-1177. · Zbl 1381.65007 |
| [36] | B. W. Silverman, Density Estimation for Statistics and Data Analysis, Routledge, Abingdon, UK, 2018. |
| [37] | D. Slepčev and M. Thorpe, Analysis of p-Laplacian regularization in semisupervised learning, SIAM J. Math. Anal., 51 (2019), pp. 2085-2120, https://doi.org/10.1137/17M115222X. · Zbl 1422.49020 |
| [38] | C. K. Smart, On the Infinity Laplacian and Hrushovski’s Fusion, Ph.D. thesis, UC Berkeley, Berkeley, CA, 2010. |
| [39] | D. Ting, L. Huang, and M. Jordan, An Analysis of the Convergence of Graph Laplacians, preprint, https://arxiv.org/abs/1101.5435, 2011. |
| [40] | N. García Trillos and D. Slepčev, Continuum limit of total variation on point clouds, Arch. Ration. Mech. Anal., 220 (2016), pp. 193-241. · Zbl 1336.68215 |
| [41] | X. Zhu, Z. Ghahramani, and J. Lafferty, Semi-supervised learning using Gaussian fields and harmonic functions, in Proceedings of the International Conference on Machine Learning, Vol. 3, 2003, pp. 912-919. |
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.
