×

On the accept-reject mechanism for Metropolis-Hastings algorithms. (English) Zbl 1533.65022

The main contribution of this work is the presentation of a fairly general method to define reversible Markov chains with respect to a given target measure, from a given proposal kernel on an extended state space, by defining a suitable acceptance probability. This extends the classical Metropolis-Hastings settings, and more precisely it is shown to be equivalent to the general settings of a work of Tierney in 1998. By contrast to the latter, the present method is written in a way which is reminiscent of the Hamiltonian Monte Carlo algorithm, which may be easier to interpret and thus to apply. The method is meant to be very versatile, covering in particular infinite-dimensional problems or non-separable Hamilonian schemes. Half of the work is concerned with examples, unifying many popular samplers and introducing some variations, motivated in particular by the use of so-called “surrogate dynamics” which can be used in place of the standard Hamiltonian dynamics with a reduce numerical cost.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
65C05 Monte Carlo methods

Software:

BayesDA; Stan; NUTS; GPS-ABC

References:

[1] ALIPRANTIS, C. D. and BORDER, K. C. (2013). Infinite-Dimensional Analysis: A Hitchhiker’s Guide, 2nd ed. Springer, Berlin. Digital Object Identifier: 10.1007/978-3-662-03961-8 Google Scholar: Lookup Link MathSciNet: MR1717083 · doi:10.1007/978-3-662-03961-8
[2] AMBROSIO, L., GIGLI, N. and SAVARÉ, G. (2008). Gradient Flows in Metric Spaces and in the Space of Probability Measures, 2nd ed. Lectures in Mathematics ETH Zürich. Birkhäuser, Basel. MathSciNet: MR2401600 · Zbl 1145.35001
[3] ANDRIEU, C., LEE, A. and LIVINGSTONE, S. (2020). A general perspective on the Metropolis-Hastings kernel. Preprint. Available at arXiv:2012.14881.
[4] ARNOLD, V. I. (2013). Mathematical Methods of Classical Mechanics. Graduate Texts in Mathematics 60. Springer, New York. MathSciNet: MR0690288
[5] ATCHADÉ, Y. F., FORT, G. and MOULINES, E. (2017). On perturbed proximal gradient algorithms. J. Mach. Learn. Res. 18 Paper No. 10, 33 pp. MathSciNet: MR3634877 · Zbl 1433.90199
[6] BÉNYI, Á., OH, T. and POCOVNICU, O. (2019). On the probabilistic Cauchy theory for nonlinear dispersive PDEs. In Landscapes of Time-Frequency Analysis. Appl. Numer. Harmon. Anal. 1-32. Birkhäuser/Springer, Cham. MathSciNet: MR3889875 · Zbl 1418.35389
[7] BESAG, J. E. (1994). Comments on “Representations of knowledge in complex systems” by U. Grenander and M. I. Miller. J. Roy. Statist. Soc. Ser. B 56 591-592.
[8] Beskos, A., Girolami, M., Lan, S., Farrell, P. E. and Stuart, A. M. (2017). Geometric MCMC for infinite-dimensional inverse problems. J. Comput. Phys. 335 327-351. Digital Object Identifier: 10.1016/j.jcp.2016.12.041 Google Scholar: Lookup Link MathSciNet: MR3612501 · Zbl 1375.35627 · doi:10.1016/j.jcp.2016.12.041
[9] BESKOS, A., KALOGEROPOULOS, K. and PAZOS, E. (2013). Advanced MCMC methods for sampling on diffusion pathspace. Stochastic Process. Appl. 123 1415-1453. Digital Object Identifier: 10.1016/j.spa.2012.12.001 Google Scholar: Lookup Link MathSciNet: MR3016228 · Zbl 1276.60078 · doi:10.1016/j.spa.2012.12.001
[10] BESKOS, A., PINSKI, F. J., SANZ-SERNA, J. M. and STUART, A. M. (2011). Hybrid Monte Carlo on Hilbert spaces. Stochastic Process. Appl. 121 2201-2230. Digital Object Identifier: 10.1016/j.spa.2011.06.003 Google Scholar: Lookup Link MathSciNet: MR2822774 · Zbl 1235.60091 · doi:10.1016/j.spa.2011.06.003
[11] BESKOS, A., ROBERTS, G., STUART, A. and VOSS, J. (2008). MCMC methods for diffusion bridges. Stoch. Dyn. 8 319-350. Digital Object Identifier: 10.1142/S0219493708002378 Google Scholar: Lookup Link MathSciNet: MR2444507 · Zbl 1159.65007 · doi:10.1142/S0219493708002378
[12] BETANCOURT, M. (2019). The convergence of Markov chain Monte Carlo methods: From the Metropolis method to Hamiltonian Monte Carlo. Ann. Phys. 531 1700214, 6 pp. Digital Object Identifier: 10.1002/andp.201700214 Google Scholar: Lookup Link MathSciNet: MR3925439 · Zbl 07759707 · doi:10.1002/andp.201700214
[13] Bogachev, V. I. (1998). Gaussian Measures. Mathematical Surveys and Monographs 62. Amer. Math. Soc., Providence, RI. Digital Object Identifier: 10.1090/surv/062 Google Scholar: Lookup Link MathSciNet: MR1642391 · doi:10.1090/surv/062
[14] Bogachev, V. I. (2007). Measure Theory. Vol. I, II. Springer, Berlin. Digital Object Identifier: 10.1007/978-3-540-34514-5 Google Scholar: Lookup Link MathSciNet: MR2267655 · Zbl 1120.28001 · doi:10.1007/978-3-540-34514-5
[15] BORGGAARD, J., GLATT-HOLTZ, N. and KROMETIS, J. (2020). A Bayesian approach to estimating background flows from a passive scalar. SIAM/ASA J. Uncertain. Quantificat. 8 1036-1060. Digital Object Identifier: 10.1137/19M1267544 Google Scholar: Lookup Link MathSciNet: MR4133486 · Zbl 1455.65205 · doi:10.1137/19M1267544
[16] BOU-RABEE, N. and EBERLE, A. (2021). Two-scale coupling for preconditioned Hamiltonian Monte Carlo in infinite dimensions. Stoch. Partial Differ. Equ. Anal. Comput. 9 207-242. Digital Object Identifier: 10.1007/s40072-020-00175-6 Google Scholar: Lookup Link MathSciNet: MR4218791 · Zbl 1470.60202 · doi:10.1007/s40072-020-00175-6
[17] BOU-RABEE, N. and SANZ-SERNA, J. M. (2018). Geometric integrators and the Hamiltonian Monte Carlo method. Acta Numer. 27 113-206. Digital Object Identifier: 10.1017/s0962492917000101 Google Scholar: Lookup Link MathSciNet: MR3826507 · Zbl 1431.65004 · doi:10.1017/s0962492917000101
[18] Bouchard-Côté, A., Vollmer, S. J. and Doucet, A. (2018). The bouncy particle sampler: A nonreversible rejection-free Markov chain Monte Carlo method. J. Amer. Statist. Assoc. 113 855-867. Digital Object Identifier: 10.1080/01621459.2017.1294075 Google Scholar: Lookup Link MathSciNet: MR3832232 · Zbl 1398.60084 · doi:10.1080/01621459.2017.1294075
[19] Bourgain, J. (1994). Periodic nonlinear Schrödinger equation and invariant measures. Comm. Math. Phys. 166 1-26. MathSciNet: MR1309539 · Zbl 0822.35126
[20] BUI-THANH, T. and GHATTAS, O. (2014). An analysis of infinite dimensional Bayesian inverse shape acoustic scattering and its numerical approximation. SIAM/ASA J. Uncertain. Quantificat. 2 203-222. Digital Object Identifier: 10.1137/120894877 Google Scholar: Lookup Link MathSciNet: MR3283906 · Zbl 1306.65270 · doi:10.1137/120894877
[21] BUI-THANH, T. and NGUYEN, Q. P. (2016). FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Probl. Imaging 10 943-975. Digital Object Identifier: 10.3934/ipi.2016028 Google Scholar: Lookup Link MathSciNet: MR3610747 · Zbl 1348.65013 · doi:10.3934/ipi.2016028
[22] Cotter, S. L., Roberts, G. O., Stuart, A. M. and White, D. (2013). MCMC Methods for Functions: Modifying Old Algorithms to Make Them Faster. Statist. Sci. 28 424-446. Digital Object Identifier: 10.1214/13-STS421 Google Scholar: Lookup Link MathSciNet: MR3135540 · Zbl 1331.62132 · doi:10.1214/13-STS421
[23] Da Prato, G. and Zabczyk, J. (2014). Stochastic Equations in Infinite Dimensions, 2nd ed. Encyclopedia of Mathematics and Its Applications 152. Cambridge Univ. Press, Cambridge. Digital Object Identifier: 10.1017/CBO9781107295513 Google Scholar: Lookup Link MathSciNet: MR3236753 · Zbl 1317.60077 · doi:10.1017/CBO9781107295513
[24] DASHTI, M. and STUART, A. M. (2017). The Bayesian approach to inverse problems. In Handbook of Uncertainty Quantification. Vol. 1, 2, 3 311-428. Springer, Cham. MathSciNet: MR3839555
[25] Duane, S., Kennedy, A. D., Pendleton, B. J. and Roweth, D. (1987). Hybrid Monte Carlo. Phys. Lett. B 195 216-222. Digital Object Identifier: 10.1016/0370-2693(87)91197-x Google Scholar: Lookup Link MathSciNet: MR3960671 · doi:10.1016/0370-2693(87)91197-x
[26] EBERLE, A. (2014). Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions. Ann. Appl. Probab. 24 337-377. Digital Object Identifier: 10.1214/13-AAP926 Google Scholar: Lookup Link MathSciNet: MR3161650 · Zbl 1296.60195 · doi:10.1214/13-AAP926
[27] FANG, Y., SANZ-SERNA, J. M. and SKEEL, R. D. (2014). Compressible generalized hybrid Monte Carlo. J. Chem. Phys. 140 174108.
[28] Folland, G. B. (1999). Real Analysis: Modern Techniques and Their Applications, 2nd ed. Pure and Applied Mathematics (New York). Wiley, New York. MathSciNet: MR1681462 · Zbl 0924.28001
[29] Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A. and Rubin, D. B. (2014). Bayesian Data Analysis, 3rd ed. Texts in Statistical Science Series. CRC Press, Boca Raton, FL. MathSciNet: MR3235677 · Zbl 1279.62004
[30] GELMAN, A., LEE, D. and GUO, J. (2015). Stan: A probabilistic programming language for Bayesian inference and optimization. J. Educ. Behav. Stat. 40 530-543. Digital Object Identifier: 10.3102/1076998615606113 Google Scholar: Lookup Link · doi:10.3102/1076998615606113
[31] GEYER, C. J. (2003). The Metropolis-Hastings-Green algorithm.
[32] Geyer, C. J. (2011). Introduction to Markov chain Monte Carlo. In Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC Handb. Mod. Stat. Methods 3-48. CRC Press, Boca Raton, FL. MathSciNet: MR2858443 · Zbl 1229.65014
[33] Girolami, M. and Calderhead, B. (2011). Riemann manifold Langevin and Hamiltonian Monte Carlo methods. J. R. Stat. Soc. Ser. B. Stat. Methodol. 73 123-214. Digital Object Identifier: 10.1111/j.1467-9868.2010.00765.x Google Scholar: Lookup Link MathSciNet: MR2814492 · Zbl 1411.62071 · doi:10.1111/j.1467-9868.2010.00765.x
[34] GLATT-HOLTZ, N., KROMETIS, J. and MONDAINI, C. (2023). A reduced order modeling approach to Hamiltonian Monte Carlo sampling for infinite-dimensional problems. To appear.
[35] GLATT-HOLTZ, N. E. and MONDAINI, C. F. (2022). Mixing rates for Hamiltonian Monte Carlo algorithms in finite and infinite dimensions. Stoch. Partial Differ. Equ. Anal. Comput. 10 1318-1391. Digital Object Identifier: 10.1007/s40072-021-00211-z Google Scholar: Lookup Link MathSciNet: MR4503169 · Zbl 1502.65004 · doi:10.1007/s40072-021-00211-z
[36] Green, P. J. (1995). Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika 82 711-732. MathSciNet: MR1380810 · Zbl 0861.62023
[37] HAIRER, E., LUBICH, C. and WANNER, G. (2006). Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, 2nd ed. Springer Series in Computational Mathematics 31. Springer, Berlin. MathSciNet: MR2221614 · Zbl 1094.65125
[38] HAIRER, M., STUART, A. and VOSS, J. (2009). Sampling conditioned diffusions. In Trends in Stochastic Analysis. London Mathematical Society Lecture Note Series 353 159-185. Cambridge Univ. Press, Cambridge. MathSciNet: MR2562154 · Zbl 1203.60100
[39] HAIRER, M., STUART, A. and VOSS, J. (2011). Signal processing problems on function space: Bayesian formulation, stochastic PDEs and effective MCMC methods. In The Oxford Handbook of Nonlinear Filtering 833-873. Oxford Univ. Press, Oxford. MathSciNet: MR2884617 · Zbl 1262.94012
[40] Hairer, M., Stuart, A. M. and Vollmer, S. J. (2014). Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions. Ann. Appl. Probab. 24 2455-2490. Digital Object Identifier: 10.1214/13-AAP982 Google Scholar: Lookup Link MathSciNet: MR3262508 · Zbl 1307.65002 · doi:10.1214/13-AAP982
[41] HAIRER, M., STUART, A. M. and VOSS, J. (2007). Analysis of SPDEs arising in path sampling. II. The nonlinear case. Ann. Appl. Probab. 17 1657-1706. Digital Object Identifier: 10.1214/07-AAP441 Google Scholar: Lookup Link MathSciNet: MR2358638 · Zbl 1140.60329 · doi:10.1214/07-AAP441
[42] HAIRER, M., STUART, A. M., VOSS, J. and WIBERG, P. (2005). Analysis of SPDEs arising in path sampling. I. The Gaussian case. Commun. Math. Sci. 3 587-603. MathSciNet: MR2188686 · Zbl 1138.60326
[43] Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 97-109. Digital Object Identifier: 10.1093/biomet/57.1.97 Google Scholar: Lookup Link MathSciNet: MR3363437 · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97
[44] Hoffman, M. D. and Gelman, A. (2014). The no-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res. 15 1593-1623. zbMATH: 1319.60150 MathSciNet: MR3214779 · Zbl 1319.60150
[45] JOSÉ, J. V. and SALETAN, E. J. (1998). Classical Dynamics: A Contemporary Approach. Cambridge Univ. Press, Cambridge. Digital Object Identifier: 10.1017/CBO9780511803772 Google Scholar: Lookup Link MathSciNet: MR1640663 · Zbl 0918.70001 · doi:10.1017/CBO9780511803772
[46] Kaipio, J. and Somersalo, E. (2005). Statistical and Computational Inverse Problems. Applied Mathematical Sciences 160. Springer, New York. MathSciNet: MR2102218 · Zbl 1068.65022
[47] LAN, S., BUI-THANH, T., CHRISTIE, M. and GIROLAMI, M. (2016). Emulation of higher-order tensors in manifold Monte Carlo methods for Bayesian inverse problems. J. Comput. Phys. 308 81-101. Digital Object Identifier: 10.1016/j.jcp.2015.12.032 Google Scholar: Lookup Link MathSciNet: MR3448239 · Zbl 1352.65010 · doi:10.1016/j.jcp.2015.12.032
[48] LEIMKUHLER, B. and REICH, S. (2004). Simulating Hamiltonian Dynamics. Cambridge Monographs on Applied and Computational Mathematics 14. Cambridge Univ. Press, Cambridge. MathSciNet: MR2132573 · Zbl 1069.65139
[49] LEVY, D., HOFFMAN, M. D. and SOHL-DICKSTEIN, J. (2017). Generalizing Hamiltonian Monte Carlo with neural networks. Preprint. Available at arXiv:1711.09268.
[50] LI, L., HOLBROOK, A., SHAHBABA, B. and BALDI, P. (2019). Neural network gradient Hamiltonian Monte Carlo. Comput. Statist. 34 281-299. Digital Object Identifier: 10.1007/s00180-018-00861-z Google Scholar: Lookup Link MathSciNet: MR3920582 · Zbl 1417.65014 · doi:10.1007/s00180-018-00861-z
[51] Liu, J. S. (2008). Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer, New York. MathSciNet: MR2401592 · Zbl 1132.65003
[52] LIU, J. S., LIANG, F. and WONG, W. H. (2000). The multiple-try method and local optimization in Metropolis sampling. J. Amer. Statist. Assoc. 95 121-134. Digital Object Identifier: 10.2307/2669532 Google Scholar: Lookup Link MathSciNet: MR1803145 · Zbl 1072.65505 · doi:10.2307/2669532
[53] LU, X., PERRONE, V., HASENCLEVER, L., TEH, Y. W. and VOLLMER, S. (2017). Relativistic Monte Carlo. In Artificial Intelligence and Statistics 1236-1245. PMLR.
[54] MARSDEN, J. E. and RATIU, T. S. (1995). Introduction to mechanics and symmetry. Phys. Today 48 65.
[55] MARTIN, J., WILCOX, L. C., BURSTEDDE, C. and GHATTAS, O. (2012). A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion. SIAM J. Sci. Comput. 34 A1460-A1487. Digital Object Identifier: 10.1137/110845598 Google Scholar: Lookup Link MathSciNet: MR2970260 · Zbl 1250.65011 · doi:10.1137/110845598
[56] MEEDS, E. and WELLING, M. (2014). GPS-ABC: Gaussian process surrogate approximate Bayesian computation. Preprint. Available at arXiv:1401.2838.
[57] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys. 21 1087-1092. · Zbl 1431.65006
[58] NAHMOD, A. R. and STAFFILANI, G. (2019). Randomness and nonlinear evolution equations. Acta Math. Sin. (Engl. Ser.) 35 903-932. Digital Object Identifier: 10.1007/s10114-019-8297-5 Google Scholar: Lookup Link MathSciNet: MR3952697 · Zbl 1419.35255 · doi:10.1007/s10114-019-8297-5
[59] NEAL, R. M. (1993). Probabilistic Inference Using Markov Chain Monte Carlo Methods. Department of Computer Science, Univ. Toronto, ON, Canada.
[60] Neal, R. M. (1999). Regression and classification using Gaussian process priors. In Bayesian Statistics, 6 (Alcoceber, 1998) 475-501. Oxford Univ. Press, New York. MathSciNet: MR1723510 · Zbl 0974.62072
[61] Neal, R. M. (2011). MCMC using Hamiltonian dynamics. In Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC Handb. Mod. Stat. Methods 113-162. CRC Press, Boca Raton, FL. MathSciNet: MR2858447 · Zbl 1229.65018
[62] NEKLYUDOV, K., WELLING, M., EGOROV, E. and VETROV, D. (2020). Involutive MCMC: A unifying framework. In International Conference on Machine Learning 7273-7282. PMLR.
[63] PETRA, N., MARTIN, J., STADLER, G. and GHATTAS, O. (2014). A computational framework for infinite-dimensional Bayesian inverse problems, Part II: Stochastic Newton MCMC with application to ice sheet flow inverse problems. SIAM J. Sci. Comput. 36 A1525-A1555. Digital Object Identifier: 10.1137/130934805 Google Scholar: Lookup Link MathSciNet: MR3233941 · Zbl 1303.35110 · doi:10.1137/130934805
[64] RADIVOJEVIĆ, T. and AKHMATSKAYA, E. (2020). Modified Hamiltonian Monte Carlo for Bayesian inference. Stat. Comput. 30 377-404. Digital Object Identifier: 10.1007/s11222-019-09885-x Google Scholar: Lookup Link MathSciNet: MR4064627 · Zbl 1436.62098 · doi:10.1007/s11222-019-09885-x
[65] RASMUSSEN, C. E. (2003). Gaussian processes to speed up hybrid Monte Carlo for expensive Bayesian integrals. In Bayesian Statistics, 7 (Tenerife, 2002) 651-660. Oxford Univ. Press, New York. MathSciNet: MR2003529
[66] REZNIKOFF, M. G. and VANDEN-EIJNDEN, E. (2005). Invariant measures of stochastic partial differential equations and conditioned diffusions. C. R. Math. Acad. Sci. Paris 340 305-308. Digital Object Identifier: 10.1016/j.crma.2004.12.025 Google Scholar: Lookup Link MathSciNet: MR2121896 · Zbl 1063.60092 · doi:10.1016/j.crma.2004.12.025
[67] ROBERT, C. P. and CASELLA, G. (2013). Monte Carlo Statistical Methods. Springer Texts in Statistics. Springer, New York. Digital Object Identifier: 10.1007/978-1-4757-3071-5 Google Scholar: Lookup Link MathSciNet: MR1707311 · doi:10.1007/978-1-4757-3071-5
[68] Roberts, G. O. and Tweedie, R. L. (1996). Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli 2 341-363. Digital Object Identifier: 10.2307/3318418 Google Scholar: Lookup Link MathSciNet: MR1440273 · Zbl 0870.60027 · doi:10.2307/3318418
[69] SILVESTER, J. R. (2000). Determinants of block matrices. Math. Gaz. 84 460-467.
[70] Stuart, A. M. (2010). Inverse problems: A Bayesian perspective. Acta Numer. 19 451-559. Digital Object Identifier: 10.1017/S0962492910000061 Google Scholar: Lookup Link MathSciNet: MR2652785 · Zbl 1242.65142 · doi:10.1017/S0962492910000061
[71] TEAM, S. D. (2016). Stan modeling language users guide and reference manual. Technical report.
[72] Tierney, L. (1998). A note on Metropolis-Hastings kernels for general state spaces. Ann. Appl. Probab. 8 1-9. Digital Object Identifier: 10.1214/aoap/1027961031 Google Scholar: Lookup Link MathSciNet: MR1620401 · Zbl 0935.60053 · doi:10.1214/aoap/1027961031
[73] TRIPURANENI, N., ROWLAND, M., GHAHRAMANI, Z. and TURNER, R. (2017). Magnetic Hamiltonian Monte Carlo. In International Conference on Machine Learning 3453-3461.
[74] TU, L. W. (2011). An Introduction to Manifolds, 2nd ed. Universitext. Springer, New York. Digital Object Identifier: 10.1007/978-1-4419-7400-6 Google Scholar: Lookup Link MathSciNet: MR2723362 · Zbl 1200.58001 · doi:10.1007/978-1-4419-7400-6
[75] ZHANG, C., SHAHBABA, B. and ZHAO, H. (2017). Precomputing strategy for Hamiltonian Monte Carlo method based on regularity in parameter space. Comput. Statist. 32 253-279. Digital Object Identifier: 10.1007/s00180-016-0683-1 Google Scholar: Lookup Link MathSciNet: MR3604217 · Zbl 1417.65018 · doi:10.1007/s00180-016-0683-1
[76] ZHANG, C., SHAHBABA, B. and ZHAO, H. (2017). Hamiltonian Monte Carlo acceleration using surrogate functions with random bases. Stat. Comput. 27 1473-1490. Digital Object Identifier: 10.1007/s11222-016-9699-1 Google Scholar: Lookup Link MathSciNet: MR3687321 · Zbl 1384.65008 · doi:10.1007/s11222-016-9699-1
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.