×

Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian. (English) Zbl 07924320

Summary: In this paper we prove the first quantitative convergence rates for the graph infinity Laplace equation for length scales at the connectivity threshold. In the graph-based semisupervised learning community this equation is also known as Lipschitz learning. The graph infinity Laplace equation is characterized by the metric on the underlying space, and convergence rates follow from convergence rates for graph distances. At the connectivity threshold, this problem is related to Euclidean first passage percolation, which is concerned with the Euclidean distance function \(d_h(x, y)\) on a homogeneous Poisson point process on \(\mathbb{R}^d\), where admissible paths have step size at most \(h > 0\). Using a suitable regularization of the distance function and subadditivity we prove that \(d_{h_s}(0, se_1)/s\to\sigma\) as \(s\to\infty\) almost surely where \(\sigma \geq 1\) is a dimensional constant and \(h_s \gtrsim \log(s)^{1/d}\). A convergence rate is not available due to a lack of approximate superadditivity when \(h_s\to\infty\). Instead, we prove convergence rates for the ratio \(\frac{d_h(0, se_1)}{d_h(0, 2se_1)}\to\frac{1}{2}\) when \(h\) is frozen and does not depend on \(s\). Combining this with the techniques that we developed in (IMA J. Numer. Anal. 43 (2023) 2445-2495), we show that this notion of ratio convergence is sufficient to establish uniform convergence rates for solutions of the graph infinity Laplace equation at percolation length scales.

MSC:

35R02 PDEs on graphs and networks (ramified or polygonal spaces)
60F10 Large deviations
60G44 Martingales with continuous parameter
60K35 Interacting random processes; statistical mechanics type models; percolation theory
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
68T05 Learning and adaptive systems in artificial intelligence

References:

[1] ALEXANDER, K. S. (1993). A note on some rates of convergence in first-passage percolation. Ann. Appl. Probab. 3 81-90. MathSciNet: MR1202516 · Zbl 0771.60090
[2] ALEXANDER, K. S. (2011). Subgaussian rates of convergence of means in directed first passage percolation.
[3] ARMSTRONG, S. and CARDALIAGUET, P. (2018). Stochastic homogenization of quasilinear Hamilton-Jacobi equations and geometric motions. J. Eur. Math. Soc. (JEMS) 20 797-864. Digital Object Identifier: 10.4171/JEMS/777 Google Scholar: Lookup Link MathSciNet: MR3779686 · Zbl 1392.35031 · doi:10.4171/JEMS/777
[4] Armstrong, S. and Dario, P. (2018). Elliptic regularity and quantitative homogenization on percolation clusters. Comm. Pure Appl. Math. 71 1717-1849. Digital Object Identifier: 10.1002/cpa.21726 Google Scholar: Lookup Link MathSciNet: MR3847767 · Zbl 1419.82024 · doi:10.1002/cpa.21726
[5] Armstrong, S., Kuusi, T. and Mourrat, J.-C. (2017). The additive structure of elliptic homogenization. Invent. Math. 208 999-1154. Digital Object Identifier: 10.1007/s00222-016-0702-4 Google Scholar: Lookup Link MathSciNet: MR3648977 · Zbl 1377.35014 · doi:10.1007/s00222-016-0702-4
[6] Armstrong, S., Kuusi, T. and Mourrat, J.-C. (2019). Quantitative Stochastic Homogenization and Large-Scale Regularity. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 352. Springer, Cham. Digital Object Identifier: 10.1007/978-3-030-15545-2 Google Scholar: Lookup Link MathSciNet: MR3932093 · Zbl 1482.60001 · doi:10.1007/978-3-030-15545-2
[7] ARMSTRONG, S. N. and SMART, C. K. (2012). A finite difference approach to the infinity Laplace equation and tug-of-war games. Trans. Amer. Math. Soc. 364 595-636. Digital Object Identifier: 10.1090/S0002-9947-2011-05289-X Google Scholar: Lookup Link MathSciNet: MR2846345 · Zbl 1239.91011 · doi:10.1090/S0002-9947-2011-05289-X
[8] Armstrong, S. N. and Smart, C. K. (2016). Quantitative stochastic homogenization of convex integral functionals. Ann. Sci. Éc. Norm. Supér. (4) 49 423-481. Digital Object Identifier: 10.24033/asens.2287 Google Scholar: Lookup Link MathSciNet: MR3481355 · Zbl 1344.49014 · doi:10.24033/asens.2287
[9] ARONSSON, G., CRANDALL, M. G. and JUUTINEN, P. (2004). A tour of the theory of absolutely minimizing functions. Bull. Amer. Math. Soc. (N.S.) 41 439-505. Digital Object Identifier: 10.1090/S0273-0979-04-01035-3 Google Scholar: Lookup Link MathSciNet: MR2083637 · Zbl 1150.35047 · doi:10.1090/S0273-0979-04-01035-3
[10] Auffinger, A., Damron, M. and Hanson, J. (2017). 50 Years of First-Passage Percolation. University Lecture Series 68. Amer. Math. Soc., Providence, RI. Digital Object Identifier: 10.1090/ulect/068 Google Scholar: Lookup Link MathSciNet: MR3729447 · Zbl 1452.60002 · doi:10.1090/ulect/068
[11] BARLES, G. and SOUGANIDIS, P. E. (1991). Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4 271-283. MathSciNet: MR1115933 · Zbl 0729.65077
[12] BOLLOBÁS, B. and BRIGHTWELL, G. (1992). The height of a random partial order: Concentration of measure. Ann. Appl. Probab. 2 1009-1018. MathSciNet: MR1189428 · Zbl 0758.06001
[13] BRAIDES, A. and CAROCCIA, M. (2023). Asymptotic behavior of the Dirichlet energy on Poisson point clouds. J. Nonlinear Sci. 33 Paper No. 80, 57 pp. Digital Object Identifier: 10.1007/s00332-023-09937-7 Google Scholar: Lookup Link MathSciNet: MR4617151 · Zbl 1520.49004 · doi:10.1007/s00332-023-09937-7
[14] Broadbent, S. R. and Hammersley, J. M. (1957). Percolation processes. I. Crystals and mazes. Proc. Camb. Philos. Soc. 53 629-641. Digital Object Identifier: 10.1017/s0305004100032680 Google Scholar: Lookup Link MathSciNet: MR0091567 · Zbl 0091.13901 · doi:10.1017/s0305004100032680
[15] BUNGERT, L., CALDER, J. and ROITH, T. (2023). Uniform convergence rates for Lipschitz learning on graphs. IMA J. Numer. Anal. 43 2445-2495. Digital Object Identifier: 10.1093/imanum/drac048 Google Scholar: Lookup Link MathSciNet: MR4621850 · Zbl 07726068 · doi:10.1093/imanum/drac048
[16] BUNGERT, L., CALDER, J. and ROITH, T. (2024). Supplement to “Ratio convergence rates for Euclidean first-passage percolation: Applications to the graph infinity Laplacian.” https://doi.org/10.1214/24-AAP2052SUPPA, https://doi.org/10.1214/24-AAP2052SUPPB
[17] CALDER, J. (2019). The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels. Nonlinearity 32 301-330. Digital Object Identifier: 10.1088/1361-6544/aae949 Google Scholar: Lookup Link MathSciNet: MR3893728 · Zbl 1408.35048 · doi:10.1088/1361-6544/aae949
[18] CALDER, J. (2019). Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data. SIAM J. Math. Data Sci. 1 780-812. Digital Object Identifier: 10.1137/18M1199241 Google Scholar: Lookup Link MathSciNet: MR4039189 · Zbl 1499.35598 · doi:10.1137/18M1199241
[19] CALDER, J. (2020). The calculus of variations.
[20] CALDER, J., COOK, B., THORPE, M. and SLEPČEV, D. (2020). Poisson learning: Graph based semi-supervised learning at very low label rates. In Proceedings of the 37th International Conference on Machine Learning 119 1306-1316. PMLR .
[21] CALDER, J. and ETTEHAD, M. (2022). Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth. J. Mach. Learn. Res. 23 Paper No. [318], 62 pp. MathSciNet: MR4577757
[22] CALDER, J. and GARCÍA TRILLOS, N. (2022). Improved spectral convergence rates for graph Laplacians on \(ε\)-graphs and \(k\)-NN graphs. Appl. Comput. Harmon. Anal. 60 123-175. Digital Object Identifier: 10.1016/j.acha.2022.02.004 Google Scholar: Lookup Link MathSciNet: MR4393800 · Zbl 1536.05286 · doi:10.1016/j.acha.2022.02.004
[23] CALDER, J., GARCÍA TRILLOS, N. and LEWICKA, M. (2022). Lipschitz regularity of graph Laplacians on random data clouds. SIAM J. Math. Anal. 54 1169-1222. Digital Object Identifier: 10.1137/20M1356610 Google Scholar: Lookup Link MathSciNet: MR4384039 · Zbl 1485.35153 · doi:10.1137/20M1356610
[24] CALDER, J. and SLEPČEV, D. (2020). Properly-weighted graph Laplacian for semi-supervised learning. Appl. Math. Optim. 82 1111-1159. Digital Object Identifier: 10.1007/s00245-019-09637-3 Google Scholar: Lookup Link MathSciNet: MR4167693 · Zbl 1465.35152 · doi:10.1007/s00245-019-09637-3
[25] CALDER, J., SLEPČEV, D. and THORPE, M. (2023). Rates of convergence for Laplacian semi-supervised learning with low labeling rates. Res. Math. Sci. 10 Paper No. 10, 42 pp. Digital Object Identifier: 10.1007/s40687-022-00371-x Google Scholar: Lookup Link MathSciNet: MR4548608 · Zbl 1538.68019 · doi:10.1007/s40687-022-00371-x
[26] CALDER, J. and SMART, C. K. (2020). The limit shape of convex hull peeling. Duke Math. J. 169 2079-2124. Digital Object Identifier: 10.1215/00127094-2020-0013 Google Scholar: Lookup Link MathSciNet: MR4132581 · Zbl 1455.35047 · doi:10.1215/00127094-2020-0013
[27] CAROCCIA, M. (2023). A compactness theorem for functions on Poisson point clouds. Nonlinear Anal. 231 Paper No. 113032, 18 pp. Digital Object Identifier: 10.1016/j.na.2022.113032 Google Scholar: Lookup Link MathSciNet: MR4575699 · Zbl 1512.49015 · doi:10.1016/j.na.2022.113032
[28] COOK, B. and CALDER, J. (2022). Rates of convergence for the continuum limit of nondominated sorting. SIAM J. Math. Anal. 54 872-911. Digital Object Identifier: 10.1137/20M1344901 Google Scholar: Lookup Link MathSciNet: MR4376298 · Zbl 1484.35152 · doi:10.1137/20M1344901
[29] COX, J. T. (1980). The time constant of first-passage percolation on the square lattice. Adv. in Appl. Probab. 12 864-879. Digital Object Identifier: 10.2307/1426745 Google Scholar: Lookup Link MathSciNet: MR0588407 · Zbl 0442.60096 · doi:10.2307/1426745
[30] Cox, J. T. and Durrett, R. (1981). Some limit theorems for percolation processes with necessary and sufficient conditions. Ann. Probab. 9 583-603. MathSciNet: MR0624685 · Zbl 0462.60012
[31] COX, J. T. and KESTEN, H. (1981). On the continuity of the time constant of first-passage percolation. J. Appl. Probab. 18 809-819. Digital Object Identifier: 10.1017/s0021900200034161 Google Scholar: Lookup Link MathSciNet: MR0633228 · Zbl 0474.60085 · doi:10.1017/s0021900200034161
[32] DARIO, P. and GU, C. (2021). Quantitative homogenization of the parabolic and elliptic Green’s functions on percolation clusters. Ann. Probab. 49 556-636. Digital Object Identifier: 10.1214/20-aop1456 Google Scholar: Lookup Link MathSciNet: MR4255127 · Zbl 1467.35033 · doi:10.1214/20-aop1456
[33] DEL TESO, F. and LINDGREN, E. (2022). A finite difference method for the variational \(p\)-Laplacian. J. Sci. Comput. 90 Paper No. 67, 31 pp. Digital Object Identifier: 10.1007/s10915-021-01745-z Google Scholar: Lookup Link MathSciNet: MR4358715 · Zbl 1486.65224 · doi:10.1007/s10915-021-01745-z
[34] DEL TESO, F., MANFREDI, J. J. and PARVIAINEN, M. (2022). Convergence of dynamic programming principles for the \(p\)-Laplacian. Adv. Calc. Var. 15 191-212. Digital Object Identifier: 10.1515/acv-2019-0043 Google Scholar: Lookup Link MathSciNet: MR4399821 · Zbl 1486.35235 · doi:10.1515/acv-2019-0043
[35] DÍAZ, J., MITSCHE, D., PERARNAU, G. and PÉREZ-GIMÉNEZ, X. (2016). On the relation between graph distance and Euclidean distance in random geometric graphs. Adv. in Appl. Probab. 48 848-864. Digital Object Identifier: 10.1017/apr.2016.31 Google Scholar: Lookup Link MathSciNet: MR3568895 · Zbl 1348.05188 · doi:10.1017/apr.2016.31
[36] DUNBAR, O. R., ELLIOTT, C. M. and KREUSSER, L. M. (2022). Models for information propagation on graphs. Preprint. Available at arXiv:2201.07577.
[37] E, W., LI, T. and VANDEN-EIJNDEN, E. (2019). Applied Stochastic Analysis. Graduate Studies in Mathematics 199. Amer. Math. Soc., Providence, RI. Digital Object Identifier: 10.1090/gsm/199 Google Scholar: Lookup Link MathSciNet: MR3932086 · Zbl 1430.60002 · doi:10.1090/gsm/199
[38] FADILI, J., FORCADEL, N., NGUYEN, T. T. and ZANTOUT, R. (2023). Limits and consistency of nonlocal and graph approximations to the Eikonal equation. IMA J. Numer. Anal. 43 3685-3728. Digital Object Identifier: 10.1093/imanum/drac082 Google Scholar: Lookup Link MathSciNet: MR4673672 · Zbl 1534.65131 · doi:10.1093/imanum/drac082
[39] FRIEDRICH, T., SAUERWALD, T. and STAUFFER, A. (2013). Diameter and broadcast time of random geometric graphs in arbitrary dimensions. Algorithmica 67 65-88. Digital Object Identifier: 10.1007/s00453-012-9710-y Google Scholar: Lookup Link MathSciNet: MR3072817 · Zbl 1275.05050 · doi:10.1007/s00453-012-9710-y
[40] GARCÍA TRILLOS, N., SLEPČEV, D., VON BRECHT, J., LAURENT, T. and BRESSON, X. (2016). Consistency of Cheeger and ratio graph cuts. J. Mach. Learn. Res. 17 Paper No. 181, 46 pp. MathSciNet: MR3567449 · Zbl 1392.62180
[41] GROISMAN, P., JONCKHEERE, M. and SAPIENZA, F. (2022). Nonhomogeneous Euclidean first-passage percolation and distance learning. Bernoulli 28 255-276. Digital Object Identifier: 10.3150/21-bej1341 Google Scholar: Lookup Link MathSciNet: MR4337705 · Zbl 1491.60178 · doi:10.3150/21-bej1341
[42] HAFIENE, Y., FADILI, J. M. and ELMOATAZ, A. (2019). Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs. SIAM J. Imaging Sci. 12 1772-1807. Digital Object Identifier: 10.1137/18M1223927 Google Scholar: Lookup Link MathSciNet: MR4025770 · Zbl 1447.65056 · doi:10.1137/18M1223927
[43] HAMMERSLEY, J. M. and WELSH, D. J. A. (1965). First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Proc. Internat. Res. Semin., Statist. Lab., Univ. California, Berkeley, Calif., 1963 61-110. Springer, New York. MathSciNet: MR0198576 · Zbl 0143.40402
[44] HIRSCH, C., NEUHÄUSER, D., GLOAGUEN, C. and SCHMIDT, V. (2015). First passage percolation on random geometric graphs and an application to shortest-path trees. Adv. in Appl. Probab. 47 328-354. Digital Object Identifier: 10.1239/aap/1435236978 Google Scholar: Lookup Link MathSciNet: MR3360380 · Zbl 1355.60018 · doi:10.1239/aap/1435236978
[45] HOWARD, C. D. and NEWMAN, C. M. (1997). Euclidean models of first-passage percolation. Probab. Theory Related Fields 108 153-170. Digital Object Identifier: 10.1007/s004400050105 Google Scholar: Lookup Link MathSciNet: MR1452554 · Zbl 0883.60091 · doi:10.1007/s004400050105
[46] HOWARD, C. D. and NEWMAN, C. M. (2001). Geodesics and spanning trees for Euclidean first-passage percolation. Ann. Probab. 29 577-623. Digital Object Identifier: 10.1214/aop/1008956685 Google Scholar: Lookup Link MathSciNet: MR1849171 · Zbl 1062.60099 · doi:10.1214/aop/1008956685
[47] HWANG, S. J., DAMELIN, S. B. and HERO, A. O. III (2016). Shortest path through random points. Ann. Appl. Probab. 26 2791-2823. Digital Object Identifier: 10.1214/15-AAP1162 Google Scholar: Lookup Link MathSciNet: MR3563194 · Zbl 1353.60028 · doi:10.1214/15-AAP1162
[48] KESTEN, H. (1981). Percolation theory for mathematicians. Nieuw Arch. Wiskd. (3) 29 227-239. MathSciNet: MR0643930 · Zbl 0483.60002
[49] Kesten, H. (1986). Aspects of first passage percolation. In École D’été de Probabilités de Saint-Flour, XIV—1984. Lecture Notes in Math. 1180 125-264. Springer, Berlin. Digital Object Identifier: 10.1007/BFb0074919 Google Scholar: Lookup Link MathSciNet: MR0876084 · Zbl 0602.60098 · doi:10.1007/BFb0074919
[50] KESTEN, H. (1993). On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 296-338. MathSciNet: MR1221154 · Zbl 0783.60103
[51] KINGMAN, J. F. C. (1993). Poisson Processes. Oxford Studies in Probability 3. The Clarendon Press, New York. MathSciNet: MR1207584 · Zbl 0771.60001
[52] LI, W. and SALGADO, A. J. (2022). Convergent, with rates, methods for normalized infinity Laplace, and related, equations. Preprint. Available at arXiv:2209.06109.
[53] LITTLE, A., MCKENZIE, D. and MURPHY, J. M. (2022). Balancing geometry and density: Path distances on high-dimensional data. SIAM J. Math. Data Sci. 4 72-99. Digital Object Identifier: 10.1137/20M1386657 Google Scholar: Lookup Link MathSciNet: MR4368991 · Zbl 1493.62391 · doi:10.1137/20M1386657
[54] OBERMAN, A. M. (2005). A convergent difference scheme for the infinity Laplacian: Construction of absolutely minimizing Lipschitz extensions. Math. Comp. 74 1217-1230. Digital Object Identifier: 10.1090/S0025-5718-04-01688-6 Google Scholar: Lookup Link MathSciNet: MR2137000 · Zbl 1094.65110 · doi:10.1090/S0025-5718-04-01688-6
[55] OBERMAN, A. M. (2006). Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems. SIAM J. Numer. Anal. 44 879-895. Digital Object Identifier: 10.1137/S0036142903435235 Google Scholar: Lookup Link MathSciNet: MR2218974 · Zbl 1124.65103 · doi:10.1137/S0036142903435235
[56] OBERMAN, A. M. (2013). Finite difference methods for the infinity Laplace and \(p\)-Laplace equations. J. Comput. Appl. Math. 254 65-80. Digital Object Identifier: 10.1016/j.cam.2012.11.023 Google Scholar: Lookup Link MathSciNet: MR3061067 · Zbl 1290.65098 · doi:10.1016/j.cam.2012.11.023
[57] PIMENTEL, L. P. R. (2011). Asymptotics for first-passage times on Delaunay triangulations. Combin. Probab. Comput. 20 435-453. Digital Object Identifier: 10.1017/S0963548310000477 Google Scholar: Lookup Link MathSciNet: MR2784636 · Zbl 1214.60048 · doi:10.1017/S0963548310000477
[58] ROITH, T. and BUNGERT, L. (2023). Continuum limit of Lipschitz learning on graphs. Found. Comput. Math. 23 393-431. Digital Object Identifier: 10.1007/s10208-022-09557-9 Google Scholar: Lookup Link MathSciNet: MR4568195 · Zbl 1512.35206 · doi:10.1007/s10208-022-09557-9
[59] SERAFINI, H. C. (1997). First-passage percolation on the Delaunay graph of a \(d\)-dimensional Poisson process. New York University.
[60] SLEPČEV, D. and THORPE, M. (2019). Analysis of \(p\)-Laplacian regularization in semisupervised learning. SIAM J. Math. Anal. 51 2085-2120. Digital Object Identifier: 10.1137/17M115222X Google Scholar: Lookup Link MathSciNet: MR3953458 · Zbl 1422.49020 · doi:10.1137/17M115222X
[61] SMART, C. K. (2010). On the infinity Laplacian and Hrushovski’s fusion. PhD thesis, UC Berkeley. MathSciNet: MR2941545
[62] SMYTHE, R. T. and WIERMAN, J. C. (2006). First-Passage Percolation on the Square Lattice. Lecture Notes in Math. 671. Springer, Berlin. MathSciNet: MR0513421
[63] YAO, C.-L., CHEN, G. and GUO, T.-D. (2011). Large deviations for the graph distance in supercritical continuum percolation. J. Appl. Probab. 48 154-172. Digital Object Identifier: 10.1239/jap/1300198142 Google Scholar: Lookup Link MathSciNet: MR2809893 · Zbl 1213.60161 · doi:10.1239/jap/1300198142
[64] ZHU, X., GHAHRAMANI, Z. and LAFFERTY, J. D. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning (ICML-03) 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.