Generative Learning for Solving Non-Convex Problem with Multi-Valued Input-Solution Mapping
Authors: Enming Liang
Minghua Chen
Venue: ICLR 2024 poster (2024)
Keywords: Non-convex optimization
Multi-valued solution mapping
Generative model
Ordinary differential equation
Supervised learning
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose a generative learning framework to learn the multi-valued input-solution mapping for non-convex optimization problems.

Abstract: By employing neural networks (NN) to learn input-solution mappings and passing a new input through the learned mapping to obtain a solution instantly, recent studies have shown remarkable speed improvements over iterative algorithms for solving optimization problems. Meanwhile, they also highlight methodological challenges to be addressed. In particular, general non-convex problems often present multiple optimal solutions for identical inputs, signifying a complex, multi-valued input-solution mapping. Conventional learning techniques, primarily tailored to learn single-valued mappings, struggle to train NNs to accurately decipher multi-valued ones, leading to inferior solutions. We address this fundamental issue by developing a generative learning approach using a rectified flow (RectFlow) model built upon ordinary differential equations. In contrast to learning input-solution mapping, we learn the mapping from input to solution distribution, exploiting the universal approximation capability of the RectFlow model. Upon receiving a new input, we employ the trained RectFlow model to sample high-quality solutions from the input-dependent distribution it has learned. Our approach outperforms conceivable GAN and Diffusion models in terms of training stability and run-time complexity. We provide a detailed characterization of the optimality loss and runtime complexity associated with our generative approach. Simulation results for solving non-convex problems show that our method achieves significantly better solution optimality than recent NN schemes, with comparable feasibility and speedup performance.

Published as a conference paper at ICLR 2024
GENERATIVE LEARNING FOR SOLVING NON-CONVEX PROBLEM WITH MAPPING
INPUT-SOLUTION
Enming Liang and Minghua Chen School of Data Science, City University of Hong Kong
ABSTRACT
By employing neural networks (NN) to learn input-solution mappings and passing a new input through the learned mapping to obtain a solution instantly, recent studies have shown remarkable speed improvements over iterative algorithms for solving optimization problems. Meanwhile, they also highlight methodological challenges to be addressed. In particular, general non-convex problems often present multiple optimal solutions for identical inputs, sigmifying a complex, multi-values input- solution mapping. Conventional learning techniques, primarily tailored to learn single-valued mappings, struggle to train NNs to accurately decipher multi-valued ones, leading inferior solutions. We address this fundamental issue by developing a generative learning approach using a rectified flow (RectFlow) model built upon ordinary differential equations. In contrast learning input-solution mapping, we learn the mapping from imput to solution-distribution exploiting the universal approximation capability of the RectFlow model. Upon receiving new imput, we employ the trained RectFlow model to sample high-quality solutions from the input- dependent distribution it has learned. Our approach outperforms conceivable GAN and Diffusion models in terms of training stability and run-time complexity. We provide a detailed characterization of the optimality loss and runtime complexity associated with our generative approach. Simulation results for solving non-convex problems show that our method achieves significantly better solution optimality than recent NN schemes, with comparable feasibility and speedup performance.
INTRODUCTION
Constrained optimization problems have widespread applications in various engineering domains, including wireless communication, power systems, and autonomous driving. Conventional iterative methods (e.g.. Gurobi and Mosek) have demonstrated satisfactory performance in solving optimiza- tion problems with static parameters. However, these methods fall short in real-time operational contexts, where problems must be solved repeatedly under rapidly changing contextual parameters. Examples of these applications include solving AC optimal power flow problems in real-time power grid operations, semi-definite programming-biie based real-time scheduling. and coding operations in modern wireless communication systems.
Recently, machine learning (ML) based strategies, including the end-to-end (E2E) solution mapping
(Pan et al. (2119) 2020) [Donti et al. (202T),
(L20) iterative scheme (Khalil et al. et al. 2020) Chen et al.) (022b), and hybrid approaches (Baker [019 Fioretto et al. Park & Van Hentenryck 2023), have shown potential in tackling such real-time constrained
2020
optimization problems. problemms...... The E2E approach, boosted by the universal approximation capabilities of
neural networks (NN) (Hornik et al.) 1989 Leshno et al.) 1993), learns the mapping between the input contextual parameters and the optimal solutions. Given new input parameters, trained NNs can directly output the solution by forward calculation with considerable speedup compared to iterative solvers (Pan et al.
2019 Kotary et al. 2021a Donti et al. 2021).
Besides ensuring the feasibility of solutions with respect the input-dependent constraint (Donti
et al. 2021 Tabas & Zhang 2022 Zhao et al. 2022 Liang et al. 2023). issues associated with
"Corresponding Author: Minghua Chen (minghua wwwhhnhhhuahhhhnnniieee www.hhietnn.eeeeee..ooo hk).

---

Published as a conference paper at ICLR 2024
multiple solutions arise for non-convex problems (Nandwani al. 2020: Kotary et al.) 2021a Pan
et al. 2023), , where there exist multiple global optimum or symmetric solutions with the same objective value. The existing supervised training approaches using NN face challenges in learning this multi-valued input-solution mapping, as illustrated in Fig.
To tackle the issues related the multi-valued input-solution mapping, researchers have utilized various prior knowledge either isolate one of the multiple input-solution mappings (Nandwani et al.
1.0
Output solutions
2020; Kotary al., 2021a) or learn multiple map- pings directly (Li et al. 2018; Courts & Kvinge 2021, Pan et al. 2023) For instance, leveraging the prior knowledge that the solution mapping for optimization problems often satisfies a local Lip-
0.0
-0.5
Target mappings NN mapping
schitz condition, Kotary et al. (2021a) develops training dataset generation scheme to circumvent the issue of multiple solutions. Pan et al. (2023)
Training dataset
1.00
0.75
0.50
0.25
0.50
0.25 0.50
0.75 1.00
utilizes initial points of the deterministic solver to characterize different solution mappings and learn single mapping augmented with input initial points. However, these approaches either rely on specific prior knowledge of the non-convex problem or do ensure the stability of the training process and performance of predictions. More discussions on related works are Sec. [
Input parameter
Figure I: Consider the setting where a non-convex problem admits two optimal solutions with the same optimal objective value for cach input, leading to 2- valued input-solution mapping. An NN trained with 100 uniformly sampled input-solution pairs and MSE loss function fails to learn a legitimate mapping.
In this paper, instead of learning input-solution mappings as in prior arts, we employ Rectified Flow (RectFlow) (Liu et al. 2022) as a generative approach to learn the mapping from input to a preferred solution distribution for solving non-convex problems. We made the following contributions.
In Sec. Dl we elucidate the challenge of solving non-convex problems characterized by multi-valued input-solution mapping. In response to this challenge, propose a novel generative learning frame- work, detailed Sec. Our approach is predicated on the availability of a training dataset sampled from preferred input- nependeepndent solution distribution, and leverages the universal approximation capability of the RectFlow model to learn the distribution. Given new input, this trained model is subsequently harnessed to generate high-quality solutions from the learned distribution.
>> In Sec. 5, we theoretically characterize the incurred optimality loss of generated solutions in Sec. 5. The results show that the probability that the generated solution incurs optimality gap larger than any 5 > O decreases exponentially to zero as we sample more from the learned input-dependent solution distribution. We also characterize the runtime complexity and discuss the training complexity of the framework.
In Sec. 6 simulation results for learning multi-valued mappings and solving various non-convex problems show that our method achieves significantly better solution optimality than the latest NN-based schemes, with comparable feasibility and speedup performance.
To our best knowledge, this is the first work advocating a paradigm shift from learning input- solution mapping to learning the mapping from input cuuuiion-disributioon for solving continuous constrained optimization problems. The code is available at Code
RELATED WORK
Recent advancements in ML-driven optimization, encompassing end-to-end (E2E) solution mapping, saaming-to-optimiie (L20) strategies, and hybrid models, have demonstrated promise in addressing constrained optimization challenges (Kotary et al.) (0211)) In the setting of supervised training, high-quality solutions are prepared in advance, and a neural network (NN) is trained to map input parameter to the solution. However, for non-convex problems, the existence of multiple solutions leads to multi-valued input-solution mapping, which introduces significant challenges when using NNs for approximation. We summarize existing proposals to address the challenges introduced by multi-valued mappings in Table
2

---

Published as a conference paper at ICLR 2024
Table 1: Existing studies for solving non-convex puzzles with a multi-valued input-solution mapping.
Existing Studies
Stable training
Multiple solutions
Optimality guarantee
Low training complexity
Low run-time complexity
(see Sec. f references)
Data generation
Data selection
x
X
X
Data augmentation
X
Hindsight loss
/
V / /
Clustering approach
X
Generative Learning
Supervised learning for input-to-solution mappings. To learn single input-solution mapping, Kotary et al. (2021a) utilizes the local Lipschitz condition to design a data generation scheme and avoid the multiple solution issues in the training dataset. Without preparing the single-solution dataset in advance, [annwaan et al. (2020) proposes a data selection approach, which trains another NN to identify one of multiple mappings from dataset mixed with numerous optimal solutions for each input. To learn multiple mappings directly from the dataset, et et al. (2018) adopts multiple models to divide one-to-many mappings and utilizes the hindsight loss to optimize them jointly. The clustering methods (Courts & Kvinge (021)) can also be applied to partition the dataset and learn different mappings separately. |Sun et al. (2017) and Pan et al. (2023) transform the multi-valued mapping into single-valued one with the augmentation of initial points information from deterministic solvers. These methodologies leverage unique aspects of the solution dataset, yet they tend to depend on additional information, such as initial points, and often lack performance guarantee.
Other approaches for input-solution mappings. scenarios lacking ground-trute optimal solutions, unsupervised learning emerges viable alternative for learning an input-to-solution mapping under the guidance of well-designed differentiable loss function (Poganćić et al. 2019: Karalias & Loukas 2020: Huang & Chen 2021: Qiu et al.) 2022 Ferber al. 2023). Reinforcement learning approaches can also be employed to train solution mappings for non problems, particularly
for combinatorial problems with discrete structures (Kwon et al. 2020 Zhang al., 2020; Xin et al.)
2021 Ma et al. 2021 Caramanis et al.] 2024). However, these approaches can easily become stuck
local optima without guidance of ground-truth optimal information.
Generative models for approximating distribution. The multi-valued input-solution mapping can be reframed as input-conditioned solution distribution from which multiple solutions are sampled. Leveraging the sequential nature of routing problems, auto-regressie (AR) distributions are trained to capture multiple symmetric solutions (Kool et al., [0188] Kwon al. 2020) Xin et al.) [202]] Hou et al. 2022). To model more intricate distributions, advanced generative models are brought into play. These models transform simple prior distribution into the complex data distribution either via push-forward mappings or through the integration of stochastic/ordinary differential equations (SDE/ODE). The push-forward generative models, such as generative adversarial networks (GANs), are known to struggle with the mode collapse issue, which limits their ability to capture multi-modal distributions effectively (Salmona et al. 2022). In contrast, SDE/ODE- generative models, like diffusion models, learn the continuous transformation dynamics rather than a single mapping, which has been demonstrated superior performance in various application scenarios (Ho et al. 2020) Song
et al.
2020b 2023a
Sun & Yang. 2024 Li et al. 2024).
In summary, existing schemes addressing multi-valued solutions issues either suffer from significant computational expense or lack prediction performance guarantee. In this work, we propose
generative learning framework for approximating the solution distribution for non-convex continuous problems with bounded optimality loss and considerable speedup. Our scheme is inspired by the recent success of SDE/ODE-basee based generative models in complex distribution modeling, such as image generation and combinatorial problems (Ho et al. [020] [Sun& Yang 2024). However, is uniquely different in the problem definition, solution optimality, and performance guarantee.
3 PROBLEM STATEMENT
We consider the following continuous optimization problem:
min ø f(x,
(I)
3

---

Published as a conference paper at ICLR 2024
where e E C C Rd denotes the input contextual variables, E Ke C R" is the decision variables, KCe C. R is the compact seput-dependent constraint set and f(x, () Rutdd + R a continuous objective function (potentially non-convex). Such a formulation in ( covers wide-ranging engineer- ing applications, including general continuous constrained optimization and relaxed combinatorial problems. The global optimal solutions are denoted x. X arg minzek. [f(x, c)}, where X2 is the optimal solution set.
For strictly-convex problems, it has a unique optimal solution x for each input c, corresponding to single-valued input-solution mapping F : - 2e (Pan et al. 2019 Donti et al. [021] Amos 2022). By learning such a mapping and passing new input through the learned mapping to obtain quality solution instantly, neural networks (NN) have shown remarkable speed improvements in solving convex problems over iterative solvers.
However, non-strictly convex or non-convex problems may exhibit a complexity that allows multiple optimal solutions for identical inputs, resulting nulti-valued input-solution associations. Conse- quently, the training dataset might include "mixed" data points, reflecting this "one-to-many" mapping. This complexity can impede the trained NN from accurately learning the intended input-solution relationship, resulting in suboptimal solutions. As discussed in Sec. 2 existing studies for continuous constrained optimization endeavor to identify a single possible mapping from the potential multiples, employing various data preparation processing techniques. Nevertheless, these approaches often compromise between poor optimality performance and high computational complexity.
In contrast, this paper introduces paradigm shift and leverages NN to learn the mapping from input to solution distribution instead of from input to solution. This method enables us to architect NN schemes that balance low computational complexity with robust optimality performance, thereby more effectively addressing non-convex problems.
3.1 INPUT-DEPENDEN SOLUTION DISTRIBUTION AND TRAINING DATA
We make the following assumption on the input-dependent solution distribution to be learned: Assumption 1. The input-dependent solution distribution Pa(xlc) obeys the Boltzmann distribution with inverse temperature parameter as 3 2
exp(-3f(z, c)) c))dx"
pa(x/c) = JK.
Vo E K...
This assumption is common in ML research and can easily be satisfied (i) when stochastic algorithms are adopted to solve the non-convex problem for general (3, for example, Markoy chain Monte Carlo (Chen et al. 2013 Deng al., 2020) and simulated annealing (Dekkers & Aarts 1991 Correia et al.) 2023), or (ii) when 3 + oo and the dataset contains only multiple global optimal solutions, which is aligned with the setting in (Nandwani al.) 2020). This assumption also implies that (i) concentration of probability in high-quality solutions, where B can represent the quality of the dataset, and (ii) continuity of the probability density Pa(zlc) on both x and given the continuous optimization problem in (1. which is critical for the theoretical guarantee for our generative framework.
Given the training dataset sampled from the distribution, in the next section, we will develop a generative learning framework to learn the mapping from input to solution distribution Pa(z]c). We can then generate quality solutions for new inputs by sampling from the learned distributions.
OUR GENERATIVE LEARNING FRAMEWORK
To address the challenge of the multi-valued solution mapping problem in Sec. B] utilize generative models to learn the input-dependent solution distribution. While there are different generative models to learn target distribution as discussed in Sec. 2 select the ODE-based generative model (RectFlow Liu et al. (2022) because of its strong approximation ability for complex distribution and fast generation process
Our framework, as shown in Fig. 2 consists of three modules designed to (i) model the input- dependent solution distribution for the given "mixed" dataset using the RectFlow model Sec.
We also provide comprehensive comparison of different generative models in the Appendix
4

---

Published as a conference paper at ICLR 2024
Input parameter c C
output sulutio
non-convex optimization
RectFlow
LC
min f(z, c) ak
x cr
de no(alc)
Wo,
Muteple optimum
ODE trajectory
initial distribution
solution distribution
objective
Figure 2: Our proposed Generative Learning framework.
(ii) train NN-approximated vector field for RectFlow in Sec. 4.2 and (iii) sample solution according
the approximated solution distribution for new input parameters in Sec. 4.3 respectively. We
characterize the optimality loss and run-time complexity associated with our approach Sec.
4.1 RECTFLOW MODEL FOR INPUT-DEPENDENT SOLUTION DISTRIBUTION
The RectFlow model is a class of ODE-based generative models that employ vector field to transform a simple initial distribution into a complex target distribution through forward ODE, Specific to our study in this paper, we select smooth distribution g(rr), e-g., Gaussian, as the initial distribution, and the input-dependent solution distribution pa(r]c) the target distribution. Then, the ODE for transformation always exists under Assumption and can be found by solving the following Pokker-Planck (FP) equations (Ambrosio et al. 2005);
Öp(a,, 1)/0l = V (p(æ,, (,(xx
dx./dt =u(xi;t,))
boundary conditions: p( 0) = q(x), p(a1, 1) pa(xlc), [(p(xl))
(5)
where p(a,, I) denotes the PDF of the random variable at 1 E [0, and u(ar, 4, Ro+d+1 represent vector field to be solved. Once u(x, 1, c) is obtained, we can generate new solutions obeying the target distribution by sampling from simple prior zo q(z) and conducting integration with the target vector field as x = zo + fo u(x;,,, 4, c)d;; see an illustrative example Fig.
R
Although the FP equations seem difficult solve, existing works have constructed some explicit-form ODE solutions for them shown in (Lipman et al.] 2022 Xu et al., 2022 Albergo et al.] al.]2203// Song
et al. 2020a 2023b). We then follow one of the ODE solutions, the RectFlow (Liu et al. (202)) to
obtain an explicit expression
vector field solution, as shown in the following proposition:
c). denoted as RectFlow, a solution to the FP equations Proposition 4.1. The vector field u(æ, t,
with boundary conditions q(x) and P1 = Pa(zlc). It is given as:
u(x, (, = (puttlll)
z0 2ol = x],
where x, t) tz
We make the following remarks. The vector field solution u(x, t) generate samples following the target distribution through forward ODE integration. However, it can not be directly calculated because of the expectation of the target distribution. On the other hand, given the historical dataset sampled from the target distribution under different input parameters, we can leverage the neural network (NN), denoted as vg (x, t,c), c). learn the target vector field in (6). which is continuous over ga+td x [0, 1), given the absolutely continuous initial and target distributions Ambrosio et al. (2005). After training, the NN-approximated vector field can be directly used to generate input-dependent solutions by conducting integration.
4.2 TRAINING NN-APPROXIMATED VECTOR FIELD
As discussed after Prop. 4.1 the target vector u(z, c) in (6) is continuous and can transform a simple distribution the target solution distribution, but it can not be directly applied. Thus,
5

---

Published as a conference paper at ICLR 2024
leverage the universal approximation capacity of NN, denoted as (0 t, c), approximate it based on the collected samples from po and p1. We employ the following loss function:
(v(v L/² (o (Ilva ( (,), (I1 =o0)l
where dt. = (1 z0 + (x1, zig ~ ((x) is sampled from a fixed prior distribution (e.g., Gaussian), and pa(()]c is the solution sampled from the training dataset. Minimizing the loss function in 7 will guide the NN to learn the target vector field in (6). as shown in the following proposition:
Proposition 4.2 (Liu et al. (2022)) The minimizer of the loss function in 7 the target vector field
c) in (6. and a solution to the FP equations with boundary conditions in 35
Therefore, we can employ the loss function in 77 to learn the target vector field solution to the FP
equations. Further, to optimize the average performance across different input parameters, we employ the total loss function follows:
[(vs) B.(CC( = S/' Bepp-glle (ooo: - (x1 xo)
(8)
To minimize the loss, we first prepare the training data, including (i) the historical dataset {ee, æ 1.N
i=]
with different input-solution pairs, (ii) samples from fixed Gaussian distribution To ~ g(x), and (iii)
uniform sampled time index t (). After that, we can train by based on the loss function in using optimizers such Adam (Kingma & Ba 2014).
4.3 GENERATING SOLUTION UNDER NEW INPUT PARAMETERS
After training the NN-approximated vector field by for the generative model, given new input parameters we can generate solutions following the target distribution approximately by solving forward ODE as 21 Zo + Io' uo ( t, c)dt. Such integration be efficiently implemented by numerical solver. For example, the Euler method with discretized step of 1/k: k is follows:
1(++1)/k Ei/h + 1/k vo( i/k: c), 0, 1, ...
where zo ~ q(x)) is sampled from Gaussian distribution. However, owing to the approximation eлror of the NN vector field and discretization error of numerical ODE solving, the optimality and feasibility of the generated solutions may not be guaranteed. We apply the following strategy to improve the solution quality:
To improve the quality of the predicted solution, we employ a sampling-thes seln-selection strategy. This strategy generates multiple solutions by sampling batch of initial points zo q(x), conducting integration simultaneously to generate candidate solutions, and selecting the one with the minimum objective value and constraint violation.
To ensure the feasibility of generated solutions for continuous constrained optimization problems, we can execute projection operations (Chen al. 202 Liang al. 2023) to find nearby feasible point. When solving the relaxed combinatorial problem, after generating relaxed continuous solution, we can adopt greedy decoding strategy recover feasible discrete solution (Kool et al. 2022
Sun & Yang 2024).
PERFORMANCE ANALYSIS
In this section, we characterize the optimality loss and the run-time complexity for our generative learning, considering factors such as the NN approximation error, ODE discretization step, and the number of sampled solutions. We then discuss the training complexity, scalability, and limitations.
5.1 SOLUTION OPTIMALITY AND RUN-TIME COMPLEXITY
The following theorem characterizes the optimality loss and run-time complexity associated with our generative approach based the NN-approximated vector field of the ODE-b generative model.

---

Published as a conference paper at ICLR 2024
Theorem 1. Recall u(x,t,,) is solution to the FP equations in 3 -5
Let ve be the NN- t, c) u(æ, t, c.
approximate vector field and Eg be the approximation error: co = (
Let ( be the generated m solutions using the vector field v4 and Euler methods with a stepsize of 1 /k, as detailed Sec. 4.3
we have
the probability that the best of the solutions {&E,) ). incurs optimality gap larger than any decreases exponentially to zero as m increases:
min Pr (min (=I....m
( e)} 2 [(x () s 5
C/ C2k-1/2)",
(10)
where C1 and C2 are positive constants depending on Lipschitz conditions of both u(x, t, c) and vg(a,t, and Pr(S5(c)= = Jsy exp(-3f(x, c))dx/ Jk. exp(-8f(z, c))dz represents the probabil-
ity of collected training data lies in the d-sublevel set S E 1 fxx f( c) + 6}.
the run-lime complexity of generating a solution at. is O(k- 1. (n + d))²,, where I is the number of layers in the fully connected NN and and d are dimensions of the decision variable and input parameter of problem in (T). respectively.
The complete proof in Appendix A We make the following remarks. First, Theorem Ieleeidteeeeeeeee the optimization gap of the solution generated under the following conditions: (i) the quality of training data, represented by Pr(S)(c), (ii) the approximation error of the learned vector field by the NN. denoted as cg. (iii) the number of ODE discretization steps, and (iv) the number of sampled candidate solutions.
To boost the probability of sampling high-quality solutions (i.e., 8 is small), certain strategies can be implemented in the offline training phase. One effective method is to collect a solution dataset of high quality (i.c., 3 is large). This ensures that pa(æ]c) predominantly focuses on the high-quality solutions, and consequently, Pr(S c) approaches 1. Furthermore, to reduce eg,, the loss function in Eq. needs to be minimized. This can be achieved by utilizing deeper NNs with less model approximation error and incorporating more training data to reduce generalization error. During the online inference phase, the total simulating step k of the ODE solver can be increased to reduce the discretization error. Another strategy is to sample a larger number of candidate solutions and select the most optimal one.
Second, the runtime complexity associated with generating solution increases linearly with the number of ODE discretization steps and is also influenced by the structure of the adopted NN. Augmenting the number of sampled solutions does not significantly exacerbate the complexity due to the efficiency of batch computation. Therefore, to strike a balance between optimality loss and runtime complexity, it is more advantageous to sample more solutions rather than increasing the number of discretization steps.
5.2 TRAINING COMPLEXITY, SCALABILITY, AND LIMITATIONS
To train the NN-approximated vector field within our generative learning framework, we require a training dataset D, which contains different input-solution pairs, samples from a fixed prior distribution (e.g.. Gaussian), and uniform time index from unit interval. Subsequently, each iteration, we separately sample batch of (c, x1). Zg. and f, and train the NN using the Adam optimizer (Kingma & Ba 2014). The training computation hinges on the forward-backwer NN, which can be efficiently executed on GPU. The principal scalability issues arise during the preparation of the training dataset. In this phase, we need repeatedly solve the non-convex problem under varied inputs using existing solvers in the offline phase. In the absence of ground-truth truth solution data, the unsuperviicddreiiffccemen learning approaches for NN training will be explored in future work.
propagation of the
EXPERIMENTS
We evaluate and compare the performance of our generative learning framework with the RectFlow model and other NN-based schemes for (i) learning a 2-dim complex multi-valued mapping, (ii) solving continuous non-convex problems with multiple solutions, and (iii) solving combinatorial
7

---

Published as a conference paper at ICLR 2024
problems. The NN-based approaches to compare include learning deterministic mappings: (i) simple NN to directly predict the solution based on the input parameter, (ii) hindsight loss to train multiple NN mappings simultaneously (Li et al.) 2018); (iii) dustering-basee methods to train multiple mappings by partitioning the datasets into clusters of different mappings (Nandwani et al.
2020: Courts & Kvinge| 2021); and learning solution distributions: (iv) generative ad verssariall network (GAN) (Goodfcllow et al., (2020); (v) diffusion-baase model (Song et al., 2020aa (Sun & Yang 2024); (vi) our generative learning with RectFlow (Liu al. 2022). The detailed setting of
pereepparaeterss and implementation of different approaches are in Appendix C.I
6.1 LEARNING MULTI-VALUED INPUT-SOLUTION MAPPING
To elucidate and juxtapose the various NN-based schemes, we commence with a two-dimensional, albeit complex, example. Consider the setting where non-convex problem admits six optimal solutions with the same optimal objective value for each input, leading to 6-valued input-solution mapping as F(c) {3c² 0.5, -3e² + 0.5, c+ -c+1, c -c 1}.
We then generate dataset, denoted as D = xc,. by sampling input-solution pairs from F(c). The constructed input-dependent solution distribution notably discrete, with support that encompasses no more than six distinct points, implied by the limit 3 - Do in Assumption | After training, we sample testing input parameters and feed them into the trained models. The output solutions visualized in Fig. 3 providing illustrative comparison of the performance of different models. Additional graphical representations, such as the visualizations of the learned ODE flow, can be found in Appendix C.2 First, the RectFlow model exhibits superior performance in approximating the target multi-vall valued mappings. In contrast, the simple NN fits an average curve across multiple mappings. The performance of both the hindsight loss-based and cluster-based methods is notably sensitive to the predefined number of potential mappings. The GAN fails to fit such a multi-modal distribution. The diffusion models display an approximation performance similar to that of RectFlow. However, the inherent stochasticity of the backward diffusion process may cause deviations in the generated solution, as indicated by the color dispersion of similar generated solutions.
NN
Hindsight
Cluster
Output solutions
Probab biility demsiity
Target mappings
approximated mappings
generated solutions RectFlow
GAN
Diffusion
Output solutions
-1.5
65
-05
6.1
-1.0
-0.5
2.5
Input parameter
Input parameter
Input parameter
Figure 3: Performance of different models learning multi-valued mapping. The approaches in the first (NN, Hindsight, Cluster) aim learn multiple single-valued mappings, while the ones second row (GAN, Diffusion, and RectFlow) learn the solution distribution instead (the color represents the sampling probability).
6.2 LEARNING SOLUTION DISTRIBUTION FOR CONTINUOUS CON-CONVEX PROBLEMS
We then test the generative learning with two real-world non-convex problems, including the inverse kinematics problem with non-convex constraints and the wireless power control with non-convex objectives, where the detailed formulations and data generation settings are in Appendix C These problems are challenging to be solved in real time due to their non-convex constraints and objectives.
As shown in Table first, those approaches aiming to learn deterministic solution mappings fail due to the existence of multiple optimal solutions. When implementing hindsight loss-based or clustering- methodologies, precise number of mappings must be designated, which is often
8

---

Published as a conference paper at ICLR 2024
Table Performance comparison on the different continuous non-convex problems
Problem Metric
Inverse kinematies problem Speedup
Wireless power control
Error
Error
Speedup
Opt. gap
Speedup
Opt. gap
Speedup
Prob. size
= n,
d
2, n
7
d 20
20
40²
40
NN
2.82
850
4.80
1327
25.42%
16
30.64%
49
Hindsight
1.06
479
3.11
751
21.71%
10
28.67%
28
Cluster
1.22
481
3.69
757
21.49%
10
27.15%
28
GAN
0.23
435
1.53
593
19.31%
8
36.39%
16
Diffusion 0.05
226
0.35
280
12.08%
4
13.77%
RectFlow 0.04
258
0.37
348
2.94%
5
3.96%
7
is the input parameter dimension and the decision variable dimension. The errur for the inverse kinematics problem represents the constraint violation.
3 The predicted solutions for the wireless power problem have been projected to its constraint set.
impractical and results in considerable optimality loss. On the other hand, facing such complex solution distribution, the GAN struggles to capture it and has a large optimality gap. Both the RectFlow and the diffusion-based model can approximate complex solution distributions. However, the adopted RectFlow model outperforms the ceffusiin-bassee model by demonstrating a smaller optimality gap and a superior speedup. In essence, the RectFlow model balances optimality and speedup when learning complex, input-dependent solution distributions, making it an excellent choice for tackling the multi-valued input-solution mapping for non-convex problems.
We also conduct an ablation study on the trade-off between optimality and run-time complexity under various parameter settings, such the number of sampled solutions and discretization steps, in Appendix C.5 This visualization aids in understanding the analysis presented in Theorem and offers further guidance for empirically tuning these parameters.
6.3 LEARNING SOLUTION DISTRIBUTION FOR COMBINATORIAL OPTIMIZATION
Table 3: Performance comparison on different non convex combinatorial problems.
Problem Metric
Maximum clique
Maximum independent set Opt. gap + Speedup t
Maximum cut
Opt. gap 4 Speedup
Opt. gap J Speedup
Graph size
100- graph: 100?, n 100
NN
22.77%
64.17
23.18%
78.46
12.06%
330.06
Hindsight
17.40%
31.00
18.84%
34.46
12.07%
106.92
Cluster
23.49%
33.45
19.20%
30.44
99.77%
139.44
GAN 20.98%
36.79
16.43%
29.68
100%
170.78
Diffusion 5.73%
14.66
5.40%
14.30
8.21%
71.10
RectFlow 4.87%
18.06
5.59%
17.02
1.35%
92.69
Note that both the optimality gap and speedup presented are based on solutions after greedy decoding, As such, the fcasibility is guaranteed be for all the schemes.
We further generalize classic cases for this purpose: the maximum clique, the maximum independent set, and the maximum-cut problem. The detailed formulations and data generation settings in Appendix C.4 As with non-convex continuous problems, combinatorial graph problems display many symmetric solutions. This vast solution space poses significant challenges for established methods that aim learn single/multiple deterministic solution mappings, as illustrated in Table However, approaches focusing on learning the solution distribution have demonstrated superior empirical performance. Specifically, RectFlow has shown a better balance between optimality and computational efficiency.
framework to cope with the combinatorial problems. We select three
7 CONCLUSION
We develop a generative learning approach for managing multi-valued input-solution mappings in continuous non-convex problems. It is built upon the ODE-based generative model and learns the mapping from input to solution distribution, a departure from the conventional focus input-solution mapping. This model, upon receiving new input, samples high-quality solutions from the learned distribution. The optimality loss and runtime complexity of our method are characterized, showing its efficiency. Simulations show that our approach achieves significantly better solution optimality compared to recent NN schemes, while maintaining comparable speedup. This highlights the potential of our method handling complex multi-valued input-solution mappings, paving the way for future research in machine learning for constrained optimization problems.

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENT
This work is supported in part by a General Research Fund from Research Grants Council, Hong Kong (Project No. 11203122), an InnoHK initiative, The Government of the HKSAR, Laboratory for Al-Powered Financial Technologies, and a Shenzhen-Hong Long-Macau Science & Technology Project (Category C, Project No. SGDX202205301 1203026). The authors would also like to thank the anonymous reviewers for their helpful comments.
REFERENCES
Michael Albergo, Nicholas M Boffi, and Eric Vanden-Eijnden. Stochastic interpolants: unifying framework for flows and diffusions. arXiv preprint arXiv:2303.08897, 2023.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
Brandon Amos. Tutorial on amortized optimization for learning to optimize over continuous domains. arXiv preprint arXiv:2202.00666 2022.
Lynton Ardizzone, Jakob Kruse, Sehastian Wirkert, Daniel Rahner, Eric W Pellegrini, Ralf's Klessen, Lena Maier-Hein, Carsten Rother, and Ullrich Köthe. Analyzing inverse problems with invertible neural networks. arXiv preprint 1808 04730, 2018.
Kyri Baker. Learning warm-start points for optimal power flow. In 2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEBE, 2019.
Constantine Caramanis, Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Optimizing solution-samplers for combinatorial problems: The landscape of policy-gradient method. Advances in Neural Information Processing Systems, 36, 2024.
Bingqing Chen, Priya L. Donti, Kyri Baker, Zico Kolter, and Mario Bergés. Enforcing policy feasibility constraints through differentiable projection for energy optimization. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems, pp. 199-210, 2021a.
Minghua Chen, Soung Chang Liew, Ziyu Shao, and Caihong Kai. Markov approximation for combinatorial network optimization. IEEE transactions on information theory, 59(10))6301-6377, 2013.
Sitan Chen, Giannis Daras, and Alex Dimakis. Restoration-deeraaattio beyond linear diffusions: non-asymptotic analysis for ddim-type samplers. In International Conference on Machine Learning, pp. 1462--444. PMLR, 2023.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and benchmark. arXiv preprint arXiv:2103. 12828, 2021b.
Alvaro HC Correia, Daniel E Worrall, and Roberto Bondesan. Neural simulated annealing. In International Conference on Artificial Intelligence and Statistics, pp. 4946-4962. PMLR, 2023.
Nico Courts and Henry Kvinge. Bundle networks: Fiber bundles, local trivializations, and generative approach to exploring many-to-one maps. arXiv preprint arXiv:2110.06983 2021.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method. Annals of operations research, 134:19-67 2005.
Anton Dekkers and Emile Aarts. Global optimization and simulated annealing. Mathematical programming, 50:367-393, 1991.
Wei Deng, Qi Feng, Liyao Gao, Faming Liang, and Guang Lin. Non-convex learning via replica exchange stochastic gradient meme. In International Conference on Machine Learning. pp. 2483. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2024
Priya L Donti, David Rolnick, and Zico Kolter. De3: A learning method for optimization with hard constraints. arXiv preprint arXiv:2104.12222: 2021.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sei, 5(1):17-60, 1960.
Aaron M Ferber, Taoan Huang. Daochen Zha, Martin Schubert, Benoit Steiner, Bistra Dilkina, and Yuandong Tian. Surco: Learning linear surrogates for combinatorial nonlinear optimization problems. In International Conference on Machine Learning, pp- 10034-10052. PMLR, 2023.
Ferdinando Fioretto, Terrence WK Mak, and Pascal Van Hentenryck. Predicting ac optimal power flows: Combining deep learning and lagrangian dual methods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 630-637, 2020.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1):139-144, 2020.
Howard Heaton, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Safeguarded learned convex optimization. arXiv preprint arXiv:2003.0/880, 2020.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-688 6851, 2020.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference Learning Representations, 2022.
Wanjun Huang and Minghua Chen. Deepopf-ngt: Fast no ground truth deep learning-basee approach for oc- problems. In ICML 202/ Workshop Tackling Climate Change with Machine Learning. 2021.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizzation with gumbel-softmax. arXiv preprint arXiv:1611.00 144, 2016.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988 2014.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference Learning Representutions, 2018
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 190-213. Springer, 2022.
James Kotary, Ferdinando Fioretto, and Pascal Van Hentenryck. Learning hard optimization problems: A data generation perspective. Advances in Neural Information Processing Systems, 34:24981- 24992, 2021a.
James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2103. /6378, 2021b.
11

---

Published as a conference paper at ICLR 2024
Yeong-Det Dae Kwon, Jinho Choo, Byoungji Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188 88-21198,, 2020.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken, Multilayer feedforward networks with nonpolynomial activation function approximate any function. Neural networks, 6(6):861-867, 1993.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
Enming Liang, Minghua Chen, and Steven H Low. Low complexity homeomorphic projection to ensure neural-network solution feasibility for optimization over (non-Jconvex set. In International Conference on Machine Learning. PMLR, 2023.
Yaron Lipman, Ricky TQ Chen, Heli for generative modeling. arXiv preprint arXi::2210.02747, 2022.
Maximilian Nickel, and Matt Le. Flow matching
Xingchao Liu, Chengyue Gong, and Qiang Liu. Flow straight and fast: Learning generate and transfer data with rectified flow. arXiv preprint arXiv:2209.0304 00000000,000 2022.
Cheng Lu, Kaiwen Zheng, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Maximum likelihood training for score-based diffusion odes by high order denoising score matching. In International Conference on Machine Learning, pp. 14429-14400. PMLR, 2022.
Yining Ma, Jingwen Li, Zhiguang Cao. Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-0061111 1199--11100 11107, 2021.
Yatin Nandwani, Deepanshu Jindal, Parag Singla, et al. Neural learning of one-of-many solutions for combinatorial problems in structured output spaces. In International Conference on Learning Representations, 2020.
Xiang Pan, Tianyu Zhao, and Minghua Chen. Deepopf: A deep neural network approach for security- constrained de optimal power flow. 2019 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmariGridCommm) 2019.
Xiang Pan, Tianyu Zhao, Minghua Chen, and Shengyu Zhang. Deepopf: deep neural network approach for Securit-consstrineet de optimal power flow. IEEE Transactions on Power Systems, 36(3):1725-1735 2020.
Xiang Pan, Wanjun Huang, Minghua Chen, and Steven H Low. Deepopf-al: Augmented learning for solving ac-opf problems with multi-valued load-solution mapping. In Proceedings of the 14th ACM International Conference on Future Energy Systems, pp. 42-47, 2023.
Seonho Park and Pascal Van Hentenryck. Self-supervised primal-dual learning for constrained optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4052-4060, 2023.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differenti- ation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. arXiv preprint arXiv:2210.04122 2022.
Antoine Salmona, Valentin De Bortoli, Julie Delon, and Agnès Desolneux. Can fush-forward generative models fit multimodal distributions? arXiv preprint arXiv:2206. 14476, 2022.
12

---

Published as a conference paper at ICLR 2024
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020a.
Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse-guided diffusion models for inverse problems. In International Conference Learning Representations, 2023a.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011. 13466, 2020b.
Yang Song, Prafulla Dhariwal, Mark Chen, and llya Sutskever. Consistency models. arXiv preprint arXiv:2303.01469, 2023b.
Haoran Sun, Xiangyi Chen, Qingjiang Shi, Mingyi Hong, Xiao Fu, and Nikos D Sidiropoulos. Learning to optimize: Training deep neural networks for wireless resource management. In 2017 IEEE 18th International Workshop on Signal Processing Advances Wireless Communications (SPAWC), pp. 1-6. IEEE, 2017.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
Daniel Tabas and Baosen Zhang. Safe and efficient model predic tive control using neural networks: An interior point approach. arXiv preprint arXiv:2203.121190 12196, 2022.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12042-12049, 2021.
Yilun Xu, Ziming Liu, Max Tegmark, and Tommi Jaakkola. Poisson flow generative models. arXiv preprint 2tt.::2229911177.. 2022.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Newral Information Processing Systems, 33:1621-1631 2020.
Tianyu Zhao, Xiang Pan, Minghua Chen, and Steven Low. Ensuring dnn solution feasibility for optimization problems with linear constraints. In The Eleventh International Conference on Learning Representations, 2022.
13

---

Published as a conference paper at ICLR 2024
A PROOF FOR THEOREM 1
Let up be the NN- approximate vector field and ca be the approximation error: co Ex, (2 c) u(x,t, f, c)ll ) Let (= be the generated m solutions using the vector field Ug and Euler methods with a stepsize of /k; as detailed in Sec. 4.3 have
Theorem 1: Recall u(2, t, c) a solution to the FP equations in -
the probability that the best of the m solutions ( 1m incurs an optimality gap larger than any 5 0 decreases exponentially zero as increases:
Pr min if( c, c)} 2 f(z () +6) s (1-0))=((111 (1 (=I.....
+ Cak 12k-1/3); m
(1I)
where C and C2 are positive constants depending on Lipschitz conditions of both u(x, i, c) and 0g(2, t, c),, and cr( Ssy exp(-3f(z, ())dxx/ exp(-8f(z, c))dr represents the probabil- ity of collected training data lies in the 6-sublevel set S = fIr K. f(z,c) c) S f(2). 6
the run-time complexity of generating solution s O(k 1- (n+ d)²). where is the number of layers in the fully connected NN and n and d are dimensions of the decision variable and input parameter of problem (T), respectively.
Proof. (a) Optimality loss of generated solutions
We first investigate the probability of collected training data lies in the d-sublevel set S fo E Kr
far c) $ (( 8} _ K..
Pr(SS(c) Pr(f(Ee, S c) -6}
(12)
/ Jk. Pf(=lc)[(f(zee]) S f(z), 8
(13)
Sst exp(= c))xz
(14)
Jk. exp(-3f(x, c))d=
when [ = 0. the solution distribution is correspondingly uniform distribution, and the probability is the ratio of two volumes of sets as Pr(Se = Vol(S Vol( < 1. With the increase of 3, the solution distribution concentrates on the solutions with better objective values. When - oc, the probability converges to Pr(S c) + 1, such that almost all sampled solutions are within S
The next step is to consider the probability of sampling from the ô sub-level with an approximated generative model, denoted Pr(Se(c. 0). To proceed, let u(r, c) and (z(r) be a target solution (e.g., RectFlow) of the Planck equation with desired boundary conditions Po g(z) and
Pi = Pa(=lc) under input parameter c. u2 c) is the NN-approximated vector field, and gi (z) the corresponding PDF driven by (1(x,, under input parameter c. (e()) is the PDF driven by vo (x, under Fuler methods of & discretization steps. The initial distribution is the same as Po(x) = (0(x) = (x) = (0, I.). The terminal distributions are denoted as De ~ P1(x) = pa(alc), & q1 (z) pa (z(c)) and dt (z) p5 (x|c) respectively.
Then we can can bound Pr(Sš]c, 0) as:
Pr(Se]c, 0)
Pr(f(1e, c) S f() 5
(15)
Pr(Sgfc,0 0) Pr(Sf(e) Pr(Sé(e)
(16)
2 Pr(St[c) |Pr(Sile, 8) Pr(Séle)
(17)
2 Pr((f(c)- sup {[Pr(Alc.6) 0) - Pr(A(c))
(18)
ACK.
Pr((f]()
pa(=))))
(19)
where the total variation distance between two distributions p(x) and q(x) with compact support set of X is defined as TV(p. q) Amppcc/pp(AA {(4))> E [0. 1].
Considering the approximation error of the generative model on the total variation distance, the probability Pr(Se c, 0) may be low. Therefore, we propose the sampling-then-selectino strategy
14

---

Published as a conference paper at ICLR 2024
improve the optimality. Suppose we select the best solution from { (x]c). The probability of at least sampling one solution within the sub-level set is bounded as:
Pr( min (f(de,, c)3 2 c) +6)
(20)
==......
(1 (c)
(21)
S (1 - TVCb(ll)
(22)
Therefore, maximize the probability of sampling high-quality solution, we can (i) prepare high-quality solution dataset where Pr(S c)) close to 1, (ii) minimize the total variation distance (P (z/cc,, (a(e))) between the approximated solution distribution via the generative model and
the data distribution and (iii) increase the number of generated solutions in the online inference phase.
We then bound the total variation distance TV (pr(e)))) (rrc), pa(a (e) considering the approximation error of NN vector field and discretization step. We split the total variation distance into two parts:
TV (V(pa PT < (V(pa(=)c)
+ TV (V P (xlcc)
(xllc)
(23)
learning error
discrctization crvor
where the learning error evaluates the distance between data distribution and generated distribution by exact integration, and the discretization error evaluates the distance between generated distributions under exact integration and Euler methods of k discretization steps.
To tackle the learning error, according to the Pinsker's inequality, we have
TV(p2(z)c), po (z|c)) z
po(x)))),
(24)
The KL divergence between two distributions p(x) and ((r) with compact support set of X is defined as KL(p q) = Seex p(x) log p(z) 2(z)dz. dz.
((w)
According to Theorem 3.1 in (Lu at. 2022), the KL divergence can be bounded as:
KT((Pa(x(c) po(xlc)) S L p(())(((a,t)))) - te(a,t,e)) (V, log)((x) V log de (x))
(25)
According to the Barccy-Schwarzinne inequality, we can decompose the bound in Eq. 25 as:
KL(pa(z(cc po(x)c) < Bt, (0,011100(z1 u(x, t, 1/2 E, V log (x)
V, log 9 (z)
13)/
NN approximation error as
Fisher divergence as Dr l
(26)
where the first part represents the NN approximation error eq Ee,a (1o u(x, (x,t,ot [?] and the second part denotes the Fisher divergence as Dr qc) = E,, V. log (z)
V, log q [1.]
We make the following remakes for the upper bound of KL divergence in 26). Firstly, this upper bound represents the product of the Neural Network (NN) approximation error in learning the target vector field and the Fisher divergence between two probability flows. The goal of our loss function (as shown in Eq. (7) is to minimize the approximation error. As for the Fisher divergence, it can be polynomially bounded under certain Lipschitz conditions of the target vector field and the NN-approximated one, as stipulated by Theorem 4.7 in (Chen et al., 2023). Moreover, as demonstrated by Theorem 3.2 in (Lu et al.) 2022). Fisher divergence can also be optimized to expedite the convergence of the KL distance. This optimization can be achieved by incorporating certain high-order regularization terms into the loss function. However, due computational constraints, we
concentrate on minimizing Eg as outlined in the loss function (refer to Eq. 7
Next, by substituting the KL divergence term in Pinsker's inequality (as given in Eq. 24 with the upper bound provided in Eq. 26). we can bound the first part of the total variation distance as follows:
V2 (Dr(pi (:)c0)
<
(27)
2
15

---

Published as a conference paper at ICLR 2024
We then tackle the discretization enror under Euler methods with & discretization steps.
1)+1 24/k + "o(oss i= 0,2,,
(28)
where the initial points zo ~ ((x) are sampled from Gaussian distribution.
Let the Lipschitz of the NN-approximated vector field over and & and L and L respectively. Suppose the stepsize 1 1/k is small enough (e.g., k 2 2L as in Lemma C.3 in (Chen et al. 2023 that the discretized ODE trajectory is invertible.
We denote the valid vector field under Euler discretization as 0g where 60 t, c) = vo t, c) for
t {0, ...... : ..... k-1 The distance between the continuous vector field and the discretized vector field can be bounded as:
|1, t, t) 60(a, t, c)ll
(29)
= =11o( t, - uz( uo(x, [tk]] /k, c) vo(x, [tk]/k, c) 00 t.
(30)
< (1vo(x,,,c) u,, [tk] / k. c) + [10 [kk] /// c) (,
(31)
where we introduce an auxiliary term, (0 (z. [tk] /k, c), which represents the vector field at the previous discretized time point.
Next, we bound the two terms in Eq. 31 respectively. For the first term, consider the Lipschitz
condition of the NN-approximated vector field with respect and derive an upper bound as [[vo 1, uo(x, [tk]/k, //, c)ll S -
For the second term, we consider the equivalence between the continuous and the discretized vector fields on the discretized points. Specifically, for a stimulating trajectory ê with dg, 0g(0,, t, e) k-1 } and h E [0, 1/k]. Therefore, we have (z t, c) = k
(f t h, c) for t E {0, E ..... 60(2 By (z, c) [ [kk]/k, c). We then consider the Lipschitz condition of the NN-
approximated vector field with respect to and derive upper bound as [| [th] / c) (1 t, c)ll = [I, [tk://k, c) 20(r 00(x, c) [tk [/k),, [tk] (/.,/.))) c)ll S L. (z t,
Combining the upper bounds of the two terms together, we have:
(vl(x,t,)) 60 (2, tclll S Le, 00,
(32)
Under Euler methods with is discretization steps, the KL divergence is similarly bounded as
KL(po(xlc) p (xxc)) s Ee,= 1, c) èg (z, 1)] 422
(33)
For the distance between vector fields, we can bound it under the Lipschtz condition according to Eq.
32
Ex (lo, to t, 1 S (1/K)" + Li, (z( tz),
(34)
According to Pinsker's inequality (as given in Eq. 24).. the second part of the total variation distance can be bounded as:
V2 (V(o((llc), < 2 (Dr(q a L.) + Lú, (0(x, (,))
(35)
Therefore, combining the two upper bounds in Eq. 27 and Eq. 35 together, the total varia- tion distance between the target distribution and the one under NN approximation error and ODE discretization error can be bounded as
V2 TV < (Dr(p: 9/44
(36)
2 + (Dr Ee, + L" 60 ()) (1/ 2
(37)
Let the constant terms as C = va (2 (pr I 1/4 and O2 = x2 Er, T. (c))))))),
16

---

Published as a conference paper at ICLR 2024
By substituting the TV distance in Eq. 22 with the bound above, we have the final result:
Pr( min (f(Eci 2 f c) + 0)) $ (1 Pr(S + (
(38)
Pr(S C1 CCsk
(39)
(b) Run-time complexity of generation process
The run-time complexity involves the forward calculation of the neural network, the number of discretized steps k, and the number of samples m.
Considering a fully connected NN represented vector field 0a (2 f, c) with input dimension of n- +++++1 1, output dimension n, layers, and O(n + d) neurons on each hidden layer. The run-time complexity for this NN is as M = Oll (n + d) On the other hand, we adopt the transformer encoder for the graph problem. Suppose n-node graph with node embedding of dimension The run-time complexity for a I layer transformed encoder is of M = Oll (n² d + n dd)).
The integration of ODE conducted sequentially, which needs NN forward calculation each discretized point. Therefore, the total run-time complexity for generating a single solution is (Mk)..
B COMPARISON OF GENERATIVE MODELS
We compare the performance of existing generative models for distribution approximation using several metrics. These include their capacity capture various modes of general distributions, the quality of the samples they generate, and the speed of the sampling process. summary of this comparison is presented in Table
Table 4: Comparison of different generative models in consideration.
Generative model
Mode Diversity
High Quality Samples
Fast Sampling
Auto-regressive model
X
Normalizing flow
Variational auto-encoder
/
Generative adversarial network
X
SDE-based (Diffusion model)
ODE-based (RectFlow)
C EXPERIMENT SETTINGS
C.I COMPARED APPROACHES
We adopt the following approaches in our experiments, including NN-based and generative model based:
NN: a neural network F Rd - R is trained by directly minimizing the prediction mean square error
min (( - =]
(40)
F
After training, the solution directly output by the trained model F(c) given new input parameters.
Hindsight loss: multiple neural networks (FrMe trained simultaneously based the hindsight loss (Li al. 2018):
min ((c=))ma(tr min ((F((c) x=|]]]]
(41)
i=l....
After training, multiple solutions are predicted by each model F((c) for = 1,.., h, and we select the best one.
17

---

Published as a conference paper at ICLR 2024
Clustering-based approach: multiple predictors (F can also be trained by adding
additional NN-based clustering/selection model: W; IR {0, 1), The training loss is as:
min ((.z,)) P.W.
Σ (.(c,))F((c) =x1
(42)
Σ [((cx)=11 W.(e,z) E {0.1].
(43)
=), is assign cluster for input-solution pair. We adopt the Gumbel Softmax layer to reparameterize the constraint and optimize the loss function jointly (Jang al. 2016). After training, predict multiple solutions and select the best one.
where the constraint Σi=
GAN: The generator R + R" is to transform a simple prior distribution to a complex target distribution, and the discriminator G Rd+= + (0, is to judge the quality of generated samples. The loss is defined as:
min max ((c.)))pa(x..) log (1x, c)] + Ne.e~ D(G(2, G
(44)
After training, we sample from the latent distribution 2 NN( feed them into the generator as G(2,c), c), and select the best solution.
Diffusion: we adopt the denoising diffusion implicit model (DDIM) with default parameter settings in (Song et al. 2020a; Sun & Yang 2024).
RectFlow: we adopted the rectified flow model as introduced in Sec.
For the Hindsight and Cluster approaches, we have chosen four predictors, which are implemented via a multi-head prediction mechanism the final layer, grounded on common embedding layers. For those generative approaches, including GAN, Diffusion, and RectFlow, we have employed the sumpling-then-selee
strategy to enhance solution quality. Specifically, we sample 1,000 initial points and generate candidate solutions simultancously in batch. For the Diffusion and RectFlow model, we have set the discretization steps to 10.
C.2 EXPERIMENT SETTINGS FOR TOY EXAMPLE
We consider the following multi-valued mapping:
F(c) (3c² 0.5, -3e² 0.5, c+ -ct -c
(45)
We then sample a dataset, sampled from [-1, 1] and the solution is randomly returned by one of the six mappings in F(c). After training, we sample input parameters from the testing dataset, feed them into the trained models, and visualize generated solutions.
{a, x, } using F(c), where the input parameter e is uniformly
For the RectFlow model, the ap-approxddated vector field under different input parameters is shown in Fig.
Initial
Evolution
Iritial
Evolution
Sandto Wetabbe 60
Sandor
1.00
1,00
81
Deraty
Time
Denstyy
Densty
Time
Donsity
Donsty
Time (t)
Dersty
Figure 4: Probability flow of NN approximated RectFlow under 0 (left), c 0.5 (center), and c = 1 (right), respectively.
18

---

Published as a conference paper at ICLR 2024
C.3 EXPERIMENT SETTINGS FOR CONTINUOUS NON-CONVEX PROBLEMS
We focus two challenging, continuous non-convex optimization problems:
(i) Inverse Kinematics Problem: in real-time control of robotic arms, given target position, the system must solve for the robotic configuration, which includes determining the angles for each joint. This process involves solving a system non-linear equations, a task that notoriously complex due to its non-convex nature. The inverse kinematics problem is fundamental challenge in robotic control, primarily because a single target position can correspond to multiple feasible configurations. This multiplicity adds complexity to existing NN-based methods.
Specifically, consider a robot arm with K degrees of freedom (DOF), where the length of arms is denoted as L...... Lk] given a target position (x, y) E R2, the optimal angles a E IR for joints is solved by the following non-convex optimization problems:
min a
f(a)
(46)
s.t.
Σ
Li cos
a2)
(47)
i=1
j=1
k
Σ
Li sin
=
(48)
i=1
==1
Onin
S
Omax
(49)
(ii) Wireless Power Control: in wireless networks, power control is critical issue. The task is to optimize the transmitter power levels in order to maximize network capacity while minimizing energy consumption. The problem is non-convex due the interaction between the transmitted power and the resulting interference levels. It also admits multiple optimal solutions given the same input, making it challenging task for existing NN-based methods.
Specifically, consider a network consisting of K single-antenns transceiver pairs. Denote the K x K channel condition matrix by h, where h4 is the direct channel between the i-th transmitter and i-th receiver, and hij is the interference channel from the i-th transmitter to the j-th receiver. Let a; denote the noise power at the i-th receiver. The optimal power level E IR K is solved by the following non-convex optimization:
K Σ log 1+
105 Pi
max PERA
(50)
Ejjt
Pj + o?
2m1
p
Sp S max
(51)
In both cases, our goal is to leverage the generative learning framework to tackle these complex, non-convex optimization problems that require real-time solutions and can have multiple optimal solutions for the same input. We use similar experimental settings as outlined in (Ardizzone al. 2018) and (Sun et al. 2017) to gather datasets for the inverse kinematics problem and wireless power control, respectively. We collected 10,000 training instances and conducted tests on an additional 1,024 instances.
The performance metrics we use include the error for the inverse kinematies problems, which evaluates the Euclidean distance between the target position and the position achieved using the predicted configuration. For the wireless power control problem, we measure the optimality gap, comparing it with the target objective value ascertained by the iterative algorithm. For assessing speedup, we chose different iterative algorithms as baselines. Specifically, we used the cross-entropy methods (De Boer et al. 2005) the iterative solver to derive the optimal solutions for the inverse kinematics problem. For the wireless power control problem, we employed the block gradient descent (Sun al. 2017) the iterative solver to obtain (locally) optimal solutions.
19

---

Published as a conference paper at ICLR 2024
C.4 EXPERIMENT SETTINGS FOR COMBINATORIAL PROBLEMS
In our study, we address three combinatorial problems over a graph, denoted as - - (V, E), wherein V embodies the of nodes, and E signifies the of edges. The associated complementary graph is represented as G = (V, E).
The three combinatorial problems are defined as follows:
Maximum clique:
max 2 LEV
Σ Ti.
(52)
S.L. 2i + Jj S v(i.)) E
2 {0, ViEV
Maximum independent set:
max Σ 36
(53)
SEV
s.t. n. Jjj S v(i,)) EE
3y {0, 11, ViEV
Maximum cut:
max Σ
IJJ
(54)
2
(U))E
s.t. D E [-1,1), Viev
For data collection, we sampled Erdos Erdos-Rényí random graphs (Erdós et al. 1960) as the instance dataset. For graphs with fewer than 100 nodes, we used the Gurobi solver to procure globally optimal solutions. For larger graphs, relied on NetworkX heuristics to identify locally optimal solutions. Our dataset comprised of 10,000 training instances, and we conducted tests on an additional 1,024 instances. The performance metrics included the optimality gap and speedup relative to iterative solver.
In terms of Neural Network (NN)-based methods, we employed Transformer encoder handle the varied graph inputs (Kool et al., 2018). Given the optimal solution involves binary variables with additional constraints, used greedy decoding strategy to convert the generated continuous solutions back into discrete feasible ones (Sun & Yang 2024).
C.5 ABLATION STUDY FOR GENERATIVE LEANRING
In this section, we evaluate our generative framework under different parameter settings, specifically varying the number of sampled solutions m E {1, 10, 100, 200, 500, 800, 1000} and discretization steps (1, 10, 100, 200, 500, 800, 1000).
Average constraint violation
Constrain violation under different sampling number
230
discretication
Number of sampled solution
10 discretization sipe
1.5
discretization
200 discretization stoe
discretization
800 discretization stoe
200
Iwerage con91A
1000 discretization
0.00
3.0
3.55
0654
0662
10
100
200
500
800
1000
Number
discretization step
Number sampled solution
Figure 5: Performance comparison on the solution quality for inverse kinematics problem.
We perform this performance comparison using the inverse kinematics problem (d 2, 4). Our evaluation metrics include average constraint violation and average inference time, as depicted in Figures 5 and 6 Our observations as follows:
20

---

Published as a conference paper at ICLR 2024
Average inference
Inference time under different discretization step
sampled salutions
Number of sampled solution
10 sampled solutions
30
sampled solutions
200 sampled soluuions
1000
Average inference
500 samoled solutions
800 sampled solutions
200
1000 sampled solutions
500
82
1000 800
81
20
500 Number discretization step
600
Number discretization step
Figure 6: Performance comparison on the inference time for inverse kinematics problem.
we notice that the number of sampled solutions significantly impacts solution quality compared to the number of discretization steps. Second, when considering runtime complexity, as gauged by inference time (Figure 6), we find that it scales linearly with the number of discretization steps. However, is sensitive to the increasing number of samples. This behavior is due to the use of batch computation.
First, regarding solution quality, as measured by constraint violation (Figure 5),
Consequently, our performance comparison only supports the assertions made in Theorem I but also provides insights for parameter tuning, thereby enabling the generation of better solutions.
21


Reviews:
[{"review_id": "OHP1eFM6rf", "reviewer": "Reviewer_GsRT", "summary": "The authors present a generative learning framework for the map between input and solutions for non-convex multi-input optimization problems, which has a wide range of applications in science and engineering. This framework leverages a generative model to learn the \nmapping from input to a solution of distributions.  A benefit of this framework is when we sample from the input-dependent solution distribution the corresponding sample with the highest probability should correspond to a feasible solution. Lastly, the authors theoretically characterize optimally the characterized solution and empirically show RectFlow outperforms other generative models in solving this task.", "questions": "1). What are the benefits of using a generative framework to solve these types of optimization problems?\n\n2). Could the authors provide a framework for practitioners on how to adopt this methodology? What requirements are needed?\n\n3). Could the authors provide the probabilities of the samples in Figure 3?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The strengths of the paper are:\n* Finding a novel application for the RectFlow model.\n* Theoretical contribution- Providing a statement about the optimally gap decreasing as the number samples increase from the learned distribution.\n* Solving an important problem that has a lot applications in engineering and science domains. \n* The experiments that were provided have strong empirical evidence the proposed method is better than other generative models and baselines.", "weaknesses": "The paper could improve improve in the following ways: \n* The motivation of the problem formulation could be more clear because there is a lack of context on the benefits of solving the problem in a generative framework. It is unclear why the authors chose to solve these particular types of non-convex problems with a generative model and why practitioners should adopt this framework.\n* The experimental section lacks plethora of empirical evidence, the proposed method is demonstrated on two toy problems. There is no evidence provided the proposed method would help you solve a particular engineering problem and perform better than current methodologies. \n     * Mirror weakness- Figure 3 would be more clear if colors associated with the samples of the probability were given as heat map.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S4Z0KZN9sw", "reviewer": "Reviewer_rFky", "summary": "The rectflow model is applied to approximate the one-to-many solution mapping function in this paper. Given the Boltzmann distribution assumpation, this work transforms RectFlow model (Liu et al., 2022) to solve (potentially) nonconvex optimization problems. The experiments showcase RectFlow is better than some other generative models rather than state-of-the-art models for each nonconvex problems.", "questions": "1. Can the authors clarify the constraints of the problems used in experiments?\n2. The authors claim nonconvex leads to more multiple-valued input solution associations. But convex problems like multi-solution TSP may also have many one-to-many mappinps. Is there any explainations on this viewpoint?\n3. The authors claim \"existing studies endeavor to identify a single possible mapping from the potential multiples\". It is not totally correct as considerable research focuses on estimating solution distributions given instances and many diversity techniques are adopted to encourage models finding more near-optimal solutions. \n4. Despite the analysis of complexity, did authors try to solve large or complex problems? Any empirical insights on performance of the method in problem scales and constraint handling?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Solution generation is well motivated in the paper and the background is clearly written. Despite the straightforward application of RectFlow, the effect of the method is manifested in experiments by evaluating on simple optimization problems. The optimality loss and runtime complexity analyzed to show the efficiency.", "weaknesses": "1) Experiments are too simple and only easy problems are tested. The first simple function estimation with a limited feasible interval is oversimplified. The second combinatorial optimization experiment uses three relatively simple problems that have simple constraints. In this sense, the constraint handling power and the mapping power under complex scenarios are not showcased. More complex problems with multiple constraints can be added to enhance the experimental part.\n2) Many generative models are designed for optimization problems. Despite the comparison with basic generative models, the generative models for optimization problems should be compared. A lot of them learn solution distributions rather than single-valued mappings, which share the same motivation in this paper. I believe they can be easily used in the tested problems in this paper. Please refer to A GNN-guided predict-and-search framework for mixed-integer linear programming, DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization, SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems\n3) The method is too straightforward by applying RectFlow, lowering the novelty of this work. Although the complexity is analyzed, the empirical results do not support the theory that the method is able to solve complex problems with multiple constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ghap89un0L", "reviewer": "Reviewer_ibgc", "summary": "This paper presents a learning-based method to compute solutions for multi-valued non-convex optimization problems. The method is based on RectFlow method.", "questions": "1. Section 4.3, it is understandable that there are issues in forward ODE solve. The authors pointed out a few possible solutions. Are these methods used to generate the results reported in section 6? \n\n2. I would like to see expanded text of Section 4.3, and some ablation study if there are multiple solutions. \n\n3. Section 6.2, Table 3, what are the `speedup` column compared against?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The proposed method addressed an important optimization problem. The concept of instead of learning input-output mapping, training a model to learn input-output-distribution is a novel concept. The authors provided concrete theoretical framework, and reasonable amount of empirical evidence to support the claims. The writing of the manuscript is clear and easy to understand.", "weaknesses": "The sampling portion of the manuscript can be further improved. The authors imply that due to the inexact approximation of NN vector field, and the discretization error when solving the forward solution of the ODE, the final results may not be as optimal as theoretically shown. This is fully understandable, however I would expect the authors to provide a more clear explanation, and also provide empirical solutions to address them. In the current version, the authors seem only point out to possible solutions.\n\nSecondly, the explanation of the experimental results needs to be clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QJldPyJcas", "reviewer": "Reviewer_85JM", "summary": "This paper considers the problem of learning neural approximations of multi-valued input solution mappings arising from solutions of non-convex optimization problems. Previous work on learning single-valued mappings struggled to approximate such multi-valued mappings, compromising between poor optimality performance and high computational complexity. This paper proposes a generative approach based on rectified flows, which is inspired by the recent successes of generative models for modeling complex multi-modal distributions. \n\nThe authors propose to process multiple samples in parallel, project them onto the feasible region, and keep only the best one, leading to high quality feasible samples.\nThis is also quantified in a theorem, which gives an upper bound on the probability of selecting a sample that has optimality gap larger than $\\delta$, elucidating the dependence of sample quality on the dataset quality, the approximation error of the learned vector field, the number of ODE discretization steps and the number of samples. Additionally the runtime complexity is characterized, giving insights into the tradeoff between increasing the number of samples and increasing the number of ODE discretization steps.\nExperimentally, the proposed approach is compared to various baseline on a synthetic multi-valued dataset and three graph-based combinatorial optimization problems. The proposed approach is shown to strongly outperform previous neural-network based approaches in terms of optimality gap while preserving a strong speedup in runtime.", "questions": "- The paragraph after equation 27, in particular how equation 28 follows, was unclear to me.\n- In the proof of the theorem, some Lipschitz assumptions are made. It would be good to make these explicit in the theorem statement, in which they are currently not mentioned.\n- The step from equation 31 to equation 32 could be explained in a bit more detail.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I really enjoyed reading this paper. It is built on a great idea of applying the recently popular diffusion-based models to learning solutions of optimization problems. The method and results are presented with great clarity, and the text reads very well overall. The quality of the paper is high, with interesting theoretical insights that have useful implications, as well as convincing experiments.\nI believe this paper makes a very significant contribution, and I agree with the authors that it could pave the way for future research in learning multi-valued solution mappings of optimization problems.", "weaknesses": "- Some parts of the proof of the theorem are a bit unclear, see questions.\n- The paper could have benefitet from more diversity in the experiments, e.g. including one of the motivating applied examples from the introduction could have made the paper even more of a slam dunk (e.g. AC optimal power flow problems in real-time power grid operations, semi-definite programming-based real-time scheduling, coding operations in modern wireless communication systems). However, I believe the given experimental evidence still makes it a good paper and I believe is sufficient for acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)