Show simple item record

dc.contributor.author
Ding, Jingqiu
dc.contributor.author
d'Orsi, Tommaso
dc.contributor.author
Nasser, Rajai
dc.contributor.author
Steurer, David
dc.date.accessioned
2022-08-04T07:28:15Z
dc.date.available
2022-08-04T07:28:15Z
dc.date.issued
2022
dc.identifier.isbn
978-1-6654-2055-6
en_US
dc.identifier.isbn
978-1-6654-2056-3
en_US
dc.identifier.other
10.1109/FOCS52979.2021.00046
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/561859
dc.description.abstract
We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms for the vanilla version of the stochastic block model. In this sense, our results show that there is no price of robustness in the stochastic block model. Our work is heavily inspired by recent work of Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient algorithm for the corresponding distinguishing problem. Our algorithm and its analysis significantly depart from previous ones for robust recovery. A key challenge is the peculiar optimization landscape underlying our algorithm: The planted partition may be far from optimal in the sense that completely unrelated solutions could achieve the same objective value. This phenomenon is related to the push-out effect at the BBP phase transition for PCA. To the best of our knowledge, our algorithm is the first to achieve robust recovery in the presense of such a push-out effect in a non-asymptotic setting. Our algorithm is an instantiation of a framework based on convex optimization (related to but distinct from sum-of-squares), which may be useful for other robust matrix estimation problems. A by-product of our analysis is a general technique that boosts the probability of success (over the randomness of the input) of an arbitrary robust weak-recovery algorithm from constant (or slowly vanishing) probability to exponentially high probability.
en_US
dc.language.iso
en
en_US
dc.publisher
IEEE
en_US
dc.subject
stochastic block model
en_US
dc.subject
robust algorithms
en_US
dc.subject
robust recovery
en_US
dc.subject
convex optimization
en_US
dc.subject
semidefinite programming
en_US
dc.title
Robust recovery for stochastic block models
en_US
dc.type
Conference Paper
dc.date.published
2022-03-04
ethz.book.title
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
en_US
ethz.pages.start
387
en_US
ethz.pages.end
394
en_US
ethz.event
62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021)
en_US
ethz.event.location
Denver, CO, USA
en_US
ethz.event.date
February 7-10, 2021
en_US
ethz.notes
Conference lecture on February 8, 2022.
en_US
ethz.grant
Unified Theory of Efficient Optimization and Estimation
en_US
ethz.identifier.wos
ethz.publication.place
Piscataway, NJ
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09622 - Steurer, David / Steurer, David
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09622 - Steurer, David / Steurer, David
en_US
ethz.grant.agreementno
815464
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
H2020
ethz.relation.isNewVersionOf
20.500.11850/521854
ethz.date.deposited
2021-12-20T12:09:38Z
ethz.source
WOS
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2022-08-04T07:28:26Z
ethz.rosetta.lastUpdated
2024-02-02T17:47:20Z
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/555890
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/521493
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Robust%20recovery%20for%20stochastic%20block%20models&rft.date=2022&rft.spage=387&rft.epage=394&rft.au=Ding,%20Jingqiu&d'Orsi,%20Tommaso&Nasser,%20Rajai&Steurer,%20David&rft.isbn=978-1-6654-2055-6&978-1-6654-2056-3&rft.genre=proceeding&rft_id=info:doi/10.1109/FOCS52979.2021.00046&rft.btitle=2021%20IEEE%2062nd%20Annual%20Symposium%20on%20Foundations%20of%20Computer%20Science%20(FOCS)
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record