{"data":{"id":"10.48550/arxiv.1807.01296","type":"dois","attributes":{"doi":"10.48550/arxiv.1807.01296","prefix":"10.48550","suffix":"arxiv.1807.01296","identifiers":[{"identifier":"1807.01296","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1807.01296"}],"creators":[{"name":"Antenucci, Fabrizio","nameType":"Personal","givenName":"Fabrizio","familyName":"Antenucci","affiliation":[],"nameIdentifiers":[]},{"name":"Krzakala, Florent","nameType":"Personal","givenName":"Florent","familyName":"Krzakala","affiliation":[],"nameIdentifiers":[]},{"name":"Urbani, Pierfrancesco","nameType":"Personal","givenName":"Pierfrancesco","familyName":"Urbani","affiliation":[],"nameIdentifiers":[]},{"name":"Zdeborová, Lenka","nameType":"Personal","givenName":"Lenka","familyName":"Zdeborová","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Approximate Survey Propagation for Statistical Inference"}],"publisher":"arXiv","container":{},"publicationYear":2018,"subjects":[{"lang":"en","subject":"Disordered Systems and Neural Networks (cond-mat.dis-nn)","subjectScheme":"arXiv"},{"lang":"en","subject":"Statistical Mechanics (cond-mat.stat-mech)","subjectScheme":"arXiv"},{"lang":"en","subject":"Information Theory (cs.IT)","subjectScheme":"arXiv"},{"lang":"en","subject":"Statistics Theory (math.ST)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (stat.ML)","subjectScheme":"arXiv"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2018-07-03T17:28:01Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2019-02-07T01:19:26Z","dateType":"Updated","dateInformation":"v1"},{"date":"2018-07","dateType":"Available","dateInformation":"v1"},{"date":"2018","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1088/1742-5468/aafa7d","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition $M=Q\u0026gt;0$ is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure.","descriptionType":"Abstract"},{"description":"37 pages, 14 figures","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xODA3LjAxMjk2PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTgwNy4wMTI5NjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5BbnRlbnVjY2ksIEZhYnJpemlvPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5GYWJyaXppbzwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5BbnRlbnVjY2k8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+S3J6YWthbGEsIEZsb3JlbnQ8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkZsb3JlbnQ8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+S3J6YWthbGE8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+VXJiYW5pLCBQaWVyZnJhbmNlc2NvPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5QaWVyZnJhbmNlc2NvPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlVyYmFuaTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5aZGVib3JvdsOhLCBMZW5rYTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+TGVua2E8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+WmRlYm9yb3bDoTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QXBwcm94aW1hdGUgU3VydmV5IFByb3BhZ2F0aW9uIGZvciBTdGF0aXN0aWNhbCBJbmZlcmVuY2U8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTg8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5EaXNvcmRlcmVkIFN5c3RlbXMgYW5kIE5ldXJhbCBOZXR3b3JrcyAoY29uZC1tYXQuZGlzLW5uKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPlN0YXRpc3RpY2FsIE1lY2hhbmljcyAoY29uZC1tYXQuc3RhdC1tZWNoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkluZm9ybWF0aW9uIFRoZW9yeSAoY3MuSVQpPC9zdWJqZWN0PgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+U3RhdGlzdGljcyBUaGVvcnkgKG1hdGguU1QpPC9zdWJqZWN0PgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+TWFjaGluZSBMZWFybmluZyAoc3RhdC5NTCk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBQaHlzaWNhbCBzY2llbmNlczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOC0wNy0wM1QxNzoyODowMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOS0wMi0wN1QwMToxOToyNlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE4LTA3PC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJUZXh0Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHJlbGF0ZWRJZGVudGlmaWVycz4KICAgIDxyZWxhdGVkSWRlbnRpZmllciByZWxhdGVkSWRlbnRpZmllclR5cGU9IkRPSSIgcmVsYXRpb25UeXBlPSJJc1ZlcnNpb25PZiI+MTAuMTA4OC8xNzQyLTU0NjgvYWFmYTdkPC9yZWxhdGVkSWRlbnRpZmllcj4KICA8L3JlbGF0ZWRJZGVudGlmaWVycz4KICA8dmVyc2lvbj4xPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9hcnhpdi5vcmcvbGljZW5zZXMvbm9uZXhjbHVzaXZlLWRpc3RyaWIvMS4wLyI+YXJYaXYub3JnIHBlcnBldHVhbCwgbm9uLWV4Y2x1c2l2ZSBsaWNlbnNlPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+QXBwcm94aW1hdGUgbWVzc2FnZSBwYXNzaW5nIGFsZ29yaXRobSBlbmpveWVkIGNvbnNpZGVyYWJsZSBhdHRlbnRpb24gaW4gdGhlIGxhc3QgZGVjYWRlLiBJbiB0aGlzIHBhcGVyIHdlIGludHJvZHVjZSBhIHZhcmlhbnQgb2YgdGhlIEFNUCBhbGdvcml0aG0gdGhhdCB0YWtlcyBpbnRvIGFjY291bnQgZ2xhc3N5IG5hdHVyZSBvZiB0aGUgc3lzdGVtIHVuZGVyIGNvbnNpZGVyYXRpb24uIFdlIGNvaW4gdGhpcyBhbGdvcml0aG0gYXMgdGhlIGFwcHJveGltYXRlIHN1cnZleSBwcm9wYWdhdGlvbiAoQVNQKSBhbmQgZGVyaXZlIGl0IGZvciBhIGNsYXNzIG9mIGxvdy1yYW5rIG1hdHJpeCBlc3RpbWF0aW9uIHByb2JsZW1zLiBXZSBkZXJpdmUgdGhlIHN0YXRlIGV2b2x1dGlvbiBmb3IgdGhlIEFTUCBhbGdvcml0aG0gYW5kIHByb3ZlIHRoYXQgaXQgcmVwcm9kdWNlcyB0aGUgb25lLXN0ZXAgcmVwbGljYSBzeW1tZXRyeSBicmVha2luZyAoMVJTQikgZml4ZWQtcG9pbnQgZXF1YXRpb25zLCB3ZWxsLWtub3duIGluIHBoeXNpY3Mgb2YgZGlzb3JkZXJlZCBzeXN0ZW1zLiBPdXIgZGVyaXZhdGlvbiB0aHVzIGdpdmVzIGEgY29uY3JldGUgYWxnb3JpdGhtaWMgbWVhbmluZyB0byB0aGUgMVJTQiBlcXVhdGlvbnMgdGhhdCBpcyBvZiBpbmRlcGVuZGVudCBpbnRlcmVzdC4gV2UgY2hhcmFjdGVyaXplIHRoZSBwZXJmb3JtYW5jZSBvZiBBU1AgaW4gdGVybXMgb2YgY29udmVyZ2VuY2UgYW5kIG1lYW4tc3F1YXJlZCBlcnJvciBhcyBhIGZ1bmN0aW9uIG9mIHRoZSBmcmVlIFBhcmlzaSBwYXJhbWV0ZXIgcy4gV2UgY29uY2x1ZGUgdGhhdCB3aGVuIHRoZXJlIGlzIGEgbW9kZWwgbWlzbWF0Y2ggYmV0d2VlbiB0aGUgdHJ1ZSBnZW5lcmF0aXZlIG1vZGVsIGFuZCB0aGUgaW5mZXJlbmNlIG1vZGVsLCB0aGUgcGVyZm9ybWFuY2Ugb2YgQU1QIHJhcGlkbHkgZGVncmFkZXMgYm90aCBpbiB0ZXJtcyBvZiBNU0UgYW5kIG9mIGNvbnZlcmdlbmNlLCB3aGlsZSBBU1AgY29udmVyZ2VzIGluIGEgbGFyZ2VyIHJlZ2ltZSBhbmQgY2FuIHJlYWNoIGxvd2VyIGVycm9ycy4gQW1vbmcgb3RoZXIgcmVzdWx0cywgb3VyIGFuYWx5c2lzIGxlYWRzIHVzIHRvIGEgc3RyaWtpbmcgaHlwb3RoZXNpcyB0aGF0IHdoZW5ldmVyIHMgKG9yIG90aGVyIHBhcmFtZXRlcnMpIGNhbiBiZSBzZXQgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSBOaXNoaW1vcmkgY29uZGl0aW9uICRNPVEmZ3Q7MCQgaXMgcmVzdG9yZWQsIHRoZW4gdGhlIGNvcnJlc3BvbmRpbmcgYWxnb3JpdGhtIGlzIGFibGUgdG8gcmVhY2ggbWVhbi1zcXVhcmVkIGVycm9yIGFzIGxvdyBhcyB0aGUgQmF5ZXMtb3B0aW1hbCBlcnJvciBvYnRhaW5lZCB3aGVuIHRoZSBtb2RlbCBhbmQgaXRzIHBhcmFtZXRlcnMgYXJlIGtub3duIGFuZCBleGFjdGx5IG1hdGNoZWQgaW4gdGhlIGluZmVyZW5jZSBwcm9jZWR1cmUuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj4zNyBwYWdlcywgMTQgZmlndXJlczwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/1807.01296","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-01T18:53:32.000Z","registered":"2022-03-01T18:53:33.000Z","published":"2018","updated":"2022-03-01T18:53:33.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1807.01296","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}