Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information
Authors: Arman Zharmagambetov
Brandon Amos
Aaron M Ferber
Taoan Huang
Bistra Dilkina
Yuandong Tian
Venue: NeurIPS 2023 poster (2023)
Keywords: learning surrogates
predict+optimize framework
combinatorial nonlinear optimization
argmin differentiation
TL;DR: Introducing LANCER, a versatile framework designed to tackle challenging optimization problems, such as those found in nonlinear combinatorial problems, smart predict+optimize framework, etc.

Abstract: Recent works in learning-integrated optimization have shown promise in settings where the optimization problem is only partially observed or where general-purpose optimizers perform poorly without expert tuning. By learning an optimizer $\mathbf{g}$ to tackle these challenging problems with $f$ as the objective, the optimization process can be substantially accelerated by leveraging past experience. The optimizer can be trained with supervision from known optimal solutions or implicitly by optimizing the compound function $f\circ \mathbf{g}$. The implicit approach may not require optimal solutions as labels and is capable of handling problem uncertainty; however, it is slow to train and deploy due to frequent calls to optimizer $\mathbf{g}$ during both training and testing. The training is further challenged by sparse gradients of $\mathbf{g}$, especially for combinatorial solvers. To address these challenges, we propose using a smooth and learnable **Landscape Surrogate** $\mathcal{M}$ as a replacement for $f\circ \mathbf{g}$. This surrogate, learnable by neural networks, can be computed faster than the solver $\mathbf{g}$, provides dense and smooth gradients during training, can generalize to unseen optimization problems, and is efficiently learned via alternating optimization. We test our approach on both synthetic problems, including shortest path and multidimensional knapsack, and real-world problems such as portfolio optimization, achieving comparable or superior objective values compared to state-of-the-art baselines while reducing the number of calls to $\mathbf{g}$. Notably, our approach outperforms existing methods for computationally expensive high-dimensional problems.

Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information
Arman Zharmagambetov'
Brandon Amos
Aaron Ferber
Taoan Huang"
Bistra Dilkina"
Yuandong Tian'
FAIR Meta
University of Southern California
{armanz, bda. yuataannnnnnnnnttttaan... com
faferber, taoanhua, wilkina)
Abstract
Recent works in where the optimization problem only partially observed or where general-purpose optimizers perform poorly without expert tuning. By learning optimizer to tackle these challenging problems with f as the objective, the optimization process can be substantially accelerated by leveraging past experience. The optimizer trained with supervision from known optimal solutions or implicitly by optimiz- ing the compound function f g. The implicit approach may not require optimal solutions as labels and is capable of handling problem uncertainty; however, it is slow to train and deploy due to frequent calls to optimizer g during both training and testing. The training is further challenged by sparse gradients g. especially for combinatorial solvers. To address these challenges, we propose using a smooth and learnable Landscape Surrogate M as a replacement for o This surrogate, learnable by neural networks, be computed faster than the solver g. provides dense and smooth gradients during training, can generalize to unseen optimization problems, and efficiently learned via alternating optimization. We test our ap- proach on both synthetic problems, including shortest path and multidimensional knapsack, and real-world problems such as portfolio optimization, achieving com- parable or superior objective values compared to state- offte-of-une of-tthe-rt baselines while reducing the number of calls g. Notably, our approach outperforms existing methods for computationally expensive high-dimensional problems.
optimization have shown promise in settings
Introduction
Mathematical optimization problems in various settings have been widely studied, and numerous methods exist to solve them [25] 32). Although the literature on this topic is immense, real-world applications consider settings that are nontrivial extremely costly solve. The issue often stems from uncertainty in the objective or in the problem definition. For example, combinatorial problems involving nonlinear objectives are generally hard address, even if there are efficient methods that can handle special cases (e.g., k-means). One possible approach could be learning so-called linear surrogate costs [66 that guide an efficient linear solver towards high quality solutions for the original hard nonlinear problem. This automatically finds surrogate mixed integer linear program (MILP), for which relatively efficient solvers exist [19] Another example is the smart predict+optimize
framework k.. decision-focused learning) 13 41 where some problem parameters are unknown test time and must inferred from the observed input using a model (e.g.. neural nets).
Despite having completely different settings and purposes, what is common among learning surrogate costs, smart predict+optimize, and other integrations of learning and optimization, the need to learn a certain target mapping to estimate the parameters of latent optimization problem. This makes the optimization problem well-defined, easy to address, or both. In this work, draw general
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Original problems
Landscape surrogate M
learn Cg: min M (c) 0
use f), to refine M
milimber
Figure 1: Overview of our proposed framework LANCER. We replace the non-convex and often non-differentiabbe function/ f' o with landscape surrogate M and use it to learn the target mapping ce. The current output of cæ is then used to evaluate f and refine M. This procedure is repeated in alternating optimization fashion.
connections between different problem families and combine them into unified framework. The core idea (section 3 is to formulate the learning problem via constructing a compound function f f g that includes parametric solver and the original objective f. To the best of our knowledge, this paper is the first to propose a generic optimization formulation (section for these types of problems.
Minimizing this new compound function f o g via gradient descent is a nontrivial task as it requires differentiation through the argmin operator. Although various methods have been proposed to tackle this issue 3 21. they have several limitations. First, they are not directly applicable to combinatorial optimization problems, which have 0 gradient almost everywhere, and thus require various computationally expensive approximations
(34] 41 15 39]. Second, even if the decision variables are continuous, the solution space (i.e., argmin) may be discontinuous. Some papers [12] 17 discuss the fully continuous domain but typically involve computing the Jacobian matrix, which leads scalability issues. Furthermore, in some cases, an explicit expression for the objective may not be given, and we may only have black-box access to the objective function, preventing straightforward end-to-end backpropagation.
These limitations motivate Landscape Surrogate losses (LANCER), a unified model for solving coupled learning and optimization problems. LANCER accurately approximates the behavior of the compound function f o g. allowing us to use it to learn our target parametric mapping (see fig. T Intuitively, LANCER must be differentiable and smooth (e.g., neural nets) enable exact and efficient gradient computation. Furthermore, we propose an efficient alternating optimization algorithm that jointly trains LANCER and the parameters of the target mapping. Our motivation is that training LANCER in this manner better distills task-specific knowledge, resulting in improved overall performance. Experimental evaluations (section 5) confirm this hypothesis and demonstrate the scalability of our proposed method.
The implementation of LANCER can be found at httpp:///ithubb.cc///ccbboreeree LANCER
2 Related work
Smart Predict+Optimizz framework considers settings where want to train target mapping which predicts latent components to an optimization problem to improve downstream performance. straightforward and naive approach in P+O is to build the target machine learning model in two-stage fashion: train the model on ground truth problem parameters using some standard measure of accuracy (e-g., mean squared error) and then use its prediction to solve the optimization problem.
However, this approach is prone to produce highly suboptimal models (6] 41 since the learning problem does capture the task-specific objectives. Instead, "smart" Predict=Optimize (SPO) [I3 proposed to minimize the decision regret, i.c., the error induced by the optimization solution based on the estimated problem parameters coming from the machine learning model. A variety of methods exist for learning such models in the continuous, and often convex, optimization setting. These approaches usually involve backpropagating through the solver [2] some isolated and simple scenarios, an optimal solution exists (22). or the learning problem can be formulated via efficient surrogate losses [3] Extending the SPO framework for combinatorial problems challenging, and current methods rely on identifying heuristic gradients often via continuous, primal, dual relaxations
39
15
28 Alternative approaches leverage specific structures of
the optimization problem
9
2
40
such as being solvable via dynamic programming graph

---

partitioning. Further work focuses on SPO for individual problems Shah et al. [77, which collects perturbed imput instances and learns a separate locally convex loss for each instance. In contrast, we define the loss over the domain rather than per instance, allowing for generalization to unseen instances, and our bilevel optimization formulation enables more efficient training. Moreover, compared to prior works, our method generically applies to a wider variety of problem settings, losses, and problem formulations. See Table for a direct comparison of the requirements and capabilities for different approaches.
Mixed integer nonlinear programming (MINLP) LANCER can be considered as a solver for constrained combinatorial problems with nonlinear and nonconvex objectives (MINLP), a challenging
class of optimization problems [4. Apart from SurCo [6]. which we will discuss in detail in section 3
specialized solvers exist that deal with various MINLP formulations 7 19 These specialized
solvers generally require an analytical form for the objective and cannot handle black-box objectives. Additionally, these methods are not designed to handle general-purpont large-scale problems without making certain approximations or using specialized modeling techniques, such as linearizing the objective function or applying domain-specific heuristics. Lastly, some previous work directly predicts solutions to economic dispatch problems [8, uses reinforcement learning to build solutions to linear combinatorial problems [23], or uses reinforcement learning for ride hailing problems [43]. These approaches are designed for specific application domains are tailored to linear optimization settings where the reward for a single decision variable is its objective coefficient, which is not trivially applicable in nonlinear settings.
family of methods considers the composition of functions where one (or more) of the functions defined as the solution a mathematical
Optimization as layer
The optimization-as-tt
optimization problem K 2 17 18 Since both P+O and SurCo can be formulated as a nesting of
target mapping with the argmin operator (i.e., optimization solver), one can leverage approaches from this literature. The core idea here is based on using the implicit function theorem to find necessary gradients and backpropagate through the solver. Similar concepts exist for combinatorial where gradient non-existence is tackled through improved primal
optimization [15 33 28 or dual relaxations.
31 29
3 A Unified Training Procedure
In this work, we focus on solving the following optimization problems:
min f(;;))
s.t. x x f
(I)
where I is the function to be optimized (linear or nonlinear), Ω are the decision variables that must lie in the feasible region, typically specified by (non)linear (in)equalities and possibly integer constraints, and z E Z is the problem description (or problem features). For example, if is to find shortest path in a graph, then x is the path to be optimized, and z represents the pairwise distances (or features used to estimate them) in the formulation.
Ideally, we would like to have an optimizer that can (1) deal with the complexity of the loss function landscape (e.g., highly nonlinear objective f, complicated and possibly combinatorial domain ?!), (2) leverage past experience in solving similar problems, and (3) can deal with a partial information setting, in which only an observable problem description y can be seen but not the true problem description z when the decision is made at test time.
To design such an optimizer, we consider the following setting: assume that for the training instances, we have access the full problem descriptions {2,} S Z, as well as the observable descriptions {y:} C y, while for the test instance, we only know its observable description Ytest, but not its full description Ztest Note that such a setting naturally incorporates optimization under uncertainty, in which a decision need to be made without full information, while the full information can be obtained in hindsight (e.g.. portfolio optimization). Given this setting, we propose the following general training procedure on training set Dunin := ((y;, x)) to learn good optimizer:
N
min L(Y, = f ())()));2,)
(2)
3

---

Here ge : + Q learnable solver that returns a high quality solution for objective f directly from the observable problem description y.. are the learnable solver's parameters. Once go is learned, we can solve new problem instances with observable description Yustt by either calling Xtest = (yteest))) to get a reasonable solution, or continue to optimize Eqn. using x Xtest as an initial solution.
Theoretically, if problem description z is fully observable (i.e., y 2). the optimization oracle arg minlxen [xx z) solves Eqn. 2 However, solving may be computationally intractable even with full information as nonlinear combinatorial optimization.
Our proposed training procedure is general and covers many previous works that rely on either fully or partially observed problem information.
Smart Predict-Optimize (P+O) this setting, / belongs to specific function family (e.g.. linear quadratic programs). The full problem description z includes objective coefficients, but we only have access to noisy versions of them in y. Then the goal in P+O is to identify a mapping ca (c.g. a neural net) that a downstream solver outputs high quality solution: gy(y) arg minxen [x; co (y)). Here arg minxen f can often be solved with standard approaches, and the main challenge is to estimate the problem description accurately (w.r.t. eq. (2). Note that other P+O formulations can be encompassed within our framework in eq. 2 For instance, the regret- based formulation described in SPO [13] can be represented maxzege (y) I (2;2)
where I" the
optimal loss that is independent of O.
Learning surrogate costs for MINLP When f is general nonlinear objective (but y z is fully observed), computing arg mingen ff also becomes non-trivial, especially if x is in combinatorial spaces. Such problems are commonly referred as mixed integer nonlinear programming (MINLP). To leverage the power of linear combinatorial solvers, SurCo [16] sets the learnable solver to be gy(y) arg min x" co (y), which is linear solver and does not include the nonlinear function f at all. Intuitively, this models the complexity of f by the learned surrogate cost Cg. which is parameterized by neural network. Surprisingly, this works quite well in practice [16]
4 LANCER: Learning Landscape Surrogate Losses
Variations of training objective Eqn. have been proposed learn 0 in one way or another. This includes derivative-baset approaches discussed in section 2 as well as domain -omaiin-ppecifc methods that learn efficiently and avoid backpropagating through the solver, e.g., SPO+ [3].
While these are valid approaches, at each step of the training process, we need to call a solver to evaluate go, which can be computationally expensive. Furthermore, go learned via gradient descent of Eqn. 2 which involves backpropagating through the solver. One issue of this procedure is that the gradient is non-zero only certain locations (i.e., when changes in the coefficients lead to changes in the optimal solution), which makes the gradient-based optimization difficult.
One question arises: can model the composite function o ge jointly? The intuition here is that while go can be hard to compute, f o go can be smooth to model, since f can be smooth around the solution provided by ge. If we model o go locally by landscape surrogate model M, and optimize directly on the local landscape of M, then the target mapping co can be trained without running expensive solvers:
min M(Y,M) = Σ M (co(y:):2.).
Note that M directly depends on (not on ge). Obviously, M cannot be any arbitrary function. Rather it should satisfy certain conditions: 1) capture task-specific loss f o go (not just f and not the solver g alone, but jointly); 2) be differentiable and smooth. Differentiability allows us to train our target model co end-to-end fashion (assuming c is itself differentiable). The primary advantage is that we can avoid backpropagating through the solver even through f (e.g., multi- armed bandits). Moreover, Mw typically high dimensional (e.g., a neural net) and potentially can make the learning problem for Co much easier. The question is how obtain such model M? One

---

way is to parameterize it and formulate the learning problem:
N
min W
(x)) (go- (y):
(4)
s.t.
0 E argmin
Σ M (coc()) 2:).
The main motivation for this bi-level optimization formulation is that the surrogate model Mw not concerned to be accurate for all possible Cę: rather, we are interested in finding the configuration of Mw that yields the closest approximation loss that approximates L at a certain landscape: MM (Y, Z; 0") ~ L(Y, Z: 0*). By adopting the bi-level optimization framework, we can focus on learning accurate Mw for such 6*.
fog near 0*, In other words, MM serves as a surrogate
It is important to note that evaluating f Tog depends on both cy(y:) and z; (see eq. (2). Therefore, to construct accurate surrogate model MM that effectively approximate f g, is essential for Mw to take into consideration the influence of both inputs.
To solve eq. 4 one could apply established methods from the bi-level optimization literature, such as (1744) However, majority of them still rely on VeC (or even V2). which involves differentiating through the solver. To overcome this issue, we propose simple and generic Algorithm [1 which based on alternating optimization (high-level idea is depicted in fig. [ The core idea to simultaneously learn both mappings (Mw and cœ) explore different solution spaces. By improving our target model Cg. we obtain better estimates of the surrogate loss around the solution, and a better estimator MW leads better optimization of the desired loss L. The of alternating optimization helps both mappings reach a common goal. Furthermore, similarly flavored alternating optimization techniques were found to be successful in other problems with non-differentiable nature 44 45)
In practice, the "inner" optimization (lines 10 and 12) does not have to be done "perfectly". In our approach, we perform fixed (smaller) number of updates; that is, do not precisely solve the minimization for both Mw and Cg. For example, most experiments use 10-20 updates per t. One potential reason is that do not want the models to overfit to the data; instead, increase the total number outer loop T. We discuss this further in the experimental setup.
Algorithm Pseudocode for simultancously learning LANCER and target model cp. Note that the algorithm may vary slightly based on setting (e.g.. P+O and variations of SurCo see Appendix
1: Input: Deain + {y., ) solver g, objective f, target model co:
2: Initialize ce (e.g. random. warm start):
3: for 1...=..11 do
-w-ttep (fix and optimize over w): 5: for (yt, z,) E Durain do
6:
evaluate C. = co (y:);
7:
evaluate f: (g(C;) 2:);
add (Gs, zi, fi) D;
9:
end for solve minw EiED Mw(e, 2.) f.l via supervised learning:
11: O-step (fix w and optimize over 0):
12:
solve ming Exermin Mw (co , z.) via supervised lcarning.
13:
end for
Note that the Algorithm D avoids backpropagating through the solver or even through f. The only requirement is evaluating the function f at the solution of g. which can be achieved by blackbox solver access. As result, this approach eliminates the complexity and computational expense associated with computing derivatives of combinatorial solvers, making it a more efficient and practical solution as shown in [
is worth noting that our framework shares similarities with actor-critic reinforcement learning 24 In this analogy, we can think of cp an actor responsible for making certain decisions, like predicting coefficients. On the other hand, M. plays the role of critic which evaluates the actor's decisions by estimating the objective value f. and provides feedback to the actor.
5

---

Table 1: Conceptual comparison of methods from related literature. Capabilities on the left are present or not for Methods the top. = given when this capability depends empirically on the problem at hand.
Feature Method
LANCER
SurCo
16
LODLs
37
SPO+
13
DiffOpt 15
34
Exact
36
On-the-fly opt Nonlinear f Blackbox f f not required Ögo not required Generalization
+
+
+
+
+
+
Few fast solver calls
1
Similar to many other approaches designed for solving problems with bi-level optimizations, including actor-critic algorithms, we currently lack theoretical guarantees regarding the convergence of LANCER with respect to either Mw or Cg. This lack of guarantees can also impact the stability of the algorithm. However, this is primarily matter that can addressed through empirical investigation and depends on various factors, which is typical in the process of model selection. In Appendix E we present ablation studies that we conducted evaluate the stability of our approach across various hyperparameters and neural network architectures. These, along with our main experimental results in section []] demonstrate that LANCER generally exhibits robustness in many cases.
4.1 Reusing landscape surrogate model MM
Once Algorithm|] finishes, we usually discard Mw as is an intermediate result of the algorithm, and we only retain Co (and solver g) for model deployment. However, we have found through empirical exploration that the learned surrogate loss MM can be reused for range of problems, increasing the versatility of the approach. This is particularly advantageous for SurCo setting, where we handle one instance at time. this scenario, we utilize the trained Mw for unseen test instances by executing only the O-step of Algorithm [ The main advantage of this extension is that it eliminates the need for access to the solver g, leading to significant deployment runtime improvements.
4.2 Reusing past evaluations of f
In LANCER, the learning process MM is solely reliant on D and is independent of the current state of ca. Put simply, to effectively learn M.w we only need the inputs and outputs of f ge- namely cy(y;) Z, and the corresponding objective value f. Interestingly, descriptions themselves, (y;).. without the need for the model 0 or problem information. This caching mechanism allows us to reuse the data (co (y:),, z, from previous iterations (1... 1) as-is. By adopting this practice, enhance and diversify the available training data for MMw which proves particularly advantageous for neural networks. This concept bears resemblance to the concept of replay buffer 27 commonly found in the literature on Reinforcement Learning.
can cache the predicted
5 Experiments
We validate our approach (LANCER) in two settings: smart predict+optimize and learning surrogate costs for MINLP. For each setting, study range of problems, including linear, nonlinear, combinatorial, and others, encompassing both synthetic and real-world scenarios. Overall, LANCER exhibits superior comparable objective values while maintaining efficient runtime. Additionally, we perform ablation studies, such as re-using M.
5.1
Synthetic data
5.1.1
Combinatorial optimization with linear objective
The shortest path (SP) and multidimensional knapsack (MKS) are both classic problems in combina- torial optimization with broad practical applications. In this setting, we consider a scenario where problem parameters z, such as graph edge weights and item prices, cannot be directly observed

---

Shortest Path
Multidimensional Knapsack
17.5
Normalteen Hegget (%6
lawd largee
12.5
10.0
7.5
5.0
SPO
D68
LOOLS
LANCER
SPD+
D8B
LOOLS
LANCER
Figure 2: Normalized test regret (lower is hetter) for different P+O methods: 2-stage, SPO+ [3] DBB B4). LODLs (37 and ours (LANCER). Overlaid dark green bars (right) indicate that the method warm started from the solution 2stg. DBB performs considerably worse on right benchmark and cut on the y-axis.
during test time, and instead need to be estimated from via learnable mapping cy) That is, we consider smart P+O setting.
Setup We use standard linear program (LP) formulation for SP and mixed integer linear program (MILP) formulation for MKS. Observed features y and the corresponding ground truth problem descriptions z for SP are generated using the same procedure as in [38]: grid size of 5 x 5, feature dimension of y E I (obtained using a random linear mapping from z). 1000 instances for both train and test. For MKS, we increased the knapsack dimension 5 and capacity to 45, and we set the number items to 100, Moreover, we use randomly initialized MLP (1 ReLu hidden layer) to generate features of dimension y E 2556 As for the baselines, apart from the naive 2-stage approach, we have SPO+ 13 and DBB 34). both implemented in PyEPO [38] library. Furthermore, we could all important
added LODLs, novel method from Shah al. (37.. We explored as best hyperparameters for all methods on fixed cross-validation set. Regarding the LANCER, we utilize ML.P with 2 tanh hidden layers of size 200 for surrogate model M. We set T = 10 and the number of updates for M and co is at most 10. We use SCIP [ to solve I. for the shortest path and MILP for knapsack. Further details be found in Appendix C.1.1
Results The results are summarized in fig. 2 We report the normalized regret as described in (38). The findings indicate that LANCER and SPO+ consistently outperform the two-stage baseline, particularly when considering the warm start. As SPO+ is specifically designed for linear programs, provides informative gradients, making robust baseline. Even MKS, where theorems proposed in [13 are no longer applicable, SPO+ performs decently with minimal tuning effort. The DBB approach, however, demonstrates unsatisfactory default performance but can yield favorable outcomes with proper initialization and tuning (see the right plot). Interestingly, the other P+O baselines, initialized randomly, were unable to outperform a naive 2stg both benchmarks.
LANCER achieves superior performance in both tasks, with a noticeable advantage in MKS. This may be attributed to the high dimension of the MKS problem and the large feature space (y). One possible explanation is that the sparse gradients of the derivative-basee method make the learning problem harder, whereas LANCER models the landscape of f o g. providing informative gradients for Co.
5.1.2 Combinatorial optimization with nonlinear objective
In this section, apply LANCER for solving mixed integer nonlinear programs (MINLP). Specifically, we transform a combinatorial problem with a nonlinear objective into an instance MILP via learning linear surrogate costs as described in Ferber et al. [16]. Note that in this setting, assume that the full problem description y z is given and fully observable (in contrast to the P+O setting).
We begin by examining on-the-fly optimization, where each problem is treated independently. In this scenario, cost vector cy(y) simplifies to constant value c. SurCo is then responsible for directly training the cost vector e of the linear surrogate. As we lack a distribution of problems to train M. are necessary, which are outlined in detail Appendix refer to this version LANCER-Zene to be consistent with SurCo-zero.
specific adaptations to Algorithm| |
We
7

---

Grid 5x5
Grid 15x15
0.10
Domain Heuristk SurCo-zero
SCIP
0.3
LANCER zero
On Time Probubility
3.50
0.50
0.46
0.45
CIM
out time
out time
out time
0.40
0.25
Locse Deadline
Normal Deadline Settings
Tight Deadline
Loose Desdlne
Normal Deadline Settings
Tight Deadline
Figure 3:
Results on stochastic shortest path using different grid sizes: 5x5 (left) and 15x15 (right). We report
avg objective values (higher is better) on three settings described in [16] For grid size of 15x15, SCTP unable to finish within the 30 min time limit.
was
Setup Nonlinear shortest path problems arise when the objective is to maximize the probability of reaching destination before a specified time in graphs with random edges 26 14. The problem formulation is similar to the standard linear programming (LP) formulation of the shortest path, as described section 5.1.I with few adjustments: 1) the weight of each edge follows normal distri- bution, i.c., along the shortest path is below threshold W. which can be expressed using the standard Gaussian cumulative distribution function (CDF), PÉ We S W) = & ((W - Me)/ / / Ve Te) where E is the set of edges belonging to the shortest path. We use 5 x 5 and 15 x 15 grid graphs with 25 draws of edge weights. We the threshold W three different values corresponding to loose, normal, and tight deadlines. The remaining settings are adapted from Ferber et al. [16. and additional details can be found in Appendix C.1.2
A (Jte, oe); 2) the objective is to maximize the probability that the sum of weights
Results Fig. iillustrates the performance of different methods in both grid sizes. SCIP directly formulates the MINLP to maximize the CDF, resulting in an optimal solution. However, this approach is not scalable for larger problems and is limited to smaller instances like the 5 x grid. The heuristic method assigns each edge weight as ui fee + c0. where y user-defined hyperparameter, and As the results indicate, this heuristic
employs standard shortest path algorithms (e.g., Bellman-Fordd approach produces highly suboptimal solutions. SurCo-zer and LANCER zero demonstrate similar performance, with LANCER-7ero being superior in almost all scenarios.
5.2
Real-world use case: quadratic and broader nonlinear portfolio selection
5.2.1 The quadratic programming (QP) formulation
tackle the classical quadratic Markowitz [30] portfolio selection problem. We use real- world data from Quandl (35) and follow the setup de- scribed in Shah et al. [37] The prediction task leverages each stock's historical data y to forecast future prices z, which are then utilized to solve the QP (i.e., P+O setting). The predictor the MLP with 1 hidden layer of size 500.
In this study,
Table 2: Portfolio selection normalized test decision loss (lower is better).
Method
Test DL
Random
Optimal
2-Stage
0.57 0.02
LODLs [37
0.55 0.02
Setup We follow a similar setup described in (37] ex- cept for fix in the objective's quadratic term that slightly affects the decision error's magnitude. More details can be found in Appendix C.2.T We compare LANCER against two-stage and LODLs. However, SPO+ is not applicable in this nonlinear setting, and DBB's s per- formance notably worse since designed for purely combinatorial problems. Additionally, we report the optimal solution (using the ground truth values of 2) and the (Melding Decision Focused Learning) MDFL. 41 method, which leverages the implicit function theorem differentiate through the KKT conditions. For LANCER implementation,
MDFL 41)
0.52 0.01
LANCER
0.53 1 0.02
MLP with 2 hidden layers for M

---

and update each of the parametric mappings 5 times per iteration with total of T 8 iterations. We use evxpy [0] solve the QP.
Results 2 summarizes results. We report the normalized decision loss (i.c., normalized Eqn. 2 on test data. Since the problem is smooth and exact gradients can be calculated, MDFL achieves the best performance closely followed by the LANCER. The remaining results in agreement with (37. While LANCER does not achieve the best overall performance, it does so using significantly smaller number of calls to solver, as we discuss in more detail in Section 5.3
5.2.2 Combinatorial portfolio selection with third-order objective
The convex portfolio optimization problem dis- cussed the previous section [52.1] is unable capture desirable properties such as logical constraints 15] 15), or higher-order loss func- tions (20) that integrate metries like co-skewness to better model risk. We use the Quandl (35)
0.025
0.000
10
-0.025
100
200
1000
data (see Appendix CC2.22 for details on setup) and similar to section 5.1.2 we assume that the
Objective
-0.050
random
SANCER-Zero
20
LANCER-prior MILP -0.100
-0.075
full problem description z given at train/test time.
MIQP
-0.125
MINLP- approx
Results are shown in fig. 4 We first tried to solve the given MINLP exactly via SCIP. How- ever, it fails produce the optimal solution within a hour time limit and we report the best incumbent feasible solution. MIQP (blue squares) and MILP (blue triangles) approxima- tions overlook the co-skewness and non-linear terms, respectively. Comparing their perfor- mance, MIQP exhibits a 2x lower loss than the MILP baseline but in significantly longer runtime. For LANCER and SurCo, we present results for two scenarios: learning the linear cost vector directly (zero) for each instance, and parameterized version (z) (prior). The main distinction of "prior" that no learning occurs during test time, as we directly map the problem descriptor to linear cost vector and solve the MILP. Consequently, the deployment runtime is similar to that of the MILP approximation, but LANCER- MANior produces slightly superior solutions. Remarkably, LANCER-Zero achieves significantly better loss values, surpassing all other methods. Although it takes longer to run, the runtime remains manageable, and importantly, the solution quality improves with increasing number of iterations.
0.150
SurCo-prior
SurCo-zero
-0.175
109
10a
10a
10a
Deployment Runtime (s)
Figure 4: Objective (lower is better) and deployment runtime for combinatorial portfolio selection problem. For LANCER zero and SurCo- zcro, numbers each point correspond to the number of iterations.
According to our experimental findings, LANCER demonstrated the most substantial improvement in this specific setting. Encouraged by this success, we conducted deeper exploration of the complexities of this problem, as detailed in Appendix
5.3 Computational efficiency
Comparing baseline methods, including LANCER, we find that querying solver go is the primary computational bottleneck. To evaluate this aspect, we empirically analyze different algorithms on various benchmarks in the P+O domain. The results, depicted in fig. [5] highlight that LODLs require sampling relatively large number of points per training instance, leading to potentially time-consuming solver access. On the other hand, gradient- based methods like DBB, MDFL, and SPO+ typically solve the optimization problem 1-2 times per update but require more iterations to converge. contrast, LANCER accesses the solver the w-step, with the number of accesses proportional to the training set size and small total number of alternating optimization iterations. Moreover, we leverage saved solutions from previous iterations, akin to replay buffer, when fitting M. These combined factors allow us to achieve favorable results with small value of T.

---

Multidimensional Knapsack
Portfolio Optimization
DGB
0.55
MDFL LODLS
SPC+
0.55
LANCER
LANCER
100
Decision Lees
Normetoed fagget
52-
0.54
0.53
10
a9-
20
0.52
0.51
4
20
0.50
200
10'
10*
10'
10t
10"h
10
Number to solver
Number cal solver
Figure 5: Trade-off curves between black-box solver calls (MILP QP) vs decision loss (or regret) on P+O problems. Point labels (e.g. 1,4,7) correspond the epoch; except for LODL,s, where they correspond to the number of samples per instance. Each algorithm uses different numher BB calls per epoch.
Table 3:
Results reusing on stochastic shortest path problem from fig. [15 grid). Here, "reused Mw has limited access to solver g, and thus much faster while retaining solution quality.
Method
Loose Deadline
Normal Deadline obj.
Tight Deadline obj.
obj.
time (s)
time (s)
time (s)
LANCER-ZeTO
0.556 + 0.006 61.1 3.2 0.497 0.004 62.3 + 2.9
0.434 + 0.005 62.8 2.7
LANCER-reused Mw
0.556 + 0.007 2.9 + 0.3 0.496 0.004 2.7 + 0.6
0.432 + 0.004
2.5 + 0.6
5.4 Reusing landscape surrogate Mw
In this scenario, we introduce dependency of Mw on both the predicted linear cost (c) and the problem descriptor (y), as described in section 4.1] This enables us to reuse MM for different problem instances without retraining, and eliminate substantial runtime acceleration. To validate this hypothesis, we pretrain Mw using 200 instances of the stochastic shortest path on x 15 grid by providing concatenated (c,y) as input. We apply LANCER-Ze zero to the same test set before and present results in performance between these two approaches, with "reused Mw being much faster.
dependency on the solver go. giving LANCER
fig. [ demonstrating comparable
6 Conclusion
This paper makes a dual contribution. Firstly, we derive a unified training procedure to address various coupled learning and optimization settings, including smart predict+optimize and surrogate learning. This significant as advances our understanding of learning-integratee optimization under partial information. Secondly, we propose effective and powerful method called LANCER to tackle this training procedure. LANCER offers several advantages over existing literature, such as versatility, differentiabilityy. and efficiency. Experimental results validate these advantages, leading to significant performance improvements, especially in high-dimensional spaces, both in problem description and feature space. One potential drawback is the complexity of tuning M, requiring model selection and training. However, future research directions include addressing this drawback and exploring extensions of LANCRR, such applying it fully black box f scenarios.
Acknowledgments and Disclosure of Funding
The research at the University of Southern California was supported by the National Science Foun- dation (NSF) under grant number 2112533. We also thank the anonymous reviewers for helpful feedback.
References
[1] Achterberg. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1-41, July 2009. ISSN 1867-2957. doi: 12532-008-0001--
10

---

[2] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems (NEURIPS), volume 32, pages 9562 1572-9574. MIT Press, Cambridge, MA, 2019.
[3] B. Amos and J. Z. Kolter. Optnet: Differentiable optimization as a layer in neural networks, In D. Precup and Y. W. Teh, editors, Proc. of the 34th Int. Conf. Machine Learning (ICML 2017), pages 136--144 145, Sydney, Australia, Aug. 6-11 2017.
[4] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1-131, May 2013.
[5] D. Bertsimas, C. Darnell, and Soucy. Portfolio construction through mixed inteegerr program- ming at grantham, mayo, van otterloo and company. Interfaces, 29:49-66, 1999.
[6] A. Beygelzimer and J. Langford. The offset tree for learning with partial labels. In Proc. of the 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (SIGKDD 2009), Paris, France, June 28 -July 1 2009.
[7] S. Burer and A. N. Letehford. Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science, 17(2):97-106, 2012. ISSN 1876- 7354.
[8] W. Chen, S. Park, M. Tanneau, and P. Van Hentenryck. Learning optimization proxies for large-scale security-onsstraieed economic dispatch. Electric Power Systems Research, 213: 108566, 2022.
[9] E. Demirović, P. J. Stuckey, J. Bailey, J. Chan, C. Leckie, K. Ramamohanarao, and T. Guns. Dynamic programming for Predict+Optimise. In Proceedings of the AAAI Conference Artificial Intelligence, 2020.
[10] S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016..
[11] Domke. Generic methods for optimization- modeling. In N. Lawrence and M. Girolami, editors, Proc. of the 15th Int. Conf. Artificial Intelligence and Statistics (AISTATS 2012), La Palma, Canary Islands, Spain, Apr. 21-23 2012.
[12] Donti, B. Amos, and Z. Kolter. Task-based end-to-end model learning in stochastic optimization. In I. Guyon, U. v. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems (NIPS), volume 30, pages 1320-1332. MIT Press, Cambridge, MA, 2017.
[13] A. N. Elmachtoub and P. Grigas. Smart "predict, then optimize". 1rX1v:1710.08005, Oct. 22 2017.
[14] Y. Y. Fan, R. E. Kalaba, and J. E. Moore. Arriving on time. Journal of Optimization Theory and Applications, 127(1):977-513 Dec. 2005, doi: 10.10077:10997-005--4499
[15] A. Ferber, B. Wilder, B. Dilkina, and M. Tambe. MIPaaL: Mixed integer program as a layer. In AAAI Conference on Artificial Intelligence (AAAI 2020), 2020.
[16] A. Ferber, T. Huang, D. Zha, M. Schubert, B. Steiner, B. Dilkina, and Y. Tian, Surco: Learning linear surrogates for combinatorial nonlinear optimization problems. arXiv:2210.12547, Oct. 22 2022.
[17] S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differenti- ating parameterized argmin and argmax problems with application to bi-level optimization. 1rXiv:1607.05447., July 21 2016.
[18] S. Gould, R. Hartley, and D. Campbell. Deep declarative networks: new hope. NXX.:11909004666 Sept. 11 2019,
[19] Gurobi. Gurobi optimizer reference manual, 2019.

---

[20] C. R. Harvey, J. C. Liechty, M. W. Liechty, and P. Muller. Portfolio selection with higher moments, Quantitative Finance, 10:469-455 485. 2010.
[21] X. Hu, J. C. Lee, J. H. Lee, and A. Z. Zhong. Branch & learn for recursively and iteratively solvable problems in predicttoptimize. arXiv:2205.0167,, May 01 2022.
[22] Y.-h. Kao, B. Roy, and X. Yan. Directed regression. In Advances in Neural Information Processing System, 2022.
[23] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[24] V. R. Konda and J. N. Tsitsiklis, Actor-critic algorithms. In Advances in Neural Information Processing System, 1999.
[25] B. Korte and J. Vygen. Combinatorial Optimization; Theory and Algorithms. Number 21 in Algorithms and Combinatorics. Springer-Vette sixth edition, 2018
[26] S. Lim, C. Sommer, E. Nikolova, and D. Rus. Practical route planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems VIII, pages 249-256, 2012. doi: 20.156 V01.I............
[27] L.-J. Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8:293 -321, 1992.
[28] Mandi, P. Stuckey, T. Guns, al. Smart predict-and-optimize for hard combinatorial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1603-1610, 2020.
[29] J. Mandi, V. Bucarey, M. M. K. Tchomba, and Guns. Decision-focused learning: Through the lens of learning to rank. In International Conference on Machine Learning, pages 14935-14947 PMLR, 2022.
[30] H. Markowitz. Portfolio selection. J. of Finance, 7(1):77-91, Mar. 1952.
[31] M. Niepert, P. Minervini, and L. Franceschi. Implicit mle: backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 34: 14567-14579, 2021.
[32] Nocedal and J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer-Verlage New York, second edition, 2006.
[33] A. Paulus, M. Rolínek, V. Musil, B. Amos, and G. Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints.
StV:22155.02443, May 12 2021.
[34] M. V. Pogančić, A. Paulus, V. Musil, G. Martius, and M. Rolinek. Differentiation of blackbox combinatorial solvers. In Proc. of the 8th Ini. Conf. Learning Representations (ICLR 2020), Addis Ababa, Ethiopia, Apr. 26-30 2020.
[35] Quandl. Wiki various end-of-day data, 2022.
[36] N. V. Sahinidis. BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs, User's Manual, 2017.
[37] S. Shah, K. Wang, B. Wilder, A. Perrault, and M. Tambe. Decision-focused learning without decision-making Learning locally optimized decision losses. In Advances in Neural Information Processing System, pages 1320-1332, 2022.
[38] B. Tang and E. B. Khalil. Pyepo: A pytorch-based end-to-end predoictthen-optimiiee library for linear and integer programming. arXiv:2206.1 14234, June 28 2022.
[39] P.W. Wang, P. Donti, B. Wilder, and Z. Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference on Machine Learning, pages 6545-6554. PMLR, 2019.
12

---

[40] B. Wilder, E. Ewing, B. Dilkina, and M. Tambe. End to end learning and optimization on graphs. In Advances in Neural and Information Processing Systems, 2019.
[41] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In AAAI Conference Artificial Intelligence (AAAI 2020), 2020.
[42] M. Ye, B. Liu, S. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach. In Advances in Neural Information Processing System, 2022.
[43] E. Yuan, W. Chen, and P. Van Hentenryck. Reinforcement learning from optimization proxy for ride-hailing vehicle relocation. Journal of Artificial Intelligence Research, 75:985-1002, 2022.
[44] A. Zharmagambetov and M. Á. Carreira-Perpittae Learning interpretable, tree-based projection mappings for nonlinear embeddings. In International Conference on Artificial Intelligence and Statistics, pages 9550-9570, 2022.
[45] A. Zharmagambetov and M. Á. Carreira-Perpinat Semi-supervised learning with decision trees: Graph Laplacian tree alternating optimization. In Advances in Neural Information Processing System, 2022.
13

---

A Computational complexity
Tin in the main paper. Let us denote lg the time to get the solution from solver g(y:). Also, let Iw and To be the runtime of training the parametric loss Mw and the target model Cø. respectively. Then, assuming evaluating is negligible, one iteration of our algorithm naively takes O gg + Iw + Ie). so the total runtime O(T N l T. I T To). ). practice, we iterate at most 100 times (7 100). Therefore, the main bottleneck is O(T N Ig). which is mainly overtaken by an access to Although we claim that leveraging M to learn 0 efficient, we admit that there still requirement access the solver g.
is quite straightforward estimate the runtime of our approach from Algorithm
However, there are several accelerations that can be made:
O(N 1g) embarrassingly parallel computation since each request g is independent and, additionally, subsampling on Drain can be performed.
2. We can "warm start" the solver g from solutions obtained in t 1, which typically yields faster convergence.
3. Although we did not test this, but one can "early stop" the solver g if it is too costly to solve optimally (e.g. large scale MILP). Our hypothesis is that it enough obtain feasible solution & in certain neighborhood of x". Since we are still able to evaluate f and (J($),, é, z) a "valid" tuple, we can use train Mww
4. Moreover, empirically found out that the supervised learning steps (lines 10 and 12) do not require "perfect" learning. That is, we perform several gradient updates over w and 0, which significantly reduces Tw and Io.
B Pseudocodes
Algorithms/ below closely resemble the Algorithm in the main paper. However, there minor variations that depend on the problem setting, whether it involves learning linear surrogates for MINLP smart Predict+Optimize setting.
Algorithm 2 Pseudocode for learning LANCER and target model Co for smart Prrdict+Optimie setting, Note: y input (always observed) features, ground truth problem descriptions (available at train time only).
1: Input: Durin < {y:. z, Ji=1: solver g, objective f (can be black-box), target model co. (optional) prediction loss penalty X;
N.
2: Initialize co from solving: ming Σie [co(y:) 2ill:
3: Set D + 00:
4: for 1...7 do
w-sttep (fix 0 and optimize over w); 6: for (yi, 2;) Drain do
5:
7:
evaluate č; = co (y:);
8:
evaluate f. = f(g(c.):z.):
9:
add (Ć:, Zi, (i) D: end for minimize: minw EjeD Mw 2,) -fyli fal1:
10:
11:
O-step (fix w and optimize over 0): minimize: ming ΣieP,,, My (co (y,), 2 Al|co(y.) z,|l-
13:
14:
end for
14

---

Algorithm 3 Pseudocode for learning linear surrogates with LANCER-Zero (used in sections|5.1. and
5.2.2) Note that y this setting and we have only one optimization problem instance.
1: Input: problem description solver g, objective f (can be black-box);
2: Initialize R
3: Set D 0:
4: for 1.... do
5:
w-step (fix с and optimize over w): randomly sample { around for L...N do evaluate f== f(g(e.):)) add (c,, fo) to D:
6:
7:
8:
9:
10:
end for minimize: minw EjeD M
11:
12:
O-step (fix w and optimize over c): 1/0 this setting as we solve for single problem instance y
14:
minimize: mine (c).
end for
Algorithm Pseudocode for learning linear surrogates with LANCER-prior (used in section 5.2.2): we learn Co on a distribution optimization problems. Note that y in this setting
1: Input: Dasin + {y: J.M. solver g, objective f (can be black-box), target model co:
2: Initialize Co (random, warm start from heuristics);
3: Set D +- ():
4: for =.... do
ww-step (fix 0 and optimize w): 6: for (y:) E Dirrii do evaluate c; cy():); evaluate f, f(g()))) add (c, to D; end for minimize: minw EjED Mw(Cj, Otstep (fix w and optimize over 0): minimize: ming ΣieDo. Mw (co (:)
5:
7:
8:
9:
10:
12:
14: end for
C Details of experimental setup
C.1
Synthetic data
C.1.1
Combinatorial optimization with linear objective
Data
We follow the setup and scripts from PyEPO 38 library to generate data.
For SP, we follow the same data generation process as in the original scripts: grid (40 total edges), 1000 training problem instances with input features (i.e., Y E IR 10000555 and the same for the test set. Input features (y) are generated using normal distribution with (O, 1). The ground truth descriptors z are obtained by first randomly and linearly projecting y in 40 dimensions followed by nonlinearity (polynomial of degree 6 and normalization). Lastly, random noise is added to to make the problem harder. We use the standard linear program (LP) formulation of the shortest path and implement solver g in SCIP M.
As for MKS, we begin by generating a cost vector for each item using random uniform distribution between and 5. Then, we obtain features y by passing through a random neural network with one hidden layer of size 500 and tanh activation. Knapsack capacity is 40, knapsack dimension is 5, 100 total items to choose from, feature dimension 256 and there are 1000 instances in both train/test. Lastly, weight for each item is generated
15

---

according to the uniform distribution between 0 and 1. We use the standard mixed- mixed-integer integer linear program (MILP) formulation of the multidimensional knapsack and implement solver g in SCIP
Target mapping co All baselines use the same target mappings for each problem: linear mapping for SP and MLP with hidden layer for MKS (size of 300 and tanh activation).
LANCER The training procedure closely follows Algorithm Other problem dependent settings are as follows:
For SP, LANCER uses MLP with 2 hidden layers of size 100 (tanh activation). We train LANCER for = 10 iterations. At each iteration, we make 5 updates (using Adam optimizer with Ir= 0.001) for each mappings (ce and Mw).
For MKS, LANCER uses MLP with hidden layers of size 200 (tanh activation). We train LANCER for T iterations. At each iteration, we perform updates (using Adam optimizer with Ir= 0.001) for Cę and 10 updates for Mw.
Baselines
SPO+,DBB: We use the versions implemented within PyEPO and set the number epochs to 25, Both methods use the Adam optimizer with learning rates tuned for each problem. Other arguments follow the default setting suggested by authors.
LODLS: We use the implementation provided by authors in (37). We set the number of sampling points to 1000 and employ "random Hessian" version of the algorithm. Other arguments follow the default setting suggested by authors.
C.1.2 Combinatorial optimization with nonlinear objective
We aim to solve the following optimization problem with nonlinear objective:
min +
(W
Σ
Σ
T an
(u,D)E
(u,jEE
s.t.
Σ
Fnat 21
(at least one unit of flow into 1)
(5)
(ut)EE
Σ
Fugt
Σ
Fn,t 20
Ve E {8,1}
(flow 2 flow out)
E
#:(o,))E
X x2 0
where & is the standard Gaussian cumulative distribution function (CDF), E is the of all edges, W is the user-defined threshold, fu,o and Du,e are the mean and the variance of the corresponding edge's weight.
Data We closely follow the data generation process described in 16]. Specifically, each edge is random variable with μ coming from the uniform distribution (between 0.1 and 0.2); and with is also generated uniformly randomly (between 0.1 and 0.3 multiplied by - μ). For thresholds W, we them follows: calculate the distance of the shortest path distance using the mean value as an edge weight and multiply it to 0.9 for tight. 1.0 for normal and 1.1 for loose deadlines, respectively. We set the number of problem instances to 25 and use the Bellman-Forr algorithm for solver g.
LANCER The training procedure closely follows Algorithm 3 We use MLP with 2 hidden layers of size 200 (300 for 15 15 grid size) and tanh activation. We train LANCER for T 40 iterations. At each iteration, we make 10 updates (using Adam optimizer) for each learnable models (c and Mw).
Baselines
SCTP attempts to solve the original MINLP defined Eqn. 5 limit to 30 min before terminating the solver.
We set the maximum time
16

---

Domain Heuristic simply assigns each edge's weight as = Me + Yo (where is hyperparameter) and run the Bellman-Forts algorithm.
SurCo [T6] replicates the
experimental setup as described in the original paper.
Specifically, we use DBB (34] to differentiate through the solver with 1000 and apply Adam optimizer for 40 epochs with the learning rate 0.1.
C.2 Real-world use case: quadratic and broader nonlinear portfolio selection
C.2.1 The quadratic programming (QP) formulation
We use the standard quadratic program formulation of the Markowitz' 30 portfolio selection problem:
min ax aaaaxxaGG Gx 1²x
(6)
2q -==1 S.L. Σ
and
X
where la is expected return vector for each portfolio and G is the covariance matrix. We set the user-defined hyperparameter a = 0.1 in all experiments and use CvxPy [0] to solve QP in eq. (6).
Data We reuse the code from Shah al. [37 generate data (downloaded from QuandIWIKI 35
and use the same setup. The features y are historical stock prices and the task is to predict an expected return 7 (using MLP with hidden layer of size 500) in smart Predict+Optimizz fashion. There 200 instances in train/validation set and 400 instances in test set. The number of portfolios in each instance is 50.
LANCER The training procedure closely follows Algorithm 2 We use MLP with hidden layers of size 100 and tanh activation. We train LANCER for T = 8 iterations. At each iteration, make 10 updates (using Adam optimizer) to each mapping (Ca and Mw).
Baselines
LODLs:
We use the implementation provided by authors in [37. We replicate their configurations for this experiment, except we made quick fix in the code as they forgot add a matrix transpose in the quadratic term.
MDFL (Melding Decision Focused Learning) and follow their configurations.
we use the version implemented in 37
C.2.2 Combinatorial portfolio selection with third-order objective
We extend the portfolio selection problem eq. 6 as follows:
min ax" Gx + 7/xx Xull2 11= 3x 3'x &
X.V
Σ xj x==1
s.t.
Jmin
Uj
34 Sma Us for i= 1=.... (fraction of each selected portfolio)
(7)
m
<
1 S M (no. of selected portfolios must be between m and M)
0
v E 10
where S is co-skewness matrix and v the binary variables to enforce discrete constraints (e.g. hard limit on number of portfolios). We also introduce the initial portfolio selection vector (generated uniformly random) and enforce our final solution to be close to it (via 7). set the penalty on co-skewness as 0.5, 7 0.01, 3, M 10, fmin 0.01 and fmax 0.2 throughout all
17

---

experiments. We reuse the same data as in section C.2.1 but increase the number of portfolios to 100 and add co-skewness matrix S Note that in this task we assume that all problem descriptors are fully observed (e.g. μ. S).
LANCER
The training procedure for LANCER-Zer closely follows Algorithm B and LANCER-prior closely follows Algorithm 4 train LANCER for 7 = iterations. At each iteration, we perform 10 updates (using Adam optimizer) for each learnable models (Ca and Mww). Additionally, LANCER-prioe uses parametric mapping for Co which implemented via hidden layer MLP of size 500, which ja takes as input.
We use MLP with 2 hidden layers of size 300 and tanh activation. We
Baselines
SCIP attempts to solve the problem defined in Eqn. 7 in three different settings related to the objective: ignores all nonlinear terms (MILP), ignores cubic term (MIQP) and attempts to solve the original nonlinear problem (MINLP), We set the maximum time limit to 60 min before terminating the solver and obtaining the best solution.
For SurCo [16], we use two versions: SurCo-prior and SurCo-zero. SurCo-prior uses the same mapping for Ca as LANCER described above. We use DBB [44 to differentiate through the solver with À 100 and apply Adam optimizer for 100 epochs with the learning rate 0.1 (0.0001 for prior).
D Combinatorial portfolio selection with third-order objective
Based on experimental findings, LANCER showcased the most significant improvement in ad- dressing the combinatorial portfolio selection problem. Inspired by this success, we delved further into the intricacies of this problem and sought visualize the actual solutions obtained by the two best-performing methods: SurCo and LANCER. We present the results for a randomly selected instance in Figure
We have assigned a symbol of a corresponding S&P company to each point for clarity. On the Y-axis, we represent the expected return of selected stock, which is multiplied by its fraction (approximate solution x in Eqn. 7 Similarly, the X-axis displays the skewness score" calculated follows: ax @ (Gx) fxx @ (Sx & x), where @ denotes element- wise multiplication. This computation results in a vector of dimensions equal to the number stocks, enabling us to interpret it as score assigned to each stock. Furthermore, the combinatorial constraints outlined in Eqn. enforce the selection a maximum of M stocks with fractions lower than or equal to fmax-
As we try to maximize the return and minimize the risw-sse score, we want all points to be in the upper-left corner. This is what LANCER achieves. is interesting to see that LANCER chooses the less number of portfolios (6 9) but assigns higher fraction to them improving overall objective.
E Stability of LANCER
Similar to many other approaches designed for solving problems with bi-level optimizations, includ- ing actor-critic algorithms, currently lack theoretical guarantees regarding the convergence of LANCER with respect to either Mw or Cg. This lack of guarantees can also impact the stability of the algorithm. However, this is primarily matter that can addressed through empirical investigation and depends on various factors, which is typical in the process of model selection. Nevertheless, we have observed that LANCER generally exhibits robustness in many cases. As an evidence. we performed additional experiments on nonlinear shortest path problem (section (5.12)). In the two tables below we demonstrate that the final objective does not fluctuate significantly when experiment with different combinations of hyperparameters and variations of neural net architecture. We will leave more ablation studies as the future work.
18

---

Zeno
0.014
SurCo-zero
AFE
TECH
SIVe
SIVB
0.012
0.010
AFE
return
0.008
0.006
QCOM
0.004
EBAY
0.002
PHM
DTECH
0.000
0.04
-0.03
-0.02
-0.01
0.00
0.01
risk skewness
Figure 6: Visualization of the solution for a single instance of the combinatorial portfolio selection with third-order objective. LANCER demonstrates a tendency to select and allocate a significant proportion to stocks characterized by combination of low 'risk skewness' and high rewards (upper-left corner).
Table 4: Exploring various hyperparameters for LANCER for nonlinear shortest path problem from section 5.122
Mw Mw max
Cg
Co max itr
OBJECTIVE
0.0005
10
0.001
10
0,4651
0,001
10
0.001
10
0,4649
0.01
10
0.001
10
0.4650
0.0005
0.001
0.4590 10
0.001
0.001
10
0.4597
0.01
5
0.001
10
0,4651
0.0005
20
0.001
10
0,4651
0.001
20
0.001
10
0.4612
0.01
0.001
0.4651 10
0.001
0.0005
10
0,4612
0.001
10
0.01
10
0,4650
0,001
10
0.001
20
0.4648
Table Exploring various model architecture for LANCER for nonlinear shortest path problem from
section 5.2
Mw num of hidden layers
Mw layer size
OBJECTIVE
50
0.4644
100
0.4646
200
0.4641
2
50
0.4646
2
100
0.4651
200
0.4651
50
0.4644
100
0.4650
3
200
0.4642
19


Reviews:
[{"review_id": "jeebX7zjdn", "reviewer": "Reviewer_1xim", "summary": "`This paper is concerned with an amortized optimization scheme for challenging variants of canonical decision problems such as MINLPs and nonlinear portfolio selection. The authors propose a method with two components, a target mapping $c_\\theta$ that maps partially observed problem descriptions $\\mathbf y$ to full descriptions $\\mathbf z$ that are passed to a traditional solver $g$ (e.g. an MILP solver), and a landscape estimator $M_w$ (i.e. a value function) that estimates the objective value attained by  $g(c_\\theta(\\mathbf y))$ w.r.t. some distribution of training instances. Together $g(c_\\theta(\\mathbf y))$ can be seen as a policy mapping problem descriptions to optimal decisions.\nThis is an empirical paper, with proof of concept results on several variants of canonical decision problems.", "questions": "- How sensitive is LANCER to hyperparameters in terms of performance and stability?\n\n- Do you think it may be necessary to regularize $c_\\theta$ to better explore the space of possible target mappings (similar to entropy-regularized policies in RL e.g. soft actor-critic)?", "limitations": "- While LANCER appears more sample efficient in terms of black-box sample efficiency is does seem a bit slower than the baselines (although it does find better solutions). Hence in latency-sensitive applications it may not be the best choice\n\n- Like Offline RL the generalization of LANCER to unseen problems will depend heavily on the support of that particular problem configuration in the training set. For out-of-distribution problems LANCER's performance is likely greatly diminished. Determining LANCER's sensitivity to distribution shift is an interesting research question.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Amortized optimization is a common technique across machine learning. For example, LANCER bears striking similarity to actor-critic methods for RL, which amortizes the evaluation of an actor (i.e. policy) $\\pi_\\theta$ into a critic (i.e. value estimate) $Q_w$, and likewise the policy amortizes the optimization problem $a^*(s) = \\mathrm{argmax}_a Q_w(s, a)$. The main difference is the objective value in RL (i.e. the policy returns) are not directly observed, and so $Q_w$ is trained by fitted Q-iteration (i.e. the Bellman backup operator) instead of a supervised loss as proposed in this paper. \n\nWhile the technique proposed in this paper is not new, it is the first time I have seen it combined with traditional optimization solvers like MILPs, which are very underutilized by the ML community. Hence the concept of the paper is very intuitive, and has as much if not more potential for impact than RL papers, which are routinely published in NeurIPS proceedings but as yet have not appeared to have significant impact on industrial optimization problems.", "weaknesses": "Like many other solutions to bilevel optimization problems (including actor-critic algorithms), LANCER is not guaranteed to converge w.r.t. $\\mathbf w$ or $\\mathbf \\theta$. Although it is not discussed in the paper, I suspect that LANCER is likely unstable if the hyperparameters are not chosen carefully. If this is not the case, please provide evidence in the rebuttal.\n\nThe connections to other amortized optimization methods in ML generally is not a weakness in my opinion, however I think the related work and discussion could be greatly improved by placing this work in context with other methods like actor-critic RL algorithms and amortized Bayesian inference algorithms to name a few. \n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Weaknesses**\n\n> 1.a. Convergence guarantees and stability\n\nWe acknowledge that, at present, we lack theoretical guarantees on convergence for LANCER. However, we observe empirically that the objective improves as the total number of alternating optimization iterations (T) increases, as shown in Figure 4.\n\nAlso, please see our response to all reviewers above (point 1) for additional experiments we conducted to test the stability of our approach across various hyperparameters and neural network architectures.\n\n> 1.b. Connections to other amortized optimization methods\n\nWe would like to extend our appreciation to the reviewer for highlighting the insightful parallels between the actor-critic framework and our LANCER methodology. Although we provide a review of several amortized methods in context of smart P+O and MINLP (e.g. [13,16,36]), we agree that enhancing the related work and discussion by placing our work in the context of actor-critic RL algorithms and amortized Bayesian inference algorithms, would be a valuable addition to the paper. We will certainly take your suggestion into consideration and make the necessary revisions to provide a more comprehensive understanding of the contributions and implications of our proposed approach in relation to these other methods.\n\n&nbsp;\n\n2. **Questions**\n\n> 2.a. How sensitive is LANCER to hyperparameters in terms of performance and stability?\n\nSee our response in the Weaknesses section (1.a.) above. \n\n&nbsp;\n\n> 2.b. \"Do you think it may be necessary to regularize to better explore the space of possible target mappings (similar to entropy-regularized policies in RL e.g. soft actor-critic)?\"\n\nIn our experiments, we have chosen to utilize simple weight decay as a means of regularizing target mappings. Other regularization approaches could apply, e.g., dropout, sparsity, and/or use networks of fewer number of parameters. Note that entropy-based regularizations are more straightforward to apply when working with probability distributions, which might not be as straightforward in the context of our study, where problems in P+O & MINLP have a deterministic nature.\n\n&nbsp;\n\n3. **Limitations**\n\n> 3.a. While LANCER appears more sample efficient in terms of black-box sample efficiency is does seem a bit slower than the baselines (although it does find better solutions). Hence in latency-sensitive applications it may not be the best choice\n\nIn all our experiments, the number of black-box (BB) accesses directly correlates with the runtime, with the w-step significantly dominating over the \\theta-step (see Section 1 in the supplementary materials). As indicated in Figure 5, LANCER consistently exhibits much faster runtime compared to the baseline methods. The only exception is shown in Figure 4, where we intentionally use more requests to the BB solver to explore a larger number of iterations for evaluation purposes.\n\nMoreover, the w-step in LANCER can be easily parallelized, offering the potential for significant improvements in runtime efficiency. We are confident that the parallelization capability can further enhance the overall performance of our approach.\n\n> 3.b out of distribution performance... \n\nOn the portfolio optimization instances, the test data is quite out of distribution from the training data as the data are split temporally. In the financial setting, it is considered that the data distribution changes wildly over time. Our performance on this domain seems to suggest that the models are able to generalize to unseen data that are dissimilar to the training data. We leave more thorough studies for future work."}, {"review_id": "If3FHSqC0A", "reviewer": "Reviewer_kDSQ", "summary": "This paper presents a unified framework for \"predict-then-optimize\" and surrogate cost learning for Mixed Integer Nonlinear Programming (MINLP). These problems are cast as learning an optimizer g with f as the objective. Current solutions either suffer from scalability issues or the sparse gradient problem. To overcome these, the authors propose learning a smooth and tractable landscape surrogate to replace the compound function $f\\circ g$. A neural network parameterizes the surrogate loss and it is learned through alternating optimization. This is done by alternately optimizing the target model c and landscape surrogate $\\mathcal{M}$ in a manner similar to Generative Adversarial Networks (GANs). Experiments covering both linear and non-linear objectives demonstrate the efficacy of the proposed method under both \"predict-then-optimize\" and surrogate learning settings.", "questions": "Have different parameterizations of \\mathcal{M} been tested and do they significantly affect performance?\n\nIn 4.1, the paper said we can execute the theta-step at testing time since c_{\\theta} for unseen test data. Did you try this step in your experiment? I did not find the number of training iterations of this theta-step at testing time in the supplementarial material.\n\nWas the replay buffer trick, as described in 4.2, used and how many points were needed to be stored? This could significantly impact training time but no implementation details are given in the experimental section or the supplementary material.", "limitations": "Please refer to the Weaknesses section for a detailed discussion of the paper's limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper proposes the first unified framework for \"predict-then-optimize\" and surrogate learning. The method is straightforward, and empirical results appear promising in terms of both optimization performance and runtime.", "weaknesses": "Directly utilizing a neural network to parameterize the landscape may not be a good idea. The complexity of a neural network typically surpasses the original objective f. A neural network can have extremely large number of local minimums and this approach could disrupt the convexity of the original optimization problem, leading to instability in the proposed method's learning procedure. In fact, in Shah et al., several parameterizations, including neural networks, were tested and found to often result in catastrophic outcomes. There's concern about this parameterization across various optimization objectives. \n\nWhile SurCo minimizes the original objective f, LANCER learns an additional surrogate loss. However, in experiment 5.2.2, LANCER significantly outperforms SurCo. The authors should provide more analysis and clarification on why employing such a surrogate loss can surpass the original loss.\n\nThe paper lacks important implementation details. In 4.1, the authors mentioned the possibility of executing the theta-step during testing since c_{\\theta} is available for unseen test data. It is unclear if this step was used during testing in the experiments. The supplementary material also does not provide details about the number of training iterations for this theta-step during testing. If this additional optimization step was used during testing, performance without this step should also be reported to pinpoint the source of the gains compared to SurCo. In fact, SurCo can also have this extra optimization step for the unseen test data.\n\nFurthermore, the paper does not provide any implementation details for the replay buffer trick discussed in 4.2, such as the number of points needed to be stored, which could significantly impact the training time.\n\nThe unification of the \"predict+optimization\" problem and surrogate cost learning problem under optimization with partial information feels forced as half of the paper focuses on surrogate objective learning for MINLP where full information is available.\n\nSection 4 could benefit from restructuring. The main introduction of the proposed method precedes 4.1 and 4.2 and lacks a subsection title, while 4.1 and 4.2 focus on implementation details.\n\nMinor:\n\nLine 285: MDFL was proposed for combinatorial decision-focused learning and it is not the first DFL paper. A more accurate citation should be Donti et al. (2017).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Weaknesses**\n\n> 1.a. On utilizing a neural network to parameterize the landscape and comparison with LODLs\n\nPlease check our response to all reviewers above (points 2 and 3)\n\n&nbsp;\n\n> 1.b. Why LANCER outperforms SurCo?\n\n**LANCER allows nondifferentiable objective $f$**. SurCo relies on (approximately) differentiating through the solver, which can be challenging and slow in combinatorial problems due to sparsity, while LANCER circumvents this issue by constructing a surrogate landscape, M, that models the composition of nonlinear objective f *and* the solver g. M is differentiable and thus provides dense gradients and facilitates faster learning. \n\n**LANCER may call solver g fewer times**. SurCo requires that the solver $\\mathbf{g}$ be called in each iteration, which can be time-consuming, while LANCER can leverage surrogate landscape $\\mathcal M_w$ to bypass the solver $\\mathbf{g}$, saving computational cost. \n\nThe pros and cons of both approaches are thoroughly discussed in sections 3 and 4.\n\n> 1.c. Implementation details for section 4.1. \n\nWe apologize for any confusion. The implementation of section 4.1 simply involves executing $\\theta$-step for unseen data once Algorithm 1 terminates. This is especially useful when Z = Y, i.e., there is no partial information in the testing instances, such as MINLP (see LANCER-zero pseudocode in the suppl. mat.). In this case, $M_w$ can be used to evaluate the quality of target mapping $c_\\theta(\\mathbf{y})$, and improve $c$ directly (through $\\theta$-step only) without calling the expensive composition $f \\circ \\mathbf{g}$. This is an optional step that one can perform once Algorithm 1 finishes. \n\nAs for the experiments, we found out that this can lead to a significant runtime reduction. We conducted ablation studies in section 5.4 to validate this.\n\n> 1.d. Implementation details of the replay buffer and the effect on runtime.\n\nWe primarily employed replay buffer for MINLP experiments, and it showcased noticeable improvements in performance. We set the number of points to be added to the buffer to N, so the total/max size of the replay buffer progressively reaches TN by the termination of the algorithm, where T is typically between 5-40. Of course, this could be controlled via setting the max buffer size if N is large. This is easy to implement as insert/retrieve operation on a buffer takes constant time. Additionally, we will make our implementation open source to allow full reproducibility.\n\nIt is crucial to note that the use of the replay buffer has only a marginal effect on the runtime and is barely noticeable. The primary purpose of the replay buffer is to store and reuse past experiences to break temporal correlations and stabilize training. This process is relatively lightweight compared to other computationally intensive parts of the algorithm, such as interacting with the black-box solvers. The runtime increase only appears at line 10 of Algorithm 1, which involves training neural networks that scale linearly with the dataset size. Fortunately, this process is straightforward to parallelize, thanks to the capabilities offered by modern frameworks.\n\n&nbsp;\n\n> 1.e. \"The unification of the P+O and surrogate cost learning feels forced...\"\n\nWe respectfully disagree with this statement. Our approach equally addresses both problems, each of which introduces uncertainty to the optimization problem. Neither of them can be straightforwardly solved in their general formulations. In the case of P+O, the problem descriptors are unknown and must be inferred from observed input $\\mathbf{y}$. On the other hand, when learning surrogates for MINLP, the cost vector of the surrogate problem is unknown. We formulate both of these uncertainties as learning problems and propose LANCER as a unified algorithm to address them. The unification is crucial to derive LANCER and successfully apply it to both of these challenging problems, without changing substantially its framework. \n\n&nbsp;\n\n2. **Questions**\n\n> 2.a. Have different parameterizations of $\\mathcal M$ been tested and do they significantly affect performance?\n\nPlease see point 3 in the main response.\n\n> 2.b. Experiments with regards section 4.1. \n\nThe ablation study in section 5.4 is specifically dedicated to this purpose. Table 3 presents the results, clearly demonstrating the benefits of the \"transferrability/reusability\" of $\\mathcal M_w$.\n\n> 2.c. Was the replay buffer trick, as described in 4.2, used? \n\nPlease, see our response 1.d. in Weaknesses."}, {"review_id": "kWqyzfhjv1", "reviewer": "Reviewer_Nect", "summary": "This paper proposes the a novel framework for learning the predicted value of an optimization task under limited information. Specifically, the goal is to learn $\\mathcal{M}\\_w(y, z) = f (g\\_\\theta (y), z)$ function where $y$ is the limited information, $z$ is the complete information, $f$ is the objective value of an optimization function to be maximized, and $g\\_\\theta$ is a way to generate a solution to the optimization problem based on the limited information $y$. In essence, there are 2 sets of interdependent parameters to learn -- $\\theta$ and $w$, and the paper proposes an alternating update scheme for solving the joint problem. They then apply this framework to 2 classes of problems---Smart Predict-then-Optimize (SPO) and Mixed Integer Non-Linear Programming (MINLP)---and show that this method outperforms similar approaches in each class.", "questions": "Apart from the questions in the weaknesses in the section above, I was wondering:\n1. **Choice of domains**: I noticed that you have not used the domains from either SurCO or LODLs on which they report good performance. While this is not a weakness in itself, I can't help but wonder how well LANCER performs on those domains. Should LANCER always be the choice of learning method or is the answer more nuanced?\n1. **Alternating updates**: Is it important to always do full updates in both spaces? Have you considered, perhaps, doing smaller updates? For example, in a recent paper, [B] seems to do some sort of meta-gradient update based on how $\\theta$ would change in response to $w$.\n1. **Re-using $\\mathcal{M}_w$**: The fact that landscape surrogates can be 're-used' seems to suggest that $\\mathcal{M}_w$ is learning something that is common across problem instances. Have you tried to analyze what it is that $\\mathcal{M}_w$ is learning?\n\nFrom the experiments, I'm convinced that there exist reasonable domains for which its possible to get this method to work. However, it's not clear at the moment how easy this process is... I'm willing to raise my score to a 7 if the authors provide more detailed answers to the questions in the weaknesses section\n\n_References:_\n\n[B] Sivasubramanian, Durga, et al. \"Adaptive Mixing of Auxiliary Losses in Supervised Learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.", "limitations": "I appreciate the inherent conflict of interest, but I think the paper could do a better job of documenting the limitations of their approach. For example, if the authors could answer (1) from the questions section above, that would help to better contextualize the advantages and limitations of this approach.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* **Great exposition**: The paper is well written and easy to follow. \n* **Good experiments**: The paper uses domains from the literature and compares to relevant past work for each problem class. The experiments are well documented and seem reasonably expansive.\n* **Interesting connection**: I'm more familiar with the SPO literature, so the connection of learned surrogates to MINLP is quite interesting!", "weaknesses": "The major weakness of this paper, imo, is that it doesn't document the **training considerations** for $\\mathcal{M}_w$. The paper mentions in the conclusions that 'one potential drawback is the complexity of tuning M, requiring model selection and training', but there are no experiments about how hard/important tuning these parameters is. Specifically, it would be good to know:\n1. Shah et al. [36] highlight the importance of *convex* surrogates for learning loss functions (because they have to be optimized over) and show specifically on a version of the Portfolio Optimization domain that neural networks performs poorly (Table 1 in their paper). However, in this paper $\\mathcal{M}_w$ seems to be a neural network and performs well? Do you not observe this phenomenon of 'convexity being important for loss functions'?\n1. There seems to be a recent follow up to [36] --> [A] which seems to do 1 iteration of your alternating update (with a 2-stage warm start) and seems to do well on the Portfolio Optimization domain, even better than the MDFL method (which seems to do much better than both LODLs and LANCER in this paper). Then:\n    * How robust are your results to hyperparameter choices?\n    * How important is it to perform repeated updates? (Is this what you mean by \"epoch\" in Figure 5? And if so, how much difference is there between 1 epoch with 10x the samples vs. 10 epochs with 1x the samples?)\n    * Relatedly, how do those results change based on how good the initial guess of $\\theta$ is? Do you need fewer updates if you warm-start $\\theta$ from a 2-stage solution?\n1. Why do you measure cost in terms of the number of calls to the BB optimizer in Figure 5? There seems to be a trade-off between (a) using more calls the BB optimizer but training a simple model (as in LODLs) vs. (b) using fewer calls to the BB optimizer but training a more complex model. Do the results look very different if you use wall-clock time?\n\n_References:_\n\n[A] Shah S, Perrault A, Wilder B, Tambe M. Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize. arXiv preprint arXiv:2305.16830. 2023 May 26.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Weaknesses**\n\n> 1.a.\"Do you not observe this phenomenon of 'convexity being important for loss functions'?\"\n\nPlease check the main rebuttal (points 2 and 3). \n\n> 1.b. Regarding follow up to LODLs. \n\nThanks for the reference. We were unaware of this work as it appeared after the submission deadline to NeurIPS. As for the results on Portfolio Optimization, there are likely large differences in the data and evaluation. Specifically in the follow-up paper [A], the 2-stage method performs catastrophically poorly compared to LODLs and the proposed approach whereas in our experiments we found that 2-stage performed worse but not disastrously bad. It is thus unclear whether the relative model performance would apply to both settings.\n\nIt is also important to note that while our results are slightly worse than MDFL, LANCER is clearly performing better in terms of runtime, as shown in Fig. 5 and acknowledged by Reviewer 7fCr.\n\n> 1.c. \"How robust are your results to hyperparameter choices?\"\n\nPlease see our response to all reviewers above (point 1) for additional experiments we conducted to test the stability of our approach across various hyperparameters and neural network architectures.\n\n> 1.d. \"How important is it to perform repeated updates? (Is this what you mean by \"epoch\" in Figure 5? And if so, how much difference is there between 1 epoch with 10x the samples vs. 10 epochs with 1x the samples?)\"\n\nYes, in Figure 5, we refer to an epoch as one step of alternating optimization. We find it quite important, and as shown in Figure 5, a larger $T$ (number of updates/iterations) typically leads to better performance. This is also related to our response to Question 2.b. below (making small number of inner updates but keeping larger $T$).\n\nAs for the \"1 epoch with 10x samples\", this is prone to overfitting. Whereas, alternating optimization can help us to mitigate overfitting as the model sees the data multiple times with different parameter configurations. Additionally, if replay buffer (section 4.2.) is enabled, then we can naturally (re-)use the target mapping output to enlarge the number of samples. Intuitively, once the number of samples reach a certain threshold, performing more inner updates could be useful. This type of \"adaptive\" learning scheme we leave for future work. We empirically observed that performing repeated updates consistently improves the performance (around 1.5-2x times in accuracy). \n\n> 1.e. \"Relatedly, how do those results change based on how good the initial guess of \\theta is?\"\n\nThe quality of the initial guess (e.g. 2-stage) affects optimization results, with a good guess leading to faster convergence and better outcomes. For example, in nonlinear shortest path problem, random initialization needs 1.5x-2x more iterations to get the same performance.\n\n> 1.f. \"Why do you measure cost in terms of the number of calls to the BB optimizer in Figure 5?\"\n\nIn all our experiments, the number of black-box (BB) accesses directly correlates with the runtime, with the w-step significantly dominating over the \\theta-step (see Section 1 in the supplementary materials). This is especially true when solving high-dimensional combinatorial problems (e.g., Multidim knapsack, MINLP Portfolio Selection) where even highly optimized solvers (e.g., Gurobi) take time to solve for a single instance. \n\nOn this note, LODLs as well take a long time during the sampling stage, where multiple calls to the optimizer occur. Additionally, a number of papers from the literature (e.g., [16]) report the number of BB calls as one of the main metrics.\n\n&nbsp;\n\n2. **Questions**\n\n> 2.a. \"Choice of domains: I noticed that you have not used the domains from either SurCO or LODLs on which they report good performance...\"\n\nWhile we appreciate your observation, it's important to note that our focus was primarily on relatively high-dimensional problems, and we aimed to cover both domains of learning surrogates for MINLP and DFL. Running all experiments from both SurCO and LODLs papers proved challenging due to the extensive scope. However, it's worth mentioning that both papers reported good results on the benchmarks we tried. For examples, SurCO shows better or similar performance in some settings of nonlinear shortest path problem.\n\n> 2.b. \"Alternating updates: Is it important to always do full updates in both spaces? Have you considered, perhaps, doing smaller updates? ...\"\n\nIn our approach, we perform a fixed (smaller) number of updates, i.e., we do not exactly solve the minimization in both spaces (lines 10 and 12 in Algorithm 1). For example, most experiment uses 10-20 updated per global iteration. Potential reason is that we don't want $\\mathcal M_w$ model to overfit to the data much and increase $T$ instead. Although we discuss this in experimental setup, this will be made clear in the description of the algorithm to avoid any ambiguity. \n\n\n> 2.c. \"Re-using $\\mathcal M$. ... Have you tried to analyze what it is that is learning?\"\"\n\nIndeed, the reuse of landscape surrogates suggests that the learning process captures common information shared across problem instances. While we haven't explicitly analyzed what the learning process captures, investigating the nature of the learned information could be an intriguing direction for further research.\n"}, {"review_id": "7Pc1w312Mt", "reviewer": "Reviewer_7fCr", "summary": "This paper considers the class of problems known as Smart Predict and Optimize (or Decision-Focused Learning) where the learning task consists in learning the parameters of an optimization model given some of their features. The difficulty comes from trying to include the optimization model into the learning pipeline, since it is hard to differentiate over the optimization model. The paper proposes to learn two optimization model: one to learn the objective of the optimization model and one to learn the coefficient of the optimization model. These are trained using an iterative algorithm that tries them in sequence. The paper applies this approach to the traditional benchmarks used in SPO and show that the approach has benefits overall.", "questions": "See above.", "limitations": "The benefits on the portfolio optimization are computational only.\n\nThis area seems to always consider the same three problems. ", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Algorithm 1 is the main contribution of the paper. It is an elegant way to solve SPO problems in general.", "weaknesses": "1. The formalization really gets in the way in this paper. I will try to list these issues here\n\n1.a  The model M which approximates the solver should receive only one set of parameters. I do not understand why you would use c_\\theta(y_i) and z_i in (3). It would be better to explain in detail the inputs of the model M\n\n1.b In (4), the notation M_w(Y,Z;\\theta^*) does not make any sense. M_w does not receive \\theta^* in Algorithm 1. As a result, the bilevel model (4) does not make sense. \n\n1.c why is the learning task expressed as min_{\\theta,w} | M_w(c_theta(y)) - f(z) |?\n\n2. Algorithm 1 is an ADMM approach to the optimization as shown above in fact.\n\n3. I do not understand 4.1. The goal of SPO is to find the parameters of the optimization which is what c_\\theta does? How is Model M useful on testing instances and model deployment? It does not compute any solution, just the objective.\n\n4. In  4.2, you mention that you need Z to train M. This is contradictory with 4.1 where you are using it in unseen test instances. You do not have Z on unseen instances. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for providing valuable comments. While we partially agree with the summary provided by the reviewer, it is essential to note that LANCER is not only applicable to SPO problems but also to another crucial class of problems: solving mixed-integer nonlinear programming via learning surrogates. We unify learning surrogates for MINLP and SPO within the same learning framework, which is another important contribution that we would like to emphasize.\n\nAccording to the reviewer's concerns, the formalization of our approach (section 4) and Algorithm 1 require more clarification, which we address below. Moreover, we will incorporate most of these responses/clarifications into the revised version.\n\n\n1. **Weaknesses**\n\n> 1.a. \"The model M which approximates the solver should receive only one set of parameters. I do not understand why you would use c_\\theta(y_i) and z_i in (3). It would be better to explain in detail the inputs of the model M\"\n\nIt is important to note that our main objective is to approximate composition function $f \\circ \\mathbf{g}$ (not just $f$ and NOT the solver $\\mathbf{g}$ alone, but jointly), please check the main rebuttal for more detailed explanation. For this, evaluating $f \\circ \\mathbf{g}$ depends on both $c_\\theta(y_i)$ and $z_i$. Therefore, to construct an accurate surrogate model $M_w$ that can effectively approximate $f \\circ \\mathbf{g}$, it is essential for $M_w$ to take into consideration the influence of both inputs. This consideration ensures that the surrogate captures the intricacies of the composition function and produces reliable predictions to aid the optimization process in both the smart P+O and learning surrogates for MINLP settings.\n\n> 1.b. \"In (4), the notation M_w(Y,Z;\\theta^*) does not make any sense. M_w does not receive \\theta^* in Algorithm 1. As a result, the bilevel model (4) does not make sense.\"\n\nWe apologize if it caused much confusion. The complete and more explicit form of Eqn. 4 should look like this:\n\n$\\min_{w}{ \\sum_i || M_w ( c_{\\theta^*}(y_i), z_i ) - f( \\mathbf{g}(c_{\\theta^*}(y_i)), z_i ) || }$\n&nbsp;\n\ns.t. $\\theta^* \\in $ arg$min_\\theta \\sum_i M_w (c_ \\theta(y_i), z_i) $\n\nAs mentioned above in 1.a., the surrogate model $M_w$ takes $c_\\theta(y_i)$ as one of its inputs. In this context, we are not concerned with making $M_w$ accurate for all possible $c_\\theta$; rather, we are interested in finding the configuration of $M_w$ that yields the closest approximation to $f \\circ \\mathbf{g}$ near $\\theta^*$. By adopting the bilevel optimization framework, we can focus on learning accurate $M_w$ for such $\\theta$. In Algorithm 1, we achieve this by first evaluating $f \\circ \\mathbf{g}$ on the current \"optimal\" $c_{\\theta^*}$, followed by retraining $M_w$ (i.e., $w$-step). Correspondingly, $w$-step ensures that $c_\\theta$ optimizes the current surrogate loss $M_w$. We will make this more explicit in the paper and will add detailed description. \n\n> 1.c. \"why is the learning task expressed as min_{\\theta,w} | M_w(c_theta(y)) - f(z) |?\"\n\nHopefully, our response above (1.b.) also clarifies this matter. Otherwise, please do not hesitate to follow up during author-reviewer discussion phase. \n\n> 2. \"Algorithm 1 is an ADMM approach to the optimization as shown above in fact.\"\n\nAlthough it has similar flavor, Algorithm 1 is not an ADMM because it does not follow the typical ADMM structure and optimization approach.\n\nADMM is used to solve problems with separable objective functions and constraints. It is based on the idea of splitting the original problem into subproblems that can be solved in parallel, and then iteratively updating the variables using the method of multipliers. The general form of ADMM involves introducing auxiliary variables, Lagrange multipliers, and penalty terms to convert a constrained optimization problem into a series of subproblems that can be solved independently and in parallel. Clearly, the formulation in eq. (4) and Algorithm 1 do not exhibit this characteristic structure of ADMM. \n\n> 3. \"I do not understand 4.1. The goal of SPO is to find the parameters of the optimization which is what c_\\theta does? How is Model M useful on testing instances and model deployment? It does not compute any solution, just the objective.\"\n\n$M_w$ can be reused when Z = Y, i.e., there is no partial information in the testing instances, such as MINLP. In this case, $M_w$ can be used to evaluate the quality of target mapping $c_\\theta(y)$, and improve $c$ directly (through $\\theta$-step only) without calling the expensive composition $f \\circ \\mathbf{g}$. This is an optional step that one can perform once Algorithm 1 finishes. (see Algorithm 2 in the supplementary materials and refer to lines 143-149 in the main paper). This leads to a significant runtime reduction. We conducted ablation studies in section 5.4 to validate this.\n\n> 4. \"In 4.2, you mention that you need Z to train M. This is contradictory with 4.1 where you are using it in unseen test instances. You do not have Z on unseen instances.\n\nIf Z only contains partial information (e.g., P+O) during testing, we may still leverage M for \"similar problems\", providing computational advantages. For example, after using Algorithm 1 for one dataset of the portfolio selection (PS) problem, we can use the pre-trained M when training on another PS dataset either as a warm start or by executing the $\\theta$-step. However, we did not validate this in our experiments, which may encounter potential issues such as distribution shifts and domain differences."}]

Author rebuttal:
We sincerely thank the reviewers for providing valuable comments and taking the time to review our paper. Here we address questions raised by several reviewers. 


> 1. [1xim,kDSQ,Nect] **Stability of LANCER to hyperparameters and NN architecture**

This is an empirical question and depends on various factors, as is typical in model selection. Nevertheless, we've observed that LANCER generally exhibits robustness in many cases. As an evidence, we performed additional experiments on the problem from section 5.1.2. In the two tables below we demonstrate that the final objective does not fluctuate significantly when we experiment with different combinations of hyperparameters and variations of NN architecture. We will leave more ablation studies as the future work. Also, see point 3 below on using quadratic losses.

|M_lrn_rate | M_max_itr	| c_lrn_rate | c_max_itr | OBJECTIVE|
|------------:|--------------:|------------:|-----------:|-------:|
|0.0005	   | 10	        | 0.001	     | 10	     | 0.4651|
|0.001	   | 10	        | 0.001	     | 10	     | 0.4649|
|0.01	   | 10	        | 0.001	     | 10	     | 0.4650|
|0.0005	   | 5	        | 0.001	     | 10	     | 0.4590|
|0.001	   | 5	        | 0.001	     | 10	     | 0.4597|
|0.01	   | 5	        | 0.001	     | 10	     | 0.4651|
|0.0005	   | 20	        | 0.001	     | 10	     | 0.4651|
|0.001	   | 20	        | 0.001	     | 10	     | 0.4612|
|0.01	   | 20	        | 0.001	     | 10	     | 0.4651|
|0.001	   | 10	        | 0.0005	 | 10	     | 0.4612|
|0.001	   | 10	        | 0.01	     | 10	     | 0.4650|
|0.001	   | 10	        | 0.001	     | 20	     | 0.4648|

|M_num_of_hidden_layers | M_layer_size | OBJECTIVE|
|:---------------------------:|------------:|-----------------:|
|1                      | 50           | 0.4644|
|1                      | 100          | 0.4646|
|1                      | 200          | 0.4641|
|2                      | 50           | 0.4646|
|2                      | 100          | 0.4651|
|2                      | 200          | 0.4651|
|3                      | 50           | 0.4644|
|3                      | 100          | 0.4650|
|3                      | 200          | 0.4642|

&nbsp;

> 2. [kDSQ,Nect] **Concerns on the form of landscape surrogate $\mathcal M$. Comparison between LANCER and other surrogate losses in P+O** 

We acknowledge that there is indeed similarity between the Decision Loss (DL) in [36], Decision Quality (DQ) in [A] and our landscape surrogate $\mathcal M_w$. Using our notation, the DL/DQ consider the loss in the form of $\mathrm{DL}(\mathbf{\hat z}, \mathbf z) := f(\mathbf g^*(\mathbf{\hat z}(\mathbf y)), \mathbf z)$, where $\mathbf z$ is the ground truth specification of the problem instance, $ \mathbf{\hat{ z }} $ its estimate, $\mathbf y$ is the features, and $\mathbf g^*$ is the groundtruth solver, and propose to use a surrogate loss $L_\phi$ to fit $\mathrm{DL}(\mathbf{\hat z}, \mathbf z)$. 

In contrast, our landscape surrogate $\mathcal M_w(\mathbf c, \mathbf z)$ is used to fit the loss in the form of $f(\mathbf g(\mathbf c(\mathbf y)), \mathbf z)$. Note that LANCER focuses on the quality of the final objective directly, rather than aim at a good estimate of $\mathbf z$ first. Therefore, there are a few key differences: 

+ we never aim to predict a good estimate of $\mathbf z$ so our loss cannot be written as the form of $DL(\mathbf{\hat z, z})$ and thus do not have the same structure as in DL/DQ loss. In fact, from the function arguments, it is clear that $\mathcal M_w(\mathbf c,\mathbf z)$ is not a symmetric function. This can be advantageous, since what we want is the solution to $f$ and getting a good estimate of $\mathbf z$ is extra work.

+ we use a target mapping $\mathbf c(\mathbf y)$ to predict the surrogate cost for a cheap surrogate solver $\mathbf g$ to give a solution. Therefore, $\mathbf g$ may be very different from the original ground truth solver, which can be very slow or impossible to run (as in the case with MINLP), and our landscape surrogate $\mathcal M_w(\mathbf {c,z})$ needs to cope with that. 

+ LODLs are trained per-instance on points sampled around the true labels which may not be representative of the region that the target model is passing through during training. Furthermore, in such a tight region it makes sense to use a simple convex model rather than a more expressive neural network. However, when trying to approximate the broad region that our target model traverses during training *across* a diverse training set (Algorithm 1, line 5), it is likely that a more expressive model is needed.

Therefore, in our case fitting it with a NN is reasonable and have more benefits:

- Expressiveness: NNs are capable of approximating complex functions, making them well-suited for approximating the Value- or Q-functions in actor-critic RL algorithms, where they are widely used. Similarly, in our setting, $f \circ \mathbf{g}$ can exhibit complex behavior, especially in high-dimensional problems. For instance, we observe such behavior in the P+O Multidim Knapsack and MINLP portfolio selection problems.

- Scalability: we mainly focused on relatively high-dimensional optimization problems, and NNs can efficiently handle such large-scale tasks, enabling effective learning in these challenging environments.

[A] Shah et al. Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize. arXiv:2305.16830.

> 3. **Other alternative landscape losses we tested**

Finally, we would like to emphasize that our method is not specifically tailored towards neural nets and is more generic. Any differentiable function $\mathcal M$ could be used. We conducted experiments with convex functions in several instances. For instance, in the nonlinear shortest path problem (section 5.1.2), the quadratic model yields an objective value of 0.412 (i.e., worse than a greedy approach). In contrast, the results obtained using the NNs are close to the optimum, with an obj value of 0.464.

Meta-review: This paper develops a novel approach for learning the predicted value of an optimization task under limited information. In this problem, there are two set of inter-dependent parameters to learn and the approach considers alternating update to solve this joint learning problem. The approach is applied to two problem classes: smart predict-then-optimize and mixed integer non-linear programming, and demonstrated good results. The paper also addresses some key shortcomings of learning surrogate losses (sample efficiency and heuristic sampling). 

Overall, reviewers' were positive about the paper and author rebuttal addressed their questions and concerns. 

I recommend accepting the paper and strongly encourage the authors' to incorporate reviewers' comments and rebuttal discussion into the final paper.
Decision: Accept (poster)