Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization. (English) Zbl 1539.62045
Summary: We study mean-field variational Bayesian inference using the TAP approach, for \(\mathbb{Z}_2\)-synchronization as a prototypical example of a high-dimensional Bayesian model. We show that for any signal strength \(\lambda > 1\) (the weak-recovery threshold), there exists a unique local minimizer of the TAP free energy functional near the mean of the Bayes posterior law. Furthermore, the TAP free energy in a local neighborhood of this minimizer is strongly convex. Consequently, a natural-gradient/mirror-descent algorithm achieves linear convergence to this minimizer from a local initialization, which may be obtained by a constant number of iterations of Approximate Message Passing (AMP). This provides a rigorous foundation for variational inference in high dimensions via minimization of the TAP free energy.
We also analyze the finite-sample convergence of AMP, showing that AMP is asymptotically stable at the TAP minimizer for any \(\lambda > 1\), and is linearly convergent to this minimizer from a spectral initialization for sufficiently large \(\lambda\). Such a guarantee is stronger than results obtainable by state evolution analyses, which only describe a fixed number of AMP iterations in the infinite-sample limit.
Our proofs combine the Kac-Rice formula and Sudakov-Fernique Gaussian comparison inequality to analyze the complexity of critical points that satisfy strong convexity and stability conditions within their local neighborhoods.
We also analyze the finite-sample convergence of AMP, showing that AMP is asymptotically stable at the TAP minimizer for any \(\lambda > 1\), and is linearly convergent to this minimizer from a spectral initialization for sufficiently large \(\lambda\). Such a guarantee is stronger than results obtainable by state evolution analyses, which only describe a fixed number of AMP iterations in the infinite-sample limit.
Our proofs combine the Kac-Rice formula and Sudakov-Fernique Gaussian comparison inequality to analyze the complexity of critical points that satisfy strong convexity and stability conditions within their local neighborhoods.
MSC:
| 62C10 | Bayesian problems; characterization of Bayes procedures |
| 15B52 | Random matrices (algebraic aspects) |
| 82D30 | Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) |
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
Keywords:
approximate message passing (AMP); landscape analysis; natural gradient descent; nonconvex optimization; TAP free energy; variational inference; \(\mathbb{Z}_2\) synchronizationReferences:
| [1] | ALQUIER, P. and RIDGWAY, J. (2020). Concentration of tempered posteriors and of their variational approximations. Ann. Statist. 48 1475-1497. · Zbl 1454.62135 · doi:10.1214/19-AOS1855 |
| [2] | AMARI, S.-I. (1998). Natural gradient works efficiently in learning. Neural Comput. 10 251-276. |
| [3] | AROUS, G. B., BOURGADE, P. and MCKENNA, B. (2021). Landscape complexity beyond invariance and the elastic manifold. Preprint. Available at arXiv:2105.05051. |
| [4] | AUFFINGER, A. and BEN AROUS, G. (2013). Complexity of random smooth functions on the high-dimensional sphere. Ann. Probab. 41 4214-4247. · Zbl 1288.15045 · doi:10.1214/13-AOP862 |
| [5] | Auffinger, A., Ben Arous, G. and Černý, J. (2013). Random matrices and complexity of spin glasses. Comm. Pure Appl. Math. 66 165-201. · Zbl 1269.82066 · doi:10.1002/cpa.21422 |
| [6] | AUFFINGER, A. and JAGANNATH, A. (2019). Thouless-Anderson-Palmer equations for generic \(p\)-spin glasses. Ann. Probab. 47 2230-2256. · Zbl 1426.82067 · doi:10.1214/18-AOP1307 |
| [7] | Augeri, F. (2020). Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs. Ann. Probab. 48 2404-2448. · Zbl 1456.60063 · doi:10.1214/20-AOP1427 |
| [8] | Baik, J., Ben Arous, G. and Péché, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 33 1643-1697. · Zbl 1086.15022 · doi:10.1214/009117905000000233 |
| [9] | BANDEIRA, A. S., CHEN, Y., LEDERMAN, R. R. and SINGER, A. (2020). Non-unique games over compact groups and orientation estimation in cryo-EM. Inverse Probl. 36 064002, 39 pp. · Zbl 1470.92163 · doi:10.1088/1361-6420/ab7d2c |
| [10] | BARBIER, J., DIA, M., MACRIS, N., KRZAKALA, F., LESIEUR, T. and ZDEBOROVÁ, L. (2016). Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. In Neural Information Processing Systems. |
| [11] | Basak, A. and Mukherjee, S. (2017). Universality of the mean-field for the Potts model. Probab. Theory Related Fields 168 557-600. · Zbl 1369.60066 · doi:10.1007/s00440-016-0718-0 |
| [12] | BASKERVILLE, N. P., KEATING, J. P., MEZZADRI, F. and NAJNUDEL, J. (2021). The loss surfaces of neural networks with general activation functions. J. Stat. Mech. Theory Exp. 2021 Paper No. 064001, 71 pp. · Zbl 1539.82374 · doi:10.1088/1742-5468/abfa1e |
| [13] | BASKERVILLE, N. P., KEATING, J. P., MEZZADRI, F. and NAJNUDEL, J. (2022). A spin glass model for the loss surfaces of generative adversarial networks. J. Stat. Phys. 186 Paper No. 29, 45 pp. · Zbl 07476207 · doi:10.1007/s10955-022-02875-w |
| [14] | BAUSCHKE, H. H., BOLTE, J. and TEBOULLE, M. (2017). A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications. Math. Oper. Res. 42 330-348. · Zbl 1364.90251 · doi:10.1287/moor.2016.0817 |
| [15] | Bayati, M., Lelarge, M. and Montanari, A. (2015). Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25 753-822. · Zbl 1322.60207 · doi:10.1214/14-AAP1010 |
| [16] | Bayati, M. and Montanari, A. (2011). The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inf. Theory 57 764-785. · Zbl 1366.94079 · doi:10.1109/TIT.2010.2094817 |
| [17] | Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31 167-175. · Zbl 1046.90057 · doi:10.1016/S0167-6377(02)00231-6 |
| [18] | BELIUS, D. and KISTLER, N. (2019). The TAP-Plefka variational principle for the spherical SK model. Comm. Math. Phys. 367 991-1017. · Zbl 1419.82069 · doi:10.1007/s00220-019-03304-y |
| [19] | Ben Arous, G., Mei, S., Montanari, A. and Nica, M. (2019). The landscape of the spiked tensor model. Comm. Pure Appl. Math. 72 2282-2330. · Zbl 1434.62078 · doi:10.1002/cpa.21861 |
| [20] | Berthier, R., Montanari, A. and Nguyen, P.-M. (2020). State evolution for approximate message passing with non-separable functions. Inf. Inference 9 33-79. · Zbl 1470.94003 · doi:10.1093/imaiai/iay021 |
| [21] | BICKEL, P., CHOI, D., CHANG, X. and ZHANG, H. (2013). Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. Ann. Statist. 41 1922-1943. · Zbl 1292.62042 · doi:10.1214/13-AOS1124 |
| [22] | BINGHAM, E., CHEN, J. P., JANKOWIAK, M., OBERMEYER, F., PRADHAN, N., KARALETSOS, T., SINGH, R., SZERLIP, P., HORSFALL, P. et al. (2019). Pyro: Deep universal probabilistic programming. J. Mach. Learn. Res. 20 973-978. |
| [23] | BLEI, D. M. (2012). Probabilistic topic models. Commun. ACM 55 77-84. |
| [24] | Blei, D. M., Kucukelbir, A. and McAuliffe, J. D. (2017). Variational inference: A review for statisticians. J. Amer. Statist. Assoc. 112 859-877. · doi:10.1080/01621459.2017.1285773 |
| [25] | Blei, D. M., Ng, A. Y. and Jordan, M. I. (2003). Latent Dirichlet allocation. J. Mach. Learn. Res. 3 993-1022. · Zbl 1112.68379 |
| [26] | Bolthausen, E. (2014). An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model. Comm. Math. Phys. 325 333-366. · Zbl 1288.82038 · doi:10.1007/s00220-013-1862-3 |
| [27] | BOLTHAUSEN, E. (2019). A Morita type proof of the replica-symmetric formula for SK. In Statistical Mechanics of Classical and Disordered Systems. Springer Proc. Math. Stat. 293 63-93. Springer, Cham. · Zbl 1446.82083 · doi:10.1007/978-3-030-29077-1_4 |
| [28] | BRAY, A. and MOORE, M. A. (1980). Metastable states in spin glasses. J. Phys. C, Solid State Phys. 13 L469. |
| [29] | BRAY, A., MOORE, M. A. and YOUNG, A. P. (1984). Weighted averages of TAP solutions and Parisi’s \(\mathit{q}(\mathit{x})\). J. Phys. C, Solid State Phys. 17 L155. |
| [30] | CARBONETTO, P. and STEPHENS, M. (2012). Scalable variational inference for Bayesian variable selection in regression, and its accuracy in genetic association studies. Bayesian Anal. 7 73-107. · Zbl 1330.62089 · doi:10.1214/12-BA703 |
| [31] | CAVAGNA, A., GIARDINA, I., PARISI, G. and MÉZARD, M. (2003). On the formal equivalence of the TAP and thermodynamic methods in the SK model. J. Phys. A 36 1175-1194. · Zbl 1066.82023 · doi:10.1088/0305-4470/36/5/301 |
| [32] | CELENTANO, M. (2022). Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy. Preprint. Available at arXiv:2208.09550. |
| [33] | CELENTANO, M., FAN, Z. and MEI, S. (2023). Supplement to “Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization.” https://doi.org/10.1214/23-AOS2257SUPP |
| [34] | CELENTANO, M., MONTANARI, A. and WEI, Y. (2020). The lasso with general gaussian designs with applications to hypothesis testing. Preprint. Available at arXiv:2007.13716. |
| [35] | CHATTERJEE, S. (2010). Spin glasses and Stein’s method. Probab. Theory Related Fields 148 567-600. · Zbl 1209.82016 · doi:10.1007/s00440-009-0240-8 |
| [36] | Chatterjee, S. and Dembo, A. (2016). Nonlinear large deviations. Adv. Math. 299 396-450. · Zbl 1356.60045 · doi:10.1016/j.aim.2016.05.017 |
| [37] | CHEN, W.-K. and LAM, W.-K. (2021). Universality of approximate message passing algorithms. Electron. J. Probab. 26 Paper No. 36, 44 pp. · Zbl 1483.60007 · doi:10.1214/21-EJP604 |
| [38] | CHEN, W.-K. and PANCHENKO, D. (2018). On the TAP free energy in the mixed \(p\)-spin models. Comm. Math. Phys. 362 219-252. · Zbl 1397.82012 · doi:10.1007/s00220-018-3143-7 |
| [39] | CHEN, W.-K., PANCHENKO, D. and SUBAG, E. (2018). Generalized TAP free energy. Comm. Pure Appl. Math. |
| [40] | CHÉRIEF-ABDELLATIF, B.-E. (2019). Consistency of ELBO maximization for model selection. In Symposium on Advances in Approximate Bayesian Inference. Proc. Mach. Learn. Res. (PMLR) 96 11-31. PMLR. |
| [41] | CRISANTI, A., LEUZZI, L., PARISI, G. and RIZZO, T. (2003). Complexity in the Sherrington-Kirkpatrick model in the annealed approximation. Phys. Rev. B 68 174401. |
| [42] | Crisanti, A., Leuzzi, L. and Rizzo, T. (2005). Complexity in mean-field spin-glass models: Ising p-spin. Phys. Rev. B 71 094202. |
| [43] | DE DOMINICIS, C. and YOUNG, A. P. (1983). Weighted averages and order parameters for the infinite range Ising spin glass. J. Phys. A 16 2063-2075. |
| [44] | Deshpande, Y., Abbe, E. and Montanari, A. (2017). Asymptotic mutual information for the balanced binary stochastic block model. Inf. Inference 6 125-170. · Zbl 1383.62021 · doi:10.1093/imaiai/iaw017 |
| [45] | DESHPANDE, Y. and MONTANARI, A. (2014). Information-theoretically optimal sparse PCA. In 2014 IEEE International Symposium on Information Theory 2197-2201. IEEE, New York. |
| [46] | Ding, J. and Sun, N. (2019). Capacity lower bound for the Ising perceptron. In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 816-827. ACM, New York. · Zbl 1447.82025 · doi:10.1145/3313276.3316383 |
| [47] | DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2009). Message-passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. 106 18914-18919. |
| [48] | DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2010). Message passing algorithms for compressed sensing: I. motivation and construction. In 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo) 1-5. IEEE, New York. |
| [49] | DRAGOMIR, R. A., EVEN, M. and HENDRIKX, H. (2021). Fast stochastic Bregman gradient methods: Sharp analysis and variance reduction. In International Conference on Machine Learning 2815-2825. PMLR. |
| [50] | DUDEJA, R., SEN, S. and LU, Y. M. (2022). Spectral universality of regularized linear regression with nearly deterministic sensing matrices. Preprint. Available at arXiv:2208.02753. |
| [51] | EL ALAOUI, A., MONTANARI, A. and SELLKE, M. (2022). Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022 323-334. IEEE Computer Soc., Los Alamitos, CA. |
| [52] | Eldan, R. (2018). Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geom. Funct. Anal. 28 1548-1596. · Zbl 1428.60045 · doi:10.1007/s00039-018-0461-z |
| [53] | FAN, Z., MEI, S. and MONTANARI, A. (2021). TAP free energy, spin glasses and variational inference. Ann. Probab. 49 1-45. · Zbl 1467.60025 · doi:10.1214/20-AOP1443 |
| [54] | FAN, Z. and WU, Y. (2021). The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings. Preprint. Available at arXiv:2105.02797. |
| [55] | FENG, O. Y., VENKATARAMANAN, R., RUSH, C., SAMWORTH, R. J. et al. (2022). A unifying tutorial on approximate message passing. Found. Trends Mach. Learn. 15 335-536. · Zbl 1491.68152 |
| [56] | FERNIQUE, X. (1975). Regularité des trajectoires des fonctions aléatoires gaussiennes. In École D’Été de Probabilités de Saint-Flour, IV-1974. Lecture Notes in Math. 480 1-96. Springer, Berlin. · Zbl 0331.60025 |
| [57] | FYODOROV, Y. V. (2004). Complexity of random energy landscapes, glass transition, and absolute value of the spectral determinant of random matrices. Phys. Rev. Lett. 92 240601, 4 pp. · Zbl 1267.82055 · doi:10.1103/PhysRevLett.92.240601 |
| [58] | GAUCHER, S. and KLOPP, O. (2021). Optimality of variational inference for stochasticblock model with missing links. Adv. Neural Inf. Process. Syst. 34 19947-19959. |
| [59] | GHORBANI, B., JAVADI, H. and MONTANARI, A. (2019). An instability in variational inference for topic models. In International Conference on Machine Learning 2221-2231. PMLR. |
| [60] | Gordon, Y. (1985). Some inequalities for Gaussian processes and applications. Israel J. Math. 50 265-289. · Zbl 0663.60034 · doi:10.1007/BF02759761 |
| [61] | GUTMAN, D. H. and PEÑA, J. F. (2023). Perturbed Fenchel duality and first-order methods. Math. Program. 198 443-469. · Zbl 1512.90167 · doi:10.1007/s10107-022-01779-7 |
| [62] | HALL, P., ORMEROD, J. T. and WAND, M. P. (2011). Theory of Gaussian variational approximation for a Poisson mixed model. Statist. Sinica 21 369-389. · Zbl 1206.62035 |
| [63] | HALL, P., PHAM, T., WAND, M. P. and WANG, S. S. J. (2011). Asymptotic normality and valid inference for Gaussian variational approximation. Ann. Statist. 39 2502-2532. · Zbl 1231.62029 · doi:10.1214/11-AOS908 |
| [64] | HAN, Q. and SHEN, Y. (2022). Universality of regularized regression estimators in high dimensions. Preprint. Available at arXiv:2206.07936. |
| [65] | HANZELY, F., RICHTÁRIK, P. and XIAO, L. (2021). Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Comput. Optim. Appl. 79 405-440. · Zbl 1473.90114 · doi:10.1007/s10589-021-00273-8 |
| [66] | HU, H. and LU, Y. M. (2020). Universality laws for high-dimensional learning with random features. Preprint. Available at arXiv:2009.07669. |
| [67] | JAIN, V., KOEHLER, F. and MOSSEL, E. (2018). The mean-field approximation: Information inequalities, algorithms, and complexity. In Conference on Learning Theory 1326-1347. PMLR. |
| [68] | Javanmard, A. and Montanari, A. (2013). State evolution for general approximate message passing algorithms, with applications to spatial coupling. Inf. Inference 2 115-144. · Zbl 1335.94015 · doi:10.1093/imaiai/iat004 |
| [69] | Javanmard, A., Montanari, A. and Ricci-Tersenghi, F. (2016). Phase transitions in semidefinite relaxations. Proc. Natl. Acad. Sci. USA 113 E2218-E2223. · Zbl 1359.62188 · doi:10.1073/pnas.1523097113 |
| [70] | Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist. 29 295-327. · Zbl 1016.62078 · doi:10.1214/aos/1009210544 |
| [71] | Jordan, M. I., Ghahramani, Z., Jaakkola, T. S. and Saul, L. K. (1999). An introduction to variational methods for graphical models. Mach. Learn. 37 183-233. · Zbl 0945.68164 |
| [72] | KABASHIMA, Y. (2003). A CDMA multiuser detection algorithm on the basis of belief propagation. J. Phys. A 36 11111-11121. · Zbl 1081.94509 · doi:10.1088/0305-4470/36/43/030 |
| [73] | KAHANE, J.-P. (1986). Une inégalité du type de Slepian et Gordon sur les processus gaussiens. Israel J. Math. 55 109-110. · Zbl 0611.60034 · doi:10.1007/BF02772698 |
| [74] | KRZAKALA, F., MANOEL, A., TRAMEL, E. W. and ZDEBOROVÁ, L. (2014). Variational free energies for compressed sensing. In 2014 IEEE International Symposium on Information Theory 1499-1503. IEEE, New York. |
| [75] | KRZAKALA, F., XU, J. and ZDEBOROVÁ, L. (2016). Mutual information in rank-one matrix estimation. In 2016 IEEE Information Theory Workshop (ITW) 71-75. IEEE, New York. |
| [76] | Lelarge, M. and Miolane, L. (2019). Fundamental limits of symmetric low-rank matrix estimation. Probab. Theory Related Fields 173 859-929. · Zbl 1411.60014 · doi:10.1007/s00440-018-0845-x |
| [77] | LESIEUR, T., KRZAKALA, F. and ZDEBOROVÁ, L. (2015). Phase transitions in sparse PCA. In 2015 IEEE International Symposium on Information Theory (ISIT) 1635-1639. IEEE, New York. |
| [78] | LI, G. and WEI, Y. (2022). A non-asymptotic framework for approximate message passing in spiked models. Preprint. Available at arXiv:2208.03313. |
| [79] | LIANG, P., PETROV, S., JORDAN, M. I. and KLEIN, D. (2007). The infinite PCFG using hierarchical Dirichlet processes. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL) 688-697. |
| [80] | LU, H., FREUND, R. M. and NESTEROV, Y. (2018). Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28 333-354. · Zbl 1392.90090 · doi:10.1137/16M1099546 |
| [81] | MAILLARD, A., AROUS, G. B. and BIROLI, G. (2020). Landscape complexity for the empirical risk of generalized linear models. In Mathematical and Scientific Machine Learning 287-327. PMLR. |
| [82] | Mei, S., Bai, Y. and Montanari, A. (2018). The landscape of empirical risk for nonconvex losses. Ann. Statist. 46 2747-2774. · Zbl 1409.62117 · doi:10.1214/17-AOS1637 |
| [83] | MINKA, T., WINN, J., GUIVER, J., WEBSTER, S., ZAYKOV, Y., YANGEL, B., SPENGLER, A. and BRONSKILL, J. (2014). Infer NET 2.6. Microsoft Research Cambridge. Available at http://research.microsoft.com/infernet. |
| [84] | MINKA, T. P. (2001). A family of algorithms for approximate Bayesian inference, PhD thesis, Massachusetts Institute of Technology. |
| [85] | MIOLANE, L. and MONTANARI, A. (2021). The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning. Ann. Statist. 49 2313-2335. · Zbl 1480.62145 · doi:10.1214/20-aos2038 |
| [86] | MONTANARI, A. (2012). Graphical models concepts in compressed sensing. In Compressed Sensing 394-438. Cambridge Univ. Press, Cambridge. · doi:10.1017/CBO9780511794308.010 |
| [87] | MONTANARI, A. and NGUYEN, P.-M. (2017). Universality of the elastic net error. In 2017 IEEE International Symposium on Information Theory (ISIT) 2338-2342. IEEE, New York. |
| [88] | Montanari, A. and Richard, E. (2016). Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Trans. Inf. Theory 62 1458-1484. · Zbl 1359.62224 · doi:10.1109/TIT.2015.2457942 |
| [89] | MONTANARI, A. and SAEED, B. (2022). Universality of empirical risk minimization. Preprint. Available at arXiv:2202.08832. |
| [90] | Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing 814-827. ACM, New York. · Zbl 1376.90043 · doi:10.1145/2897518.2897548 |
| [91] | MONTANARI, A. and VENKATARAMANAN, R. (2021). Estimation of low-rank matrices via approximate message passing. Ann. Statist. 49 321-345. · Zbl 1461.62070 · doi:10.1214/20-AOS1958 |
| [92] | MUKHERJEE, S. S., SARKAR, P., WANG, Y. and YAN, B. (2018). Mean field for the stochastic blockmodel: Optimization landscape and convergence issues. Adv. Neural Inf. Process. Syst. 31. |
| [93] | NEMIROVSKY, A. S. and YUDIN, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York. · Zbl 0501.90062 |
| [94] | OYMAK, S., THRAMPOULIDIS, C. and HASSIBI, B. (2013). The squared-error of generalized lasso: A precise analysis. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) 1002-1009. IEEE, New York. |
| [95] | PEARL, J. (1982). Reverend Bayes on inference engines: A distributed hierarchical approach. In Proceedings of the Second AAAI Conference on Artificial Intelligence 133-136. |
| [96] | Péché, S. (2006). The largest eigenvalue of small rank perturbations of Hermitian random matrices. Probab. Theory Related Fields 134 127-173. · Zbl 1088.15025 · doi:10.1007/s00440-005-0466-z |
| [97] | PLEFKA, T. (1982). Convergence condition of the TAP equation for the infinite-ranged Ising spin glass model. J. Phys. A 15 1971-1978. |
| [98] | PLUMMER, S., PATI, D. and BHATTACHARYA, A. (2020). Dynamics of coordinate ascent variational inference: A case study in 2D Ising models. Entropy 22 Paper No. 1263, 33 pp. · doi:10.3390/e22111263 |
| [99] | QIU, J. and SEN, S. (2022). The TAP free energy for high-dimensional linear regression. Preprint. Available at arXiv:2203.07539. |
| [100] | RAJ, A., STEPHENS, M. and PRITCHARD, J. K. (2014). fastSTRUCTURE: Variational inference of population structure in large SNP data sets. Genetics 197 573-589. · doi:10.1534/genetics.114.164350 |
| [101] | RANGAN, S. (2011). Generalized approximate message passing for estimation with random linear mixing. In 2011 IEEE International Symposium on Information Theory Proceedings 2168-2172. IEEE, New York. |
| [102] | RANGAN, S. and FLETCHER, A. K. (2012). Iterative estimation of constrained rank-one matrices in noise. In 2012 IEEE International Symposium on Information Theory Proceedings 1246-1250. IEEE, New York. |
| [103] | RANGAN, S., FLETCHER, A. K., SCHNITER, P. and KAMILOV, U. S. (2017). Inference for generalized linear models via alternating directions and Bethe free energy minimization. IEEE Trans. Inf. Theory 63 676-697. · Zbl 1359.94157 · doi:10.1109/TIT.2016.2619373 |
| [104] | RANGAN, S., SCHNITER, P. and FLETCHER, A. K. (2019). Vector approximate message passing. IEEE Trans. Inf. Theory 65 6664-6684. · Zbl 1432.94036 · doi:10.1109/TIT.2019.2916359 |
| [105] | RAY, K. and SZABÓ, B. (2022). Variational Bayes for high-dimensional linear regression with sparse priors. J. Amer. Statist. Assoc. 117 1270-1281. · Zbl 1506.62341 · doi:10.1080/01621459.2020.1847121 |
| [106] | RUSH, C. and VENKATARAMANAN, R. (2016). Finite-sample analysis of approximate message passing. In 2016 IEEE International Symposium on Information Theory (ISIT) 755-759. · Zbl 1432.62017 · doi:10.1109/ISIT.2016.7541400 |
| [107] | RUSH, C. and VENKATARAMANAN, R. (2018). Finite sample analysis of approximate message passing algorithms. IEEE Trans. Inf. Theory 64 7264-7286. · Zbl 1432.62017 · doi:10.1109/TIT.2018.2816681 |
| [108] | SAADE, A., KRZAKALA, F. and ZDEBOROVÁ, L. (2014). Spectral clustering of graphs with the Bethe Hessian. In Neural Information Processing Systems. |
| [109] | Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal. 30 20-36. · Zbl 1206.90116 · doi:10.1016/j.acha.2010.02.001 |
| [110] | Slepian, D. (1962). The one-sided barrier problem for Gaussian noise. Bell Syst. Tech. J. 41 463-501. · doi:10.1002/j.1538-7305.1962.tb02419.x |
| [111] | Stojnic, M. (2013). A framework to characterize performance of lasso algorithms. Preprint. Available at arXiv:1303.7291. |
| [112] | SUBAG, E. (2017). The complexity of spherical \(p\)-spin models—A second moment approach. Ann. Probab. 45 3385-3450. · Zbl 1417.60029 · doi:10.1214/16-AOP1139 |
| [113] | SUBAG, E. (2021). The free energy of spherical pure \(p\)-spin models—Computation from the TAP approach. Preprint. Available at arXiv:2101.04352. · Zbl 1517.82043 |
| [114] | SUDAKOV, V. N. (1971). Gaussian random processes, and measures of solid angles in Hilbert space. Dokl. Akad. Nauk SSSR 197 43-45. · Zbl 0231.60025 |
| [115] | SUDAKOV, V. N. (1979). Geometric problems in the theory of infinite-dimensional probability distributions. Proc. Steklov Inst. Math. 2 i-v, 1-178. Cover to cover translation of Trudy Mat. Inst. Steklov 141 (1976). · Zbl 0409.60005 |
| [116] | SUN, J., QU, Q. and WRIGHT, J. (2018). A geometric analysis of phase retrieval. Found. Comput. Math. 18 1131-1198. · Zbl 1401.94049 · doi:10.1007/s10208-017-9365-9 |
| [117] | Talagrand, M. (2011). Mean Field Models for Spin Glasses. Volume I: Basic Examples. Ergebnisse der Mathematik und Ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics] 54. Springer, Berlin. · Zbl 1214.82002 · doi:10.1007/978-3-642-15202-3 |
| [118] | THOULESS, D. J., ANDERSON, P. W. and PALMER, R. G. (1977). Solution of ‘Solvable model of a spin glass’. Philos. Mag. 35 593-601. · doi:10.1080/14786437708235992 |
| [119] | THRAMPOULIDIS, C., OYMAK, S. and HASSIBI, B. (2015). Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory 1683-1709. PMLR. |
| [120] | TRAN, D., KUCUKELBIR, A., DIENG, A. B., RUDOLPH, M., LIANG, D. and BLEI, D. M. (2016). Edward: A library for probabilistic modeling, inference, and criticism. Preprint. Available at arXiv:1610.09787. |
| [121] | WAINWRIGHT, M. J. and JORDAN, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference. Now Publishers, Hanover. · Zbl 1193.62107 |
| [122] | WANG, T., ZHONG, X. and FAN, Z. (2022). Universality of approximate message passing algorithms and tensor networks. Preprint. Available at arXiv:2206.13037. |
| [123] | Wang, Y. and Blei, D. M. (2019). Frequentist consistency of variational Bayes. J. Amer. Statist. Assoc. 114 1147-1161. · Zbl 1428.62119 · doi:10.1080/01621459.2018.1473776 |
| [124] | Yan, J. (2020). Nonlinear large deviations: Beyond the hypercube. Ann. Appl. Probab. 30 812-846. · Zbl 1464.60026 · doi:10.1214/19-AAP1516 |
| [125] | YANG, Y., PATI, D. and BHATTACHARYA, A. (2020). \(α\)-variational inference with statistical guarantees. Ann. Statist. 48 886-905. · Zbl 1450.62031 · doi:10.1214/19-AOS1827 |
| [126] | YEDIDIA, J. S., FREEMAN, W. T. and WEISS, Y. (2003). Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium 8 236-239. |
| [127] | Zhang, A. Y. and Zhou, H. H. (2020). Theoretical and computational guarantees of mean field variational inference for community detection. Ann. Statist. 48 2575-2598. · Zbl 1462.62221 · doi:10.1214/19-AOS1898 |
| [128] | ZHANG, F. and GAO, C. (2020). Convergence rates of variational posterior distributions. Ann. Statist. 48 2180-2207 · Zbl 1471.62243 · doi:10.1214/19-AOS1883 |
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.
