SurCo: Learning Linear Surrogates for Combinatorial Nonlinear Optimization Problems
Authors: Aaron M Ferber
Taoan Huang
Daochen Zha
Martin Schubert
Benoit Steiner
Bistra Dilkina
Yuandong Tian
Venue: Submitted to ICLR 2023 (2023)
Keywords: Differentiable Optimization
Machine Learning
Nonlinear Optimization
Combinatorial Optimization

Abstract: Optimization problems with expensive nonlinear cost functions and combinatorial constraints appear in many real-world applications, but remain challenging to solve efficiently. Existing combinatorial solvers like Mixed Integer Linear Programming can be fast in practice but cannot readily optimize nonlinear cost functions, while general nonlinear optimizers like gradient descent often do not handle complex combinatorial structures, may require many queries of the cost function, and are prone to local optima. To bridge this gap, we propose SurCo that learns linear Surrogate costs which can be used by existing Combinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We learn these linear surrogates end-to-end with the nonlinear loss by differentiating through the linear surrogate solver. Three variants of SurCo are proposed: SurCo-zero operates on individual nonlinear problems, SurCo-prior trains a linear surrogate predictor on distributions of problems, and SurCo-hybrid uses a model trained offline to warm start online solving for SurCo-zero. We analyze our method theoretically and empirically, showing smooth convergence and improved performance. Experiments show that compared to state-of-the-art approaches and expert-designed heuristics, SurCo obtains lower cost solutions with comparable or faster solve time for two real-world industry-level applications: embedding table sharding and inverse photonic design.

Under review as a conference paper at ICLR 2023
SURCo: LEARNING LINEAR SURROGATES FOR COM- BINATORIAL NONLINEAR OPTIMIZATION PROBLEMS
Anonymous authors
Paper under double-blind review
ABSTRACT
Optimization problems with expensive nonlinear cost functions and combinato- rial constraints appear many real-world applications. but remain challenging solve efficiently. Existing combinatorial solvers like Mixed Integer Linear Pro- gramming can be fast in practice but cannot readily optimize nonlinear cost fune- tions, while general nonlinear optimizers like gradient descent often do not handle complex combinatorial structures, may require many queries of the cost function, and prone to local optima. To bridge this gap, we propose SurCo that learns linear Surrogate costs which can be used by existing Combinatorial solvers to output good solutions the original nonlinear combinatorial optimization prob- lem, combining the flexibility of gradient-basee methods with the structure of lin- ear combinatorial optimization. We learn these linear surrogates end-to-end with the nonlinear loss by diffcrentiating through the linear surrogate solver. Three variants of SurCo are proposed: SurCo-zero operates on individual nonlinear problems, SurCo-prine for trains linear surrogate predictor on distributions of problems, and SurCo-hybrid uses model trained offline to warm start online solving for SurCo-zero. We analyze method theoretically and empirically, showing smooth convergence and improved performance. Experiments show that compared to state-of-the-art approaches and expert-designed heuristics, SurCo obtains lower cost solutions with comparable or faster solve time for two real- world industry-level applications: embedding table sharding and inverse photonic design.
INTRODUCTION
Combinatorial optimization problems with linear objective functions, like linear programming (LP) (Chvatal et al. 1983) and mixed integer linear programming (MILP) (Wolsey) 2007), have been extensively studied in operations research (OR). The resulting high-performance solvers like Gurobi (Gurobi Optimization, LLC LLC| (022) can solve industrial-scale optimization problems with ten of thousands of variables in few minutes.
issue remains: the cost functions f(x:) in many practical problems are nonlinear, and the highly-optimize solvers mainly handle linear or convex formu- lations while real-world problems have less constrained objectives. For example, in embedding table sharding (Zha et al. (022a) one needs to distribute embedding tables to multiple GPUs for the deployment of recommendation systems. Due to the batching behaviors within a single GPU and communication cost among different GPUs, the overall latency (cost function) in this application depends on interactions of multiple tables and thus can be highly nonlinear (Zha et al. 2022a).
However, with perfect solvers,
To obtain useful solutions to the real-world problems, one may choose to directly optimize the nonlinear cost, which is either a black-box output of simulator (Gosavi et al., 2015) Ye et al.) 2019), or a cost estimator learned by machine learning techniques (e.g.. deep models) from offline data (Steiner al., 2021 Koziel et al., 2202 1 Wang et al., 2021b Cozad et al. 2014). However, many of these direct optimization approaches either rely human-defined heuristics (e.g., greedy (Korte)
& Hausmann 1978; Reingold & Tarjan 1981 Wolsey 1982). local improvement VoB et al. 2012
Li al. 2021). ), resort to general nonlinear optimization techniques like gradient descent (Ruder
2016), reinforcement learning (Mazyavkina et al.) 202I), or evolutionary algorithms (Simon) 2013).
While these approaches work in practice, they may lead to slow optimization process, in

---

Under review as a conference paper at ICLR 2023
particular when the cost function is expensive to evaluate, and they often ignore the combinatorial nature of most real-world applications (encoded in the feasible set a E 22..
In this work, propose systematic framework SurCo that leverages existing efficient combi- natorial solvers to find solutions to nonlinear combinatorial optimization problems arising in real- world scenarios. There are three versions of SurCo, SurCo-zero, SurCo-prior and SurCo- hybrid. In SurCo-zero, given nonlinear differentiable cost f(z) to be minimized, we optimize linear surrogate cost é so that the surrogate optimizer (SO) min è outputs solution that is expected to be optimal w.r.t. the original nonlinear cost f(x). Due to its linear nature, SO can be solved efficiently with existing solvers, and the surrogate cost è can be optimized in an end- to-end manner by back propapropgg through the solver (Pogančić et al. 2019; Niepert et al., [202]] Berthet et al., 2020).
SurCo-pri or, we consider family of nonlinear differentiable func- tions [2; y), where y parameterizes problem descriptions. We train the linear surrogate e(y) on set of optimization problems (called the training set {v:}) and evaluate on a held-out problem y'. by directly optimizing SO: x² (3/) := arg minge ê (y')x, which avoids optimizing the cost f(;; 3²) from scratch. Finally, in SurCo-hybrid we use initial surrogate costs predicted by fully-trained SurCo-pri or and then fine-tune the surrogate costs further using SurCo-zero to leverage both domain knowledge synthesized offline and information about the specific instance.
All versions of CurCo are evaluated in two real-world nonlinear optimization problems: embedding table sharding (Zha et al. 2022a), and photonic inverse design (Schubert et al. (022). In both cases, we show that in the on-the-fly setting, SurCo achieves higher quality solutions in comparable or less runtime, faster optimization in wall-clock time with lower solution cost, thanks to the help of an efficient combinatorial solver; in prior, our method obtains better solutions in held-out problems compared to other methods that require training (e.g., reinforcement learning). More specifically, in table sharding SurCo-zerr ro obtains between 14% to 85% improvement in solution quality with between 2% and 23% increase in runtime overhead compared to the greedy baseline, SurCo-pri obtains between 47% and 71% solution quality improvement against the state of the art RL-based table sharding algorithm Zha al. (2022b). SurCo-hybrid obtains better solutions than either SurCo-zezt or SurCo-prior, with similar runtime overhead as SurCo-zero. In photonic inverse design, SurCo-zero finds 21% more viable solutions for the beam splitter and twice as many solutions for the wavelength demultiplexers with all problems solving successfully for the mode converter and bend problems, taking between 10% to 64% less time than the pass-through approach from previous work (Schubert et al., 2022). While the offline trained SurCo-pri or misses some optimal solutions in the different settings, it frequently obtains solutions in 0.5% to 2% of the runtime due to not needing evaluate the objective and perform gradient steps. Again, hurCo-hybri iirridd d is able to obtain solutions more often than the other approaches, with a runtime overhead comparable to SurCo-zero, We additionally present theoretical results that help motivate why training model to predict surrogate linear coefficients exhibits better sample complexity than directly predicting the optimal solution (Li et al. 2018 Ban & Rudin 2019)
PROBLEM SPECIFICATION
Our goal is to solve the following nonlinear optimization problem describe by y:
min (a; y)
S.L. x E P(y)
where 2 E R are the variables to be optimized, f(x;; y) is the nonlinear differentiable cost function to be minimized, f2y)) is the feasible region, typically specified by linear (in)equalities and integer constraints, and y E Y are the problem instance parameters drawn from distribution D over Y. For example, in the traveling salesman problem, can be the distance matrix among cities. We often consider solving a family of optimization problems, described as y E Y.
Differentiable cost function. The nonlinear cost function fæ; y) can either be the result of a simulator made differentiable via finite differencing (e.g., JAX (Bradbury et al., 2018)), or cost model that is learned from an offline dataset, often generated via sampling multiple feasible solutions within Pyy), and recording their costs. The cost model often takes the form of deep neural network. In this work, assume the following property of f(:; y):
Assumption 2.1 (Cost function). During optimization, the cost function f(x; y) and its partial derivative Of da are accessible.
2

---

Under review as a conference paper at ICLR 2023
Learning good nonlinear cost model f is highly non-trivial for practical applications (e.g., Al- phaFold @Jumper et al. 2021). Density Functional Theory (Nagai et al. 2020), cost model for em- bedding tables (Zha et al. 2022a)) and is beyond the scope of this work.
Evaluation Metric. In real-world applications, querying f can slow and expensive, and thus a lower number of queries while getting better quality solution is the goal. We mainly focus on two aspects: how good the solution & is, by checking the value of fă; y), and how many queries of the nonlinear function f are needed during optimization in order achieve the solution at
Linear/nonlinear cost function. When s(æ; y) is linear w.r.t æ, and the feasible region can be encoded using mixed integer programs other mathematical programs, the problem can be solved efficiently using existing scalable optimization solvers. When f(;; y) is nonlinear, we propose SurCo that learns surrogate linear objective function, which allow us leverage these existing scalable optimization solvers, and which results in solution that has high quality with respect to the original hard-to- to-eoo-- objective function (æ: y). We will elaborate in the following sections.
Nonlinear optimization with combinatorial constraints
Surrogate optimization
min f x
x' (v) = argmin c(y)
Predict surrogate cost = c(y)
x
s.t S.t
t x E Ω
combinatorial
solved by existing combinatorial solvers
(t) optimizes yx; as much possible
Figure Overview our proposed algorithm SurCo.
3 SURCo: LEARNING LINEAR SURROGATES
3.1 SURCO-2FRO: ON-THE-FLY OPTIMIZATION
We start from the simplest case in which we focus on single instance with f(x) f(æ; y) and
Q = ())). SurCo-zero aims to optimize the following objective:
(SuzCo-zero): min (z)ro()) == (gg((c)
(2)
where the surrogate optimizer 92 R" + R" is the output certain combinatorial solvers with linear cost weight E R and feasible region Ω R". For example, In be the following (n is the number of variables to be optimized):
(c( == arg min e s.t. ZE {Ax < b, a Z"}
(3)
which is the output of MILP solver. Thanks to previous works (Ferber et al. 2020 Pogančié et al., 2019) we can efficiently compute the partial derivative @ga(c)/Oe. Intuitively, this means that (c) can be buckpropagated through.
Since is also differentiable with respect to the solution is evaluating, we thus can optimize Eqn.
öga 0r an end-to-ent manner using any gradient- optimizer. That is, c(t + 1) c(t) a de öx where a is the learning rate. The procedure starts from randomly initialized c(0) and converges at local optimal solution of e.
While Eqn. 2 still nonlinear optimization and there is guarantee about the quality of the final solution C, we argue that optimizing Eqn. is better than optimizing the original nonlinear cost minger f(x). Furthermore, while we cannot guarantee optimality, we are able guarantee fea- sibility by leveraging a linear combinatorial solver. We note that SurCo somewhat limited to problems without interior integer solutions, since the linear surrogate cannot yield interior points. However, many rorldworld settings, such as our two domains, consider making binary decisions which lack interior integer points. Intuitively, instead of optimizing directly over the solution space
3

---

Under review as a conference paper at ICLR 2023
a, we optimize over the space of surrogate costs c, and delegate the combinatorial feasibility require- ments of the nonlinear problem to SoTA combinatorial solvers. Compared to naive approaches that directly optimize f(x) via general optimization techniques, constraints of the feasible regions, and thus makes the optimization procedure easier. Furthermore, it also helps escape from local minima, thanks to the embedded search component of existing com- binatorial solvers (e.g., branch-and-boum (Land & Doig 2010) in MILP solvers). As we see in the experiments, this is particularly important when the problem becomes large-scale with more local optima. This approach works well when we are optimizing individual instances and may not have access to offline training data or the training time cost- costtprohibitive.
method readily handles complex
3.2 SURCO-PRIOR, OFFLINE SURROGATE TRAINING
We now discuss more general cases, where the nonlinear loss function f(:; y) represents family of cost function to be optimized. Here the description of each problem instance y is drawn from a fixed problem distribution D. We then ask the following question: how can we find solutions to batch of training instances Derain == {yx j gain useful knowledge of the cost functions, and leverage such knowledge in held-out evaluation problem instances Deval to accelerate the optimization procedure?
Following standard machine learning practice, let us first consider a naive two-stage approach. In the data collection stage, we simply apply SurCo-zero(Eqn, 2 every y; separately to get N surrogate cost vectors c. Then in the training stage, we train a regressor è = č(y; 0) on the dataset (1y,, c;)) to learn to predict the surrogate costs from the problem features. Here é is a parameterized model (e.g., a deep network) with the parameters O to be learned. This learned regressor č(y; 0) can thus be used for held-out problem instance y' to directly predict c' = č(y'; 0) and get the solution x' " ) (c') via surrogate optimizer (SO).
While this approach simple, the N optimization procedures in the data collection stage are inde- pendent of each other, and can lead to excessive number of calls to f that are not helpful. E.g., if an optimization procedure converges to a bad local solution, then even if it achieves perfect conver- gence, which requires a lot of function calls, the resulting data point is still of low quality.
This motivates us to add a regularizer for the optimization:
(SurCo-prior-A):
min Cprior (0, (ci]:))= = Σ (() - 0():1)))l (4) 0,(0))
1=1
Note that when x = O, it reduces to N independent optimizations, while when À > 0, the surrogate costs {c;) } interact with each other. The intuition is that, the regressor č(y: 0), even if not trained fully, can be very useful to guide e; rather than just using its randomly initialized version. Further- more, if è is mapping global optimal solution of ær then it will pull the solutions out of local optima to re-target towards global ones, even when starting from poor initialization, yielding fast convergence and better final solutions for individual optimization instances.
A special case is when À + +oc, we arrive at a novel objective that jointly learns the surrogate cost function, given the training set Dirain:
(SurCo-prior): min Sprior (0) 0
Σ (c(ys; yi)
(5)
This approach is useful when the goal is to find high-quality solutions for unseen instances of problem distribution when the upfront cost of offline training is acceptable but the cost of optimizing un-the-fly fly is prohibitive. Here, we require access to distribution of training optimization problems, but at test time only require the feasible region and not the nonlinear objective.
3.3 SURCO-HYBRID: FINE-TUNING A PREDICTED SURROGATE
Naturally, we consider SurCo-hybrid, a hybrid approach which initializes the coefficients of SurCo-zero with the coefficients predicted from SurCo-prior which was trained offline data. This allows SurCo-hybrid to start out optimization from an initial prediction which has good performance for the distribution at large but which is then fine-tuned for the specifie instance.
4

---

Under review as a conference paper at ICLR 2023
Formally, we initialize c(0) c(y;; 0) and then continue optimizing based on the update from SurCo-zezo. This approach is geared towards optimizing the nonlinear objective using a high- quality initial prediction that is based on the problem distribution and then tine-tuning the objective coefficients based on the specific problem instance at test time. Here, high performance comes at the runtime cost of both having to train offline on problem distribution fine-tuning steps on-the-fly. However, this additional cost is often worthwhile when the main goal to find the best possible solutions by leveraging synthesized domain knowledge in combination with individual problem instances as arises in chip design (Mirhoseini et al. 2021) and compiler optimization (Zhou al. 2020).
well performing
3.4 COST REGRESSION VERSUS SOLUTION REGRESSION: THEORETICAL ANALYSIS
We also want to compare SurCo with the previous works on ML optimizers (Ban & Rudin 2019)
that try to directly learn the mapping from problem description y to the solution, i.e. solution regression. Given set of training instances Dirain from distribution D, these approaches first collect a set of training samples D Ddirect == (y. x (y) y E Derain): ). and then learn a function # ²²(y) to fit the training samples.
While this is conceptually simple, there exist fundamental difficulties to learn such a direct mapping. First, as mentioned above, it can be quite expensive to obtain the optimal solution x' x²())) due the nature of nonlinear optimization and the query cost. Second, even if a perfect dataset Dairect is accessible, the number of samples needed learn mapping directly predict x* (γ) is related to the Lipschitz constant L of the mapping, and for a direct mapping, L can be very large.
3.4.1 LIPSCHITZ CONSTANT AND SAMPLE COMPLEXITY
Let us first consider the sample complexity of solution regression methods as described above.
Formally, consider fitting any function Φb TR 2 Y R with a dataset (y:: Here Y is compact region with finite volume vol(Y). The Lipschitz constant L is the smallest number so that ((Φ())) Φ(y2)ll2 I L| Y2ll2 holds for any yı y/2 E Y. The following theorem shows that the dataset covers the space Y, we could achieve high accuracy prediction: |<b(y) (gg)ll2 S for any E Y.
Definition 3.1 (б-cover). A datasel Ddtrect: = ((y,, &i) 8-covers the space Y, if any y E Y, there exists at least one ys so that [ly Ye lll
Lemma 3.1 (Sufficient condition of prediction with e-accuracy). the dataset Deirect (e/ve-cover Y, then for any y E Y, a t-nearest-neighhor regressor o leads to (1 Φlu))12 S.
Lemma 3.2 (Lower bound of sample complexity for c/ L-oover). To achieve c/ L-cover the size of the training set N 2 No(e)
(4) where vol, is the volume of unit ball in d-dimension. vol(Y)
volo
Please find all proofs in the Appendix. While do not rule out more advanced regressor than 1- nearest-neighhor that leads to better sample complexity, the lemmas demonstrate that the Lipschitz constant L. plays an important role in sample complexity.
3.4.2 DIFFERENCE BETWEEN COST AND SOLUTION REGRESSION
In the following we will show that in certain cases, the direct prediction y + x (y) could have an infinitely large Lipschitz constant L.
To show this, let us consider general mapping Φ Rd C Y + Rm. Let ( be the image of Y under mapping & and :(YY) be the number of connected components for region Y.
Theorem 3.1 (A case of infinite Lipschitz constant). If the minimal distance duin for different con- nected components of ((Y) is strictly positive, and k(O(Y)) > x(Y), then the Lipschitz constant of the mapping & is infinite.
Note that this theorem applies wide variety of combinatorial optimization problems. For ample, when Y is a connected region and the optimization problem can be formulated as an integer program, the optimal solution set xx" (Y) = {ar Y} is discrete set of integral vertices,

---

Under review as a conference paper at ICLR 2023
so the theorem applies. Combined with analysis in Sec. 3.4.1 know the mapping y x= x²()) is hard to learn even with lot of samples.
On the other hand, the mapping c(y) can avoid too many connected components in its image ((Y).u by connecting disjoint components of aa"(( (Y) together.
EMPIRICAL EVALUATION
We evaluate the two variants of SurCo on two real-world settings, embedding table sharding and inverse photonic design. Both have industrial application. Each setting consists of a family of problem instances with varying feasible region and nonlinear objective function.
4.1
EMBEDDING TABLE SHARDING
Table Sharding Solution Loss (Latency)
Table Sharding Deployment Runtine
Solstion Loss (Latency)
SerCn-2n0
Devendhentt Serts Collaard
Deployment
20
0.3
Satting
Setting
(b)
Table placement plan latency (a) and solver runtime (b). We evaluate SurCo against Dreamshard (Zha et al. 2022b) a SoTA offline RL sharding tool, a -herrist of assigning tables based on dimension, and a greedy heuristic based the estimated runtime increase. Striped approaches require pre-trate training.
Figure 2:
The task of sharding embedding tables arises in the deployment of large scale neural network mod- els which operate over both sparse and dense inputs (e.g., in recommendation systems (Zha et al. 2022a by (Sethi al. (0222). Given 7 embedding tables and D homogeneous devices, the goal is to distribute the tables among the devices such that no device's memory limit is exceeded, while the tables are processed efficiently. Formally, let Ft,d be the binary variable indicating whether ble / assigned to device d, and (It,a) E {0, 1 be the collection of the variables. The optimization problem is:
min f(x; s.t. TE = x:: VI, Σ Ft,d
= -t,d=11
Vd. Σ maTia S M
(6)
Here the problem description y includes table memory usage {m²). and capacity M of each device. Lt,d 1 means each table t should be assigned to exactly one device, and E. myFt,a S. M means the memory consumption
each device should not exceed its capacity. The nonlinear cost function f(æ; y) is the latency, i.c., the runtime of the longest-running device. Due to shared computation (e.g.. batching) among the group of assigned tables, and communication costs across devices, the objective is highly nonlinear. f(æ; y) is well-approximated by sharding plan runtime estimator proposed by Dreamshard (Zha et al., 2022b).
SurCo learns to predict T x D surrogate cost Gt,d one for each potential table-device assignment. During training, the gradients through combinatorial solver 0g/ 00c are computed via CVXPYLayers (ggawaal et al., 2019a) and the integrality constraints are relaxed. We found that in practice, obtained solutions that were mostly integral in that only one table on any given device was fractional. At test time solve for the integer solution using SCIP (Achterberg 2009).
Settings. We evaluate SurCo on the publicly available Deep Learning Recommendation Model (DLRM) dataset (Naumov et al., 2019). We consider 6 settings: 10. 20, 30, 40, 50, and 60 tables are placed to 4 devices with each GPÜ device having a 5GB memory limit. Each setting has 100 problem instances (50 training and 50 test).

---

Under review as a conference paper at ICLR 2023
Baselines. For SurCo-zero baselines, while observing memory limits according to the predicted latency f. and Domain-Heurrsttl the domain-expert algorithm of allocating tables to balance the aggregate dimension (Zha et al. 2022b). For Su SurCo-prior, we use Dreamshard, the SoTA embedding table sharding algorithm that requires training offline RL policy.
Greedy that greedily allocates tables devices
Results. Fig. 2 SurCo-zero finds lower latency sharding plans than the baselines, while it takes and DreamShard due taking optimization steps rather than selecting based on a heuristic feature or reinforcement learned policy. SurCo-prior obtains lower latency solutions in about the same time as DreamShard with slight increase in overhead due to using SCIP (Achterberg, 2009), branch and bound MILP solver. Lastly, SurCo-hybrid obtains the best solutions in terms solution quality and has runtime comparable to SurCo-zero since at test time it performs similar operations. In smaller problem instances (T 10 to 7 40), SurCo-prion obtains better quality solutions than impromptu counterpart, SurCo-zero, likely due training
slightly longer than Somain-Heurisse
variety of examples and being able to better escape local optima in any given problem instance as might be the case with the impromptu solver. However, as the problem size increases and more tables available for placement, SurCo-zero gives better performance by optimizing for the test instances question as opposed to SurCo-prior which only uses training data obtain surrogate costs. Using Su Co-hhbrr we able obtain the best quality solutions but incur the upfront cost of pretraining and the deployment-tie cost of optimizing the coefficients on-the-fly.
4.2 INVERSE PHOTONIC DESIGN
Inverse Photonics Solution Loss (% Invalid)
Inverse Photonics Deployment Runtime (s)
Soltton Invald))
Deployment Runtine
64
20
Through
SurOi-sero
SurOk prior
Bead
Mode Converter Multiplener
Boan Spatter
Bend
Made Convecter
Muttppeeeer
Boun Spiller
Setting
Selling
(a)
(b)
Figure 3: (a) The solution loss (% of failed instances when the design loss is not 0), and (b) lest time solver runtime in log scale, For both, lower is better. We compare against the pass-through gradient approach proposed in (Schubert et al. (2022). We observe that SurCo-priox achieves similar success rates the previous ap- proach P Pass-through with a substantially improved runtime. Additionally, SurCo-zers runs comparably or faster, while finding more valid solutions than Pass-thr tasssttrrugh.... SurCo-hybrl obtains valid solutions most often and is faster than SurCo-zero at the expense pretraining. Striped approaches use pretraining.
Photonic devices play an important role in high-speed communication (Marpaung et al. 2019),
quantum computing (Arrazola al. (021). I), and machine learning hardware acceleration (Wetzstein et al. 2020). The photonic components can be formulated filled or void. There are constraints for binary patterns: only those that can be drawn by a physical brush instrument with certain cross shape can be manufactured.
binary 2D grid, with each cell being
remains challenging to find designs that are manufacturable and satisfy design specifications (e.g- beam splitting). An example solution developed by SurCo is shown in Figure 44b coming from the top, beams are routed to the left or right, depending on wavelength. The solution is also manufac- turable: 3-by-3 brush cross fit in all filled and void space.
Given the design, existing work (Hughes et al. 2019) enables differentiation of the design misspec- ification cost, evaluated how far off the transmission of the wavelengths of interest is from the desired locations, with zero design loss meaning that the specification is satisfied. Researchers also develop a standard benchmark of inverse photonic design problems (Schubert al. 2022

---

Under review as a conference paper at ICLR 2023
Settings. We compare approaches against the "Pass-Througee Through" method (Schubert et al. 2022 on randomly generated instances of the four types problems Schubert et al. (2022): Waveguide Bend, Mode Converter, Wavelengths Division Multiplexer, and Beam Splitter. We generate 50 instances each setting (25 training/25 test). Further generation details are in the appendix. We evaluated several algorithms described in the appendix, such genetic algorithms and derivative- free optimization, which failed to find physically feasible solutions. We consider two wavelengths (1270nm/1290nm) and optimize at resolution of 40nm, visualizing the test results in Fig.
Results. Fig. SurCo-zero consistently finds as many or more valid devices compared to the Tass-Through baseline (Schubert et al., 2022). Additionally, since the on on-the-fly solvers stop when they either find a valid solution, or reach a maximum of 200 steps, the runtime of SurCo- zero is slightly lower than the Pass-Through baseline. SurCo-prion foor obtains similar success rates as Pass-Through while taking two orders of magnitude less time as it does not require expensive impromptu optimization, making SurCo-prior a promising approach for large-scale settings or when solving many slightly-varied instances. Lastly, SurCo-hybrid performs best in terms of solution loss, finding valid solutions more often than the other approaches. It also takes less runtime than the other on-the-fly fly approaches since is able reach valid solutions faster, although it still requires optimization on-the fly so it takes longer than SurCo-prior We visualize the convergence of impromptu solvers in Fig. 4a where SurCo-zero has smoother and faster convergence compared to the Pass thrughh approach.
Photonics
Couvergence
Device Design
Mattied
Sexto-aaro
Tedggn Misppethotts
0.4
0.0
00
Stopp
(a) Loss Convergence
(b) Device
Es magnitude
E, magnitude second wavelength
first wavelength
(c) Wave Mangitude
Figure 4: Inverse photonic design convergence for a single instance (Schubert et al. 2022). SurCo- zero smoothly lowers the loss while the pass-through baseline converges noisily. Also, SurCo- hybrid starts out with a high-quality solution and fine-tunes until an optimal solution is reached. We also visualize the SurCo-zero solution with magnitudes of the two wavelengths of interest which we successfully route from the input at the top to the two different waveguides at the bottom.
RELATED WORK
Differentiable Optimization Previous work differentiated through several optimization problems, calculating how changes in imput parameters impact the optimal solution. Initially, differentiable convex quadratic programming solver called OptNet (Amos & Kolter (017)) proposed to implicitly differentiate the optimal solution with respect to input parameters through the KKT optimality con-
8

---

Under review as a conference paper at ICLR 2023
ditions, set of linear equations that determined the optimal solution. Following this, researchers
differentiated through linear programs (Wilder et al.] 2019a). submodular optimization problems
(ioolonga & Krause 2017 Wilder et al.
2019a), cone programs (Agrawal et al.. 2019a b). MaxSAT
Wang et al. 2019). Mixed Integer Linear Programming (Ferber et al. 20200 Mandi et al.) 2020),
Integer Linear Programming (Mandi et al.
2020), dynamie programming sol Demirovic et al.
(020)) blackbox discrete linear optimizers (Pogančić et al. 2219 Rolínek et al.
2020a b). maxi-
mum likelihood estimation (Niepert et al. (021), kmeans clustering (Wilder et al. 2019b). knapsack
(Guler et al. [022] Demirović et al. 2019), the cross- cross-entropy method (Amos & Yarats 2020). and
SVM training (Lee et al. (209)) Additionally, WWng et al. (2020a) learned to linearly combine LP
variables. SurCo can use these differentiable surrogates based on the problem domain.
Task Based Learning Task-based learning solves distributions of linear or quadratic optimization problems with the true objective hidden at test time but available for training (Elmachtoub & Grigas
2022
Donti et al. 2017 EII Balghiti et al. 2019. Liu & Grigas 2021: Hu et al. 2022). (Donti et al,
2021
predicts and corrects solutions for continuous nonlinear optimization. Bayesian optimization
(BO)
(Shahriari et al. 2016), optimizes blackbox functions by approximating the objective with a
learned model that be optimized over. Recent work optimizes individual instances over discrete
spaces like hypercubes (Baptista & Poloczek 2018), graphs (Deshwal et al. 202I), and MILP Pa-
palexopoulos al.] 2022). Data reuse from previous runs is proposed to optimize multiple correlated
instances (Swersky et al. 2013 Feurer et al. 2018). 1 However, the surrogate Gaussian Process (GP)
models are memory and time intensive in high-dimensional settings. Recent work has addressed GP scalability via gradient updates (Ament & Gomes 2022); however, it is unclear whether GP can scale in conjunction with combinatorial solvers. Machine learning is also used to guide combina- torial algorithms. Several approaches produce combinatorial solutions (Zhang & Dietterich] [995] Khalil et al. 2017; Kool et al.) 2018 Nazari et al., 2018: Zha et al.) 2022a b). Here, approaches limited to simple feasible regions by iteratively building solutions for problems like routing, signment, or covering. However, these approaches fail to handle more complex constraints. Other approaches parameters that improve solver runtime (Khalil et al. 2016 |Begiio et al. 2021).
Learning Latent Space for Optimization As we learn latent linear objectives to optimize nonlin- ear functions, other approaches learn latent embeddings for faster solving. Faloutsos & Lin (1995)
proposed FastMap, which learns latent object embeddings for efficient search. Variants of FastMap
are used in graph optimization and shortest path (Cohen et al. 2018 Hu et al. 2022 Li et al. 2019).
Wang et al.] (2020b; 2021a): Yang et al.] (2021); iZhao et al. (2022) use monte carlo tree search to perform single and multi-objective blackbox optimization by learning to split the search space.
Mixed Integer Nonlinear Programming (MINLP) SurCo-zero falls into the broad family of MINLP solvers, optimizing nonlinear and nonconvex objectives over discrete linear feasible re- gions. Specialized solvers handle many problem variants in the MINLP space (Burer & Letchford 2012 Belotti et al., 2013); however, scalabliliy in the nonconvex setting is usually obtained by opti- mization experts who rely on problem-specific solving techniques such as making piecewise linear approximations, convexifying the objective, or exploiting special structure.
6 CONCLUSION
We introduced SurCo, a method for learning linear surrogates for combinatorial nonlinear opti- mization problems. SurCo learns linear objective coefficients for a surrogate solver which results in solutions that minimize the nonlinear loss via gradient descent. At its core, SurCo differenti- ates through the surrogate solver which maps the predicted coefficients to a combinatorially feasible solution, combining the flexibility of gradient-basse based optimization with the structure of combina- torial solvers. We presented three variants of SurCo, SurCo-zero which optimizes individual instances, SurCo-prior which trains coefficient prediction model offline, and SurCo-hybric which fine-tunes the coefficients predicted by SurCo-prior on individual test instances. While SurCo's performance is somewhat limited to binary problems due to the lack of interior integer points, we find that many real-world domains operate on binary decision variables. We evaluated variants of SurCo two domains against the state of the art approaches used in industry, obtaining better solution quality for similar or better runtime in the embedding table sharding domain, and quickly identifying viable photonic devices.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Compu- tation, 1(1):1-41, 2009.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019a.
Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M Moursi. Differentiating through cone program. Appl. Numer. Optim, 1(2):107-115, 2019b.
Sebastian Ament and Carla Gomes. Scalable first-order bayesian optimization via structured au- tomatic differentiation. In International Conference on Machine Learning, pp. 500-516. PMLR, 2022.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Brandon Amos and Denis Yarats. The differentiable cross-entropy method. In International Con- ference on Machine Learning, pp. 291-302 PMLR, 2020.
Juan M Arrazola, Ville Bergholm, Kamil Brádler, Thomas R Bromley, Matt J Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G Helt, et al. Quantum circuits with many photons programmable nanophotonic chip. Nature, 591 (7848):54--6) 60, 2021.
Gah-Yr Yi Ban and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1):90-108, 2019.
Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In International Conference on Machine Learning, pp. 462-471. PMLR, 2018.
Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, James Luedtke, and Ashutosh Ma- hajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1-131, 2013.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2); 405-421, 2021.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances in neural information process- ing systems, $3:9508-9519, 2020.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Minn and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
// //qithub. com
Samuel Burer and Adam N Letchford. Non-convex mixed-integer nonlinear programming: A sur- vey. Surveys in Operations Research and Management Science, 17(2):7--066, 2012.
Vasek Chvatal, Vaclav Chvatal, al. Linear programming. Macmillan, 1983.
Liron Cohen, Tansel Uras, Shiva Jahangiri, Aliyah Arunasalam, Sven Koenig, and TK Satish Kumar. The fastmap algorithm for shortest path computations. In IJCAI, 2018.
Alison Cozad, Nikolaos V Sahinidis, and David C Miller, Learning surrogate models for simulation- based optimization. AIChE Journal, 60(6):2211-22)) 1-2227, 2014.
Emir Demirović, Peter J Stuckey, James Bailey, Jeffrey Chan, Christopher Leckie, Kotagiri Ra- mamohanarao, and Tias Guns. Predict+ optimise with ranking objectives: Exhaustively learning linear functions. In Proceedings the Eventy-Eightl International Joint Conference Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16. 2019, pp. 1078-1011000 1085. International Joint Conferences Artificial Intelligence, 2019.
10

---

Under review as a conference paper at ICLR 2023
Emir Demirovic, Peter J Stuckey, Tias Guns, James Bailey, Christopher Leckie, Kotagiri Ramamo- hanarao, and Jeffrey Chan. Dynamic programming for predict+ optimise. In The Shirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applica- fions of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp- 1444-1451. AAAI Press, 2020.
Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Mercer features for efficient combi- natorial bayesian optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35 (8):7210-7218, May 2021. doi: 10.1609/aaii. 16886. URL https: //ojs aaai . org/
index httpppppp.hhaaaaa wttpllleeewww/ee 6
Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. Advances in Neural Information Processing Systems, 30, 2017.
Priya Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning stochastic optimization. Advances in neural information processing systems, 30, 2017.
Priya Donti, David Rolnick, and J Zico Kolter. DC3: learning method for optimization with hard constraints. In International Conference on Learning Representations, 2021. URL httpt:::
//openreview. http:/oorrmm..d/11/2vXX
Othman El Balghiti, Adam N Elmachtoub, Paul Grigas, and Ambuj Tewari. Generalization bounds in the predict-then-optimize framework. Advances in neural information processing systems, 32,
2019.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 9-26, 2022.
Christos Faloutsos and King-lp Lin. Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. SIGMOD '95, pp. 163-174, New York, NY, USA, 1995. Association for Computing Machinery. ISBN 0897917316. doi: 10.1145/223784. 223812. URL htttts:://dett oecil.orggllo /0. 11 1445/22788444 223812
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp- 1511-1511, 2020.
Matthias Feurer, Benjamin Letham, and Eytan Bakshy, Scalable meta-learning for bayesian opti- mization. stat, 1050(6), 2018
Ahmed Fawzy Gad. Pygad: An intuitive genetic algorithm python library, 2021.
Abhijit Gosavi et al. Simulation- optimization. Springer, 2015.
Ali Ugur Guler, Emir Demirović, Jeffrey Chan, James Bailey, Christopher Leckie, and Peter J
Stuckey. A divide and conquer algorithm for predict+ optimize with non-convex problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3749-3757, 2022.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://www gurobi com
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. Manage- ment Science, 2022.
Tyler W Hughes, Ian AD Williamson, Momchil Minkov, and Shanhui Fan. Forward-mode differen- tiation of maxwell's equations. ACS Photonics, 6(1 11:30))33330111 2019.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvumakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-50) 2021.

---

Under review as a conference paper at ICLR 2023
Elias Khalil, Pierre Le Bodic, Le Song. George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Bernhard Korte and Dirk Hausmann. An analysis of the greedy heuristic for independence systems. In Annals of Discrete Mathematics, volume pp. 65- Elsevier, 1978.
Slawomir Koziel, Nurullah Çalik, Peyman Mahouti, and Mehmet A Belen. Accurate modeling of antenna structures by means of domain confinement and pyramidal deep neural networks. IEEE Transactions on Antennas and Propagation, 70(3):2174 21887 2021.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pp. 105-132. Springer, 2010.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10657-10665, 2019.
Jiaoyang Li, Ariel Felner, Sven Koenig, and TK Satish Kumar. Using fastmap to solve graph prob- lems in euclidean space. In Proceedings of the international conference automated planning and scheduling, volume 29, pp. 273-278, 2019.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Ad- vances in Neural Information Processing Systems, 34:26198-26211, 26211, 2021.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
Heyuan Liu and Paul Grigas. Risk bounds and calibration for a smart predict- Advances in Neural Information Processing Systems, 34:22083-22094 2021.
predict-then-oppeeeeee then-optimize method.
Giampaolo Liuzzi, Stefano Lucidi, and Francesco Rinaldi. Derivative- methods for mixed- integer constrained optimization problems. Journal of Optimization Theory and Applications, 164(3):933 2015.
Jayanta Mandi, Peter J Stuckey, Tias Guns, et al. Smart predict-and-optmiize for hard combina- torial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1603-1610, 2020.
David Marpaung, Jianping Yao, and José Capmany. Integrated microwave photonics. Nature pho- tonics, 13(2)800-90, 2019.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 1 134:105400, 2021.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joor Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodol- ogy for fast chip design. Nature, 594(7862):007-212, 2021.
Ryo Nagai, Ryosuke Akashi, and Osamu Sugino. Completing density functional theory by machine learning hidden messages from molecules. npj Computational Materials, 6(1):1-8, 2020.
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G. Azzolini, Dmytro Dzhulgakov, Andrey Mallevich, Ili Cherniavskii, Yinghai Lu, Raghuraman Krish- namoorthi, Ansha Yu, Volodymyr Kondratenko, Stephanie Pereira, Xianjie Chen, Wenlin Chen, Vijay Rao, Bill Jia, Liang Xiong, and Misha Smelyanskiy. Deep learning recommendation model for personalization and recommendation systems. CoRR, 1bs//1906.00091 2019. URL https: // wtwg/bbs........ 906 00091
12

---

Under review as a conference paper at ICLR 2023
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 34:14567-14579, 2021.
Theodore P Papalexopoulos, Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, and David Belanger. Constrained discrete black-box optimization using mixed-integer programming. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings Machine Learning Research, pp. 173222 PMLR, 17-23 Jul 2022. w.w.pprrss/ve.
URL
aas.e.iingg... prep eepps///oo wwwpp html
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bus B E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL
neuri style--sssee-eee wtt.:p/www....a..............aaa
9015- pdf
iibraryr..
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek, Differ- entiation of blackbox combinatorial solvers. In International Conference on Learning Represen- tations, 2019.
J. Rapin and O. Teytaud. Nevergrad A gradient-free free optimization platform. https://CitHu: 2018.
com/ http///coooooeeercceeeeeeeeeeeee
Edward M Reingold and Robert E Tarjan. On greedy heuristic for complete matching. SIAM
Journal on Computing, 10(4):676-681, 1981.
Michal Rolínek, Vít Musil, Anselm Paulus, Marin Vlastelica, Claudio Michaelis, and Georg Mar- tius. Optimizing rank-based metries with blackbox differentiation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7620-7630, 2020a.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Confer- ence on Computer Vision, pp. 407-424. Springer, 2020b.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016.
Martin F. Schubert, Alfred K. C. Cheung, Ian A. D. Williamson, Aleksandra Spyra, and David H. Alexander. Inverse design of photonic devices with strict foundry fabrication constraints. ACS Photonics, 97))2327--3366 2022. doi: 10. 00.102//acphhoommies2000333
Geet Sethi, Bilge Acun, Niket Agarwal, Christos Kozyrakis, Caroline Trippel, and Carole-Jean Wu. Recshard: statistical feature-based memory optimization for industry-scale neural recommenda- tion. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 344 358, 2022.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104()): 148-175, 2016. doi: 10.1109/PRO..2015.2444.
Dan Simon. Evolutionary optimization algorithms. John Wiley & Sons, 2013.
13

---

Under review as a conference paper at ICLR 2023
Benoit Steiner. Chris Cummins, Horace He, and Hugh Leather. Value learning for throughput optimization of deep learning workloads. In A. Smola, A. Dimakis, and I. Stoica (eds.), Proceedings of Machine Learning and Systems, volume 3, pp. 323-334, 2021. URL. https::/prroceddinm mlm.mmss... ww..mmsssssmmmmmmmmmmmmmmmmmmmmm wtwpss...s...spaae.ereeeeoo wttpppaper/022//1112.
Kevin Swersky, Jasper Snoek, and Ryan P Adams. Multi-task bayesian optimiza- tion. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL E33bal5effacclee7 hot.a/c110.e.1foo8aaaaaaaaaaaa Paper. pdf
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Stefan VoB, Silvano Martello, Ibrahim H Osman, and Catherine Roucairol. Meta-heuristies: Ad- vances and trends in local search paradigms for optimization. Springer Science Business Media, 2012.
Kai Wang, Bryan Wilder, Andrew Perrault, and Milind Tambe. Automatically learning compact quality- surrogates for optimization problems. Advances in Neural Information Processing Systems, 33:9586 2020a.
Linnan Wang, Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. Advances in Neural Information Processing Systems, 33:19511-19522. 2020b.
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-effccient neural architecture search by learning actions for monte carlo tree search. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021a.
Po- Ro-Wei Wang. Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and log- ical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pp. 6545-6554, PMLR, 2019.
Xiaodi Wang, Youbo Liu, Junbo Zhao, Chang Liu, Junyong Liu, and Jinyue Yan. Surrogate model enabled deep reinforcement learning for hybrid energy community operation. Applied Energy, 289: 16722, 2021b.
Gordon Wetzstein, Aydogan Ozean, Sylvain Gigan, Shanhui Fan, Dirk Englund, Marin Soljačić, Cornelia Denz, David AB Miller, and Demetri Psaltis. Inference in artificial intelligence with deep optics and photonics. Nature, 588(7836):39447 2020.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 1658-1665, 2019a.
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization on graphs. Advances Neural Information Processing Systems, 32, 2019b.
Laurence Wolsey, An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982.
Laurence A Wolsey. Mixed integer programming. Wiley Encyclopedia of Computer Science and Engineering, pp. 1-10, 2007.
Kevin Yang, Tianjun Zhang, Chris Cummins, Brandon Cui, Benoit Steiner, Linnan Wang, Joseph E Gonzalez, Dan Klein, and Yuandong Tian. Learning space partitions for path planning. Advances in Neural Information Processing Systems, 34:378-391, 2021.
14

---

Under review as a conference paper at ICLR 2023
Yingjun Ye, Xiaohui Zhang, and Jian Sun. Automated vehicle's behavior decision making using deep reinforcement learning and high-fidelity simulation environment. Transportation Research Part C: Emerging Technologies, 107:155-170, 2019.
Daochen Zha, Louis Feng, Bhargav Bhushanam, Dhruv Choudhary, Jade Nie, Yuandong Tian, Jay Chae, Yinbin Ma, Arun Kejariwal, and Xia Hu. Autoshard: Automated embedding table sharding for recommender systems. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4461-4471, 2022a.
Daochen Zha, Louis Feng, Qiaoyu Tan, Zirui Liu, Kwei-Herng Lai, Bhushanam Bhargav, Yuandong Tian, Arun Kejariwal, and Xia Hu. Dreamshard: Generalizable embedding table placement for recommender systems. In Advances in Neural Information Processing Systems, 2022b.
Wei Zhang and Thomas G Dietterich. A reinforcement learning approach to job-shop scheduling. In IJCAI, volume 95, pp. 1114-1120. Citeseer, 1995.
Yiyang Zhao, Linnan Wang, Kevin Yang, Tianjun Zhang, Tian Guo, and Yuandong Tian. Multi- objective optimization by learning space partition. International Conference on Learning Rep- resentations, 2022. URL http::ttppteeeeiiii...///
net forum?id== LwzV JfMzyn
Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong. Peter Ma, Qiumin Xu, Hanxiao Liu, Phitchaya Phothilimtha, Shen Wang, Anna Goldie, et al. Transferable graph optimizers for compilers. Advances in Neural Information Processing Systems, 33:13844 13855, 2020.
15

---

Under review as a conference paper at ICLR 2023
A PROOFS
Lemma 3.1 (Sufficient condition of prediction with c-accuracy). If the dataser Ddirect (c/ L)) Y, then for any y E Y, --eeaesst-niihhhor regressor è leads to (1 Φ l2 S.
Proof. Since the dataset is a e/ L-cover, for any y E Y, there exists at least one y, so that | yoll2 L/L. L. Let ynn be the nearest neighbor of y, and we have:
y Ymn 12 I l yill2
c/L
(7)
From the Lipschitz condition and the definition of l-nearest-neighbor classifier (Φ(y) (yym)), know that
(Φ()) 0(v))12 (Ø( ((yan)ll2 & Llyy Yuallz S
(8)
Lemma 3.2 (Lower bound of sample complexity for T.-ove--, To achieve of the training set N 2 No(c) == vol(Y')
L-cover of,, the size
(t) where voly is the volume of unit ball in d-dimension.
volo
Proof. We prove by contradiction. IN < No(e), then for each training sample (y., Ø.), we create ball B; B (yy,,// L). Since
vol (UBnr)) 1
N
N
vol( = Nvolo ( < vol(Y)
S vol
1=1
Therefore, there exists least y Y so that y & B, for any isis N. This means that is not / L-ooered.
Theorem 3.1 (A of infinite Lipschitz constant). the minimal distance dmin for different con- nected components of ((Y) is strictly positive, and k()(Y)) > s(Y), then the Lipschitz constant of the mapping & infinite.
Proof. Let R1. Rg, Rg be the K = x(o(Y)) connected components of Φ(Y), and Yi, .Y...., YJ be the x(Y) connected components Y. From the condition, we know that mink41 dist RR, R2) dmin 0.
We have R3 n Rg = for 1 + W. Each RŞ has a pre-image Sk == Φ (RA( S Y. These pre-images (Sx K form partition of Y since
S Sw 0 for ls k since any y Y cannot be mapped more than one connected components;
U Sx = UK x (Re)) = - 6U Rk) - - S.
((x)==))
Since K= x((()) x(Y), by pigeonhole principle, there exists one Y, that contains at least part of the two pre-images S& and Sy with & + K. This means that
Su ny, + 00 Se nY, +
(10)
Then pick y E S& ny and y' Sw n Y. Since y, EY and Y, is connected component, there exists continuous path [0, + Yg so that (0) and 71) y'. Therefore, we have (0)( R2 and ((>(1)) Ry. Let to == sup(t: t [0, (()))()))))))))))))))))))))))))) E Rx). then to 1. For any sufficiently small > 0, we have:
* By the definition of sup, we know there exists to - S t' S to so that Φ()(t)) Ra-
Picking 1" to < 1, then (({((")) RR with some 1." k.
16

---

Under review as a conference paper at ICLR 2023
On the other hand, by continuity of the curve % there exists constant C(to) that ll((t') r(t") I C(to)]li' tl - (0ooe Then we have
( p [[(()(t)) - +(>(t"))l2 Il((t)) - (("))l2
dmia
L
max nAy' V.V'EY EY
to0
(11)
y 32
2C((o)e
B EXPERIMENT DETAILS
B.1 SETUPS
Experiments are performed a cluster of identical machines, each with 4 Nvidia A100 GPUs and 32 CPU cores, with IT of RAM and 40GB of GPU memory. Additionally, we perform all operations in Python (ann Rossum & Drake 2009) using Pytorch (Paszke al. (219)). For em- bedding table placement, the nonlinear cost estimator is trained for 200 iterations and the offline- trained models of Dreamshard and SurCo-prior
trained against the pretrained cost esti- mator for 200 iterations. The DLRM Dataset Naumov et al.) (2019) available at https: and the dreamshard (Zha et al.
//github. cttp:uubbooo/eeeeeeeeeeeeeee wctp///aaccboooeerrrreee/ddaaaaa
2022b) code is available at
dreamshard aatpchheezzhaadrdaaaahaaaaa Additional com/ wwt./hncchhhcccccooo
details on dreamshard's 's model architecture and features can be obtained in the paper and codebase. Training time for the networks used in SurCo-pri cofoo-rrorr and SurCo-bybrid are on average 8 hours for the inverse photonic design settings and 21, 39, 44, 50, 63 minutes for DLRM 10, 20, 30, 40, 50, 60 settings respectively.
B.2 NETWORK ARCHITECTURES
B.2.1 EMBEDDING TABLE SHARDING
The table features are the same used in Zha et al. (002b)) and sinusoidal positional encod- ing Vaswani et al. (2017) is used device features so that the learning model able to break symmetries between the different tables and effectively group them onto homogeneous devices. The table and device features are concatenated and then fed into Dreamshard's initial fully-connected table encoding module to obtain scalar predictions Jτ, for each desired objective coefficient. The architecture trained with the Adam optimizer with learning rate 0.0005.
B.2.2 INVERSE PHOTONIC DESIGN
Network architectures. The input design specification 2D image) is passed through 3 layer convolutional neural network with ReLU activations and final layer composed of filtering with the known brush shape. Then tanh activation is used obtain surrogate coefficients è, one component for each binary input variable. The architecture is trained with the Adam optimizer with learning rate 0.001.
This is motivated by previous work (Schubert et al. 2022) that also uses the fixed brush shape filter and tanh operation transform the latent parameters into continuous solution that is projected onto the space of physically feasible solutions.
In each setting, optimization is done on binary grid of different sizes meet fabrication constraints, namely that a 3 by 3 cross must fit inside each fixed and void location. In the beam splitter the design an 80 60 grid, mode converter is 40 40 grid, waveguide bend it is x 40 grid, in wavelength division multiplexer is an 80 x 80 grid.
Previous work formulated the projection as finding a discrete solution that minimized the dot prod- uet of the input continuous solution and proposed discrete solution. The authors then updated the continuous solution by computing gradients of the loss with respect to the discrete solution and us- ing tass-through gradients to update the continuous solution. By comparison, approach treats the projection as an optimization problem and updates the objective coefficients so that the resulting projected solution moves in the direction of the desired gradient.
17

---

Under review as a conference paper at ICLR 2023
Task
Randomization
mode converter
randomize the right and left waveguide width randomize the waveguide width and length randomize the waveguide separation, width and length randomize the input and output waveguide locations
bend setting
beam splitter
wavelength division multiplexer
Table 1: Task randomization of 4 different tasks in inverse photonic design.
To compute the gradient of this blackbox projection solver, we leverage the approach suggested by Pogančić al.] (2019) which calls the solver twice, once with the original coefficients, and again with coefficients that are perturbed in the direction of the incoming solution gradient as being an "improved solution". The gradient with respect to the input coefficients are then the difference between the "improved solution" and the solution for the current objective coefficients.
C PSEUDOCODE
Here the pseudocode for different variants of our algorithm. Each of these leverage a differen- tiable optimization solver to differentiate through the surrogate optimization problem.
Algorithm SurCo-zero
Algorithm 2 SurCo-prior Training
Input: y
Input: Q2 Derain {y: |/
1: e < initssurrogate.coff///
1: 0 <- wtt.suurrgtte_mmdeee
2: while not converged do
while not converged do Sample batch B { k Dirain
3: I + arargg min c
4: loss + ( y)
4: for y E B do
---grad_updateld Voloss) 6: end while
5:
Ć t č(y;
6: x - arg min cTa
7: return
loss += f( y) end for
8:
9:
0 <-grrd update Voloss)
10: end while
Algorithm 3 SurCo-prior Deployment
Algorithm 4 SurCo-hybrid
Input: Q, Purain = {3.) f. yostt
Input: Q. Derain { f. Plest
1: 0 <- train SurCo-pri (1, D f)
1: 0 + train SurCo-prior()), Derains c c(y: 0)
2: c < č(y;0) 0)
3: œ arg min cTa
3: while not converged do
4: return
a f- arg ming c
I y)
6: c e-grad update(e, Veloss)
end while
8: return x
D ADDITIONAL FAILED BASELINES
SOGA
Single Objective Genetic Algorithm Using PyGAD (Gad 2021), we attempted several approaches for both table sharding and inverse photonics settings. While we were able to obtain feasible table sharding solutions, they underperformed the greedy baseline by 20%. Additionally, they were unable to find physically feasible inverse photonics solutions. We varied between random, swap, inversion, and scramble mutations and used all parent selection methods but were unable to find viable solutions.
18

---

Under review as a conference paper at ICLR 2023
DFL A Derivative-Free Library We could not easily integrate DFLGEN Liuzzi et al. 2015) into our pipelines since it operates in fortran and we needed to specify the feasible region with python in the ceviche challenges. DFLINT works in python but took more than 24 hours to run individual instances which reached a timeout limit. We found that the much longer runtime made this inapplicable for the domains of interest.
Nevergrad We enforced integrality in Nevergrad (Rapin & Teytaud 2018 using choice variables which selected between and This approach was unable to find feasible solutions for inverse photonics in less than 10 hours. For table sharding we obtained solutions by using choice variable for each table, selecting one of the available devices. This approach was not able to outperform the greedy baseline and took longer time was strictly dominated by the greedy approach.
19


Reviews:
[{"review_id": "y154aTrjclF", "reviewer": "Reviewer_n7J2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper propose, SurCO, a combinatorial solver using adaptively tuned linear surrogate models. SurCO utilizes off-the-shelf mixed integer linear program solvers and the differentiability through such solvers. With recent advances in differentiation through optimization layers, SurCO enables end-to-end differentiable training of linear surrogate models. Moreover, the authors propose a meta-learning approach, SurCO-HYBRID, that utilizes the optimization results of previously solved ones for more efficient optimization in new but similar problems. The paper provides a rigorous argument why directly learning a mapping from a problem instance to an optimum is difficult. SurCO is tested on two real-world combinatorial optimization problems.", "summary_of_the_review": "The paper proposes an interesting way to solve combinatorial problems which can get the best of both, well-developed combinatorial solvers with their long history and data-driven combinatorial solver. The proposed method SurCO-HYBRID is quite appealing even though some intuition or rationale behind it can be discussed better. However, a weak theoretical justification can be made up by more extensive empirical analysis. Weak empirical analysis and not enough details on the experiment need to be improved. If those concerns can be addressed by experiments on other benchmarks or convincing discussions on the benefit of the method, I would increase my score.", "strength_and_weaknesses": "### Strengths\n- The paper presents a way to exploit readily available and efficient MILP solvers to solve even nonlinear problems. Especially, the usage of such solvers handles the feasibility of the solution, i.e. integer constraints, seamlessly and efficiently.\n- While its basic for SurCO-zero efficiently utilizes off-the-shelf MILP solvers, its combination with SurCO-prior, SurCO-HYBRID provides a meta-learning approach enabling efficient optimization of the same type of problems by transferring knowledge of similar problems.\n- The derivation of SurCO-prior is well-motivated from the regularization perspective.\n- The authors rigorously show the difficulty of the widely adapted approach &mdash; using machine learning to learn a mapping from problem instances to solutions. \n\n\n### Weaknesses\n- Limited empirical evaluations\n    - Even though the authors admit that there is no performance guarantee, the authors say 'we argue that optimizing Eqn. 2 is better than optimizing the original nonlinear cost'. Considering that the experiments were conducted on two types of problems, this argument is not convincingly supported by extensive empirical analysis or some discussion on the rationale behind it.\n- Any discussion on how easier SurCO formulation is compared with direct solution learning?\n    - In 3.4, it is shown how difficult it is to learn a mapping from problem instances to an optimum. However, in a sense, SurCO finds an alternative to the optimum solution &mdash; weights of a linear model which can give an optimal solution. Since both have the same dimensionality, on the surface, the reasons for the benefit of SurCO over direction solution learning is not clear. Can you elaborate on this more?\n- Reporting more details on the offline data used to fit SurCO-prior.\n    - I guess that the number of data, training time, hyperparameters, etc. may affect the performance of SurCO-prior and SurCO-HYBRID significantly. Since the gain of it does not come for free, reporting such detail will be fairer to compare its runtime-related efficiency with baselines.\n    - How was the offline data for SurCO-prior in inverse photonic design generated?\n\n\n### Others\n- Offline data for SurCO-prior generation\n    - It is interesting that in embedding table sharding, SurCO-prior using offline data generated from DreamShard outperforms DreamShard quite significantly. Maybe some discussion on this highlights further the benefit of the approach.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UAcMO0oIJt", "reviewer": "Reviewer_qvJ5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of non-linear optimization with combinatorial constraints. A surrogate model based approach is proposed where the key idea is to learn a linear model of the underlying objective which is optimized via combinatorial solvers (for e.g. mixed integer program solvers SCIP) to generate a solution. This training is done in an end-to-end differentiable manner where the gradients are passed through the combinatorial solver generating the solution conditioned on the input weights (denoted as cost in the paper) of the linear model. There are three classes of the proposed approach: (1) SURCO-ZERO, which is applicable to individual instances of a problem, (2) SURCO-prior, which is applicable to a family of problem instances and (3) SURCO-HYBRID, which warm-starts the surrogate weights with that obtained from SURCO-prior. Experiments are performed on two real-world benchmarks: embedding table sharding and inverse photonic design.\n", "summary_of_the_review": "Overall, I found the proposed approach interesting and novel while addressing an important and relevant problem for the ICLR community. ", "strength_and_weaknesses": "- The paper considers an important problem with many real world applications. Experiments demonstrate the efficacy of the proposed approach on challenging domains. \n\n- I found the paper to written quite well with clear description and motivation of the proposed approach. It will be really useful to the reader if a pseudo-code like algorithmic description of the key steps is added in the main paper.\n\n- It is a little suprising to not see any discussion around Bayesian optimization (1) techniques which are quite relevant for this setting. In fact, similar ideas of incorporating combinatorial solvers (not in an end-to-end procedure) have been investigated in the Bayesian optimization literature (Mixed integer program in [2], semi-definite programming in [3], submodular optimization in [4]). Moreover, the setting of SURCO-PRIOR with multiple problem instances can be handled by multi-task or meta Bayesian optimization ([5, 6]). Gaussian processes are the go-to-choice in Bayesian optimization and there is some work on extending GPs to incorporate first-order gradient information as well ([7]). Please consider contextualizing the proposed approach along some of this related work. I feel most of these approaches cannot handle high dimensionality but still it would be nice to discuss the relevance.\n\n\n\nReferences\n\n[1] Shahriari, Bobak, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. \"Taking the human out of the loop: A review of Bayesian optimization.\" Proceedings of the IEEE 104, no. 1 (2015): 148-175.\n\n[2] Papalexopoulos, Theodore P., Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, and David Belanger. \"Constrained discrete black-box optimization using mixed-integer programming.\" In International Conference on Machine Learning, pp. 17295-17322. PMLR, 2022.\n\n[3] Baptista, Ricardo, and Matthias Poloczek. \"Bayesian optimization of combinatorial structures.\" In International Conference on Machine Learning, pp. 462-471. PMLR, 2018.\n \n[4] Deshwal, Aryan, Syrine Belakaria, and Janardhan Rao Doppa. \"Mercer features for efficient combinatorial Bayesian optimization.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, pp. 7210-7218. 2021.\n\n[5] Swersky, Kevin, Jasper Snoek, and Ryan P. Adams. \"Multi-task bayesian optimization.\" Advances in neural information processing systems 26 (2013).\n\n[6] Feurer, Matthias, Benjamin Letham, and Eytan Bakshy. \"Scalable meta-learning for Bayesian optimization.\" stat 1050, no. 6 (2018).\n\n[7] Ament, Sebastian E., and Carla P. Gomes. \"Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation.\" In International Conference on Machine Learning, pp. 500-516. PMLR, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OqhB4w20nM", "reviewer": "Reviewer_r1VR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a learning-based approach to solve combinatorial optimization problems with non-linear objectives and linear constraints. The paper introduces a linear surrogate cost function that can be used by existing solvers, and proposes to learn this surrogate cost in order to efficiently approximate the original problem. This idea is developed in two settings, either for solving individual instances or training a surrogate cost prediction model -- that can possibly be fine-tuned at test time. The approach is evaluated on two industrial problems.", "summary_of_the_review": "I would vote for borderline reject.\n\nThe main contribution of the paper is the introduction of a linear surrogate cost in order to approximate non-linear combinatorial optimization problems. Although it leads to very good experimental results, the main idea is not well-motivated in my opinion, neither theoretically nor intuitively. This makes it hard to see why the proposed approach would work in general, beyond the two presented problems. Some parts of the paper lack clarity and several general claims/arguments need to be clarified or better justified.\n", "strength_and_weaknesses": "**Strengths**\n1. The paper is well-written \n1. It addresses an important and challenging problem: non-linear combinatorial optimization \n1. Strong empirical results: clear improvements over the baselines in 2 problems.\n\n**Weaknesses**\n1. The paper proposes a surrogate g(c) that is used with the non-linear function f — and not instead of f. Theoretically and intuitively, it is not clear why optimizing f(g(c)) (ie Eq 2) is better than directly optimizing f (Eq 1)\n   * I agree with the paper that the proposed optimization (Eq 2) allows to easily handle the linear constraints. But MINLP solvers also generally handle linear constraints (e.g. SCIP).\n   * I don’t agree or did not understand the other arguments (see questions 1 to 7)\n\n1. The theoretical analysis (Sec 3.4), that compares “learning solutions” versus the proposed “learning surrogate costs” only holds for a nearest neighbor regressor, which is a very special model and not realistic in practice. Therefore I don’t see how it supports the claims of the paper. \n   * For example, learning solutions for CO problems is often formulated as an auto-regressive task (e.g. Pointer Networks by [Vinyals et al 2015] or the Attention Model by [Kool et al 2019]) \n   * Are there any works that use nearest neighbor regression to predict the solutions of CO problems?\n\n1. Important information is missing in the empirical evaluation:\n    * How long did the training take, esp. in terms of number of calls to f?\n    * Training datasets are very small: 50 instances for the Embedding Table Sharding problem and 25 instances for the Inverse Photonic Design problem. More information about how training converges and esp. if/how overfitting is avoided would be beneficial. \n    * Regarding Inverse Photonic Design, it is not clear what's the objective and what are the constraints. \n    * It looks like the objective may be the “design misspecification loss”. Which means that the complex constraints are in fact penalized in the objective. This is a fair strategy when feasibility is challenging but then the argument that the proposed method is more able to handle complex constraints than existing works does not seem fair. [Sec 5: “However, these approaches are unable to handle more complex combinatorial constraints that arise in practice such as those in inverse photonic design”]. Or maybe there are other constraints that are handled — hence the need for a clear formulation of the problem.\n    * What’s the size of considered instances of the Inverse Photonic Design?\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject