HARDNESS OF RANDOM OPTIMIZATION PROBLEMS FOR BOOLEAN CIRCUITS, LOW-DEGREE POLYNOMIALS, AND LANGEVIN DYNAMICS

被引:2
作者
Gamarnik, David [1 ,2 ]
Jagannath, Aukosh [3 ,4 ]
Wein, Alexander S. [5 ]
机构
[1] MIT, Sloan Sch Management, Cambridge, MA 02140 USA
[2] MIT, Operat Res Ctr, Boston, MA 02140 USA
[3] Univ Waterloo, Dept Stat & Actuarial Sci, Dept Appl Math, Waterloo, ON, Canada
[4] Univ Waterloo, Cheriton Sch Comp Sci, Waterloo, ON, Canada
[5] Univ Calif Davis, Dept Math, Davis, CA 95616 USA
基金
加拿大自然科学与工程研究理事会;
关键词
spin glasses; maximum independent set; random graphs; random optimization problems; average-case hardness; Boolean circuits; low-degree methods; Langevin dynamics; overlap gap property; MESSAGE-PASSING ALGORITHMS; SPIN-GLASS; LOCAL ALGORITHMS; INDEPENDENT SETS; SPHERICAL-MODELS; COMPLEXITY; LIMITS; GAP;
D O I
10.1137/22M150263X
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising p-spin glass model and (b) finding a large independent set in a sparse ErdoH \s--Re'\nyi graph. The following families of algorithms are considered: (a) low-degree polynomials of the input---a general framework that captures many prior algorithms; (b) low-depth Boolean circuits; (c) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm. We show that these families of algorithms cannot have high success probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory (although we consider the search problem as opposed to the decision problem). Our proof uses the fact that these models are known to exhibit a variant of the overlap gap property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions whose objectives are above a certain threshold are either close to or far from each other. The crux of our proof is that the classes of algorithms we consider exhibit a form of stability (noise-insensitivity): a small perturbation of the input induces a small perturbation of the output. We show by an interpolation argument that stable algorithms cannot overcome the OGP barrier. The stability of Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials and Boolean circuits is established using tools from Gaussian and Boolean analysis-namely hypercontractivity and total influence, as well as a novel lower bound for random walks avoiding certain subsets, which we expect to be of independent interest. In the case of Boolean circuits, the result also makes use of Linial-Mansour-Nisan's classical theorem. Our techniques apply more broadly to low influence functions, and we expect that they may apply more generally.
引用
收藏
页码:1 / 46
页数:46
相关论文
共 84 条
[1]  
Achlioptas D., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P130, DOI 10.1145/1132516.1132537
[2]  
Alon N., 2004, The probabilistic method
[3]  
[Anonymous], 2003, Slow Relaxations and Nonequilibrium Dynamics in Condensed Matter, DOI [10.1007/978-3-540-44835-8, DOI 10.1007/978-3-540-44835-8]
[4]  
[Anonymous], 1976, Algorithms Complex. New Dir. Recent Results
[5]  
Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P1, DOI 10.1017/CBO9780511804090
[6]   On the energy landscape of spherical spin glasses [J].
Auffinger, Antonio ;
Chen, Wei-Kuo .
ADVANCES IN MATHEMATICS, 2018, 330 :553-588
[7]   Random matrices and complexity of spin glasses [J].
Auffinger, Antonio ;
Ben Arous, Gerard ;
Cerny, Jiri .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2013, 66 (02) :165-201
[8]   A NEARLY TIGHT SUM-OF-SQUARES LOWER BOUND FOR THE PLANTED CLIQUE PROBLEM [J].
Barak, Boaz ;
Hopkins, Samuel ;
Kelner, Jonathan ;
Kothari, Pravesh K. ;
Moitra, Ankur ;
Potechin, Aaron .
SIAM JOURNAL ON COMPUTING, 2019, 48 (02) :687-735
[9]   COMBINATORIAL APPROACH TO THE INTERPOLATION METHOD AND SCALING LIMITS IN SPARSE RANDOM GRAPHS [J].
Bayati, Mohsen ;
Gamarnik, David ;
Tetali, Prasad .
ANNALS OF PROBABILITY, 2013, 41 (06) :4080-4115
[10]  
Ben Arous G, 2001, PROBAB THEORY REL, V120, P1