Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method
Authors: Constantine Caramanis
Dimitris Fotakis
Alkis Kalavasis
Vasilis Kontonis
Christos Tzamos
Venue: NeurIPS 2023 oral (2023)
Keywords: Policy Gradient
Combinatorial Optimization
Gradient Descent
TL;DR: We theoretically study the problem of optimizing solution-samplers for combinatorial problems via gradient-based methods.

Abstract: Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network is used as a solution generator which is then trained by gradient-based methods (e.g., policy gradient) to successively obtain better solution distributions.
In this work we introduce a novel theoretical framework for analyzing the effectiveness of such methods. We ask whether there exist generative models that (i) are expressive enough to generate approximately optimal solutions; (ii) have a tractable, i.e, polynomial in the size of the input, number of parameters; (iii) their optimization landscape is benign in the sense that it does not contain sub-optimal stationary points. Our main contribution is a positive answer to this question. Our result holds for a broad class of combinatorial problems including Max- and Min-Cut, Max-$k$-CSP, Maximum-Weight-Bipartite-Matching, and the Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla gradient descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.

Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
Constantine Caramanis UT Austin & Archimedes/ / Athena RC constantineeutexxs. edu
Dimitris Fotakis
NTUA & Archimedes / Athena RC
fotakis@cs iat.aiiissnntuu..g ntua.gr
Alkis Kalavasis
Vasilis Kontonis
Yale University
UT Austin vkonton@gmail.com com
alvertos. kalarrossaallaasisllllllle.ec edu
Christos Tzamos
UOA & Archimedes Athena RC
tzamos@wisc. edu
Abstract
Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network is used as solution generator which is then trained by gradient-basee methods (e.g., policy gradient) to successively obtain better solution distributions. In this work we introduce a novel theoretical framework for analyzing the effectiveness of such methods. We ask whether there exist generative models that (i) are expressive enough to generate approximately optimal solutions; (ii) have a tractable, i.e, polynomial in the size of the input, number of parameters; (iii) their optimization landscape is benign in the sense that it does not contain sub-optimal stationary points. Our main contribution a positive answer to this question. Our result holds for a broad class of combinatorial problems including Max- and Min-Cut, Max-k-CSP, Maximum-Wan Weight- Weight-Biparttte-- Sipprttie-Matchiie Traveling Salesman Problem. As byproduct of our analysis we introduce novel regularization process over vanilla gradient descent and provide thcoretical and experimental evidence that it helps address vanishing maiisiinggrrdienl issues and escape bad stationary points.
and the
Introduction
Gradient descent has proven remarkably effective for diverse optimization problems in neural net- works. From the early days of neural networks, this has motivated their use for combinatorial optimization [HT85, Smi99, VFJ15, 16]. More recently, an approach by [BPL 16], where neural network is used to generate (sample) solutions for the combinatorial problem. The parameters of the neural network thus parameterize the space of distributions. This allows one perform gradient steps in this distribution space. In several interesting settings, including the Traveling Salesman Prob- lem, they have shown that this approach works remarkably well. Given the widespread application but also the notorious difficulty of combinatorial optimization [GLS12, PS98, S 03, Sch05, CLS -9S, approaches that provide more general solution framework are appealing.
This is the point of departure this paper. We investigate whether gradient descent can succeed in a general setting that encompasses the problems studied in [BPL*16 This requires parameterization
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of distributions over solutions with "nice" optimization landscape (intuitively, that gradient descent does not get stuck in local minima or points of vanishing gradient) and that has polynomial number of parameters. Satisfying both requirements simultaneously is non-trivial. As we show precisely below, a simple lifting to the exponential-size probability simplex on all solutions guarantees convexity; and, on the other hand, compressed parameterizations with "bad" optimization landscapes are also easy to come by (we give a natural example for Max- in Remark 1). Hence, we seek to understand the parametric complexity of gradient-based methods, i... how many parameters suffice for a benign optimization landscape in the sense that it does not contain "bad" stationary points.
We thus theoretically investigate whether there exist solution generators with tractable number of parameters that are also efficiently optimizable, i.e., gradient descent requires small number of steps to reach a netimoptimal solution. We provide a positive answer under general assumptions and specialize our results for several classes of hard and easy combinatorial optimization problems, including Max-Cut and Min-Cut, Max-k-CSP, Maximum- Seeein--eeghted-Biiie Bipartite-Matchin and Traveling Salesman. We remark that key difference between (computationally) easy and hard problems not the ability to find a compressed and efficiently optimizable generative model but rather the ability to efficiently draw samples from the parameterized distributions.
1.1 Our Framework
We introduce a theoretical framework for analyzing the effectiveness of gradient-based methods on the optimization of solution generators in combinatorial optimization, inspired by 1BPL+16].
Let be a collection of instances of combinatorial problem with common solution space S and L(;1)= S + R be the cost function associated with an instance / E I, i.e., L(s; I) is the cost of solution & given the instance I. For example, for the Max-Cut problem the collection of instances corresponds to all graphs with nodes, the solution space S consists of all subsets of nodes, and the loss L(s; I) is equal to (minus) the weight of the cut (s, [n] s) corresponding to the subset of nodes E S (our goal is to minimize L).
Definition 1 (Solution Cost Oracle), For a given instance I we assume that we have access to an oracle II; the cost of any given solution s S. i.e. O(; I) L(s; I).
The above oracle standard in combinatorial optimization and query-efficient algorithms are provided for various problems [RSW17, GPRW19, LSZ21, A PRW22]. We remark that the goal of this work is not to design algorithms that solve combinatorial problems using access to the solution cost oracle (as the aforementioned works do). This paper focuses on landscape design: the algorithm fixed, namely (stochastic) gradient descent; the question is how to design a generative model that has small number of parameters and the induced optimization landscape allows gradient- based methods to converge to the optimal solution without getting trapped at local minima or vanishing gradient points.
Let R be some prior distribution over the instance space and W be the space of parameters of the model. We now define the class of solution generators. The solution generator p(w) with parameter w E W takes as input an instance I and generates a random solution s S. To distinguish between the output, the input, and the parameter of the solution generator, we use the notation p(: I; w) to denote the distribution over solutions and p(s; I; w) to denote the probability of an individual solution W] the above parametric class of solution generators. For some parameter w, the loss corresponding to the solutions sampled by p(: I; w) is equal to
E S. We denote by P = [y(w)=
[(w)= I
[[](,)), Lr(w)=
E
[[(s; T)].
s>p((s/p))
Our goal is to optimize the parameter w E W in order to find a sampler p(:; ()w) whose loss [(w) close to the expected optimal value opt:
min L(s; 11
opt I~R
SES
The policy gradient method [Kak01] expresses the gradient of L as follows
Tn C(w) = T- s-pp s [L(;;] V,, log [;w)],
E
and updates the parameter or using the gradient descent update, Observe that a (stochastic) policy gradient update can be implemented using only access solution cost oracle of Definition 1.

---

Solution Generators. In [BPL 16] the authors used neural networks as parametric solution gen- erators for the TSP problem. They provided empirical evidence that optimizing the parameters of the neural network using the policy gradient method results to samplers that generate very good solutions for (Euclidean) TSP instances. Parameterizing the solution generators using neural networks essentially compresses the description of distributions over solutions (the full parameterization would require assigning parameter to every solution-instance pair (s, Since for most combinatorial problems the size of the solution space is exponentially large (compared to the description of the instance), it is crucial that for such methods to succeed the parameterization must be compressed in the sense that the description of the parameter space W is polynomial in the size of the description of the instance family I. Apart from having a tractable number of parameters, it is important that the optimization objective corresponding to the parametric class P can provably be optimized using some first-order method in polynomial (in the size of the input) iterations.
We collect these desiderata in the following definition. We denote by [I] the description size of I,, i.e., the number of bits required to identify any element of I. For instance, I is the space of unweighted graphs with at most nodes, [ = =nn").
Definition 2 (Complete, Compressed and Efficiently Optimizable Solution Generator). Fix a prior R over I, a family of solution generators P {p(w): : w W), a loss function C as in Equation (I) and some 0.
1. We say that P is complete if there exists some w E W such that L(w) S opt + E, where opt is defined in (2).
2. We say that P compressed if the description size of the parameter space W is polynomial in [T] and in log(1/E).
3. We say that P is efficiently optimizable if there exists a first-oreer method applied on the objective L such that after T = poly 1/e) many updates the parameter vectors, finds an (at most) e-sub-optimal vector Φū, i.e., L(σ)) S [(w)++ +
Remark 1. We remark that constructing parametric families that are complete and compressed, complete and efficiently optimizable, or compressed and efficiently optimizable (i.e., satisfying any pair of assumptions of Question I but not all 3) is usually much easier task. Consider, for example, the Max-Cut problem on a fixed (unweighted) graph with n nodes. Note that I has description size O(n²). Solutions of the Max- Cut for a graph with n nodes are represented by vertices on the binary hypercube {=1}" (coordinate dictates the side of the cut that we put node i). One may consider the full parameterization of all distributions over the hypercube. It is not hard to see that this is a complete and efficiently optimizable family (the optimization landscape corresponds to optimizing a linear objective). However, it is not compressed, since it requires 2n parameters. On the other extreme, considering product distribution over coordinates, i.e., we set the value of node i to be +1 with probability p; -1 with - P; gives a complete and compressed family. However, as we show in Appendix B, the landscape of this compressed parameterization from highly sub-optimal local minima and therefore, it is not efficiently optimizable.
Therefore, in this work we investigate whether it is possible to have all 3 desiderata of Definition 2 at the same time.
Question 1. Are there complete, compressed, and efficiently optimizable solution generators (i.e., satisfying Definition 2) for challenging combinatorial tasks?
1.2 Our Results
Our Contributions. Before we present our results formally, we summarize the contributions of this work.
Our main contribution is a positive answer (Theorem 1) to Question 1 uuderr general assumptions that capture many combinatorial tasks. We identify set of conditions (see Assumption 1) that allow us to design a family of solution generators that are complete, compressed and efficiently optimizable.
The conditions are motivated by obstacles that are important for any approach of this nature. This includes solutions that escape to infinity, and also parts of the landscape with vanishing gradient. See the discussion in Section 3 and Figure 1.
3

---

We specialize our framework to several important combinatorial problems, some of which are NP-hard, and others tractable: Max-Cut, Min-Cut, Max-k-CSP, Maximum- -Wiigtt- BipariiteMaathingg and the Traveling Salesman Problem.
Finally, we investigate experimentally the effect of the entropy regularizer and the fast/slow mixture scheme that we introduced (see Section 3) and provide evidence that it leads to better solution generators.
We begin with the formal presentation of our assumptions on the feature mappings of the instances and solutions and on the structure of cost function of the combinatorial problem.
Assumption 1 (Structured Feature Mappings). Let be the solution space and I be the instance space. There exist feature mappings Vs S - X. for the solutions, and, ΦI I Z. for the instances, where X, Z are Euclidean vector spaces of dimension n and nzz such that
1. (Bounded Feature Spaces) The feature and instance mappings are bounded, ie., there exist Ds, DI > such that [s)s())] & Ds. all s E S and [[)x(1)]22 S DI, for all 1 E I.
2. (Bilinear Cost Oracle) The cost of solution s under instance I can be expressed as bilinear function of the corresponding feature vector (bs(8) and instance vector ())( i.e the solution oracle can be expressed as (s,,1) (z Mabs(s) for any s E S.IEI, for some matrix M with || C.
3. (Variance Preserving Features) There exists a > 0 such that Var (S)) (b)) 2 aaloo12 for any X, where (S) is the uniform distribution over the solution space S.
4. (Bounded Dimensions/Diamettee
The feature dimensions nxx ,lz, and the diameter bounds Ds, DI, C are bounded above by a polynomial of the description size of the instance space I. The variance lower bound is bounded below by 1/poly([Z)
Remark 2 (Boundedness and Bilinear Cost Assumptions). We remark that Items 1, 4 are simply boundedness assumptions for the corresponding feauture mappings and usually follow easily assum- ing that we consider reasonable feature mappings. Al a high-level, the assumption that the solution is a bilinear function of the solution and instance features (Item 2) prescribes that "good" feature mappings should enable a simple (i.e., bilinear) expression for the cost function. In the sequel we see that this is satisfied by natural feature mappings for important classes of combinatorial problems.
Remark 3 (Variance Preservation Assumption). In Item 3 (variance preservation) we require that the solution feature mapping has variance along every direction, ie., the feature vectors corresponding to the solutions must be "spread-oul" when the underlying solution generator is the uniform distribution. As we show, this assumption is crucial so that the gradients of the resulting optimization objective are not-vanishing allowing for its efficient optimization.
We mention that various important combinatorial problems satisfy Assumption 1. For instance, Assumption is satisfied by Max-Cut, Min-Cut, Max-k-CSP. Maximum-Weight- Biiparite-Matchiie and Traveling Salesman. We refer the reader to the upcoming Section for an explicit description of the structured feature mappings for these problems. Having discussed Assumption 1, we are ready to state our main abstract result which resolves Question 1.
Theorem 1. Consider combinatorial problem with instance space I that satisfies Assumption 1. For any prior R over I and e > 0, there exists a family of solution generators P = {p(w) w E W) with parameter space W that is complete, compressed and, efficiently optimizable.
A sketch behind the design of the family P can be found in Section and Section 4.
Remark 4 (Computational Barriers in Sampling). We note that the families of generative models (a.k.a.. solution generators) that we provide have polynomial parameter complexity and are opti- mizable in a small number of steps using gradient- based methods. Hence, in a small number of iterations, gradient-base based methods converge to distributions whose mass is concentrated on nearly optimal solutions. This holds, as we show, even for challenging (NP-hard) combinatorial problems. Our results do not, however, prove P = NP, as it may be computationally hard to sample from our generative models. We remark that while such approaches are in theory hard, such models seem to perform remarkably well experimentally where sampling is based on Langevin dynamics techniques [SE20, SSDK+20J. Though as our theory predicts, and simulations support, landscape problems seem to be direct impediment even to obtain good approximate solutions.
4

---

Remark 5 (Neural Networks as Solution Samplers), A natural question would be whether our results can be extended to the case where neural networks are (efficient) solution samplers, as [BPL" 16). Unfortunatel, a benign landscape result for neural network solution generators most likely cannot exist. It is well-known that end-to-end theoretical guarantees for training neural networks are out of reach since the corresponding optimization tasks are provably computationally intractable, see, e.g., [CGKM22] and the references therein.
Given combinatorial problem, Assumption 1 essentially asks for the design of feature mappings for the solutions and the instances that satisfy desiderata such boundedness and variance preservation. Max-Cut, Min-Cut, TSP and Max-k-CSP and other problems satisfy Assumption because we managed to design appropriate (problem-specifie) feature mappings that satisfy the requirements of Assumption 1. There are interesting combinatorial problems for which we do not know how to design such good feature mappings. For instance, the "natural" feature mapping for the Satisfiability problem (SAT) (similar to the one we used for Max-k-CSPs) would require feature dimension exponential in the size of the instance (we need all possible monomials of n variables and degree at most n) and therefore, would violate Item 4 of Assumption 1.
Finally, we would like mention an interesting aspect of Assumption 1.
1.3 Related Work
Neural Combinatorial Optimization. Tackling combinatorial optimization problems constitutes one of the most fundamental tasks of theoretical computer science [GLS12, PS98, S+03, Sch05, CL5+ and various approaches have been studied for these problems such as local search methods, branch-and-bound algorithms and heuristtss such genetic algorithms and simulated annealing. Starting from the seminal work of [HT85], researchers apply neural networks [Smi99, VFJ15, BPL+16] to solve combinatorial optimization tasks. In particular, researchers have explored the power of machine learning, reinforcement learning and deep learning methods for solving combinatorial optimization problems [BPL* * 16, YW20, LZ09, DCL 18, BLP21, MSIB21, NOST18, SHM + 16, MKS 13, SSS 17, ER18, K8 ZCH 20, CCK 21, MGH 19, GCF+ 19, KLMS19].
The use of neural networks in combinatorial problems is extensive [SLB 18, JLB19, GCF+ 19, YGS20, MSIB21, BPI,+16, KDZ+ 17, YP19, CT19, YBV19, KCK+20, KCY+21, DAT20, N1,+ TRWG21, AMW18, 8,, KL20, Jeg22, SBK22, ART23] and various papers aim to understand the the- oretical ability of neural networks to solve such problems [HS23b, HS23a, Gam23]. Our paper builds on the framework of the influential experimental work of [BPL 16] to tackle combinatorial optimization problems such as TSP using neural networks and reinforcement learning. [KP+21] an entropy maximization scheme in order to generate diversified candidate solutions. This experimental heuristic is quite close to our theoretical idea for entropy regularization. In our work, entropy regularization allows to design quasar conver landscapes and the fast/slow mixing scheme to obtain diversification of solutions. Among other related applied works, [KCK+20, KPP22] study the use of Transformer architectures combined with the Reinforce algorithm employing symmetries (i.e., the existence of multiple optimal solutions of a CO problem) improving the generalization capability of Deep RL NCO and [MLC+2I] studies Transformer architectures and aims learn improvement heuristics for routing problems using RL.
Gradient Descent Dynamics. Our work provides theoretical understanding on the gradient-descent landscape arising in NCO problems. Similar questions regarding the dynamics of gradient descent have been studied in prior work concerning neural networks; for instance, [AS20] and [AKM fix the algorithm (SGD on neural networks) and aim to understand the power of this approach (which function classes can be learned). Various other works study gradient descent dynamics in neural networks. We refer to [AS18, AS20, ABAB+21 21, MYSSS21, BEG+22, DLS22, ABA22, AAM22, BBSS22, ABAM23, AKM+21, EGK+ (GGK+23) 23] (and the references therein) for a small sample of this line of research.
2 Combinatorial Applications
We now consider concrete combinatorial problems and show that there exist appropriate and natural feature mappings for the solutions and instances that satisfy Assumption 1; so Theorem is applicable for any such combinatorial task. For more detailed treatment, we refer to Appendix G.
5

---

Min-Cut and Max-Cut. Min-Cut (resp. Max-Cut) are central graph combinatorial problems where the task is to split the nodes of the graph in two subsets so that the number of edges from one subset to the other (edges of the cut) is minimized (resp. maximized). Given a graph G with n nodes represented by its Laplacian matrix L = D A, where D is the diagonal degree matrix and A is the adjacency matrix of the graph, the goal in the Min-Cut (resp. Max-Cut) problem is to find a solution vector s E {+1]" so that 8 LGs/4 is minimized (resp. maximized).
We first show that there exist natural feature mappings so that the cost of every solution s under any instance/graph G is a bilinear function of the feature vectors, see Item of Assumption 1. We consider the correlation-base feature mapping (s) = (ss J' E R² where by (.)o we denote the vectoriiaation/llatten (Lo)² F= Then simply setting the matrix M be the identity I E I= xn= the cost of any solution s can be expressed as the bilinear function ('r (ús(s) We observe that for (unweighted) graphs with nodes the description size of the family of all instances is roughly (n²), and therefore the dimensions of the feature mappings Vss tir are clearly polynomial in the description size of I. Moreover, considering unweighted graphs, it holds that (G)x()) (s)s(s) lla | S poly(n). Therefore, the constants Ds, DI, C are polynomial in the description size of the instance family.
operation and the Laplacian for the instance (graph), (G)
=s (ss)) LGs.
It remains show that our solution feature mapping satisfies the variance preservation assumption, i.e,, Item in Assumption 1. A uniformly random solution vector E {+1]" is sampled by setting each 8; with probability 1/2 independently. In that case, we have Elu- æ] O and therefore Var(v x)- = E((v
E((u-z)² -) Enjj jej fiu, E|m,ay] Σ; r. = ||0|22 since, by the independence of Li,Tj the cross-terms of the sum vanish. We observe that the same hold true for the Max-Cut problem and therefore, structured feature mappings exist for Max-Cut as well (where L(s; G) = -s" LG We shortly mention that there also exist structured feature mappings for Max-k-CSP. We refer to Theorem for further details.
Remark 6 (Partial Instance Informatiion/nstaacc Context). We remark that Assumption I allows for the "instance" " I to only contain partial information about the actual cost function. For example, consider the setting where each sampled instance is an unweighted graph G but the cost oracle takes the form O(G,s) s) (Lc)' M (ss" Y' for a matrix Maj = a; when i = j and Mij = 0 otherwise. This cost function models having a unknown weight function, i.e., the weight of edge i of G is a, if edge i exists in the observed instance G, on the edges of the observed unweighted graph G, that the algorithm has to learn in order to be able to find the minimum or maximum cut. For simplicity, in what follows, we will continue referring to I as the instance even though it may only contain partial information about the cost function of the underlying combinatorial problem.
Beximum--eeigh-Bieee Stipartite-Matching and TSP. The Maximum- Maximum-Weight-ii Weight-Bipartie--Me Biachitt--Matchinn (MWBP) problem is another graph problem that, given a bipartite graph G with nodes and m edges, asks for the maximum-weight matching. The feature vector corresponding to a matching can be represented as binary matrix R E 1)xm with Σ, R,g = for all and Ray = I for all j. i.e., R is a permutation matrix. Therefore, for a candidate matching s, we set (s) to be the matrix R defined above. Moreover, the feature vector of the graph is the (negative flattened) adjacency matrix E The cost oracle is then L(R; E) = Σ Esy R.j perhaps for an unknown weight matrix M,, (see Remark 6). For the Traveling Salesman Problem (TSP) the feature vector is again a matrix R with the additional constraint that R has represent a single cycle (a tour over all cities). The cost function for TSP is again L(R; E)- = Eij Ei MiyRis One can check that those representations of the instance and solution satisfy the assumptions of Items and 4. Showing that the variance of those representations has polynomial lower bound is more subtle and we refer the reader to the Supplementary Material.
We shortly mention that the solution generators for Min-Cut and Maximum-Weis Weight-Bipartii Matching are also efficiently samplable.
3 Optimization Landscape
Exponential Families as Solution Generators. A natural candidate to construct our family of solution generators to consider the distribution that assigns to each solution s E and instance E I mass proportional to its score exp(-TL(s; [)) exp(-rύz(I) My)s(s) exp(-rz" Mx)

---

Figure 1: In the left plot, we show the landscape of the "vanilla" objective of (1) for the feature domain X = [(1, 0), (2, (0,2) and linear cost oracle c for e = (-3, 3). We see that the "vanilla" objective minimized at the direction of -c, i.c., along the direction 7 r11, for + +.c. We observe the two issues described in Section 3, i.c., that the true minimizer is point infinity, and that gradients vanish so gradient deseent may get trapped in sub-optimal solutions, (c.g., in the upper-right corner initialized the top corner). In the middle plot, we show the landscape of the entropy-regularian finite and brings it closer to the origin. Observe that even if a gradient iteration is initialized in the top corner it will eventually converge to the minimizer; however the rate of convergence may be very slow. The right plot corresponds to loss objective where we combine a mixture of exponential families as solution generator, as Eq,(5), and the entropy regularization approach. We observe that we are able to obtain benign (quasar- landscape via the entropy regularization while the mixture-generator generator guarantees non- vanishing gradients.
objective of (3) that makes the minimizer
for some "temperature" parameter т, where ur and ays are the feature mappings promised to exist due to Assumption 1, z = (1), and, x = (s)) Note that as long as + +o0, this distribution tends to concentrate on solutions that achieve small loss.
Remark To construct the above solution sampler one could artificially query specific solutions to the cost oracle of Definition and try to learn the cost matrix M. However, we remark that our goal (see Definition 2) is to show that we can train a parametric family via gradient-base methods so that it generates (approxinately) optimal solutions and not to simply learn the cost matrix M via some other method and then use to generate good solutions.
Obstacle I:
Minimizers at Infinity. One could naturally consider the parametric family ((x; 2; W) ox exp(= [op==WWa) Wx)) (note that with W -,, we recover the distribution of the previous paragraph) and try perform gradient-bass based methods the loss (recall that L(x; 2) = 2 Mx))
((W)
= E Z~R (~)((;;WW)
Mx).
(1)
The question is whether gradient updates on the parameter W eventually converge to a matrix W whose associated distribution o(W) generates near-optimal solutions (note that the matrix -TM with r + +oo is such a solution). After computing the gradient of L, we observe that
Vw L(W) M Var 2R
Ma) 2 0,
where the inner product between two matrices A - B is the trace Tr(A B) = =i, A.g This means that the gradient field of L always has a contribution to the direction of M. Nevertheless the actual minimizer at infinity, i.c., it corresponds to the point W = --M when t + +oc. While the correlation with the optimal point is positive (which is encouraging), having such contribution to this direction is not sufficient condition for actually reaching W. The objective has vanishing gradients infinity and gradient descent may get trapped sub-optimal stationary points, see the left plot in Figure 1.
Solution I: Quasar Convexity via Entropy Regularization. Our plan is try and make the objective landscape more benign by adding an antropy-regularie objective convex (which may be too much ask in the first place) we are able obtain much better landscape with finite global minimizer and a gradient field that guides gradient descent to the minimizer: Those properties are described by the so-called class of "quasar-convex" functions. Quasar convexity (or weak quasi-convexity [HMR 16]) is a well-studied notion in optimization [HMR16 16, HSS20, LV16, ZMB 17, HLSS15] and can be considered as a high-dimensional generalization of unimodality.
Instead of trying to make the
We note that we overload the notation and assume that our distributions generate directly the featurizations (resp. I) of I (resp. s).
7

---

Definition 3 (Quasar Convexity THMR16, HSS20). Letry E (0, 1] and let E be minimizer of the differentiable function f IR" R. The function f is n-quusar-convve with respect to on domain D S Te for all x E D, Vf(x) (a x) 2 (J(()) - [(z)).
In the above definition, notice that the main property that need to establish is that the gradient field of our objective correlates positively with the direction W - W, where W is its minimizer. We denote by : W - R. the negative entropy of ((W), i.e.
H(W)
= E E 2~R x~0((;;;W)
[lo o();; W)];
and consider the regularized objective
(W) = L(W) + AH(W),
(3)
for some À > O. We show (follows from Lemma 4) that the gradient- field of the regularized objective indeed "points" towards a finite minimizer (the matrix W = M/A)):
V Vw VW)) (W+ +M/A)
Varlz] (W + M//Axx] 20,
(4)
where the randomness over ~ R, 2(:;;; W). Observe that now the minimizer of Cx is the point -M/A, /A, which for À = poly(e, a, 1/s. 1/Dr) (these are the parameters of Assumption 1) is promised to yield solution sampler that generates e-sub-optimal solutions (see also Proposition 2 and Appendix C). Having the property of Equation (4) suffices for showing that a gradient descent iteration (with an appropriately small step-size) will eventually converge to the minimizer.
Obstacle I: Vanishing Gradients. While we have established that the gradient field of the regularized objective "points" towards the right direction, the regularized objective still suffers from vanishing gradients, see the middle plot in Figure 1. In other words, ? in the definition of quasar convexity (Definition 3) may be exponentially small, as it is proportional to the variance of the random variable z (W + M/A)z, see Equation (4). As we see in the middle plot of Figure the main issue is the vanishing gradient when W gets closer to the minimizer -M/A (towards the front-corner). For simplicity, consider the variance along the direction of W. i.e., Varlz (ifzzTWa) xr] and recall that æ is generated by the density exp(= ( T W Wx)/(Exe exp(2 T Wx)). When || 12 + +oo we observe that the value z Wr x concentrates exponentially fast to m 2 2T WW (think of the convergence of the soft-max to the max function). Therefore, the variance Varlz Wa] may vanish exponentially fast making the convergence of gradient descent slow.
Solution II: Non- Non-Vanishing Gradients via Fast/Slow Mixture Generators. We propose fix to the vanishing gradients issue by using a mixture of exponential families as a solution generator. We define the family of solution generators P (p(W): W E W) to be
(5) for a (fixed) mixing parameter 3* and a (fixed) temperature parameter p². The main idea is to have the first component of the mixture converge fast to the optimal solution (to - M/A) while the second "slow" component that has parameter " stays closer to the uniform distribution over solutions that guarantees non-trivial variance (and therefore non-vanishing gradients).
P = {(1 8 (o() 3 ((p W): W EW).
More precisely, taking p² to be sufficiently small, the distribution <(p"W) is almost uniform over the solution space (S). Therefore, in Equation (4), the almost uniform distribution component of the mixture will add to the variance and allow us to show a lower bound. This is where Item of Assumption comes into play and gives the desired non-trivial variance lower bound under the uniform distribution. We view this fast/slow mixture technique as an interesting insight of our work: use the "fast" component (the with parameter W) to actually reach the optimal solution ~ and and we use the "slow" component (the one with parameter p W that essentially generates random solutions) to preserve non-trivial variance lower bound during optimization.
4 Complete, Compressed and Efficiently Optimizable Solution Generators
In this section, we discuss the main results that imply Theorem the family P of Equation (5) is complete, compressed and efficiently optimizable (for some choice of 3*,, ,"pp and W).
8

---

Completeness. First, we show that the family of solution generators of Equation (5) is complete. For the proof, we refer Proposition 2 in Appendix C. At a high-level, we to pick 9 p* to be of order poly(e, a, 1/C, 1/Ds, 1/ Dz). This yields that the matrix W -MM/X is such that L(W) S opt where M is the matrix of Item 2 in Assumption I and À is po]y(e/[Z]). To give some intuition about this choice of matrix, let us see how L(W) behaves, By definition, we have that
2 ((W)
E
E
[= Mx]
2~R pmp((::W)
where the distribution p belongs the family of Equation (5), i.e., p(W) = (1)
3* (><((WW) W). Since the mixing weight 8* is small, we have that p(W) is approximately equal to <W)). This means that our solution generator draws samples from the distribution whose mass given instance is proportional to exp(-2 Mz/X) and, since À > 0 is very small, the distribution concentrates to solutions that tend to minimize the objective 2 Mx. This is the reason why
W = M/ is close to opt in the sense that L(W) I opt +
Compression. As a second step, we show (in Proposition 3, see Appendix D) that P is a compressed family of solution generators. This result follows immediately from the structure of Equation (5) (observe that W has n.x n2 parameters) and the boundedness of W = - -M/X.
Efficiently Optimizable. The proof of this result essentially corresponds to the discussion provided in Section 3. Our main structural result shows that the landscape of the regularized objective with the fast/slow mixture -eaeriooongeerooorrroo is quasar convex. More precisely, we consider the following objective:
(W)
E E [xTMx) + AR(W),
Z p.)(:;;W)
where p(W) belongs in the family P of Equation (5) and is weighted sum of two negative entropy regularizers (to be in accordance with the mixture structure of P), i.e., R(W) = (1 (W) 3*/p" (pp W). Our main structural results follows (for the proof, see Appendix E.
Proposition 1 (Quasar Convexity). Consider > 0 and a prior R over I. Assume that Assumption I holds. The function Ls of Equation (1) with domain W is poly(e, at, 1/C, 1/Ds, 1/ convex with respect - MM/ on the domain W.
Since p" is small (by Proposition 2). H (p W)) is essentially constant and close in value to the negative entropy of the uniform distribution. Hence, the effect of R(W) during optimization essentially the same as that of H(W) (since 3** is close to 0). We show that Lx is quasar convex with non-trivial parameter 7 (see Proposition 1). We can then apply (in a black-box manner) the convergence results from [HMR16 16] to optimize it using projected SGD. We show that SGD finds a weight matrix W such that the solution generator ((W) generates solutions achieving actual loss L close to that of the near optimal matrix W- M/ ie., L(W)= < L(W) + e. For further details, see Appendix E.3.
Experimental Evaluation
In this section, we investigate experimentally the effect of our main theoretical contributions, the entropy regularizer (see Equation (2)) and the fast/slow mixture scheme (see Equation (5)). We try to find the Max-Cut of a fixed graph G. i.c., the support of the prior R is a single graph. Similarly to our theoretical results, our sampler is of the form ( where E {-1, 1} (here is the number of nodes in the graph) is a candidate solution of the Max -axt problem. For the score function we
used simple linear layer (left plot of Figure 2) and a 3-layer ReLU network (right plot of Figure 2).
Small Graph Instances. Focusing on instances where the number of nodes n is small (say 15). we can explicitly compute the density function and work with an exact sampler. We generate 100 random G(n,p) p) graphs with n = 15 nodes and p 0.5 and train solution generators using both the "vanilla" loss L and the entropy-regularized loss LA with the fast/slow mixture scheme. We perform 600 iterations and, for the entropy regularization, we progressively decrease the regularization weight, starting from 10, and dividing it by 2 every 60 iterations. Out of the 100 trials we found that our proposed objective was always able to find the optimal cut while the model trained with the vanilla loss was able to find it for approximately 65% of the graphs (for 65 out of 100 using the linear network and for 66 using the ReLU network).
9

---

Hence, our experiments demonstrate that while the unregularized objective is often "stuck" at sub- optimal solutions- and this happens even for very small instances (n =15 nodes) - of the Max-Chl Cut problem, the objective motivated by our theoretical results is able to find the optimal solutions. For further details, see Appendix
Pagurannzdd
Reqularadd
vanilaa USSS
Vorila
31-
34-
100 200 300
402 300 600 200 200 200
400
300
002
Figure 2: Plot of the Max-Cut value trajectory of the "vanilla" objective and entropy-regularize objective with the slow/fast mixture scheme. We remark that we plot the value of the cut of each iteration (and not the value of the regularized-loss). On the horizontal axis plot the number of iterations and the vertical axis we plot the achieved value of the cut. Both graphs used were random ((n. p) graphs generated with 15 nodes and edge probabilitdy p = 0.5. For left plot we used a linear network (the same exponential family as the one used in our theoretical results). For the right plot we used a simple 3-Layer ReLU network to generate the scores. We observe that the "vanilla" loss gets stuck on sub-optimal solutions.
Large Graph Instances. A natural question is whether this improvement is also apparent in larger graphs. We focus on the case of random d-regular graphs with nodes. is well-known that for this family of graphs, with high probability as > co, the size of the maximum cut satisfies MaxCut(G(nn, d)) = n(d/4 + P. P.yd/4+ ou(va) + o(n), where P. = 0.7632 is universal constant [DMS17]. We aim to find a good approximation for the normalized cut-value, - d/4). / d/4, which (roughly speaking) takes values in [0, P.]. We obtain approximate random samples from the density ef using the Setropolis-Adjusted Langevin Algorithm (MALA). In particular, an approximate sample from this density is obtained by the Euler-Maruyama method for simulating the Langevin diffusion: Fk++1 xx >V f + 2 where & is an independent Gaussian vector (0, 7). MALA incorporates an additional step based on the Metropolis- Hastings algorithm (see [Bes94, SK21J). In our case, the score function f is simple 3-layer ReLU network. In our experiments for larger random regular graphs (600 nodes) using the fast/slow mixing technique along entropy regularization we see that our method leads to improvements over the vanilla objective. Plots of the trajectories of the vanilla and our method can be found in Figure 3. In the horizontal axis plot the iterations and in the vertical axis we plot the normalized cut score of each method (higher better)- we stop the plot of the vanilla trajectory after 200 iterations because observed that its output has fully converged and is stuck.
defined as (cut_valung
3300
Plypa 10P
2339
335
3475
381
387
3.00
Figure 3: Plot of the Max- Cut value trajectory of the "vanilla" objective and entropy- objective with the slow/fast mixture scheme on large instances. On the horizontal axis we plot the number iterations and on the vertical axis we plot the achieved value of the normalized cut-value. The graphs used were random G(n,, p) graphs generated with n = 600 nodes and edge probability 0.5. We stop the plot of the vanilla trajectory after 200 iterations because we observed that its output has fully converged and is stuck.
10

---

Acknowledgements
This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
Constantine Caramanis was partially supported by the NSF IFML Institute (NSF 2019844), and the NSF AI-EDGE Institute (NSF 21 12471).
Dimitris Fotakis has been partially supported by the Hellenic Foundation for Research and Innovation (H.FR.I.) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant", project BALSAM, HERI- FM17-1424.
Christos Tzamos partially supported by the NSF IFML Institute (NSF 2144298).
References
[AAM22] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewiez. The merged-stairease property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782 4887. PMLR, 2022. 5
[ABA22] Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. arXiv preprini urXiv:2208.03/135 2022. 5
[ABAB*21] Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure guide deep learning. Advances in Neural Information Processing Systems, 34:26989-27002, 2021. 5
[ABAM23] Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. Sgd learning neural networks: leap complexity and saddle-to-saddle dynamics. arXiv preprins vrXiv:2302./1055 2023.
[AEG+22] Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. arXiv preprint arXiv:2201.0561 2022. 2
[AKM*21] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340-2435 24351, 2021. 5
[AMW18] Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit- sat: An unsupervised differentiable approach. In International Conference on Learning Representations, 2018. 5
[ART23] Maria Chiara Angelini and Federico Ricci- vecciTTrsennhi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29-3) 31, 2023.
[AS18] Emmanuel Abbe and Colin Sandon. Provable limitations of deep learning. arXiv preprint arXiv: 181 2.06669 2018. 5
[AS20] Emmanuel Abbe and Colin Sandon. On the universality of deep learning. Advances in Neural Information Processing Systems, 33:20061-20072, 2020.
[BBSS22] Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 05:9768-9788 2022.
[BEG+22] Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. arXiv preprint arXiv:2207.0879) 2022. 5
11

---

[Bes94] Julian Besag. Comments on "representations of knowledge in complex systems" by u. grenander and mi miller. J. Roy. Statist. Soc. Ser. B. 56(591-592):4 1994. 10
[BLP21] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinato- rial optimization: methodological tour d' h'rriizo.. European Journal of Operational Research, 290(2):405 421, 2021.
[6]L+16] Irwan Bello, Hieu Pham, Quoc Lc, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940 2016. 3,5
[CCK+21] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Velíčković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
[CGG 19] Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via markov chains. arXiv preprint arXiv: arXiv:/901. 1901.06653, 2019. 27
[CGKM22] Sitan Chen, Aravind Gollakota, Adam Klivans, and Raghu Meka. Hardness of noise- free learning for two-hidden-layer neural networks. Advances in Neural Information Processing Systems, 15:10709-10724 2022. 5
9CL) William Cook, László Lovász, Paul D Seymour, et al. Combinatorial optimization: papers from the DIMACS Special Year, volume 20, American Mathematical Soc., 1995. 1,5
[CLV22] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Spectral independence via stability and applications to holant-type problems. In 2021 IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pages 149-160, IEEE, 2022. 27
[COLMS22] Amin Coja-Oghlan, Philipp Loick, Balázs F Mezei, and Gregory B Sorkin. The ising antiferromagnet and max cut on random regular graphs. SIAM Journal on Discrete Mathematics, 36(2):1306-1322 2022. 27
[CT19] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[CZ22] Xiaoyu Chen and Xinyuan Zhang. A near-linear time sampler for the ising model. arXiv preprint arXiv:2207.0939/ 2022. 27
[d' A08] Alexandre d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Optimization, 19(3)1111-11833 2008. 28
[DAT20] Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja, Reinforcement learning with combinatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, 33:609-620, 2020.
[DCL+18] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis- Martin Rousseau, Learning heuristics for the tsp by policy gradient. In International conference on the integration of constraint programming, artificial intelligence, and operations research, pages 170-181. Springer, 2018. 5
[DLS22] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pages 5413-5452. PMLR, 2022. 5
[DMS17] Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 1902)::190-121,,,000 10
[dPS97] JC Anglès d' Auriac, M Preissmann, and A Sebö. Optimal cuts in graphs and statistical mechanics. Mathematical and Computer Modelling, 26(8- 10): 1997. 27
[Rdm65] Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55 1965. 29
12

---

[EGK*233 Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Pareto frontiers in neural feature learning: Data, compute, width, and luck. arXiv preprini arXiv:2309.03880 2023. 5
[BR18] Patrick Emami and Sanjay Ranka. Learning permutations with sinkhorn policy gradient. arXiv preprint arXiv: 2018. 5
[Gam23] David Gamarnik. Barriers for the performance of graph neural networks (gnn) in discrete random structures. comment on \eite {schuet2022comnnatrii]]]]] citt {angelini2023modemm) ccite 2023.
ciite (schuerz2023reply, arXiv preprint vrXiv:2306.0255x
[GCF+19] 19] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[GLS12] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012. 1,
[GPRW19] Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S Matthew Weinherg. New query lower bounds for submodular function minimization. arXiv preprint 2019. 2
/91
[HLSS15] Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi- convex optimization. Advances in neural information processing systems, 28, 2015. 7
[HMR16] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynami- cal systems. arXiv preprint urXiv:/609.055 1609.65999, 2016. 7, 8, 9, 17, 23, 24
[HS23a] Christoph Hertrich and Leon Sering. Relu neural networks of polynomial size for exact maximum flow computation. In International Conference on Integer Programming and Combinatorial Optimization, pages 187-202. Springer, 2023. 5
[HS23b] Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS Journal on Computing, 2023. 5
(HSS20) Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference learning theory, pages 1894-1938.
PMLR, 2020. 7, 8
[HT85] John Hopficld and David W Tank. "neural" computation decisions in optimization problems. Biological cybernetics, 52(3):141-152 1985. 1,5
[Jeg22] Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2020, 2022. 5
[Jer03] Mark Jerrum. Counting, sampling and integrating: algorithms and complexity. Springer Science & Business Media, 2003. 30
[JLB19] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph con- volutional network technique for the travelling salesman problem. arXiv preprint 190i:: 01207,, 2019.
[J893] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the ising model. SIAM Journal on computing, 22(5):1087-1116 1993. 27
[JSV04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. polynomial- approximation algorithm for the permanent of matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671 167777666 697, 2004. 30
[Kak01] Sham M Kakade, natural policy gradient. Advances neural information processing systems, 14, 2001. 2
13

---

[KC Yeong-Dat Dae Kwon, Jinho Choo. Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188-22 21988, 2020. 5
[KCY+21] Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5143 2021. 5
17] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combina- torial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[KI,20] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. Advances Neural Information Processing Systems, 33:6659-666 6672, 2020.
[KLMS19] Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D Sivakumar, new dog learns old tricks: RI finds classic optimization algorithms. In International conference on learning representations, 2019.
[KP+21] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34:10418-10430, 2021. 5
[KPP22] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-neo: Leveraging symmetricity for
neural combinatorial optimization. arXiv preprint 1.XXiv22005.32009 2022. 5
[KVHW18] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing
problems! arXiv preprint (XXXvv8803308473 2018. 5
[LSS19] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The ising partition function: Zeros and deterministic approximation. Journal of Statistical Physics, 174(2):287-315, 2019. 27
[LSZ21] Troy Lee, Miklos Santha, and Shengyu Zhang. Quantum algorithms for graph problems with cut queries. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939-958. SIAM, 2021. 2
[LV16] Jasper CH Lee and Paul Valiant. Optimizing star-convex functions. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 603-614. IEEE, 2016. 7
[LZ09] Fei Liu and Guangzhou Zeng. Study of genetic algorithm with reinforcement learning to solve the tsp. Expert Systems with Applications, 36(3):6995-7001, 2009.
[MGH+19] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv: /tt:::/911.44990 1.04936, 2019. 5
[3]S+13] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Joannis Antonoglou, Daan Wienstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 322.5602 2013.
[MLC+21] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1ett1109--11000 2021.
[MSIB21] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: survey. Computers Operations Research, 134: 134:105400, 2021. 5
14

---

[MYSSS21] Eran Malach, Gilad Yehudai, Shai Schhaa-,, and Ohad Shamir. The connection between approximation, depth separation and learnability neural networks. In Conference on Learning Theory, pages 2265-3295. PMLR, 2021. 5
[N] Yatin Nandwani, Deepanshu Jindal, Parag Singla, et al. Neural learning of one-of- many solutions for combinatorial problems in structured output spaces. arXiv preprint arXiv:2008.11990 2020. 5
[NOSTI8] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe, Re- inforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[PRW22] Orestis Plevrakis, Seyoon Ragavan, and Matthew Weinberg. On the cut-query complexity of approximating max-cut. arXiv preprint arXiv:2211.04506, 2022. 2
[PS98] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algo- rithms and complexity. Courier Corporation, 1998. 1,5
[RSW17] Aviad Rubinstein, Tselil Schramm, and S Matthew Weinberg. Computing exact minimum cuts without knowing the graph. arXiv preprint 1. 166,,,,,,66,,, 2017.
[S+ Alexander Schrijver al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. 5,5
[SBK22] Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial opti- mization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022. 5
[Sch05] Alexander Schrijver. On the history of combinatorial optimization (till 1960). Hand- books in operations research and management science, 12:1-68, 2005.
1,5
[SE20] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances neural information processing systems, 33:12438-12245 2020.
[SHM* 16] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016. 5
[Sin12] Alistair Sinclair. Algorithms for random generation and counting: Markov chain approach. Springer Science Business Media, 2012. 30, 33
[SK21] Yang Song and Diederik Kingma. How to train your energy-based models. arXiv preprint arXiv:2101.03288. 2021. 10
[SLB+18] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning sat solver from single-bit bit supervision. arXiv preprint 1802.0380..0368. 2018.
[Smi99] Kate Smith. Neural networks for combinatorial optimization: review of more than a decade of research. Informs journal Computing, 11(1):15-34, 1999. 1,5
XSDK+220 Yang Song, Jascha Sohl-Dickstedi Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations, arXiv preprint arXiv:2011.13456, 2020. 4
[S] David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker. Matthew Lai, Adrian Bolton, et al. Mas- tering the game of go without human knowledge. nature, 550(7676) 2017. 5
[TRWG21] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.
5
15

---

[VFJ15] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015. 1,5
[YBV19] Weichi Yao, Afonso S Bandeira, and Soledad Villar. Experimental performance of graph neural networks on random instances of max-cut, In Wavelets and Sparsity XVIII, volume 11 11138, pages 242-251. SPIE, 2019.
[YGS20] Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what cannot teach. In International conference machine learning, pages 10831-10841. PMLR, 2020. 5
[YP19] Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfia-
bility, Advances in Neural Information Processing Systems, 32, 2019. 5
[YW20] Yunhao Yang and Andrew Whinston, survey on reinforcement learning for combina-
torial optimization. arXiv preprint arXiv:2008. /2248, 2020. 5
[ZCH+20] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang. Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 1:57-81, 2020. 5
[ZMB+17] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent in variationally coherent optimization problems. Advances in Neural Information Processing Systems, 30, 2017. 7
16

---

A Preliminaries and Notation
This lemma is a useful tool for quasar convex functions.
Lemma ([HMR16)) Suppose that the functtins fn are individually y-quasar convex in X with respect to a common global minimum Σ. Then for non-negee negativee weights a1...., Ons the linear combination f Eie(n) a:fi is also y-quasar convex with respect to E in X.
In the proofs, use the following notation: for matrix W and vectors æ, 2, we let
exp(2 <xp==TW> Σvex exp(= Wy)
<1;;;;))
(I)
be a probability mass function over X and we overload the notation as
exp(w x))
<(;; w) Eyex exp(1e y)
(2)
B The Proof of Remark 1
Proof. Let .i,..., T. be the variables of the Max-Cut problem of interest and S {-1, be the solution space. Consider d to be the collection of product distributions over S, i.e., for any
P E P, it holds that, for any S. Pra<pl=- s] = [e P; (1-2)) - Let us consider the cube [e, 1--e-ej e)", This family is complete since the O(e)-uub-optimal solution of / belongs P and is compressed since the description size is poly(n, log(1/e)), We show that in this setting there exist bad stationary points. Let La be the Laplacian matrix of the input graph. For some product distribution E P, it holds that
14.2
E [ = -20 Lo 1), vpC(p)= -4Io 1), ((p) =>-((-)
where Tug is in the diagonal and equal the Laplacian otherwise. Let consider vertex of the cube p E eee" which is highly and strictly sub-optimal, i.c., any single change of a node would strictly improve the number of edges in the cut and the score attained in p very large compared to minges x LGG. For any i E [n], we show that
(VL(p) (2) 1).1)) e4) <.
This means that if p; is large (i.c., - e), then the i-th coordinate of the gradient of C(p) should be negative since this would imply that the negative gradient would preserve to the right boundary. Similarly for the case where p. is small. This means that this point is a stationary point and highly sub-optimal by assumption.
Let P (resp. N) be the set of indices in [n] where p takes the value 1 (resp. c). For any E [n]. let ((t) be its neighborhood in G. Let us consider i P. We have that (2p - 1) es > 0 and so it
suffices to show that
(Io(2p - 1)) -e, > 0,
which corresponds to showing that
Σ
La(i,)) - 26) +
Σ
Lo(i.))(2e- - 11 0,
P
JEN(())
and so we would like to have
Lo..i.)-
L >.
JEN
Note that this is true for any [n] since the current solution is strict local optimum. The same holds if 1 E N.
D
17

---

C Completeness
Proposition 2 (Completeness), Consider O and prior R over I. Assume that Assumption / holds. There exist 3 .p' E (0, and W such that the family of solution generators P of Equation (5) complete.
Proof. Assume that O(s, /) = w M (8) and let = (xx(1) and x = (sss)). Moreover, let or C, Ds, Dr be the parameters promised by Assumption 1. Let consider the family P (p(W): W E W) with
W'
p 2; W) = ()) Σ yex e²
Wy + 3*
Σvex e² p'
where the mixing weight 3 E (0, 1) and the inverse temperate o are to be decided. Recall that
L(W)= E E
2~R x>p(:::W) [L(x;))]
E
E
[= T Mx).
Let us pick the parameter matrix W = -M/A. Let M. we can consider the finite set of values V obtained by the quadratic forms {z Mx)zees(S)) We further cluster these values so that they have distance at least e between each other. We consider the level sets C₁ where C1 is the subset of S with minimum value (= v1()) V. C2 is the subset with the second smallest U2( 02(2)) E V. etc. For fixed & E ebz we have that
a f/z For the given matrix
E snupl M/A)
Mx]
)*)
E
[2 Mz) + 8r
E SND(
[2 T Ma],
M/N)
where á comes from (I). We note that
V./l viAA
Pr a--b(11 M/A)
Mx E E, 1Cyle-u//
We claim that, by letting À 0, the above measure concentrates uniformly C2. The worst scenario is when |C2] = [S| -1c1 and 1/2 = 01 + c. Then we have that
C21/1Cile(
Pr T Mr E C2) 1+ [cll/CC
So,
x~<(( (::; M/A)
when 1/X >
log((vs(5)1/6)/ since in the worst case |Cal/[Ci| = (())(())). Using this choice of X and taking expectation over 2, we get that
E
E
T Ma] < (1 (1-3")
E 2
(1- 8)
min L(x; + 000(2)) +33 =Eve((S)
E
Mx].
2-pp( M/A)
a~ M/A)
First, we remark that by taking pa poly(a, 1/C, 1/Dz), the last term the right-hand side of the above expression can be replaced by the expected score of an almost-uniform solution (see Lemma 3 and Proposition 8), which is at most pD Dr, -)2--1/ve (S)) (and which is essentially negligible). Finally, one pick 3* poly(c, 1/C,1,1/////,/,, 1/Dz) that
C( ((-M Z~R - M/X)
E
12 Mx S
min L(x; 2) +c. (EVs(S)
2~R
This implies that P is complete by letting W M// / W. This means that one can take W be ball centered at with radius (of c-sub-optimality) to be of order least = |
D Compression
Proposition 3 (Compression). Consider >> O and a prior R. over I. Assume that Assumption I holds. There exist 3* p² 10 and such that the family of solution generators of Equation (5) is compressed.
Proof. We have that the bit complexity to represent the mixing weight 3* (Ds. Dr, C, 1/e)
and the description size of W is polynomial in [T] and in (og())). This follows from Assumption since the feature dimensions nx and nz are poiy([Z]) and W is ball centered with radius OBB), where B = |M / C/A, which are also pe)
D
18

---

E Efficiently Optimizable
Proposition (Efficiently Optimizable). Consider > and prior R. over I. Assume that Assumption I holds. There exist ,' E (0, and W such that family of solution generators P of Equation (5) efficiently optimizable using Projected SGD, where the projection set is W.
The proof of this proposition is essentially decomposed into two parts: first, we show that the entropy-reularized loss of Equation (2) quasar convex and then apply the projected SGD algorithm to Lx.
Recall that H() EgwR :x [log o(1; 2; W)]- Let R be weighted (to be in accordance with the mixture structure of P) of negative entropy regularizers
8*
R(W) = (1 (0-8~)H()) + -H(w")).
where 8*, p² are the fixed parameters of d (recall Equation (5)). We define the regularized loss (x(W) L(W) XR(W),
where
((W) = Z p-)((s;;W)
[[(xx)]], ( p(W) EP.
E.1 Quasar Convexity of the Regularized Loss
In this section, we show that Lx of Equation (2) is quasar convex. We restate Proposition 1.
Proposition 5 (Quasar Convexity). Consider > 0 and a prior R over I. Assume that Assumption 1 holds. The function Lx of Equation (2) with domain W is poly(C, Ds, Dz, 1/e, 1/aaa//uasat convex with respect to - M/ X on the domain W.
Proof. We can write the loss Lx as
(WW E ICx, 2~
E (W. + (R_(W)) Z~
where the mappings C. and R2 are instance-specific (i.e., have fixed z). We can make of Lemma 1, which states that linear combinations of quasar convex (with the same minimizer) remain quasar convex. Hence, since the functions Lx have the same minimizer MM/, suffices to show quasar convexity for a particular fixed instance mapping, i.e., it sufffices to show that the function
Lx.a (W) = C. (W) + (R)
quasar convex. Recall that W matrix of dimension nz nx. To deal with the function Cx. we consider the simpler function that maps vectors instead of matrices to real numbers. For some vector e, let Cxer Rx RR be
Cx (w)
E x-p((-ta)
[c-
(w)))()))
where for any vector RTx, define the probability distribution o(;: over the solution space X = (S) with probability mass function
6(2; w)
Σ VEX ewyy
We then define
pl: w) = (01-3")0 30)((; w) +B"(::p"")
and (w)( (1 - (w) + -- (pp"w) (this is a essentially a weighted sum of regularizers,
8'
needed to simplify the proof) with ((w) Ez log ó(x, w). These quantities essentially the ixxe-instancee analogues of Equations (5) and (2). The crucial observation is that by taking z M and applying the chain rule we have that
V Ww.xx
[VwCX (2TT3
(4)
19

---

This means that the gradient of the fixed-instance objective Lx,2 is matrix of dimension R2 x nx that equal the outer product of the instance featurization 2 and the gradient of the simpler function e evaluated at W. Let us now return on showing that Lx,; is quasar convex. To this end, we observe that
M V (W) (w -) ) Vx (700(37T
(=TW
M X
This means that, since is fixed, it suffices to show that the function 2xee is quasar convex. We provide the next key proposition that deals with issue. This result is one the main technical aspects of this work and its proof can be found in Appendix E.2.
In the following, intuitively X' is the post-featurization instance space and is the parameter space.
Proposition 6. Consider c, > O. Let |cel2 Cy- Let be an open ball centered 0 with diameter 201/X /x. Let X' be space of diameter D and let Var [v. xi] 2 a<]ool for any Z. The function LX (w) Em-p(:soole x] (R) is poly(1/C1, e, a--quaaar convex with respect to -c/ on 2.
w w = = W D = D5 and Ci = DrC. These give that We can apply the above result with c = = TM, the quasar convexity parameter y is of order y = poly(e, 1/C, 1/C,1/Ds, // 1/Dz). Since we have that Cx (z W) Lx,e (W), we get that
Vw Lw.x,, (W + M/A) 2 7(x,, - (xx((-MAA))
This implies that Lx is y-quasar convex with respect to the minimizer MM/X and completes the proof using Lemma
E,2 The Proof of Proposition
Let us consider _ to be real-valued differentiable function defined on Z. Let w, -c/ X 2 and let L be the line segment between them with E Z. The mean value theorem implies that there exists w' E L such that
(w) (-ccA) = (w)) (w c/A) S (w') + c/A/2-
Now we have that Lxe has bounded gradient (see Lemma 2) and so we get that
VV (w') (w')ll2 s D²IIc+ Aw'l12 D2 D2>1|w'' (/Allw'+c//A cc/Alla S DR c/1112,
since w E L. This implies that
(w) - (-c/ D'A + +
1 VVxx (w + c/A),
where 1/y= = Lemma 3). 2a22
CL. The last inequality an application of the correlation lower bound (see
In the above proof, we used two key lemmas: a bound for the norm of the gradient and a lower bound for the correlation. In the upcoming subsections, we prove these two results.
E.2.1 Bounded Gradient Lemma and Proof
Lemma 2 (Bounded Gradient Norm of ) Consider c, > O. Let Z be the domain of L of (3). Let X be a space of diameter D. For any E Z, it holds that
W (w)ll2 < O(D?)llc+ Xw|le.
Proof. We have that
V F = =(1 8t Gt + pppppppp Gp
where
G
Il(c (w) x)x]
[[c + Xw) x]
[
2owp(:10)
20

---

and
Gp'
E
[l(c Aw) x))]
[(e (ex)
E
[x]
2m-0 z~-0(:0- w)
x~pl(:0" w)
ammbl (pppppp"i0
Note that since X, holds that ||0|| S D. Hence
||uull==
sup 0=|vi|la=1
|e. Gwl S 22 Awlle
Moreover, we have that
GGrull2 S 2| Auo122.
This means that
I (00xxxxw)ll 2 B*) + Avol2 + 28 pa > =0(3)l+ AwI12-
E.2.2 Correlation Lower Bound Lemma and Proof
The following lemma is the second ingredient in order show Proposition 6.
Lemma 3 (Correlation Lower Bound for C Let X > Let ||c||2 I C1. Let Z be an open ball centered at with diameter B 201/>. Let X' be space of diameter D. Assume that E Z and Var u + Aw) xi] 2 a-lcc + 2 some a > 0. Then, for any 3 E (0, 1), there exists p* O such that it holds that
[w) Xwo) 12 (8+ a² (BD3) xw
where Cxe is the regularized loss of Proposition 6, p² is the scale in the second component of the mixture of (5) and 3 (0, 1) is the mixture weight.
First, in Lemma 4 and Lemma 5, we give a formula for the desired correlation V Exx (w) (c+ Xw) and, then we can provide a proof for Lemma by lower bounding this formula. Lemma 4 (Correlation with Regularization). Consider the function g(w) Ex [c=x] XH((W) where is the negative entropy regularizer. Then it holds that
Veg(w) (c+ Xw)= Var Varz> [[ Aw) .z).
Proof. Let us consider the following objective function:
exp(w x)
g(w) =>w)(-;))
[c. x] + AH()), ((r =
- Eyex exp(w v)
where H is the negative entropy regularizer, i.e.,
Hww)= a~)((;w))
[log ((;;
E x~v((-w)
[w-x] log Σ eooyy
yEA
The gradient of g with respect to W is equal to [[c xx) x) log 6l AV H(w)
V Vug(w)=
E
x~o((sw)
It holds that
Va log (bx; w) V..
w. x log
wwy
x
E xm
[x]
DEX
and
(w)
E
[x]+
E
[(w-x)) V. log (b:;; w))
[x]]
E
[(w-r)) V an log ((; w)]
x~o(;w)
zm0((;a))
So, get that
Vug(w)=
E
[((c Aw) x))a]
E
((c Xro) x0]
E xoo
[x]]
Note that
V Vwg(w)- (c+ (w))= = Var Varz~o(sw [[c Xww) x]].
21

---

Lemma 5 (Gradient with Regularization and Mixing), For any > O, for the family of solution
generators P {p(:;w) w)) = (1 3 )0((;;)) + 8 pr:lpppa E W] and the objective Lx= of
Equation (3), it holds that
VuLxx(10 (c+ Xw) = (1- Var pr) Xw) -x] + p"pp Var parr-~llppre
(( w))l xw) -x],
for any > O.
Proof. Let us first consider the scaled parameter pw E W for some p > 0. Then it holds that
[c-]
(c. x) pz
E
lpxi)
=
(c. 2
[xr] ]
x~((:)00)
Moreover, the negative entropy regularizer at pi is
((ww)= xrd((ppw)
((ww) x] log
c(pw)
NEN
It holds that
V..lH
E [pw-x) wo log (2;; pw)] p²
E [(w x)a]
E 2~0(sp))
[w
x]
E
[a]]
(-wo(-spu))
We consider the objective function CXe to be defined as follows: first, we take
p(: w) = 3*) )o(: w) 8 ((:pp" w), i.e. p(:; w) is the mixture of the probability measures o(;; w) and o(:; p"w) with weights 1 3 and 3 respectively for some scale p² > O. Moreover, we take (v = (1 - 3* H))) z:t H (p'ww) w)
Then we define our regularized loss L to be
_xee (w)
E x>p((:w)
[c.2] Awve
Using Lemma 4 and the above calculations, we have that
V ViL vec (w) (1 V
E x~o(sw)
[c. + A(1 Br V
E
[c. x]
>
V H('ww)
pa
=(1 11-33 3*)
E
[((e + Aw) xr)a|
E x>)((;)))
[[e Aw)
E [2s]
(>p((;a))
2~0 vw))
E (-
[l(c (w) z)z]
Ile Aw) x]
E
[x]]
x~bb(ip"") w)
w~oll-pp w)
The above calculations yield V (c + Aw) (1 3rr) Var Var +w))(((++wwww-- x] 3"ppp Var Var a0 w) Aw) x].
and this concludes the proof.
The above correlation being positive intuitively means that performing gradient descent to Exee gives that the parameter w converges to -c/A, X the point that achieves completeness for that objective.
However, to obtain fast convergence, we need to show that the above correlation is non-trivial. This means that our goal in order to prove Lemma quantity, i.c., it suffices to give a non-trivial lower bound for the variance of the random variable +c+ Xw) x with respect to the probability measure o(; p"w). It is important to note that in the above statement we did not fix the value of p". We can now make use of Proposition 8. Intuitively, by taking the scale parameter appearing in the mixture p² to be sufficiently small, we can manage to provide a lower bound for the variance of (c+ Aw) x with respect to the almost uniform measure, i.e, the second summand of the above right-hand side expression has significant contribution. We remark that y corresponds to the inverse temperature parameter. Hence, our previous analysis essentially implies that policy gradient on combinatorial optimization potentially works if the variance Var (upao [(c + Aw)- z) is non- non-vanishing at high temperatures 1/p.
to provide a lower bound for the above
22

---

The proof of Lemma 3. Recall that
e
((1; w)
Evex ewly
Let also D be the diameter of X' and B the diameter of Z. Recall from Lemma 5 that we have that Vu-X" (w)) (c+ Aw) (1 3*) Var |(c Aw) xx] 8"pp" Var w])c Aw) x], where the scale parameter p² > 0 be decided. This means that
V V (w) (c + Aw) 2 3*p" Varg=o(ssptoolee Aw) x].
Our goal is now to apply Proposition 8 in order to lower bound the above variance. Applying Proposition 8 for y < "(:ppw), c c+ Aw and, for some absolute constant Co, we can pick
a
0² = Co BD3
Thus, have that
Var Var wool w/ ((c + Aw) x] 2 M(allc+ + xw
This implies the desired result since
V V v
Avec (w) (c + Aw) 2 22 Aw
E.3 Convergence for Quasar Convex Functions
The fact that Lx is quasar convex with respect to MM/A implies that projected SGD converges to that point in a small number steps and hence the family P efficiently optimizable. The analysis is standard (see e.g., [HMR16]). For completeness a proof can be found in Appendix E.3.
Proposition 7 (Convergence). Consider > and a prior R over I. Assume that Assumption holds with parameters C, Ds, Dz, Let Wi...., Wr be the updates of the SGD algorithm with projection set W performed on Lx of Equation (2) with appropriate step size and parameter Then, for the non-regularized objective L, it holds that
[C(W)) S C(-M/A) +c,
(~((()
when T' 2 1/ly C, Ds, Dz, 1116 + M/AlIE).
Our next goal is to use Proposition and show that standard projected SGD on the objective L.x converges in polynomial number of steps. The intuition behind this result is that since the correlation between V (W) and the direction M XW positive and non-trivial, the gradient field drives the optimization method towards the point M//
Proof. Consider the sequence of matrices Wi,..., W..... Wr generated by applying PSGD on Lx with step size 77 (to be decided) and initial parameter vector Wo W. We have that Zx is 7-quasar convex and is also -(T'-le smooth² since we now show that it I-smooth.
Lemma 6. Lx is poly(Ds, Dr, -mssmoohh.
Proof. We have that
[VLx =
E VVC,
E ||
(x
WW)
It suffices to show that Exec is smooth. Recall that
V (w) (1)
E (w)e(::w)
[[[c + (w)) 2)a]
E 2vo((;))
[[c Aw)
E
[x]
+
xndd(-sw)
+ p* x-p((:p-r)
[[(c + (w) r)a]
E
[(e + Aw) x
[x)
z =x
3~ we
As mentioned in [HMR16], function f is w--eeklly smooth if for point 0, <(((())) )()")). Moreover, function f that is smsshoth (in the sense V < 1'), also O(e'-l smooth.
23

---

This means that
V w -x
( = (1 ( (A1 A2) + 3 p033 + Aa):
where
A =
V
E z-30(:3a))
[([e + Aw) x)0:]
A2 =
V
E xmwl(-sw)
[[e + Aro) x]]
E
[x]]
F7
A3 =
V
[[(c Aw) x)œ]
A4 =
Vu
E
[(c + xw) ax]
[x]]
((:pp)))
F
x
Standard computation of these values yields that, since Ds and Dr are bounds to æ and respectively, we have that Lx is smooth with parameter poly(Ds. Dr, C).
Let V be the variance of the unbiased estimator used for Vw) We can apply the next result of [HMR16].
Lemma 7 ([HMR16)) Suppose the objective function f 7-weakly quasi convex and T-weakly smooth, and let r(-) be unbiased estimator for f(0) with variance V. Moreover, suppose the global minimun 0 belongs W, and the initial point Og satisfies |10g - 011 S R. Then projected stochastic gradient descent with proper learning rate returns Or in T iterations with expected error
TR 7T VT
RVV
f(0.) - f(0) S max (T))
E
We apply the above result to LA in order to find matrices W1,..., Wr that achieve good loss on average compared M/A. Moreover, using batch SGD update, in the crucial parameters of the problem. We note that one can adapt the above convergence proof and show that the actual loss L (and not the loss Lx) are close after sufficiently many iterations (as indicated by the above lemma). We know that the Frobenius norm of the gradient of L(W) is at most of order O (&) We can apply the mean value theorem in high dimensions (by taking W to be an open ball of radius O(B)) and this yields that the difference between the values of L(WT) and C(-M/)) is at most D by the correlation between (W,) and W. + M/A. Hence, we can still use this correlation as potential in order minimize L. This implies that the desired convergence guarantee holds long as T 2 poly(1/c.1/,,,,D) C, Dr, IWo + M/AlIe).
take V to be also polynomial
+ M/ However, the right-hand side is upper bounded
F Deferred Proofs: Variance under Almost Uniform Distributions
This section is technical section that states some properties of exponential families. We use some standard notation, such as w and z, for the statements and the proofs but we underline that these symbols not correspond to the notation in the main body of the paper.
We consider the parameter space θ and for any parameter w E O, we define the probability distribution oi; w) over space X' with density
6(1; w)
EvEx ewry
In this section, our goal is to relate the variance of under the measure o(: (uniform case) and o(; ww for some w E W and some sufficiently small p" (almost uniform case). The main result of this section follows.
Proposition 8 (Variance Lower Bound Under Almost Uniform Distributions). Assume that the variance of x under the uniform distribution over X, whose diameter is D, is lower bounded by it holds
ar||c]|2 Moreover assume that w E θ with ||l||2 < B. Then, setting p* that Varz=<(=p==)) (e- = (a]]ee))))
We first provide general abstract lemma that relates the variance of the uniform distribution U over X' to the variance of an almost uniform probability measure μ. For simplicity, we denote the uniform distribution over X' with U (X)).
24

---

Lemma 8. Let w E è and a E X with |æl|2 S D. Consider the uniform probability measure U over X and let ir over X' such that there exist EI, 62 with:
[ En- [x]]22 S and, Exzalat (ax Iwo 2 w Ex (xr Jw e2|lw|1e.
Then holds that Varzan (w x 2 Varm-ulu (w x| max (,
Proof. We have that
Varz [w
[w
z)²
ampp
We first deal with upper-bounding the square the first moment. Note that
E Smp
[x]
E mmC
[2c]
S
||
E pro
E and
[or]
Sei
Se1///o|22.
Let us take 0 (with
e1) for simplicity to be such that (E (w x²)
(Ez~ [w- x] + e|]w]ll2?? This means that
E w 2| mmn
2 + 2c||w|12 E [w 21)
E ww æ1| + e 11w12
2 +
w x
2 1
Lenu
Next we lower-bound the second moment. It holds that
[[w 2)
T
E 20pp
rx
w
2
[w x² callw]|3
zrpp
amaff
for some 62 0. This means that
Varaa (w . x)
[(w x) - e2/ e2|1wr11
E [w 21) D/wl - 1w01
anli
Hence,
Varesplu [w.r) Varzwulw- x] m (1
Our next goal to relate o(: p" w) with the uniform measure ob:; 0). According to the above general lemma, we have to relate the first and second moments of Φ(:; p"w) with the ones of the uniform distribution U ():
The Proof of Proposition 8. Our goal is to apply Lemma 8. First, let us set
(p
E
[V x],
a~0(s000)
for any unit vector v E ④ Then it holds that
sup
(f((0) - [o()
2~)((-0)
e: e:]|v]|==1
Using the mean value theorem in [0, p-] for any unit vector have that there exists a Eu (0, p²) such that
(f) fo())) (5(())
It suffices to upper bound (E) for any unit vector and & E p0) Let us compute f. We have that
df. dp dp Is cetwyldy
/ (v (v.x) d el(we) dr
E [10 x x:)]
E amdt (opb)((pp)) (ppp))
E 1
w x
x~o((sm))
25

---

Since x E N, we have that
sup (
sup
[f((5)
S 2|[w||2D2
This gives that
E
S 2p' 22212w1122
x~~0(::)
2
We then continue with controlling the second moment: it suffices to find Eg such that for any O it holds
E I (:ipo w)
Ix lu 2 u
[x 1V c2 ce|lul13-
Let us set (p)p) = Eg (sppo)
[(0 x) for any vector E θ We have that
(g)(0) gole") p= (E),,
where & E p",p"). It holds that
dg:
[(v x) x)]
E xnd(=sp))
[(v x
E [w x
s 2/1u/
|| w
dp (>~p()
xmo((:pp)
This gives that for any O holds
E
[xr Tl
Fr [V 2p" ||
20d w)
2~0((:0)
Note that the above holds for too. Lemma 8 gives that
Var wc) 2 Vara~e(-:0 (c x] - 3 max e. HHcdl1
where E = 2p" BDd and 62 2p BDd, This implies that by picking
a
p Co BD
for some universal constant Co. we get that Var var œ| [(allcl13).
In this section, we considered p" as indicated by the above Proposition
G Applications to Combinatorial Problems
In this section we provide a series of combinatorial applications of our theoretical framework (Theorem 1). In particular, for each one of the following combinatorial problems (that provably satisfy Assumption 1), suffices to specify the feature mappings tis, 4/z and compute the parameters C, Ds, Dz, a.
G.1 Maximum Cut, Maximum Flow and Max-k-CSPs
We first provide general lemma for the variance of "linear tensors" under the uniform measure.
Lemma 9 (Variance Lower Bound Under Uniform). Let n, k E N. For any w E (R(,,, holds that
Var Var,-u((-1,))))ee
Σ
DASCIn)|S1E
Proof. For any E IR (R),, it holds that
Var Var,-o((-1))))) 00
(~U(11111))) [[w x 28h22
E (0(((11))))
[w
x 2012
Note that R can be written the Fourier expansion and w = (SS is the vector of the remaining coordinates. The Fourier expansion implies that
(wp, w) where we corresponds to the constant term of
Var Var oK] = ||
which yields the desired equality for the variance.
26

---

G.1.1
Maximum Cut
Let us consider graph with nodes and weighted adjaceney matrix A with non-negative weights. Maximum cut is naturally associated with the Ising model and, intuitively, our approach does not yield an efficient algorithm for solving Max-Cur since cannot efficiently sample from the Ising model in general. To provide some further intuition, consider a paggle-rreetter Ising model for 1ts,, Then the partition function is equal G = (V, b) with Hamiltonian Ha(r) = LijjEr 2
to (3( = Exe(-1.1y (x)() Note that when 3 > O, the Gibbs measure favours configurations with alligned spins (ferromagnetic case) and when 3 < O, the measure favours configurations with opposite spins aaniimeeroomagnetic case). The antiferromagnetic Ising model appears to be more challenging. According physicists the main reason is that its Boltzmann distribution is prone to a complicated type of long-range correlation known as 'replica symmetry breaking' [COLMS22J. From the TCS viewpoint, observe that as B goes to -o0, the mass of the Gibbs distribution shifts to spin configurations with more edges joining vertices with opposite spins and concentrates on the maximum cuts of the graph. Hence, being able efficiently approximate the oog-partition function for general Ising models, would lead to solving the Max-Cut problem.
Theorem 2 (Max-Cut has a Compressed and Efficiently Optimizable Solution Generator). Consider a prior over Max- Cut instances with n nodes. For any E > O, there exists a solution generator P = {p(w) : w E W] such that P is complete, compressed with description poly(n) polylog(1// and L + XR : W + TR efficiently optimizable via projected stochastic gradient descent in poly(n, 1/c) steps for some X > O.
Proof of Theorem 2. It suffices to show that Max-Cut satisfies Assumption 1. Consider an input graph G with n nodes and Laplacian matrix LG. Then
s LGs 1 min -8 Las.
max MAXCUT SE (-11)"
4 (-(3)
We show that there exist feature mappings so that the cost of every solution under any instance/graph
G a bilinear function of the feature vectors (ef. Item 2 of Assumption 1). We consider the correlation- based feature mapping (s) (ss T TR= where by (-)² we denote the vectorizattion/lateeiin operation and the negative Laplacian for the instance (graph), vlz(G) = (LLa)² E R== Then simply setting the matrix M to be the identity / E R²² xn² x=""x" the cost of any solution can be expressed as the (.L")Tsss""))
bilinear function th (G) T (s) graphs) with n nodes the bit-complexity of the family of all instances I is roughly O(n²), and therefore the dimensions of the shs, t/z feature mappings are clearly polynomial in the bit-complexity of T. Moreover, considering unweighted graphs, it holds [lvbz(G) ( [l), ||M S poly(n). Therefore, the constants Ds. Dz, C' are polynomial in the bit-complexity of the instance family.
-8 Las. We observe that (for unweighted
It remains to show that our solution feature mapping satisfy the variance preservation assumption. For any U, we have that Var (S) [s){s Var (((,-p((( (ssT)² y) 2(Ivv))), using Lemma 9 with &- = 2, since cg = with loss of generality.
G.1.2 Minimum Cut/Maximum Flow
Let us again consider a graph with n nodes and Laplacian matrix Lg. is known that the minimum problem is solvable in polynomial time when all the weights are positive. From the discussion of the maximum cut case, we can intuitively relate minimum cut with positive weights to the ferromagnetic Ising setting [dPS97]. We remark that
consider the ferromagnetic parameter
(3)
space Wier R 20 and get the variance lower bound from Lemma We constraint projected SGD in Wier This means that during any step of SGD our algorithm has to sample from a mixture of ferromagnetic models with known mixture weights. The state of the art approximate sampling algorithm from ferromagnetic Ising models achieves the following performance, improving on prior work [JS93, LSS19, CLV22, CGG-T 19].
Proposition 9 (Theorem 1.1 of [CZ22]). Let d, 52 E 1) be constants and l be the Gibbs
distribution of the ferromagnetic Ising model specified by graph = (V, F), V n, |,|FE = m, parameters 3 E [1 + ög, +00) and external field X [0, 1 - 8x]". There exists algorithm that
27

---

samples X satisfying TV,X, 14) S e for any given parameter (0, 1) within running time
logg 05
m
This algorithm can handle general instances and it only takes near-linear running time when parameters are bounded away from the all-ones vector. Our goal is to sample from a mixture of two such ferromagnetic Ising models which can be done efficiently. For simplicity, we next restrict ourselves to the unweighted case.
Theorem 3 (Min-Cut has a Compressed, Efficiently Optimizable and Samplable Solution Generator).
Consider a prior over Min-Cu instances with nu nodes. For any e >> there exists a solution generator
(n P = {p((w) w E W} such that P is complete, compressed with description (ooo(loo (1/e), AR: W R is efficiently optimizable via projected stochastic gradient descent in poly (n, 1/e)
steps for some X > 0 and efficiently samplable in poly(n, 1/e) steps.
Proof. We have that
min x' LGx. MINCUT 4 #E (-1,)
The analysis (i.e., the selection of the feature mappings) is similar to the one of Theorem 2 with the sole difference that the parameter space is constrained be Wier and y (La)². We note that Proposition 9 is applicable during the optimization steps. Having an efficient approximate sampler for solutions of Min-Cut, it holds that the runtime of the projected SGD algorithm is poly(n, 1/e). We note that during the execution of the algorithm we do not have access to perfectly unbiased samples from mixture ferromagnetic Ising models. However, we remark that SGD is robust to that inaccuracy in the stochastic oracle. For further details, we refer e.g., to [d' A08))
G.1.3 Max-k-CSPs
In this problem. we are given a set of variables {xaJacu where [24] = n and a set of Boolean predicates P. Each variable x, takes values in {-1, 1). Each predicate depends at most k variables. For instance, Max-Cut is a Max-2-CSP. Our goal is to assign values to variables so as to maximize the number of satisfied constraints (i.e., predicates equal to 1). Let us fix predicate h P. ie., a Boolean function h: 1-1 + {0, 1} which a k-junta. Using standard Fourier analysis, the number of satisfied predicates for the assignment &
E (-1,1)" is
IPI F(x) Σ
Σ
RR(S)
II Tu. WES
J=1 SChNLISskk
where (S)) is the Fourier coefficient of the predicate hy at S.
Theorem 4 (Max-k-CSPs have Compressed and Efficiently Optimizable Solution Generator). Consider a prior over Max-k- CSP instances with n variables, where k E NN can be considered constant compared to n. For any e >> O, there exists a solution generator = {p(w): : w E W) such that P is complete, compressed with description O(n polyloog)))))//)) and L + XR W + R is efficiently optimizable via projected stochastic gradient descent in poly(n* 1/e) steps for some 0.
Proof. Any instance of Max-k-CSP is a list of predicates (i.c., Boolean functions) and our goal is to maximize the number of satisfied predicated with a single assignment E 1-1,1)". We show that there exist feature mappings that the cost of every solution under any instance/predi- cates list P is a bilinear function of the feature vectors (cf. Item 2 of Assumption 1). We con- sider the order h correlation-based feature mappings vbs(s) (sSK)> E R²* where by (.) we denote the flattening operation of the order l tensor, and, (I(P) vir(hi,..., hi))) -, ($) E Rn* where (S)(()))s( is vector of size n* with the Fourier coeffients of the j-th predicate. We take v'z being the coordinate-wise sum of these coefficients. The setting the matrix M to be the identity matrix R x** we get that the cost of any solution can be expressed as the bilinear function (P(P) Mabs(s)
28

---

-Ij- Esch, R,(5) Ines For any h: (-1,1}" - {0,1], we get that the description
size of any MS) is poly(n, k) and so the dimensions of the dss the feature mappings are polynomial in the description size of I. Moreover, we get that | [|)s())]] [ ||А]|| S poly(n²). Hence, the constants Ds, Dr, C are polynomial in the description size of the instance family. Finally, we have that for any Var,-u(s)(r (s(ss] ((-11=1 assuming that By is 0 without loss of generality. This implies the result.
s = (2([)=))), using Lemma 9,
G.2 Bipartite Matching and TSP
G.2.1 Maximum Weight Bipartite Matching
In Maximum Weight Bipartite Matching (MWBM) there exists a complete bipartite graph (4, B) with |A| = |B]=
(the assumptions that the graph is complete and balanced is without loss of generality) with weight matrix W where (i..)) indicates the value of the edge (i.j), é E A.j E B and the goal is match the vertices in order to maximize the value. Hence the goal is maximize L(II) = W IT over all permutation matrices. By the structure of the problem some maximum weight matching is a perfect matching. Furthermore, by negating the weights of the edges can state the problem as the following minimization problem: given a bipartite graph (A, B) and weight matrix W E (IR {)))) find a perfect matching M with minimum weight. One of the fundamental results in combinatorial optimization is the polynomial-time blossom algorithm for computing minimum-weight perfect matchings by [Edm65].
We begin this section by showing a variance lower bound under the uniform distribution over the permutation group
Lemma 10 (Variance Lower Bound), Let (S..) be the uniform distribution over n X n permutation matrices. For any matrix W E Rnxn, with >: Wi, 0 and
E, Wij = 0 we have
W l
Varn [W- II|
1-1
Proof. We have that En- [1y = 1/n and En- [Lag
[istnnjshh n(n-1)
+
1imma.
We have
IW 11) - E W III 2
Varn~u(S.)) [W III
E (8.)
TT~U(A)))
2
[(iiaajj #b} bj
lii 0. =b]
W Σ
Wiy
n(n 1)
n
n
+ b}
W3
Σ
Wi W ab
n(n 1)
ijabb
[WIF
1i + a,j + b}
Σ
Woy
n
n(nn - 1)
i.j.a
where obtain the third equality we used assumption that Eij Wij = 0. We observe that, by Waj and therefore, we have our assumption that E. Was = 0 for all it holds Eoss Wab =W
Wi + a.j + b} = 1(i + aa} Σ Was 1 (j + b) - 1(i + Was
Similarly, using the fact that Eajs Waj = WWis we obtain that
Σ Was (i + j + b) = Σ W ai W
ab
Therefore, using the above identity, we have that
1 n
W
W n1
Σ Wo b.j.a,b
nnn -1
1)
Combining the above we obtain the claimed identity.
29

---

Remark 8. We note that in MWBM the conditions E, Wi = and Σ, Wa 0 are without loss of generality.
We next claim that there exists an efficient algorithm for (approximately) sampling such permutation matrices.
Lemma 11 (Efficient Sampling). There exists an algorithm that generates approximate samples from the Gibbs distribution p(:; W) with parameter W over the symmetric group, i.e., p(I:; W) x exp(W 11) E }, in poly(n) time.
Proof. This lemma essentially requires approximating the permanent of a weighted matrix, since this would imply that one has an approximation of the partition function. Essentially, goal is to generate a random variable that c-close statistical distance to the probability measure
IIII W) x exp(W II) E }
Note that the partition function is
z(W)=
Σ M
W-1
Σ IIE (4.)
II
W.
W th
Σ II As,o(1)> DE iE(n]
where A is non-negative real matrix with entries Aú ex)(W,)) Note that in the third equality, we used the isomorphism between permutations and permutation matrices. Hence, Z(W) is exactly the permanent of the matrix A.
Proposition 10 (USVO4D. There exists fully polynomial randomized approximation scheme for the permanent of an arbitrary n. x n matrix A with non-negative entries.
To conclude the proof of the lemma, we need the following standard result.
Propusition (See Appendix H and [Sin12, 12, Jer03]). For relf-reducible problems. polynomial approximate integration and fully polynomial approximate sampling equivalent.
This concludes the proof since weighted matchings are self-reducible (see Appendix H).
The above lemma establishes our goal:
Theorem 5 (MWBM has Compressed, Efficiently Optimizable and Samplable Solution Gen- erator). Consider a prior over MWBM instances with nodes. For any > O, there exists solution generator P (p(w) : w E W] such that is complete, compressed with description poly(n)polylog() polplogll/ll/))))) ( + XR W + R is efficiently optimizable via projected stochastic gradient descent in poly(n, (n, 1/c) steps for some > and efficiently samplable in poly (n, 1/c) steps.
Proof. Consider input graph G with nodes and adjacency matrix F. The feature vector corresponding to matching can be represented as binary matrix 11 E {0, 1jnxan with E, Mi = 1 for all and E; II: = 1 for all j. i.., II is permutation matrix. Then
MWBM
max E' 11 min -E-1 11. IIES
HES.
Therefore, for candidate matching 8, we set (s) to be the matrix II defined above. Moreover, the feature vector of the graph is the negative (flattened) adjacency matrix -E The cost oracle is then L(R: E) = - Eig Eij MijM, R.j perhaps for unknown weight matrix Mij (see Remark 6).
This means that the dimensions of the feature mappings the, t/r are polynomial in the bit complexity of Z. Morcover, we get that ())(l))le (s)((,) [|M]] S poly(n). We can employ Lemma 10 to get the variance lower bound under the uniform probability distribution in the subspace induced by the matrices satisfying Lemma 10, ie.. the matrices of the parameter space (see Remark 9).
Finally, (approximate) sampling from solution generators be done efficiently using Lemma 11 and hence (noisy) projected SGD will have a runtime of order poly(n, 1/c) (as in the case of Min- Cut).
We close this section with remark about Item 3 of Assumption 1.
30

---

Remark 9. We note that Item 3 of Assumption I can be weakened. We use our variance lower bound in order handle inner products of the form w where will lie in the parameter space and is the featurization of a solution that lies in some space X. Hence it is possible that w lies in div-dimeniional subspace of X. For our optimization purposes, it suffices to provide variance lower bounds only in the subspace where w lies into.
G.2.2 Travelling Salesman Problem
Let us consider weighted clique K₂ with n vertices and weight matrix W E Raxx, solution to the TSP instance W is sequence [n] - [n] of the n elements indicating the TSP tour (2), (n)),(()) (1)) and suffers cost
n-1 L(T) Σ ((()) + W (x)))a())
Crucially, the allowed sequences are proper subset of all possible permutations. For instance, the permutations with fixed points or small cycles are not allowed. In partieular, the solution space of TSP corresponds to the set of cyclic permutations with Clearly, the number of n-cyclls is (n - 1)!. The goal is to find a tour of minimum cost. Our first goal is to write the cost objective as a linear function of the weight matrix W and the feasible solutions, which correspond to cyclic permutations. To this end, we can think of each cyclic permutation π as a eyclic permutation matrix II E (0, 1]"xx. Then, the desired linearization is given by L(II) = WW II (for a fixed graph instance).
trivial cycles, i.c., containing an n-cycle.
Our next task is to provide Gibbs measure that generates random cyclic permutations. Let C, be the space of n n eyclic permutation matrices. Then we have that the tour IT is drawn from
Pw (II) exp(W - 1I) E C.)
Envec, exp(W II')
where W is the weight matrix. The following key lemma provides guarantees for the performance of our approach to TSP. This lemma allows us to show that the number of optimization steps is poly(n, (n, 1/e).
Lemma 12 (Variance Lower Bound). Let (C,) be the uniform distribution over x cyclic permutation matrices. For any matrix W RRxx, with E; Wej and E; Wii 0 we have
W
Varn-u
1)(n
The first step is to compute some standard statistics about cyclic permutations (see Lemma 13). Lemma 13 and the analysis of Lemma 10 gives us that Varn=-e'E..)) [W 11] is equal to
Proof.
| + Σ n1
[i == (n 1)(n (n-1)(n-2) + + (n 1)
b a}
Wab
a.j.abb
Let us set
A Σ WyWallita=j
We have that
- 1(t #
Warlfi
W -(i j
Hence
4 =
ai) = W,, -,,,,,= ig
i..00
Due to symmetry, A2 Eijab W W
# b- = E, Wz3 It remains to argue about
Ag
Σ
W;Wollita+tj$441
i.j.bb
31

---

We have that
Σ Warlfi # af زززز + b) - + af1fa # ji(Wos + Wa).
This gives that
A =
Σ
Wiy(Was + Wa)lli *
Note that
Σ Ww +3 Σ aJaa
Waylfa 13 Σ
-t===-wwtt a2 2,a
3.0
This implies that
A₃
Σ W2
Σ
W2 =2 Σ
W
i&a
In total, this gives that
WIF n
28, W
2 2 i5 W7
W
|| (n 1)(n 2)
Varn-u(c.) [I
+
+
2
(n 1)(n - 2)
(n 1)(n -3)
1
Remark 10. We note that in TSP the conditions generality.
Σ, Wij and E, Wij 0 are without loss of
The next lemma a generic lemma that states some properties of random eyclic permutation matrices. Lemma 13. Consider a uniformly random cyclie permutation matrix II. Let us fix i + and + b. Then
E[[[[y] n-1
E[[I =
(isa-iih)
Hjsb-i ig [n 1)m=2)
+
(ipan1jyza)) (n- 1)(-33) + ((mmajjm))
(a- (n-
First, note that any matrix that corresponds to cyclic permutation does not contain fixed points and so the diagonal elements are deterministicallyy For the first item, the number of cyclic permutations such that i - j (i.e., I 1) is (n 2).. This implies that the desired expectation is (n - (0-/)///C,//= = 1/(n- 1). For the second item, if = a, j = b, we recover the first item. Otherwise if or j 6, then the expectation vanishes since we deal with permutation matrices. Finally, let us consider the case where + a and j # b. Our goal is to count the number of cyclic permutations with i + and - b.
Proof.
if * a * # o i, then there are choices place and n 2 choices to place a. Then there are (n - 4)! possible orderings for the remaining elements. This gives an expectation equal to 1/((n (n 3)).
if a j + oo + b = i o a, then there are n choices for i and (n 3)! orderings for the remaining elements. Hence, the expectation is 1/((n 1)(n 2)).
We note that sampling from our solution generators is the reason that we cannot find an optimal TSP solution efficiently. In general, algorithm that has converged to almost optimal parameter W has to generate samples from the Gibbs measure that is concentrated on cycles with minimum weight. In this low-ten now-temperature regime, sampling is Na-hard. We now ready to state our result.
Theorem 6 (TSP has Compressed, Efficiently Optimizable Solution Generator). Consider prior over TSP instances with n nodes. For any > O, there exists a solution generator P (p(w): : E W} such that P is complete, compressed with description poly(n) (olyll)l and L XR: W R. is efficiently optimizable via projected stochastic gradient descent poly(n, 1/e) steps for some X 0.
32

---

Proof. Consider an input graph G with nodes and weighted adjaceney matrix E. The feature vector again a permutation matrix II with the additional constraint that II has to represent single cycle (a tour over all cities). Then
TSP
min E II. mEC,
The cost function for TSP is L(II; = Ei Fay M,y We refer to Theorem 5 for the details about the feature mappings. We can finally use Lemma to obtain a variance lower bound (in the subspace induced by the parameters satisfying this lemma, see Remark 9) under the uniform measure over the space of cyclic permutation matrices C,.
H Sampling and Counting
In this section, we give quick overview of the connections between approximate sampling and counting. For formal treatment, we refer to [Sin12].
In what follows, a may be thought of an encoding of an instance of some combinatorial problem, and the of interest are encodings of the structures we wish to generate. Consider a weight function W and assume that (or,w) is computable in time polynomial in |o|.
Definition 4 (Approximate Sampling). A fully polynomial approximate sampler for (Sa Ta) is a Probabilistic Turing Machine which, on inputs and E Q+ (0 < c 11,,, outputs E E', according to a measure Po satisfying TT Po) S in time bounded by a bivariate polynomial in |o| and log()/)).
One of the main applications of sampling is to approximate integration. In our setting this means estimating (o) to some specified relative error.
Definition 5 (Approximate Integration). A fully polynomial randomized approximation scheme for (o) is a Probabilistic Turing Machine which on input a, c, outputs an estimate so that
Pr[Z/(1+ 2 < (1 + e)+ 2
and which runs in time polynomial in |a| and 1/E.
Definition 6 (Seli-Reducible Problems). An NP search problem is self-reducible the set of solutions can be partitioned into polynomially many sets each of which is one-to-one correspondence with the set of solutions of a smaller instance of the problem, and the polynomial size set of smaller instances are efficiently computable.
For instance, consider the relation MATCH which associates with undirected graph G all matchings (independent sets of edges) G. Then MATCH self-reducible since, for any edge = (u,v). E(G), we have that
MATCH(G) = MATCH(( U (M {e} M M2TC
where G1 is the graph obtained by deleting and G2 is the graph obtained be deleting both u and v together with all their incident edges.
Theorem (See Corollary 3.16 in [Sin12]). For self-reducible problems, approximate integration and good sampling are equivalent.
We remark that the above result holds for the more general class of self self-partitionable problems.
I Details of the Experimental Evaluation
We investigate the effect of the entropy regularizer (see Equation (2)) in a very simple setting: we try find the Max-Cut fixed graph G. i.e., the support of the prior R a single graph. We show that while the unregularized objective is often "stuck" at sub-optimal solutions and this happens even for very small instances (15 nodes) of the Max-Cut problem, the regularized version (with the fast/slow mixture scheme) is able to find the optimal solutions. We consider instance randomly generated by the Erdös-Rényi model G(n, p) and then optimize the "vanilla" loss and the regularized loss LA defined in Equation (3). The solutions are vectors E [+1]", We first use the feature mapping (s)(s) (ss T)' described in Section 1.1 and exponential family solution generator that samples
33

---

class Fast:louMixxure (torch mn. Module) def _..init__ (self, dimension, rho):
The Model parameters.
super .i._.iit__..
self .1 torch. nn P..Paammtteetorrccc empty dimension) torch mn init. www.in..aaiiinnn................ www.iiin__niiffm__ss_ssss 11, a=5*+0.5)
self 12 torch. www.:aa.aaaaeeeeeettttetteooo (torch empty (10, 30))
torch mn inwt. www....aiiiiiiinnn.....m wawpingnniiffommsssae_essse 12, a=5**0.5)
self 13 = torch. nn Pwr.metrrrrreereeeeemmamma (torch. empty 10))
torch mn initi.iitt.. kwinitt.iiiiinnniiii unifurm (self 13, a=5*+0.5)
R.rch.nn.RLLU self. a2
self al torch.nn.c ReLU
self rho = rho
def forward(self, x, is_cold-True):
temp self rho * (1. is_cold) is_cold
out
out torch nn functional linear (out, temp self .11)
self. al (out)
out torch, nn functional. linear (out, temp self 12)
out self a2 (out)
out torch. nn functional. .inear (out, temp self .13)
return out
Figure 4: Our implementation the fast/slow network. The output of the network the log-density (score) of solution E (+1) dimemeioon evaluated with the is-cold set to False, the parameters of every linear layer are re-scaled by the inverse temperature rho.
solution s with probability x exp(w +ss(s) for some weight vector w R= We also consider optimizing simple 3-layer ReLU network solution generator with input E {=1}" on the same random graphs. We generate 100 random G(n,, p) graphs with n = 15 nodes and p= 0.5 and train solution generators using both the "vanilla" and the entropy-regulariae 600 iterations and, for the entropy regularization, we progressively decrease the regularization weight, starting from 10, and dividing it by every 60 iterations. We used fast/slow mixing with mixture probability 0.2 and inverse temperature rho=0.03 (see Figure 4).
loss functions. We perform
For convenience, we present pytorch implementation of our simple 3-layer ReL.U network here. For more details we refer to our full code submitted in the supplementary material.
Out of the 100 trials we found that our proposed objective was always able to find the optimal cut while the model trained with the vanilla loss was able to find for approximately 65% of the graphs (for 65 out of 100 using the linear network and for 66 using the ReLU network). In Figure 2 we show two instances where the model trained with the "vanilla" loss gets stuck on a sub-optimal solution while the entropy-regue regulaaiee one succeeds in finding the optimal solution. Our experiments show that the regularization term and the fast/slow mixture scheme that we introduced to achieve our main theoretical convergence result, see Section 3 and Proposition 4, are potentially useful for training more realistic models for bigger instances and we leave more extensive experimental evaluation as an interesting direction for future work.
34

---

We note that, similarly to our theoretical results, our sampler in this experimental section is of the form ( where E {-1, 1 here is the number of nodes in the graph) is a candidate solution of the Max-Cut problem. The function used a 3-layer MLP (see Figure Figure 4). Since the instances that we consider here are small (n = 15) we can explicitly compute the density (score) of every solution and use that compute the expected gradient. For larger instances, one could use some approximate sampler (e.g., via Langevin dynamics) to generate samples. The main message of the current experimental section is that even for very small instances of Max-Cut (i.e., with 15 nodes), optimizing the vanilla objective is not sufficient and the iteration gets trapped in local optima. In contrast, our entropy regularized always manages to find the optimal cut.
35


Reviews:
[{"review_id": "zp4Ymku7o4", "reviewer": "Reviewer_jXn4", "summary": "This paper deals with a significant question at the intersection of combinatorial optimization and continuous-based optimization: is it possible to design solution generators for combinatorial problems that are (1) expressive enough to generate approximately optimal solutions, (2) tractable so that their parameterization is only polynomial in the number of inputs, and (2) efficiently optimizable so that only a polynomial number of stochastic gradient descent (SGD) steps is required to learn a parameterization with almost optimal performance? The paper answers this question in the affirmative. It develops a general framework that can be used to describe complete, compressed and efficiently optimizable solution generators, which can be instantiated to accommodate a wide range of NP-hard problems. The framework requires feature mappings for both the instances and the solutions tat have a number of desired properties. Assuming this is the case, the authors provide a very general positive result. The paper highlights two challenges related to the optimization. First, the loss function may accept a minimizer at infinity, so that gradient descent may get stuck to sub-optimal configurations. The authors address this by introducing an entropy regularization term. Second, vanishing gradients may slow down optimization, rendering it inefficient. This is addressed by introducing a mixture of a fast and a slow solution generator: the fast component helps to reach the optimal solution while the slow component helps to keep a non-zero variance throughout the optimization process, hence avoiding the problem of vanishing gradients. The authors provide experimental evidence in favor of their entropy regularizer and the fast/slow mixing scheme.", "questions": "1. Is this work only intended to theoreticians or to practitioners as well? If the latter is the case, then the authors would need to provide evidence for that claim, e.g., performance of their solution generators compared to other continuous solvers. I feel that this question is not answered in the current paper.\n2. On a similar note, the number of nodes n=15 used in the ablation study is small - could these methods scale to larger instances? Do the authors have any take-away messages for practitioners who may be interested in trying out such methods? Is it perhaps fair to say that the proposed framework mostly serves as an abstraction but without necessarily powerful practical implications?\n3. In the discussion of P vs. NP, the authors explain that sampling from their solution generators may be computationally expensive but add that technique based on Langevin dynamics may help to circumvent this issue in practice. It would be worthwhile for the authors to see whether such techniques would be of any help, especially with large instances.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The paper is extremely well-written. The authors have done an excellent job presenting in a simple yet rigorous manner the main insights behind their framework and the various design choices. Every single choice is adequately justified, which makes it very easy even for non-familiar readers to grasp the main messages of this work. I also liked the the fact that the authors took extra care to elucidate some potentially confusing aspects, e.g., with respect to the P vs. NP question.\n2. The main result requires very reasonable assumptions and is general enough to encompass several standard hard problems. \n3. The two proposed tricks (entropy regularization and fast/slow mixing scheme) are extremely well motivated but also justified theoretically. The ablation study at the end confirms their usefulness empirically.\n4. The framework is novel and a major part of its novelty precisely stems from its generality. \n5. Even though I was not able to check all math details, the part that I was able to check was free of problems.", "weaknesses": "1. I understand that the main focus of this work is to provide a generic framework with reasonable assumptions and strong performance guarantees. I feel that the authors have delivered on that premise. That said, readers may be left with the question: what is the true empirical potential of this framework, especially when we compare it to state of the art combinatorial neural solvers? After reading the paper, I was not really clear whether this work is mainly about introducing a generic framework, or if it was also about proving its practical value on various benchmarks. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe would like to thank the reviewer for the positive feedback and insightful questions.\n \n> - *I understand that the main focus of this work is to provide a generic framework with reasonable assumptions and strong performance guarantees. I feel that the authors have delivered on that premise. That said, readers may be left with the question: what is the true empirical potential of this framework, especially when we compare it to state of the art combinatorial neural solvers? After reading the paper, I was not really clear whether this work is mainly about introducing a generic framework, or if it was also about proving its practical value on various benchmarks.*\n>\n>\n>- *Is this work only intended to theoreticians or to practitioners as well? If the latter is the case, then the authors would need to provide evidence for that claim, e.g., performance of their solution generators compared to other continuous solvers. I feel that this question is not answered in the current paper.*\n\n*Response:* In this work, we present a general framework for establishing **theoretical** understanding regarding challenging and fundamental combinatorial problems such as Max-Cut, TSP, and Max-$k$-CSP. Hence, our work is mainly intended for theoreticians and we leave more extensive experimental evaluation of our work as an interesting question for future work.\n\nHowever, as our simulations (see also the additional experiments on larger instances provided in this rebuttal) show that some of the insights we obtain as a byproduct of our theoretical proof of convergence may be of practical significance. Moreover, we would like to point out an interesting connection between our theoretical work and a prior experimental paper. The work of Kim et al. (2021) uses an entropy maximization scheme in order to generate diversified candidate solutions. This experimental heuristic is quite close to our theoretical idea for entropy regularization. In our work, entropy regularization allows us to design quasar-convex landscapes and the fast/slow mixing scheme to obtain diversification of solutions.\n\n[Kim, Park, Kim, Learning Collaborative Policies to Solve NP-hard Routing Problems, 2021]\n\n>- *On a similar note, the number of nodes $n=15$ used in the ablation study is small - could these methods scale to larger instances? Do the authors have any take-away messages for practitioners who may be interested in trying out such methods? Is it perhaps fair to say that the proposed framework mostly serves as an abstraction but without necessarily powerful practical implications?*\n>- *In the discussion of P vs. NP, the authors explain that sampling from their solution generators may be computationally expensive but add that techniques based on Langevin dynamics may help to circumvent this issue in practice. It would be worthwhile for the authors to see whether such techniques would be of any help, especially with large instances.*\n\n*Response:* We refer to our previous answer and the additional simulations in the general response. In our additional simulations, we implemented our method using approximate samplers based on Langevin dynamics to circumvent this issue.  Given that even in larger instances our method outperforms the vanilla objective we are optimistic that our theoretical insights are going to be of practical significance."}, {"review_id": "nMtKVNphSH", "reviewer": "Reviewer_VMa2", "summary": "This paper proposes a theoretical framework for analyzing the effectiveness of deep models trained by gradient-based methods as solution generators for combinatorial problems. The authors first investigate the complete, compressed and efficiently optimizable properties of the solution generator on many combinatorial tasks. To address the challenges of minimizers at infinity and vanish gradients, the authors devise an entropy regularization and a fast/slow mixture generation scheme. Experiments demonstrate that the proposed method helps address vanishing-gradient issues and escape bad stationary points.\n", "questions": "1. Could you please give some examples of combinatorial problems that do not satisfy Assumption 1?\n2. Could you please provide more details on the representations of input data, such as the input features and data format?", "limitations": "Assumption 1 might be difficult to check for a general combinatorial problem, which may limit the applicability of the theoretical results in this paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper gives a positive answer to the existence of complete, compressed and efficiently optimizable solution generators for combinatorial tasks, and it designs a family of such solution generators.\n2. The paper addresses the challenges of minimizers at infinity and vanishing gradients by the proposed entropy regularization and fast/slow mixture generation scheme.\n3. A general and solid foundational theorem (Theorem 1) is clearly presented.\n", "weaknesses": "1. The authors may want to conduct experiments on more combinatorial problems with larger scales to demonstrate the effectiveness of the proposed method.\n2. The authors analyze the existence and properties of the feature mappings for the solutions and instances, but how to learn such mappings remains unexplored.\n3. The authors apply MLP to combinatorial problems with a fixed number of graph nodes. However, MLPs fail to process instances with varying scales. The authors may want to consider more suitable models such as the graph neural network (GNN).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the very positive feedback and the provided questions.\n\n> *The authors may want to conduct experiments on more combinatorial problems with larger scales to demonstrate the effectiveness of the proposed method.*\n\n*Response:* We kindly refer to our general response about experimental evaluation on large instances for Max-Cut. As a direct future direction we aim to extend our experiments to other interesting combinatorial problems.\n\n\n> *The authors apply MLP to combinatorial problems with a fixed number of graph nodes. However, MLPs fail to process instances with varying scales. The authors may want to consider more suitable models such as the graph neural network (GNN).*\n\n*Response:* We agree with the reviewer that GNNs are more suitable for such tasks and plan to use them in future experimental evaluation of our work. Since our current work is primarily theoretical, we tried to keep our simulations as simple as possible (we do not aim to improve over SOTA methods for NCO). \n\n\n> *Could you please give some examples of combinatorial problems that do not satisfy Assumption 1?*\n\n*Response:* An interesting combinatorial problem not captured by our framework is SAT.\n\nGiven a combinatorial problem, Assumption 1 essentially asks for the **design** of feature mappings for the solutions and the instances that satisfy desiderata such as boundedness and variance preservation.\n \nMax-Cut, Min-Cut, TSP and Max-$k$-CSP and other problems satisfy Assumption 1 because we managed to design appropriate (problem-specific) feature mappings (see Section 2) that satisfy the requirements of Assumption 1. \n\nThere are interesting combinatorial problems for which we do not know how to design such good feature mappings. For instance, the \"natural\" feature mapping for the Satisfiability problem (SAT) (similar to the one we used for Max-$k$-CSPs) would require feature dimension exponential in the size of the instance (we need all possible monomials of $n$ variables and degree at most $n$) and therefore, would violate item 4 of Assumption 1.\n\n\n> *Could you please provide more details on the representations of input data, such as the input features and dataformat?*\n\n*Response:* At each iteration, the input is an instance (e.g., a graph). A potential representation of the graph is the Laplacian matrix (e.g., in Max-cut). Hence, the input features are a collection of Laplacian matrices. We note that the input features depend on the combinatorial problem in hand.\n\n\n> - *The authors analyze the existence and properties of the feature mappings for the solutions and instances, but how to learn such mappings remains unexplored.*\n> \n> - *Assumption 1 might be difficult to check for a general combinatorial problem, which may limit the applicability of the theoretical results in this paper.*\n\n*Response:* In this work, we present a general framework for establishing the first theoretical understanding regarding challenging and fundamental combinatorial problems. Assumption 1 allows for our framework to be quite general and expressive. The mildness of our Assumption is justified by the number of problems it captures (Max-Cut, TSP, and Max-$k$-CSP). We emphasize that the featured mappings for the instances and the solutions correspond to a design problem; in our work, we designed appropriate feature mappings for Max-Cut, TSP and other combinatorial problems. Hence, it is not exactly the case that Assumption 1 is hard to check; the challenge is to design good feature mappings, which currently is a problem-specific task. Designing principled ways to find these mappings is an interesting direction. \n\n"}, {"review_id": "5cCpsSQk7r", "reviewer": "Reviewer_m1vy", "summary": "The paper provides a theoretical analysis of policy-gradient methods for combinatorial optimization problems. It defines a set of three desirable properties one might wish to be fulfilled for such a property, namely being able to generate an approximately optimal solution, being small in size, and enabling efficient optimization via SGD. The main result of the paper is to prove that there exists a policy gradient method satisfying all three properties simultaneously. The proposed method is general enough to capture many well-known combinatorial optimization problems. A small empirical study is provided, too.", "questions": "- line 73: why is this the gradient? Please provide some explanation. In particular: where does the logarithm come from?\n- line 75: what do you mean by \"using only access to a solution cost oracle\"? Do you want to point out that something particular is not used? If so, what? I suppose you also need to be able to sample $I$ and $s$ according to their respective distributions, and you need to be able to compute the gradient of $log(p(s;I;w))$ w.r.t. $w$.\n- line 96: what is the \"description size of the parameter space $\\mathcal{W}$\"? Is it the number of bits required to represent any parameter $w\\in \\mathcal{W}$? But then, $\\mathcal{W}$ is a finite set, so how can you ever perform gradient descent on it?\n- line 99: why do you allow running time polynomial in $1/\\epsilon$, but the parameter space must be polynomial in $\\log(1/\\epsilon)$?\n- line 107: I do not understand what \"the full parametrization of all distributions over the hypercube\" is. There are uncountably many such distributions, so how can you ever represent them in a set $\\mathcal{W}$ of finite description size?\n- Remark 5: Is this a formal statement or an intuitive statement? I really would like to see more details about how exactly the cited paper implies a negative result for neural network solution samplers in the setting of your paper.\n- Remark 6: What if I WANT to encode the weights into the instances? I suppose you would it call \"known\" weights then. But it is less clear how to define the feature maps then and still preserve bilinearity. I do not see why what you call \"unknown\" weights is the more general / difficult case.", "limitations": "In principal, the authors provide all details required to understand the scope of their results. The discussion on limitations could be improved by answering the following two questions:\n- Are there natural combinatorial optimization problems to which the framework is not applicable? If so, which problems, and why?\n- It seems like the proposed method is theoretically superior to what people use in practice. Is this true? And if so, why is it not the standard method in practical settings nowadays? Do you expect it to become that?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I think the idea behind this work is great. Theoretical foundations for reinforcement learning methods applied to CO problems are highly needed. Defining a set of desirable properties and analyzing whether and how they can be satisfied simultaneously seems to be the right approach.", "weaknesses": "Since I believe that the contributions of this paper are great, I feel really sorry that I cannot give a more positive evaluation at the moment. I try to give as much constructive feedback as possible and encourage the authors to revise the manuscript and, if not accepted here, resubmit to another top venue. My main concern is:\n- I have a few mathematical issues / questions, where I do not understand the paper. I think one source of these issues is that the model of computation is not well-defined. The authors wildly switch between bit-representations and real models of computation. To solve these issues, the authors should clearly define in which model of computation they work and make all assumptions / requirements / statements consistent with this model. There are a few more unrelated issues, see my more specific questions in the \"Questions\" section.\n\nApart from that, I have a whole bunch of secondary comments, see below:\n- I think the paper (implicitly and sometimes explicitly) oversells the contribution of [BPL+16] to amplify the motivation for their own work. So far, reinforcement learning is NOT a state-of-the-art method for combinatorial optimization problems like TSP. The work of [BPL+16] is great as a proof of concept, but statements like \"[BPL+16] [...] generate very good solutions for (Euclidean) TSP instances\" without mentioning that these are very small toy problems should be avoided. I think the fact that NNs for CO are still in their beginnings should be pointed out more clearly and the motivation of this paper should build upon a larger variety of prior work than only [BPL+16].\n- line 103: I suppose you want to refer to Def. 2 and not to Qu. 1 here (in particular, because otherwise you refer to Qu. 1 before even stating it).\n- line 143: I find it more natural to write this with $L(s,I)$ instead of $\\mathcal{O}(s,I)$. I understand that this is the same by definition, but here the focus is more on the cost structure and less on the fact that such an oracle exists. Maybe one could even drop the notation $\\mathcal{O}(s,I)$ everywhere in the paper and use always $L$? In Definition 1, one could instead just write in words that such an oracle exists.\n- line 196: I feel that the split into supervised and unsupervised models here is very artificial because papers in both categories apply sophisticated algorithms mixing very different paradigms. I doubt that the negative result [YGS20] is directly applicable to the settings of the three papers you cite for the supervised case. I suggest not to artificially split the related work into these two categories.\n- Related work: even though of a very different flavor, I think the following two papers about the theoretical ability of neural networks to solve CO problems should be discussed in the related work section: Hertrich, C., & Skutella, M. (2023). Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS Journal on Computing. AND: Hertrich, C., & Sering, L. (2023). ReLU neural networks of polynomial size for exact maximum flow computation. In International Conference on Integer Programming and Combinatorial Optimization.\n- line 219: please either provide a proof or a reference for the reformulation of the MaxCut problem via the Laplacian.\n- line 241: say that Thm. 4 is in the appendix.\n- line 246: a unknown -> an unknown. Also the whole sentence is a bit hard to read, maybe split into two?\n- line 286: \"the point $\\bar{W}=-\\tau M$ when $\\tau\\rightarrow+\\infty$\" is not a point. What you write here is not mathematically precise, even though I understand what you mean. Consider revising.\n- lines 323/324: I recommend a comma between \"fast\" and \"making\".\n- line 344: there is a \"to\" too much (between \"we\" and \"pick\").\n- line 382: you should not assume that everyone knows what $G(n,p)$ is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer (i) for finding the contribution of our paper great and for providing extensive constructive feedback, (ii) for pointing out various typos in the current draft, which we will fix in our first revision and (iii) for proposing additional references and suggestions for the Related Work section; we added the papers' for a more complete and detailed exposition. We continue by explicitly addressing the reviewer's questions.\n\n> I think the paper (implicitly and sometimes explicitly) oversells the contribution of [BPL+16] ...\n\nThe work of  [BPL+16] is the (experimental) work that introduced the framework of Neural Combinatorial Optimization. Our work is the first theoretical approach to design a rigorous and principled way to study and argue about the fundamental questions behind this problem. Hence, we chose to design our theoretical framework on top of this (arguably) well-accepted work. We do not claim that the experimental results of  [BPL+16] are SOTA. However, we find that this work is the simplest and most natural setting to go from a completely practical to a rigorous theoretical framework. Hence, our work does not build on the experimental contribution of  [BPL+16] (as the reviewer correctly mentions there are various follow-up works that improve on this front) but builds on the conceptual contribution of  [BPL+16] providing the first formal theoretical guarantees. We will clarify the fact that the results of  [BPL+16]  are for smaller instances.\n\n> Line 219\n\nThis is standard, see e.g., Spielman (2010). We will add a reference, as the Reviewer proposes.\n\n[Spielman, Algorithms, graph theory, and linear equations in Laplacian matrices, 2010]\n\n> Line 73\n\nThis is the standard expression for policy gradient, for the reference see e.g., Section 2 and 5 in the paper of Kakade (2001) as we mention in our manuscript and for a proof see the book by Szepesvári (2022).\n\n[Kakade, A natural policy gradient, 2001]\n\n[Szepesvári, Algorithms for reinforcement learning, 2022]\n\n> Line 75\n\nOne does not need access to an explicit representation of the cost function (e.g., the Laplacian matrix of the Graph in the Max-Cut problem) but only black box access to the cost oracle (i.e., the values of the function).\n\n> Model of Computation\n> \n> Line 96\n\nGradient descent is not explicitly performed on a finite set – it is just the rounding of the iterates (due to finite memory in its implementation) that implicitly makes the set discrete.  Our description size captures exactly this finite precision issue. Say we require $d$ parameters for the parameter space of gradient descent; then a description size of $O(d \\log(1/\\epsilon))$ would mean that when you implement gradient descent you should use $O(d \\log(1/\\epsilon))$ bits for the representation of its iterates (roughly $\\log(1/\\epsilon)$ bits for each parameter).  Since the loss that we use is $\\mathrm{poly}(d)$-Lipschitz with respect to the parameter $w$ (assuming that $w$ belongs in the continuous space), rounding the iterates of Gradient descent to $O(d\\log(1/\\epsilon))$ bits does not introduce substantial error. We performed the analysis of gradient descent in the real-valued model for simplicity; we will add a remark on this in our updated manuscript.\n\n> Line 99\n\nAs it is standard in the optimization literature (see e.g., Bubeck (2015)), we cannot hope for truly polynomial dependence on $1/\\epsilon$ unless the objective enjoys some special structure such as strong convexity. To this end, we settle for the natural $\\mathrm{poly}(1/\\epsilon)$ dependence. In contrast, we stress that the parameter space should be of truly polynomial size, i.e. polynomial in $\\log(1/\\epsilon)$. \n\n[Bubeck, Convex optimization: Algorithms and complexity, 2015]\n\n> Line 107\n\nEach point of the hypercube corresponds to a cut in the graph. The full parametrization corresponds to assigning a single parameter to any possible cut (which are exponentially many). The description is finite due to the finite precision requirement (see also our response to the previous question regarding finite precision).\n\n> Remark 5\n\nAs our wording of Remark 5 shows this is a high-level/intuitive statement. The fact that optimizing (even simple) two layer neural networks is computationally intractable indicates that end-to-end optimization of deep solution samplers that can generate samples efficiently (in polynomial-time) is most likely impossible.  For more evidence we remark that having an efficient (and “small”, i.e., with polynomial number of parameters) neural network sampler that can also be provably optimized via gradient descent in polynomial iterations would imply a polynomial-time algorithm for the problems considered in this work (e.g., for Max-Cut) which is a well-known NP-hard (even to approximate) problem.\n\n> Remark 6\n\nLet us consider the weighted Max-Cut problem, with known weights. In this case, one can take the weighted Laplacian matrix and again express the loss function in the exact same form as in the unweighted case. Then the feature mappings are exactly the same.\n\n> Are there natural combinatorial optimization problems to which the framework is not applicable? If so, which problems, and why?\n\nWe kindly refer to our response to Reviewer VMa2.\n\n> It seems like the proposed method is theoretically superior to what people use in practice. Is this true? And if so, why is it not the standard method in practical settings nowadays? Do you expect it to become that?\n\nYes, our method is theoretically superior to the vanilla objective as the additional reguralization and the fast/slow mixture generators help avoid minimizers at infinity and vanishing gradients (see Section 3 of our manuscript). Our preliminary experimental evaluation indicates that some of our theoretical insights (entropy regularization, fast/slow mixing) leads to better performance. We also kindly refer to our response to Reviewer jXn4."}, {"review_id": "iUNAbZhPXI", "reviewer": "Reviewer_dPn4", "summary": "The paper presents a thorough consideration on the parametrization of optimizable solution generators that allow using gradient descent to find solutions for combinatorial optimization methods. They find a set of assumptions that enable complete, compressed and efficiently optimizable representations, in particular existence of feature maps of solution and instances onto bounded (norm, diameter and dimensionality) and variance preserving feature spaces which allow for a bilinear cost oracle $c(I,S)=f_I^T M f_S$ for instance/solution features $f_I/f_S$ and a matrix $M$ s.t. $\\Vert M \\Vert_F\\$ is bounded by a constant $C$.\n\nThe implications of this result (including the existence of such parametrizations for TSP) are discussed, notably that existance of such generators does not mean P=NP since sampling from the generator might still take exponential time.\n\nThe theory is developed on max/min cut, max-k-CSP, max-weight BP matching and TSP and experimentally evalauted on max-cut", "questions": "None", "limitations": "I think everything was addressed", "rating": 10, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Originality: I love this paper for taking the obvious in hindsight question for actually asking what types of representations make combinatorial optimisation via first order methods work on a *principles* basis\nClarity: The paper is superbly written and conveys it's ideas and limitations well\nQuality: while I did not have the time to carefully check every brief, on a cursory reading they appear to make sense and align well with intuitions.\nSignificance: I think this paper will completely change how the deep learning community will think about dealing with combinatorial optimization (or at least I hope so)", "weaknesses": "I cannot point to any", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe are very encouraged from the very positive feedback of the reviewer and their excitement about our work and potential impact.  We are also very excited about our work and believe that our work will initiate a principled theoretical study of neural combinatorial optimization and its theoretical insights will be of practical significance."}]

Author rebuttal:
**General Response**

We thank all reviewers for taking the time to read our manuscript carefully and for providing constructive and insightful feedback. We are very encouraged by the positive comments of the reviewers on the novelty and significance of our theoretical framework for Neural Combinatorial Optimization (Reviewers jXn4, dPn4), theoretical contributions (Reviewers m1vy, dPn4) and the writing quality and the clarity of the presentation of the ideas (Reviewers jXn4, VMa2, dPn4). 

We provide detailed responses to each reviewer separately. We look forward to engaging in further discussion with the reviewers, answering questions, and discussing improvements. 

Before that, we start with a general comment where we provide detailed additional experimental results on large instances.


**Additional Simulations - Larger Instances/Approximate Samplers**


Our experiments in the paper (which do not need Langevin dynamics for sampling) showed that even for very small instances of Max-Cut (i.e., with 15 nodes), optimizing the vanilla objective is not sufficient and the iteration gets trapped in local optima. In contrast, our method using entropy regularization always manages to find the optimal cut. A natural question raised by the reviewers is whether this improvement is also apparent in larger graphs.

We focus on the case of random $d$-regular graphs with $n$ nodes. It is well-known that for this family of graphs, with high probability as $n \to \infty$, the size of the maximum cut satisfies $\mathrm{MaxCut}(G(n,d)) = n(d/4 + P_\star \sqrt{d/4} + o_d(\sqrt{d})) + o(n)$, where $P_\star \approx 0.7632$ is a universal constant [Dembo et al., 2017].

We aim to find a good approximation for the normalized cut-value, defined as $(\mathrm{cut\_value}/n - d/4)/\sqrt{d/4}$, which (roughly speaking) takes values in $[0,P_\star]$.

We obtain approximate random samples from the density $e^f$ using the Metropolis-Adjusted Langevin Algorithm (MALA). In particular, an approximate sample from this density is obtained by the Euler–Maruyama method for simulating the Langevin diffusion: $x_{k+1} = x_k + \tau \nabla f(x_k) + \sqrt{2\tau} \xi_k$, where $\xi_k$ is an independent Gaussian vector $\mathcal{N}(0,I)$. MALA incorporates an additional step based on the Metropolis-Hastings algorithm (see [Besag, 1994, Song and Kingma, 2021]). In our case, the score function $f$ is a simple 3-layer ReLU network. 

**In our additional experiments for 3 larger random regular graphs (600 nodes) using the fast/slow mixing technique along entropy regularization we see that our method leads to improvements over the vanilla objective.** Plots of the trajectories of the vanilla and our method can be found in the figures provided in the pdf of the rebuttal. In the horizontal axis we plot the iterations and in the vertical axis we plot the normalized cut score of each method (higher is better) -- we stop the plot of the vanilla trajectory after 200 iterations because we observed that its output has fully converged and is stuck.

[Dembo, Montanari and Sen, Extremal cuts of sparse random graphs, 2017]

[Besag, Comments on “Representations of knowledge in complex systems” by U. Grenander and MI Miller, 1994]

[Song and Kingma, How to train your energy-based models, 2021]


Meta-review: The reviewers have provided a thorough evaluation of the paper and have generally agreed on its strengths and potential impact. The paper presents a novel theoretical framework for analyzing the effectiveness of deep models trained by gradient-based methods as solution generators for combinatorial problems. The authors have done an excellent job in presenting their work and justifying their design choices. The paper is well-written and the main insights are presented in a simple yet rigorous manner. 

The reviewers have raised some concerns and questions, mainly related to the practical implications of the framework and its scalability. However, these concerns do not undermine the theoretical contributions of the paper. The authors are encouraged to address these concerns in their final version of the paper or in future work.

Overall, the paper is technically solid and has the potential to have a high impact on the field. The theoretical contributions are significant and the paper is well-positioned to stimulate further research in this area. Therefore, I recommend accepting this paper.
Decision: Accept (oral)