The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels. (English) Zbl 1408.35048
Summary: We study the game theoretic \(p\)-Laplacian for semi-supervised learning on graphs, and show that it is well-posed in the limit of finite labeled data and infinite unlabeled data. In particular, we show that the continuum limit of graph-based semi-supervised learning with the game theoretic \(p\)-Laplacian is a weighted version of the continuous \(p\)-Laplace equation. We also prove that solutions to the graph \(p\)-Laplace equation are approximately Hölder continuous with high probability. Our proof uses the viscosity solution machinery and the maximum principle on a graph.
MSC:
| 35J62 | Quasilinear elliptic equations |
| 35R02 | PDEs on graphs and networks (ramified or polygonal spaces) |
References:
| [1] | Chapelle, O.; Scholkopf, B.; Zien, A., Semi-Supervised Learning, (2006), Cambridge, MA: MIT Press, Cambridge, MA |
| [2] | Zhu, X., Semi-supervised learning using gaussian fields and harmonic functions, vol 3, 912-919, (2003) |
| [3] | Zhou, D.; Huang, J.; Schölkopf, B., Learning from labeled and unlabeled data on a directed graph, 1036-1043, (2005), New York: ACM, New York |
| [4] | Zhou, D.; Bousquet, O.; Lal, T. N.; Weston, J.; Schölkopf, B., Learning with local and global consistency, Adv. Neural Inf. Process. Syst., 16, 321-328, (2004) |
| [5] | Zhou, D.; Weston, J.; Gretton, A.; Bousquet, O.; Schölkopf, B., Ranking on data manifolds, Adv. Neural Inf. Process. Syst., 16, 169-176, (2004) |
| [6] | Ando, R. K.; Zhang, T., Learning on graph with laplacian regularization, Adv. Neural Inf. Process. Syst., 19, 25, (2007) |
| [7] | He, J.; Li, M.; Zhang, H-J; Tong, H.; Zhang, C., Manifold-ranking based image retrieval, 9-16, (2004), New York: ACM, New York |
| [8] | He, J.; Li, M.; Zhang, H-J; Tong, H.; Zhang, C., Generalized manifold-ranking-based image retrieval, IEEE Trans. Image Process., 15, 3170-3177, (2006) · doi:10.1109/TIP.2006.877491 |
| [9] | Wang, Y.; Cheema, M. A.; Lin, X.; Zhang, Q., Multi-manifold ranking: using multiple features for better image retrieval, 449-460, (2013), Berlin: Springer, Berlin |
| [10] | Yang, C.; Zhang, L.; Lu, H.; Ruan, X.; Yang, M-H, Saliency detection via graph-based manifold ranking, 3166-3173, (2013) |
| [11] | Zhou, X.; Belkin, M.; Srebro, N., An iterated graph laplacian approach for ranking on manifolds, 877-885, (2011), New York: ACM, New York |
| [12] | Xu, B.; Bu, J.; Chen, C.; Cai, D.; He, X.; Liu, W.; Luo, J., Efficient manifold ranking for image retrieval, 525-534, (2011), New York: ACM, New York |
| [13] | Nadler, B.; Srebro, N.; Zhou, X., Semi-supervised learning with the graph Laplacian: the limit of infinite unlabelled data, Neural Information Processing Systems, (2009) |
| [14] | El Alaoui, A.; Cheng, X.; Ramdas, A.; Wainwright, M. J.; Jordan, M. I., Asymptotic behavior of lp-based Laplacian regularization in semi-supervised learning, 879-906, (2016) |
| [15] | Bridle, N.; Zhu, X., p-voltages: Laplacian regularization for semi-supervised learning on high-dimensional data, (2013) |
| [16] | Alamgir, M.; Luxburg, U. V., Phase transition in the family of p-resistances, 379-387, (2011) |
| [17] | Kyng, R.; Rao, A.; Sachdeva, S.; Spielman, D. A., Algorithms for lipschitz learning on graphs, 1190-1223, (2015) |
| [18] | Luxburg, U. V.; Bousquet, O., Distance-based classification with lipschitz functions, J. Mach. Learn. Res., 5, 669-695, (2004) · Zbl 1222.68326 |
| [19] | Aronsson, G.; Crandall, M.; Juutinen, P., A tour of the theory of absolutely minimizing functions, Bull. Am. Math. Soc., 41, 439-505, (2004) · Zbl 1150.35047 · doi:10.1090/S0273-0979-04-01035-3 |
| [20] | Lindqvist, P., Notes on the p-Laplace Equation, (2017), Jyväskylä: University of Jyväskylä University Printing House, Jyväskylä |
| [21] | Peres, Y.; Schramm, O.; Sheffield, S.; Wilson, D., Tug-of-war and the infinity laplacian, J. Am. Math. Soc., 22, 167-210, (2009) · Zbl 1206.91002 · doi:10.1090/S0894-0347-08-00606-1 |
| [22] | Lewicka, M.; Manfredi, J. J., Game theoretical methods in pdes, Boll. Unione Mat. Ital., 7, 211-216, (2014) · Zbl 1322.35139 · doi:10.1007/s40574-014-0011-z |
| [23] | Calder, J., Consistency of Lipschitz learning with infinite unlabeled and finite labeled data, (2017) |
| [24] | Slepčev, D.; Thorpe, M., Analysis of p-laplacian regularization in semi-supervised learning, (2017) |
| [25] | LeCun, Y.; Bottou, L.; Bengio, Y.; Haffner, P., Gradient-based learning applied to document recognition, Proc. IEEE, 86, 2278-2324, (1998) · doi:10.1109/5.726791 |
| [26] | Hein, M.; Audibert, J-Y, Intrinsic dimensionality estimation of submanifolds in Rd, 289-296, (2005), New York: ACM, New York |
| [27] | Costa, J. A.; Hero, A. O., DDetermining intrinsic dimension and entropy of high-dimensional shape spaces, Statistics and Analysis of Shapes, 231-252, (2006), Berlin: Springer, Berlin · Zbl 1160.94303 |
| [28] | Deng, J.; Dong, W.; Socher, R.; Li, L-J; Li, K.; Fei-Fei, L., Imagenet: a large-scale hierarchical image database, 248-255, (2009), Piscataway, NJ: IEEE, Piscataway, NJ |
| [29] | Spielman, D. A.; Teng, S-H, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, 81-90, (2004), New York: ACM, New York · Zbl 1192.65048 |
| [30] | Cohen, M. B.; Kyng, R.; Miller, G. L.; Pachocki, J. W.; Peng, R.; Rao, A. B.; Xu, S. C., Solving SDD linear systems in nearly m log 1/2 n time, 343-352, (2014), New York: ACM, New York · Zbl 1315.65026 |
| [31] | Boyd, S.; Vandenberghe, L., Convex Optimization, (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 |
| [32] | Manfredi, J. J.; Oberman, A. M.; Sviridov, A. P., Nonlinear elliptic partial differential equations and p-harmonic functions on graphs, Differ. Integral Equ., 28, 79-102, (2015) · Zbl 1349.35382 |
| [33] | Tolksdorf, P., Regularity for a more general class of quasilinear elliptic equations, J. Differ. Equ., 51, 126-150, (1984) · Zbl 0488.35017 · doi:10.1016/0022-0396(84)90105-0 |
| [34] | Lieberman, G. M., Boundary regularity for solutions of degenerate elliptic equations, Nonlinear Anal. Theory Methods Appl., 12, 1203-1219, (1988) · Zbl 0675.35042 · doi:10.1016/0362-546X(88)90053-3 |
| [35] | Crandall, M. G.; Ishii, H.; Lions, P-L, User’s guide to viscosity solutions of second order partial differential equations, Bull. Am. Math. Soc., 27, 1-67, (1992) · Zbl 0755.35015 · doi:10.1090/S0273-0979-1992-00266-5 |
| [36] | Oberman, A. M., Finite difference methods for the infinity laplace and p-laplace equations, J. Comput. Appl. Math., 254, 65-80, (2013) · Zbl 1290.65098 · doi:10.1016/j.cam.2012.11.023 |
| [37] | Barles, G.; Souganidis, P. E., Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal., 4, 271-283, (1991) · Zbl 0729.65077 |
| [38] | Hein, M.; Audibert, J-Y; Luxburg, U. V., Graph Laplacians and their convergence on random neighborhood graphs, J. Mach. Learn. Res., 8, 1325-1368, (2007) · Zbl 1222.68215 |
| [39] | Hein, M., Uniform convergence of adaptive graph-based regularization, 50-64, (2006), Berlin: Springer, Berlin · Zbl 1143.68416 |
| [40] | Belkin, M.; Niyogi, P., Towards a theoretical foundation for Laplacian-based manifold methods, J. Comp. Sys. Sci., 74, 1289-1308, (2008) · Zbl 1124.60030 · doi:10.1214/074921706000000888 |
| [41] | Giné, E.; Koltchinskii, V., Empirical graph laplacian approximation of Laplace–Beltrami operators: large sample results, vol 51, 238-259, (2006), Beachwood, OH: Institute of Mathematical Statistics, Beachwood, OH · Zbl 1124.60030 |
| [42] | Hein, M.; Audibert, J-Y; Von Luxburg, U., From graphs to manifolds-weak and strong pointwise consistency of graph Laplacians, 470-485, (2005), Berlin: Springer, Berlin · Zbl 1095.68097 |
| [43] | Singer, A., From graph to manifold Laplacian: the convergence rate, Appl. Comput. Harmon. Anal., 21, 128-134, (2006) · Zbl 1095.68102 · doi:10.1016/j.acha.2006.03.004 |
| [44] | Ting, D.; Huang, L.; Jordan, M. I., An analysis of the convergence of graph Laplacians, 1079-1086, (2010) |
| [45] | Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities: a Nonasymptotic Theory of Independence, (2013), Oxford: Oxford University Press, Oxford · Zbl 1279.60005 |
| [46] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 13-30, (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830 |
| [47] | Silverman, B. W., Density Estimation for Statistics and Data Analysis, (2018), London: Routledge, London · Zbl 0617.62042 |
| [48] | Juutinen, P.; Lindqvist, P.; Manfredi, J. J., On the equivalence of viscosity solutions and weak solutions for a quasi-linear equation, SIAM J. Math. Anal., 33, 699-717, (2001) · Zbl 0997.35022 · doi:10.1137/S0036141000372179 |
| [49] | Calder, J.; Esedoḡlu, S.; Hero, A. O III, A PDE-based approach to non-dominated sorting, SIAM J. Numer. Anal., 53, 82-104, (2015) · Zbl 1330.65158 · doi:10.1137/130940657 |
| [50] | Ishii, H.; Nakamura, G., A class of integral equations and approximation of p-Laplace equations, Calculus Variations PDE, 37, 485-522, (2010) · Zbl 1198.45005 · doi:10.1007/s00526-009-0274-x |
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.
