The overlap gap property: A topological barrier to optimizing over random structures
<jats:p> The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures, finding optimal solutions by means of fast algorithms is not know...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Proceedings of the National Academy of Sciences
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144131 |
| _version_ | 1826197243253751808 |
|---|---|
| author | Gamarnik, David |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Gamarnik, David |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | <jats:p>
The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures, finding optimal solutions by means of fast algorithms is not known and often is believed not to be possible. At the same time, the formal hardness of these problems in the form of the complexity-theoretic
<jats:italic>NP</jats:italic>
-hardness is lacking. A new approach for algorithmic intractability in random structures is described in this article, which is based on the topological disconnectivity property of the set of pairwise distances of near-optimal solutions, called the Overlap Gap Property. The article demonstrates how this property 1) emerges in most models known to exhibit an apparent algorithmic hardness; 2) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, 3) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms that exhibit the input stability (insensitivity).
</jats:p> |
| first_indexed | 2024-09-23T10:44:43Z |
| format | Article |
| id | mit-1721.1/144131 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:44:43Z |
| publishDate | 2022 |
| publisher | Proceedings of the National Academy of Sciences |
| record_format | dspace |
| spelling | mit-1721.1/1441312023-04-18T20:12:53Z The overlap gap property: A topological barrier to optimizing over random structures Gamarnik, David Massachusetts Institute of Technology. Operations Research Center Sloan School of Management <jats:p> The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures, finding optimal solutions by means of fast algorithms is not known and often is believed not to be possible. At the same time, the formal hardness of these problems in the form of the complexity-theoretic <jats:italic>NP</jats:italic> -hardness is lacking. A new approach for algorithmic intractability in random structures is described in this article, which is based on the topological disconnectivity property of the set of pairwise distances of near-optimal solutions, called the Overlap Gap Property. The article demonstrates how this property 1) emerges in most models known to exhibit an apparent algorithmic hardness; 2) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, 3) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms that exhibit the input stability (insensitivity). </jats:p> 2022-07-29T16:12:00Z 2022-07-29T16:12:00Z 2021 2022-07-29T16:07:52Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/144131 Gamarnik, David. 2021. "The overlap gap property: A topological barrier to optimizing over random structures." Proceedings of the National Academy of Sciences of the United States of America, 118 (41). en 10.1073/PNAS.2108492118 Proceedings of the National Academy of Sciences of the United States of America Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Proceedings of the National Academy of Sciences PNAS |
| spellingShingle | Gamarnik, David The overlap gap property: A topological barrier to optimizing over random structures |
| title | The overlap gap property: A topological barrier to optimizing over random structures |
| title_full | The overlap gap property: A topological barrier to optimizing over random structures |
| title_fullStr | The overlap gap property: A topological barrier to optimizing over random structures |
| title_full_unstemmed | The overlap gap property: A topological barrier to optimizing over random structures |
| title_short | The overlap gap property: A topological barrier to optimizing over random structures |
| title_sort | overlap gap property a topological barrier to optimizing over random structures |
| url | https://hdl.handle.net/1721.1/144131 |
| work_keys_str_mv | AT gamarnikdavid theoverlapgappropertyatopologicalbarriertooptimizingoverrandomstructures AT gamarnikdavid overlapgappropertyatopologicalbarriertooptimizingoverrandomstructures |