Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
Authors: Shinsaku Sakaue
Taihei Oki
Venue: NeurIPS 2024 poster (2024)
Keywords: data-driven algorithm design
linear programming
dimensionality reduction
generalization bound
Primary area: learning_theory
TL;DR: We present a generalization bound and learning methods for reducing the dimensionality of linear programs with projection matrices learned from data.

Abstract: How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question.
Recently, there has been a surge of interest in reducing LP sizes using *random projections*, which can accelerate solving LPs independently of improving LP solvers. 
This paper explores a new direction of *data-driven projections*, which use projection matrices learned from data instead of random projection matrices.
Given training data of $n$-dimensional LPs, we learn an $n\times k$ projection matrix with $n > k$. 
When addressing a future LP instance, we reduce its dimensionality from $n$ to $k$ via the learned projection matrix, solve the resulting LP to obtain a $k$-dimensional solution, and apply the learned matrix to it to recover an $n$-dimensional solution.

On the theoretical side, a natural question is: how much data is sufficient to ensure the quality of recovered solutions? We address this question based on the framework of *data-driven algorithm design*, which connects the amount of data sufficient for establishing generalization bounds to the *pseudo-dimension* of performance metrics. We obtain an $\tilde{\mathrm{O}}(nk^2)$ upper bound on the pseudo-dimension, where $\tilde{\mathrm{O}}$ compresses logarithmic factors. We also provide an $\Omega(nk)$ lower bound, implying our result is tight up to an $\tilde{\mathrm{O}}(k)$ factor. 

On the practical side, we explore two simple methods for learning projection matrices: PCA- and gradient-based methods. While the former is relatively efficient, the latter can sometimes achieve better solution quality. Experiments demonstrate that learning projection matrices from data is indeed beneficial: it leads to significantly higher solution quality than the existing random projection while greatly reducing the time for solving LPs.

Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
Shinsaku Sakaue
Taihei Oki
The University of Tokyo and RIKEN AIP Tokyo, Japan
Hokkaido University Hokkaido, Japan oki@icrede hokudai......................... ac. jp
sakaueSmist. stt.aueeemmtt......oooo....o.. jc.jp
Abstract
How to solve high-dimenn nigh-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been surge of interest reducing LP sizes using random projections, which can accelerate solving LPs independently of improving LP solvers. This paper explores a new direction of data- projections, which use projection matrices learned from data instead of random projection matrices. Given training data of n--dimensional LPs, we learn an n k projection matrix with >> k. When addressing future LP instance, we reduce its dimensionality from n to it via the learned projection matrix, solve the resulting IPP to obtain a k- dimensional solution, and apply the learned matrix to it to recover an n--dimensional solution. On the theoretical side, a natural question how much data is sufficient ensure the quality of recovered solutions? We address this question based on the framework of data-driven algorithm design, which connects the amount data sufficient for establishing generalization bounds to the pseudo-dimension of performance metrics. We obtain an ( upper bound the secudo-iiennsoon where Ô compresses logarithmic factors. We also provide Q(nk) lower bound, implying result tight up Ö(k) factor. On the practical side, explore two simple methods for learning projection matrices: PCA- and gradient-bant based methods. While the former relatively efficient, the latter can sometimes achieve better solution quality. Experiments demonstrate that learning projection matrices from data is indeed beneficial: leads to significantly higher solution quality than the existing random projection while greatly reducing the time for solving LPs.
Introduction
Linear programming (LP) has been one of the most fundamental tools used in various industrial domains [23, 18], and how to address nigh-dimensional LPss efficiently has been major research subject in operations research. To date, researchers have developed various fast LP solvers, most of which stem from the simplex or interior-point method. Recent advances include a parallelized simplex method [27] and randomized interior-point method [16]. Besides the improvements in LP solvers, there has been growing interest in reducing LP sizes via random projections [44, 37, 2], motivated by the success of random sketching in numerical linear algebra [48]. Such a projection-bas based approach solver-agnostic in that it can work with any solvers, including the aforementioned recent solvers, for solving reduced-size LPs. This solver-agnostic nature is beneficial, especially considering that LP solvers have evolved in distinct directions of simplex and interior-poin methods.
In the context of numerical linear algebra, there has been notable shift towards learning sketching matrices from data, instead of using random matrices [28, 29, 12, 33, 40]. This data-driven approach effective when we frequently address similar instances. The line of previous research has demonstrated that learned sketching matrices can greatly improve the performance of sketching-bar methods.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1
Our contribution
Drawing inspiration from this background, we study a data-driven projection approach for accelerat- ing repetitive solving of similar LP instances, which often arise in practice [21] (see also Remark 3.2). Our approach inherits the solver-agnostic nature of random projections for LPs, and it can improve solution quality by learning projection matrices from past LP instances. Our contribution is a cohesive study of this data-driven approach to LPs from both theoretical and practical perspectives, as follows.
Generalization bound. We first formulate the task of learning projection matrices as a statistical learning problem and study the generalization bound. Specifically, we analyze the number of LP- instance samples sufficient for bounding the gap between the empirical and expected objective values attained by the data-driven projection approach. Such generalization bound is known to depend on the dreuddddimension of the class of performance metrics. We prove an Ö(nk²) upper bound on the pseudo- ggeudo-dimension (Theorem 4.4), where n and k are the original and reduced dimensionalities, respectively, and Ô compresses logarithmic factors. A main technical non-triviality lies in Lemma 4.3, which elucidates piecewise polynomial structure of the optimal value of LPs function of input parameters. Besides playing key role in proving Theorem 4.4, Lemma 4.3 offers general insight into the optimal value of LPs, which could have broader implications. We also give an (2(kk) lower bound on the eseudo-dimension (Theorem 4.5). As experiments demonstrate later, we can get high-quality solutions with k much smaller than n, suggesting our result, with only an (() gap, is nearly tight.
Learning methods. We then explore how learn projection matrices in Section 5. We consider two simple learning methods based on principal component analysis (PCA) and gradient updates. The former efficiently constructs a projection matrix by extracting the top-k subspace around which optimal solutions of future instances are expected to appear. The latter, although more costly, directly improves the optimal value of LPs via gradient ascent. In Section 6, experiments on various datasets confirm that projection matrices learned by the PCA- and gradient-basee methods can lead to much higher solution quality than random projection [2]. while greatly reducing the time for solving LPs.
1.2 Related work
Random projections for LPs. Vu et al. [44] introduced a random-projection method to reduce the number of equality constraints, and Poirion et al. [37] extended it to inequality constraints. As discussed therein, reducing the number of inequality constraints of LPs corresponds to reducing the dimensionality (the number of variables) of dual LPs.. Recently, Akchen and Mišić [2] developed a column-randomized method for reducing the dimensionality of LPs. While these studies provide high probability guarantees, we foeus on data-driven projections and discuss generalization bounds.
Data-driven algorithm design. Data-driven algorithm design [7], initiated by Gupta and Rough- garden [25], has served foundational framework for analyzing generalization bounds of various data-driven algorithms [8, 10, 11, 12, 39, 9]. Our statistical learning formulation in Section 3 and a general proof idea in Section 4 are based on it. Among the line of studies, the analysis technique for data-driven integer- proerraporgamnnnggg (IP) methods [10, 11] is close to ours. The difference is that while their technique is intended for analyzing IP methods (particularly, branch-and-cut methods), we focus on LPs and discuss a general property of the optimal value viewed as a function of input parameters. Thus, our analysis is independent of solution methods, unlike the previous studies. This aspect is crucial for analyzing our solver-agnostic approach. Some studies have also combined LP/IP methods with machine learning [14, 21, 41], while learning of projection matrices has yet to be studied.
Learning through optimization. Our work is also related to the broad stream of research on learning through optimization procedures [4, 47, 1, 13, 42, 36, 3, 20, 45, 19], which we discuss in Appendix A.
Notation. For a positive integer n, let I, and O, be the n identity matrix and the n-dimensional all-zero vector, respectively, where we omit the subscript when it is clear from the context. For two matrices A and B with the same number of rows (columns), [A, B) ((A: B)) denotes the matrix obtained by horizontally (vertically) concatenating A and B.
2 Reducing dimensionality of LPs via projection
We overview the projection-based approach for reducing the dimensionality of LPs [37, 2]. For ease of dealing with fcasibility issues, focus on the following inequality- -fomm LP with input parameters

---

E IR", A E R and b E R.:
maximize c. subject to Ax S
(I)
When n is large, restricting variables to a low-dimensional subspace can be helpful for computing an approximate solution to (1) quickly. Specifically, given projection matrix P E B with n > k. we consider solving the following projected LP, instead of (1):
maximiZeyER* C Py subject to APy S b.
(2)
Once we get an optimal solution y" to the projected LP (2). can recover n-dimensional solution, = py", to the original LP (1). Note that the recovered solution always feasible for (1), although not always optimal. We measure the solution quality with the objective value e. a c Py". Ideally, P's columns span a linear subspace that contains an optimal solution to (I), the recovered solution E Py" is optimal to (1) due to the optimality of y to (2). Therefore. if we find such good P close to being ideal with small k; we can efficiently obtain a high-quality solution क = Py to (1) by solving the smaller projected LP (2).
Remark 2.1 -Seeiff- aspects). As mentioned in Section 1, this projection-basee based approach is solver-agnostic in that we can apply any LP solver to projected LPs (2). To preserve this nature, we focus on designing projection matrices and do not delve into solver-specific discussions. Experiments in Section 6 will use Gurobi as fixed LP solver, which is standard choice. Strietly speaking, pro- jections alter the sparsity and numerical stability of projected LPs, which can affect the performance of solvers. This point can be important, especially when original LPs are sparse and solvers exploit the sparsity. Investigating how to take such solver-specific aspects into account is left for future work.
3 Data-driven projection
While the previous studies [44, 37, 2] have reduced LP sizes via random projections, we may be able to improve solution quality by learning projection matrices from data. We formalize this idea as statistical learning problem. Let II denote the set of all possible LP instances and D an unknown distribution on II. Given LP instances sampled from D. our goal is to learn P that maximizes the expected optimal value of projected LPs over D. Below, we assume the following three conditions. Assumption 3.1. (i) Every
II takes the inequality form (1), (ii) x O,, is feasible for all E II, and (iii) optimal values of all instances in II are upper bounded by a finite constant H > O.
Although Assumption 3.1 narrows the class of LPs we can handle, it is not as restrictive as it seems. Suppose for example that LP instances in II have identical equality constraints. While such LPs in their current form do not satisfy (i), we can convert them into the inequality form (I) by considering the null space of the equality constraints (see Appendix for details), hence satisfying (i). This conversion is useful for dealing with LPs of maximum-fio and minimum-come coonuum-cost-foooo floww problems a fixed graph topology, where we can remove the flow-conservation equality constraints by considering the null space of the incidence matrix of the graph. Regarding condition (ii), we may instead assume that there exists an arbitrary common feasible solution Vn without loss of generality. This because we can translate the feasible region so that an coincides with the origin O,, Condition (ii) also implies that for any P E R projected IPs are feasible (i.e., their feasible regions are non-empty) since y= is always feasible for any projected LPs. Condition (iii) is satisfied simply by focusing on bounded LPs (i.c., LPs with finite optimal values) and setting H to the largest possible optimal value. Conditions (ii) and (iii) also ensure that the optimal value of projected LPs always lies in [0, H], which is used to derive a generalization bound in Section 4. In Section 6, we see that many problems, including packing and network flow problems, can be written LPs satisfying Assumption 3.1.
Due to condition (i), we can identify each LP instance π II with its input parameters (c, A, b) in (1), i.e., (c. A, b). For an I.P instance и E TT and projection matrix P E RRn we define u( (P, T) max( c Py APy S b}
as the optimal value of the projected LP. Our goal is to learn P E Ra*k from LP instances sampled from D to maximize the expected optimal value on future instances, i.c., Ex<D|u (P.))
Remark 3.2 (Validity of the setting). The above statistical learning setting regarding LP instances is not an artifact. As Fan et al. [21] discussed, LPs often serve as descriptive models, and each instance can be viewed as realization of input parameters following some distribution. Such scenario arises in, for example, daily production planning and flight scheduling. Note that the statistical learning setting is also widely used as foundational framework in data-driven algorithm design [25, 8, 12, 9].
3

---

4 Generalization bound
This section studies the generalization bound, namely, how many samples from D are sufficient for guaranteeing that the expected optimal value, En-Dlu, [u[(u[( P. r)}, of learned P is close to the empirical optimal value on sampled instances. First, let us overview the basics of learning theory. Let u S " be a class of functions, where each E U takes some input π E II and returns a real value. We use the following pseudo-diments
[38] to measure the complexity of class of real-valued functions.
Definition 4.1. Let N be positive integer. We say U C R!'l shatters an input set, {T TT S II, if there exist threshold values, fI..... ty E R. such that each of all the 2d outcomes of
{ [((T.) 2 t; : i I...................... N } realized by some u E U. The pseudo pseudo-dimense dimension of U, denoted by pdim(24) the maximum size of an input set that Ul can shatter.
In our case, the set V consists of functions uP.:)): :T] - matrices P E = Each -(P.-) E 24 takes an LP instance
+ IR defined in (3), for all possible projection
(c, A. b) E as input and returns the optimal value of the projected LP. Assumption 3.1 ensures that the range of un (P..) is bounded by [0, H] for all P E 1Rn* Thus, the well-known uniform convergence result (see, e.g., Anthony and Bartlett [5, Theorem 19.2] and Balcan [7. Theorem 29.2]) implies that for any distribution D on II, e >> O, and 5 E (0, 1). if N = {{(H/))² (pdinm(() + log (1/()))) instances drawn i.i.d. from D
are given, with probability at least 1 - 6, for all P E Rank it holds that
N E. u(P, m:) - ENND (u( P. ] S.
That is, if a projection matrix P produces high-quality solutions on N x (H/a)² pdim(U() instances sampled i.idd from D, it likely yields high-quality solutions on future instances from D as well. Thus, analyzing pdim((() of 21 = =( P. : R P E Rn*k) } reveals the sufficient sample size.
Remark 4.2 (Importance of uniform convergence). While the above generalization bound is not the sole focus of learning theory, it is particularly valuable data-driven algorithm design, as is also discussed in the literature [8, 10]. Note that (4) holds uniformly for all P E R offering performance guarantees regardless of how P is learned. Thus, we may select learning methods based on their empirical performance. This is helpful since there are gold-standard methods for learning parameters of algorithms; we discuss learning methods for our case in Section 5. This situation differs from the standard supervised learning setting, where we minimize common losses, e.g., squared and logistic. Additionally, the uniform bound ensures that learned P does not overfit sampled instances.
4.1 Upper bound on p2im((()
Building upon the above learning theory background, crucial factor for establishing the generaliza- tion bound is pdim(Zf). To upper bound this, we give a structural observation of the optimal value of LPs (Lemma 4.3) and combine it with a general proof idea in data-driven algorithm design [25, 7J.
We first overview the general proof idea. Suppose that we have an upper bound on the number of outcomes of { uu(2 x.)) 2 t; : : 1...... .N that grows more slowly than 2 Since shattering N instances requires 2 outcomes, the largest N, such that the upper bound is at least 2 serves as an up- per bound on pdim (24) (intuitively, pdim (14) S log2(""pppe bound on the number of outcomes")). Below, we discuss bounding the number of outcomes, which is the most technically important step.
To examine the number of possible outcomes, we consider a fundamental question related to sensitivity analysis of LPs: how does the optimal value of an LP behave when input parameters change?! In our case, a projected LP has input parameters (P* c, AP, b) E R& x m x IR"", where P c and AP change with P E IR x Thus, addressing this question offers insight into the number of outcomes. Lemma 4.3 provides answer for more general setting, which might find other applications beyond our case since learning through LPs is not limited to the projection-base -based approach [47, 13, 42, 20].
Lemma 4.3. Let t E R. be threshold value. Consider an LP न = (c, A, R mm x R such that each entry of ē, Å, and b is polynomial of degree most d in v real variables, O E R
While similar question is studied Balcan et al. [11, Theorem 3.1], their result focuses on the case where new constraints are added to LPs to analyze branch-and-cu methods, unlike our Lemma 4.3, In our case, we need to care about rank deficient input matrices, which we circumvent via the reformulation given at the beginning of the proof of Lemma 4.3.

---

Assume that गे is bounded and feasible for every 0 E R". Then, there are up to ( (m + 2k + 2) polynomials of degree at most (2k + 1)d in whose sign patterns (< 0, = 0. or > 0) partition R into some regions, and whether max č Ay S b) 2 t or not is identical within each region.
Proof. First, we rewrite the LP = (2. b) as an equivalent 2k-dimensional LP with non-negativity constraints: max T (y+ y- Ayy+-y>> b, [u:::= 0). The resulting constraint matrix, A' = [Á. A: ]. has full column rank, which simplifies the subsequent discussion. Note that the maximum degree of input parameters remains at most d, while the sizes, m and k, increase m' == m + 2k and K' == 2k, respectively. Below, we focus on the reformulated LP (c', A',' E IK x R'''' Rm' where c' == (c: -cj. b' == [6; 02s] and A' has full column rank.
We consider determining max c y: A'y S 2 t or not by checking all vertices of the feasible region. For any size-k' subset, 1 C (1,..., m'), ) of row indices of A' R xk', let A', denote the k' x k submmtrix of A' with rows restricted For every subset / with del A', * 0, let yr == b', Since the LP bounded and feasible, and A' has full column rank, there is a vertex optimal solution written as yr = A'r ' for some (see the proof of Korte and Vygen [31, Proposition 3.1]). Thus, the optimal value is at least t if and only there exists at least one size-k' subset / with det A', + O, A'y, S b', and c' y: 2 t.
and b' RR the corresponding subvector of b'.
Based on the above observation, we identify polynomials whose sign patterns determine max c' A'y S. b') > t or not. For any subset I, if det A', # O, Cramer's rule implies that yr A'i -'', is written as f0) det A', I. where fr (0) is some k'-valued polynomial vector of 0 with degrees at most k'd. Thus, we can check y'yr= S D' and c yr 2 t by examining sign patterns of m + 1 polynomials, A' fr (0) (det A'r)b and c ((0)-Ldel A'r, whose degrees are at most (k' + 1)d. Considering all the (m'') choices of I, there are (m-) (m' + 2) polynomials of the form det A',, (0) (det A', 1) and c' f:(0) - det A', with degrees at most (k' + +1d such that their sign patterns partition RR." into some regions, and max c' y A'y S b') } 2 or not identical within each region. Substituting m + 2k and 2k into m² and k', respectively, completes the proof.
L
Lemma 4.3 states that the outcome of whether u (PP π) = max( c' Py APy S b) exceeds or not is determined by sign patterns of polynomials of P. and upper bound on the sign patterns of polynomials is known as Warren's theorem [46]. as detailed shortly. Combining them with the aforementioned general idea yields the following upper bound on pdim(lf).
Theorem 4.4. pllm(l)) = Onn?² mk)..
Proof. Let (T, E II x R be a pair of an LP instance and a threshold value. Setting 0 and = 1 in Lemma 4.3, we have up to (m)+ (m + 2k: + 2) polynomials of degree at most 2k + 1 whose sign patterns determine whether u( π) 2 or not. Thus, given N pairs of input instances and threshold values, (Te, / we have up to N x (m-42k)
2k (m + 2k + 2) polynomials whose sign patterns determine u(P, n.)) 2 t, or not for all = L, I,..., i.c., outcomes of N instances.
Warren's 's theorem states that given l polynomials of и variables with degrees at most A, the number of all possible sign patterns is most (Be(A/v) /v)" [46] (see also Goldberg and Jerrum [24, Corollary 2.1 In our case, the number of polynomials is nk variables (P's entries) and degrees at most A = 2k 1. Thus, the number of all possible
x
(m++2))
2k (m + 2k + 2), and each of them has
outcomes is at most 8o.N (0,N(m+20 m++2k) 22+))
(m
nk
2 (Ax) nk poly(m, kim To shatter the set
2k
nk
of N instances, the right-hand side must be at least 2t Taking the base-2 logarithm, it must hold that N N n log, nk Onk?? log mk) S . + O(nk? log mk), where used x logz 1 I 3 for > 0. Therefore, U can shatter O(nk² lkg instances, obtaining the desired bound on p2).
4.2 Lower bound on pdim(l4
We then provide Q(nk) lower bound on p2im((4) to complement the above Ö(nk?) upper bound, implying the tightness up to Ō(k) factor. See Appendix B for the proof. Theorem 4.5. pdim(lf) 2(nk).
5

---

Our proof indeed gives the same lower bound on the y-fat shattering dimension for < 1/2, which implies lower bound of ((nk/E) on N, the sample size needed to guarantee (4) [5. Theorem 19.5]. Thus, in terms of the sample complexity, our result is tight up to an (kk/s) factor. The 1/s gap is inevitable in general [5, Section 19.5], while closing the (Ak) gap is an interesting open problem.
5 Learning methods
We then discuss how to learn projection matrices from training datasets. From the bound (4), given N training LP instances, the expected solution quality on future instances likely remains within the range of t from the empirical one, where R H H/ypdimm pdimm(4)/N & /l/nn/N due to Theorem 4.4, regardless of how we learn projection matrix P. Therefore. in practice, we only need to find an empirically good projection matrix P. which motivates us to explore various ideas for learning P. Below, we discuss two natural ideas: PCA- and gradient-baset based methods.
Remark 5.1 (Training time). We emphasize that learning methods are used only before addressing future LP instances and not once projection matrix P learned. Hence, they can take much longer than the time for solving new LP instances. Similarly. we suppose that optimal solutions to training instances are available, as we can compute them a priori. Note that similar premises are common in most data-driven algorithm research [28, 14, 12, 9, 21, 41]. Considering this, our learning methods are primarily intended for conceptual simplicity, not for efficiency. For completeness, we present the theoretical time complexity and the training time taken in the experiments in Appendix E.
5.1 PCA-based method
As described in Section 2, projection matrix P should preferably have columns that span low- dimensional subspace around which future optimal solutions will appear. Hence, a natural idea is to use PCA to extract such a subspace, regarding optimal solutions to training instances as data points.
Formally, let X R. N x be a matrix whose ith row is an optimal solution the ith training instance. We apply PCA to this X. Specifically, we subtract the mean, o = - X 1v, from each row of X and apply the singular value decomposition (SVD) to X 1 obtaining a decomposition of the form UEV X - l Let V E Rax (I-1) be the submatrix of V whose columns are the top-(As - 1) right-singular vectors of X 1v T. We use
projection matrix. Here, æ is concatenated due to the following consideration: since V, is designed to satisfy
[,, V 1 E "=*
Vi-Y''=X² X I for some Y E I we expect [.. V = X to hold for some Y E R hence P [ Vk-1). This method is not so costly when optimal solutions to training IP instances are given, as it only requires finding the top-(k - 1) right-singular vectors of X - N
5.2 Gradient-based method
While the PCA-based method aims to extract the subspace into which future optimal solutions are likely to fall, it only uses optimal solutions and discards input parameters of LPs. As complementary approach, we provide a gradient-basce method that directly improves the optimal value of LPs.
As warm-up, consider maximizing u( (P,x)) = m c Py : APy S b) of single LP instance (c, A, b) via gradient ascent. Assume that the projected LP satisfies a regularity condition, which requires the existence of an optimal solution y" at which active constraints are linearly independent. Then, u( P, x) is differentiable P and the gradient expressed as follows [42, Theorem 1] (see Appendix D for details of the derivation):
(P,)))=cpp T AA
(5)
where X Rd is dual optimal solution. Thus, we can use the gradient ascent method to maximize u(P R) under the regularity condition. However, this condition sometimes prone be violated, particularly when Slater's 's condition does not hold (i.e., there is no strictly feasible solution). For example, if the original LP has a constraint x 2 O,, and every column of P has opposite-sign entries, it is likely that only y O₂ satisfies Py 2 O, by equality, which is the unique optimal solution but not strictly feasible. In this case, the regularity condition violated since rows of P g Bank are active at Og and linearly dependent due to > k. To alleviate this issue, apply the following

---

Table Sizes of inequality-form LPs, where m (n) represents the number of constraints (variables).
Packing
MaxFlow
MinCostFlow
GROW7
ISRAEL
SC205
SCAGR25
STAIR
m
50
1000
1000
581
316
317
671
696
500
500
500
301
142
203
500
467
projection for 1,...,k A before computing the gradient in (5):
P.j s- arg mingeR- { [| - P.yll : Ax S b),
(6)
where P.j. denotes the jth column of P. This minimally changes each column P.j. to satisfy the original constraints. Consequently, any convex combination of P's columns feasible for the original LP, increasing the chance that there exists a strictly feasible solution in { E R APy S b}. although is not guaranteed. This improves the likelihood that the regularity condition is satisfied.
Given N training instances, ....... NN we repeatedly update P as with SGD: for each TTs we iterate to compute the gradient (5) and update P with it. The projection (6) onto the feasible region of n, comes before computing the gradient for T.. We call this method SGA (stochastic gradient ascent).
5.3 Final projection for feasibility
The previous discussion suggests that making each column of P feasible for training LP instances can increase the likelihood that future LP instances projected by P will have strictly feasible solutions. Considering this, after obtaining projection matrix P with either the PCA- gradient-basse we project each column of P onto the intersection the feasible regions of training LP instances, which we call the final projection. This can be done similarly to (6) replacing the constraints with [A::...; AN S [bi;..:; :b.. bx]. If AI,..., ......,,A AN are identical, we can do it more efficiently by replacing the constraints with A₁æ: min ..... by ). where the minimum is taken element-wise. Note that although the final projection can be costly for large N. we need to do it only once at the end of learning P. This final projection never fails since O, is always feasible in Assumption 3.1.
method,
6 Experiments
We experimentally evaluate the data-driven projection approach. 2 We used MacBook Air with Apple
M2 chip, 24 GB of memory, and macOS Sonoma 14.1. We implemented algorithms in Python 3.9.7
with NumPy 1.23.2. We used Gurobi 10.0.1 [26] for solving LPs and computing projection in (6). We used the following three synthetic and five realistic datasets, each of which consists of 300 LP instances (200 for training and 100 for testing). Table 1 summarizes LP sizes of the eight datasets."
Synthetic datasets. We consider three types of LPs representing packing, maximum flow, and minimum-cost flow problems, denoted by Packing, MaxFlow, and MinCostFlow, respectively. A packing problem is LP with non-negative parameters c, A, and b. We created base instance by drawing their entries from the uniform distribution on [0, 1] and multiplying b by n. We then obtained 300 random instances by multiplying all input parameters by 1 + w, where was drawn from the uniform distribution on [0, 0.1]. To generate MaxFlow and MinCostFlow LPs, we first randomly created a directed graph with 50 vertices and 500 ares and fixed source and sink vertices, denoted by and f, respectively. We confirmed there was an arc from to & to ensure feasibility. We set base are capacities to 1. which we perturbed by multiplying 1 1+ w with w drawn from the uniform distribution on [0, 0.1]. thus obtaining 300 MaxFlow instances. For MinCostFlow, we set supply at and demand to 1. We set base are costs for all ares but (s, t), whose cost was fixed to be large enough, and perturbed them similarly using 1 + w to obtain 300 MinCostFlow instances. We transformed MaxFlow and MinCostFlow instances into equivalent inequality- foom LPs with a method given in Appendix C. which requires (trivially) feasible solution Zn. For MaxFlow, we used on = 0 (i.e., no flow) as trivially feasible solution. For MinCostFlow, we let 2g be all zeros but single at the entry corresponding to (s, f), which is a trivially feasible (but costly) solution.
'Th source code is available at https://githubbb wow/ssaaaue//aataaaaaaaaaaaaaaaa driven- projection -Ip---ppppp- lodcode.
*While Gurobi can solve larger LPs, we used the moderate-sine size LPs as the learning methods could take much longer with the limited computational resources. We admit that larger instances might introduce new challenges. Nevertheless, the trends observed in our experiments offer informative insights for larger scenarios well.
7

---

Realistic datasets. We used five LPs in Netlib [15], GROW7, ISRAEL, SC205, SCAGR25, and STAIR. For each, we generated datasets of 300 random instances. To create realistic datasets, we made them contain 2% of outliers as follows. For normal 98% data points, we perturbed coefficients of objective functions by multiplying 1 0.1w, where w was drawn from the normal distribution; for 2% outliers, we perturbed them by multiplying 1 + w, i.e., 10 times larger noises. Except for ISRAEL, the LPs have equality constraints. We transformed them into inequality-fone LPs as described in Appendix C, using 2o found by the initialization procedure of Gurobi's interior-pois point method."
Methods.
We compared four methods, named Full, ColRand, PCA, and SGA. The first two are baseline methods, while the latter two are our data-driven projection methods. Note that all four methods solved LPs with Gurobi, the state-of oh-the-art commercial solver. The only difference among them lies in how to reduce the dimensionality of LPs, as detailed below.
Full: a baseline method that returns original n-dimensional LPs without reducing the dimensionality.
ColRand: a column-randomizer method based on the work by Akchen and Mišić [2], which reduces the dimensionality by selecting k out of variables randomly and fixing the others to zeros.
PCA: the PCA-based method that reduces the dimensionality with projection matrix P learned as in Section 5.1, followed by the final projection described in Section 5.3.
SGA: the gradient-based method that learns P as deseribed in Section 5.2, followed by the final projection as with PCA. We initialized P with that obtained by PCA and conducted a single epoch of training, setting the learning rate to 0.01.5
For ColRand, PCA, and SGA, we used increasing values of the reduced dimensionality,
LT00 [ _ ... ..... until it reached the maximum value no more than LT i.e. up to 10% of the original dimensionality. PCA and SGA learned projection matrices P from N = 200 training instances, which were then used to reduce the dimensionality of 100 test instances, For ColRand, we tried 10 independent choices of variables and recorded the average and standard deviation.
Results. Figure shows how the solution quality and running time of Gurobi differ among the four methods, where "objective ratio" means the objective value divided by the optimal value computed by Full. For all datasets except STAIR, PCA and/or SGA with the largest k: achieved about 95% to 99% objective ratios, while being about to 70 times faster than Full. Regarding STAIR, PCA and SGA attained 13.1% 16 and 51. 31.2% objective ratios, respectively. By stark contrast, ColRand resulted in objective ratios close to zero in most cases except for Packing and ISRAEL. The results suggest that given informative training datasets, data-driven projection methods can lead to significantly better solutions than the random projection method. Regarding running times, there were differences between PCA/SGA and ColRand, which were probably caused by the numerical property of Gurobi. Nonetheless, all of the three were substantially faster than Full. In summary, the data-driven projection methods achieve high solution quality while greatly reducing the time for solving LPs.
Comparing PCA and SGA, SGA achieved better objectives than PCA in Packing, MaxFlow, Min- CostFlow, and STAIR, while performing similarly in GROW7 and SC205. In ISRAEL and SCAGR25, SGA was worse than PCA, but this is not surprising since optimizing u( (P. x) a non-convex prob- lem. The results suggest that no method could be universally best. Fortunately, the generalization bound (4) justifies selecting a learning method based on empirical performance. Specifically, if we adopt a learning method that produces P with the best empirical performance on N instances at hand, its expected performance on future instances is likely to stay within the range of des of the empirical one, where E S H / /Ddimm2))/N S Hk /n/N since pdim((I) = Ō(nk²) due to Theorem 4.4. If IN is sufficiently large, the high empirical performance is expected to be maintained on future instances.
Additionally, we examined the effect of the noise strength on the performance of PCA and SGA using the synthetic datasets. The details of the experiment and the results are shown in Appendix G. Therein, we found that PCA and SGA were robust against noise on capacities and costs in MaxFlow and Min- CostFlow datasets. This is probably because they can exploit fixed topologies of underlying graphs, even if the capacities and costs are largely perturbed. Fixed graph topologies are common in real- world LPs, such as those appear in transportation planning. Our data-driven projection methods can be effective in such scenarios, particularly if sufficiently large datasets of such LP instances are available.
*We expect this we is (close to) the analytic center, although we could not verify Gurobi's internal processes. 'While we also tried SGA with the random initialization, we found that the "CA-initialization worked better. We present the results with the random initialization in Figure in Appendix F for completeness.
8

---

Full
ColRand
PCA
SGA
Packing
MasFlow
MinCatFFlor
GROWT
Objecive callo
1.0
0.5
0.5
0.0
0.0
20
ISRAEL
SC2S
SCACR2S
STAIR
Objective calup
A
Ruarine of Gatol (8)
Paelding
MaxeFlow
MinCastFlon
GROWT
10
10
10
10-1
10-22
10
10-2
10
A:
Ragtine of Guroka (8)
ISRAAL
10
SC205
SCACR25
STAIR
10-3
10
10
10
10-3
10.0
10-4
10
15
20
40
Figure Plots of objective ratios (upper) and Gurobi's running times (lower, semi-log) for Full, ColRand, PCA, and SGA averaged over 100 test instances. The error band of ColRand indicates the standard deviation over 10 independent trials. The results of Full are shown for every &o for reference, although it always solves n-dimensional LPs and hence is independent of k.
Conclusion
We have studied the data-driven projection approach to LPs. We have established generalization bound by proving an Ö(nk²) upper bound the pseudo-dimension and complemented by an U(nk) lower bound. We have also proposed PCA- and gradient-basee learning methods and experimentally evaluated them. Our theoretical and empirical findings lay the groundwork for the further development of the data-driven approach to LPs and contribute to the broader trend of AI/ML for optimization [43].
8 Limitations and discussions
Our work limited to the statistical learning setting with assumptions on LP instances (see Section and Assumption 3.1). In particular, the current approach cannot deal with equality constraints varying across instances since they usually make LP instances have no common feasible solution. Despite the narrowed applicability, we believe driven projection approach to LPs, as is also discussed Remark 3.2 and the paragraph following Assumption 3. I. Overcoming these limitations will require more involved methods, such training neural networks to extract meaningful oiwddimessional subspaces from non-i.i.d. messy LP instances.
setting is reasonable starting point for developing the data-
Our learning methods are not efficient, and applying them to huge LPs in practice might be challenging. Similar challenges are common in most data-driven algorithm research, as discussed in Remark 5. and we believe our conceptually simple learning methods are helpful for future research. Regarding the data-driven approach to low-rank approximation, Indyk et [29] found that few-shot learning method is uscful for efficiently learning sketching matrices. A key ingredient in their method is

---

surrogate loss, which enjoys a consistency guarantee and whose gradient can be computed efficiently. Empirically, they found that minimizing this loss through only a few iterations of SGD yields good sketching matrix. We expect that similar ideas will be effective for learning projection matrices for I.ss efficiently, while how to design surrogate losses in our setting is left for future work. For the same reason, our experiments are limited to moderate-size LPs, as mentioned in Footnote 3. Nevertheless, the results sufficiently serve as a proof of concept of the data-driven projection approach.
There also exist general limitations of the projection-basd approach [44, 37, 2]. First, it does not consider solver-specific aspects, including numerical stability and sparsity, as discussed in Remark 2.1. Second, the projection-base approach has a limited impact on the theoretical time complexity. The theoretical time complexity of the projection- based approach is dominated by two factors: multiplying P to reduce the dimensionality and solving the projected LP. Recent theoretical studies have revealed that solving an LP takes asymptotically the same computation time as matrix multiplication [17, 30J, suggesting projections may not contribute to improving the total theoretical time complexity. Nevertheless, the projection- based approach leads to dramatic speedups in practice, as in Figure I. Moreover, it can be even faster beyond the theoretical implications when GPUs are available. It is noteworthy that the projection-basee can be highly parallelized. An exciting future direction is to combine recent GPU-implemented LP solvers [6, 34, 35] with projections, which will have vast potential for solving huge LPs efficiently. Exploring data-driven projections for reducing the number of constraints will also be interesting, while this involves addressing the feasibility issue. Poirion et al. [37] used random projections for reducing the number of incquality constraints, which would provide useful insights into this direction.
approach largely benefits from GPUs, as matrix multiplication
Acknowledgements
The authors thank the anonymous reviewers for their valuable comments and suggestions, particularly for inspiring to conduct the experiments in Appendix G. This work was supported by JST ERATO Grant Number JPMJER 1903, JST CREST Grant Number JPMJCR2402, JST FOREST Grant Number JPMJFR232L, and JSPS KAKENHI Grant Numbers J722K17853 and 24K21315.
References
[1] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Advances Neural Information Processing Systems (NeurIPS 2019), volume 32, pages 9562 -9744. Curran Associates, Inc., 2019 (cited on pages 2, 13).
[2] Y.-C. Akchen and V. V. Misić. Column-randomized linear programs: Performance guarantees and applications. Operations Research, 0(0), 2024 (cited on pages 1-3, 8, 10).
[3] B. Amos. Tutorial on amortized optimization. Foundations and Trends@ in Machine Learning, 16(5):1935-822) 8237, 2023 (cited on pages 2, 13).
[4] B. Amos and J. Z. Kolter. OptNet: Differentiable optimization as a layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning (ICML 2017), volume 70, pages 136-145. PMLR, 2017 (cited on pages 2, 13).
[5] M. Anthony and P. I.. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 2009 (cited pages 4, 6).
[6] D. Applegate, M. Diaz, Hinder, Lu, M. Lubin, B. O'Donoghue, and W. Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. In Advances in Neural Information Processing Systems, volume 34, pages 20243-20222 20257. Curran Associates, Inc.. 2021 (cited on page 10).
[7] M.-F Balcan. Data-driven algorithm design. In Beyond the Worst-Case Analysis of Algorithms, pages 626 645. Cambridge University Press, 2021 (cited on pages 2, 4).
[8] M.-F. Balcan, D. DeBlasio, T. Dick, C. Kingsford, T. Sandholm, and E. Vitercik. How much data is sufficient to learn high- performiig algorithms? Generalization guarantees for data- driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pages 9199999999999999 932.992.44 ACM, 2021 (cited on pages 2-4).
[9] M.-F Balcan, Dick, T. Sandholm, and E. Vitercik. Learning to branch: Generalization guarantees and limits of data- inta-inddeendeet discretization. Journal of the ACM, 2023 (cited on pages 2, 3, 6).
10

---

[10] M.-F. Balcan, S. Prasad, T. Sandholm, and E. Vitercik. Improved sample complexity bounds for -en-ch-and-cut. In Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Schloss Dagstuhl Leibniz-7eentrum für Informatik, 2022 (cited on pages 2, 4).
[11] M.-F. Balcan, S. Prasad, T. Sandholm, and E. Vitercik. Structural analysis of branch-and- cut and the learnability of Gomory mixed integer cuts. In Advances in Neural Information Processing Systems (NeurIPS 2022), volume 35, pages 33890-33903. Curran Associates, Inc., 2022 (cited on pages 2, 4).
[12] P. L.. Bartlett, P. Indyk, and T. Wagner. Generalization bounds for data-driven numerical linear algebra. In Proceedings of the 35th Conference on Learning Theory (COLT 2022), volume 178, pages 2013-2040 PMLR, 2022 (cited on pages 1-3, 6).
[13] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differen- tiable pertubed optimizers. In Advances in Neural Information Processing Systems (NeurIPS Curran Associates, Inc., 2020 (cited on pages 2, 4, 13). [14] T. Berthold and G. Hendel. Learning to scale
2020), volume 33, pages
programs. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), volume 35, pages 3661-3668,
2021 (cited on pages 2, 6).
[15] S. Browne, J. Dongarra, E. Grosse, and T. Rowan. The Netlib mathematical software repository. D-lib Magazine, 1995. The dataset used this study is freely available at https://ww..nellib. org/Ip/datal. (cited on page 8).
[16] A. Chowdhury, G. Dexter, P. London, H. Avron, and P. Drineas. Faster randomized interior point methods for tall/wide linear programs. Journal of Machine Learning Research, 23(336):1-
48, 2022 (cited on page 1).
[17] M. B. Cohen, Y. Lee, and 7.. Song. Solving linear programs the current matrix multiplica- tion time. Journal of the ACM, 68(1):1-39, 2021 (cited on page 10).
[18] H. A. Eiselt and C.-L. Sandblom. Linear Programming and its Applications. Springer, 2007
(cited on page 1).
[19] O. El Balghiti, A. N. Elmachtoub, P. Grigas, and A. Tewari. Generalization bounds in the framework, Mathematics of Operations Research, 48(4))2043-2065
predict-then-optmmie
2023 (cited on pages 2, 13).
[20]
A. N. Elmachtoub and P. Grigas. Smart "predict, then optimize". Management Science, 68( (8)19
26, 2022 (cited on pages 2, 4, 13).
[21] Z. Fan, X. Wang, O. Yakovenko, A. A. Sivas, O. Ren, Y. Zhang, and Z. Zhou. Smart initial basis selection for linear programs. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), volume 202, pages 9650-9664. PMLR, 2023 (cited on pages 2, 3, 6).
[22] D. Garber and N. Wolf. Frank-Wolfe with nearest extreme point oracle. In Proceedings of the 34th Conference on Learning Theory (COLT 2021), volume 134, pages 2103-2132. PMLR, 2021 (cited on page 14).
[23] S. I. Gass. Linear Programming: Methods and Applications. McGraw-Hill, 1985 (cited on page 1).
[24] P. W. Goldberg and M. R. Jerrum. Bounding the Chenk--Chervooenkiss dimension of concept classes parameterized by real numbers. Machine Learning, 18(2):131-148, 1995 (cited on page 5).
[25] R. Gupta and T. Roughgarden. A PAC approach to application-specifi algorithm selection. SIAM Journal on Computing, 46(3):992-1017 2017 (cited on pages 2-4). [26] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. https://www.gurbbi.co
2023. Used under academic license. (cited on page 7).
[27] Q. Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method. Matherattial Programming Computation, 10(1): 2018 (cited on page 1). (28) P. Indyk, A. Vakilian, and Y. Yuan. Learning based low-rank approximations. In Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32, pages 7402-7412. Curran Associates, Inc., 2019 (cited on pages 1, 6).
[29] P. Indyk, T. Wagner, and D. Woodruff. Few-shot data-driven algorithms for low rank approxi- mation. In Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, pages 10678- 10990 Curran Associates, Inc., 2021 (cited on pages 1, 9).
11

---

[30] S. Jiang, Z. Song, O. Weinstein, and H. Zhang. A faster algorithm for solving general LPs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pages 823-832. ACM, 2021 (cited on page 10).
[31] B. Korte and J. Vygen. Cobinatorial Optimization: Theory and Algorithams. Springer, 5th edi-
tion, 2012 (cited on page 5).
[32] S. Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank-Wolfe optimization variants. In Advances in Neural Information Processing Systems (NIPS 2015), volume 28, pages 496-504, Curran Associates, Inc., 2015 (cited on page 14).
[33] Y. Li, H. Lin, S. Liu, A. Vakilian, and D. Woodruff. Learning the positions in CountSketch. In International Conference on Learning Representations (ICLR 2023), 2023 (cited on page 1). [34] H. Lu and J. Yang. cuPDLP.jI: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. arXiv:2311.12188 2023 (cited on page 10).
[35] H. Lu, J. Yang, H. Hu, Q. Huangfu, J. Liu, T. Liu, Y. Ye, C. Zhang, and D. Ge. cuPDLP- C: A strengthened implementation of cuPDLP for linear programming by C language. arXiv:2312. /4832, 2023 (cited on page 10).
[36] Z. Meng, L. Mukherjee, Y. Wu, V. Singh, and S. Ravi. Differentiable optimization of general- ized nondecomposable functions using linear programs. In Advances in Neural Information Processing Systems (NeurIPS 202/), volume 34, pages 29129-299 29141. Curran Associates, Inc., 2021 (cited on pages 2, 13).
[37] P.-L. Poirion, F. Lourenço, and A. Takeda. Random projections of linear and semidefinite problems with linear inequalities. Linear Algebra and its Applications, 664:24-60 60, 2023 (cited on pages 1-3, 10).
[38]
D. Pollard. Convergence of Stochastic Processes, Springer, 1st edition, 1984 (cited on page 4).
[39]
S. Sakaue and T. Oki. Sample complexity of learning heuristic functions for greedy-best- first and A search. In Advances in Neural Information Processing Systems (NeurIPS 2022), volume 35, pages 2889-2901. Curran Associates, Inc., 2022 (cited on page 2).
[40] S. Sakaue and T. Oki. Improved generalization bound and learning of sparsity patterns for data-driven low-rank approximation. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023), volume 206, pages 1-10. PMLR, 2023 (cited on page 1).
[41] Y. Sun, A. T. Ernst, X. Li, and J. Weiner. Learning to generate columns with application to vertex coloring. In International Conference on Learning Representations (ICLR 2023), 2023 (cited on pages 2, 6).
[42] Y. Tan, D. Terekhov, and A. Delong. Learning linear programs from optimal decisions. In Advances in Neural Information Processing Systems (NeurIPS 2020), volume 33, pages 19738- 19749. Curran Associates, Inc., 2020 (cited on pages 2, 4, 6, 13, 14).
[43] P. Van Hentenryck and K. Dalmeijer. A14OPT: AI institute for advances in optimization. Al Magazine, 45(1):42 47, 2024 (cited on page 9).
[44] K. Vu, P.-L. Poirion, and L. Liberti. Random projections for linear programming. Mathematics
of Operations Research, 43(4): 105) 1-1071, 2018 (cited on pages 1-3, 10).
[45] K. Wang, B. Wilder, A. Perrault, and M. Tambe. Automatically learning compact quality-aware surrogates for optimization problems. In Advances in Neural Information Processing Systems (NeurIPS 2020), volume 33, pages 9586-9596. Curran Associates, Inc., 2020 (cited on pages 2, 13).
[46] H. E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167-178 1968 (cited on page 5).
[47] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), volume 33, pages 1658-1665, 2019 (cited pages 2, 4,
13).
[48] D. P. Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-17, 2014 (cited on page 1).
12

---

A Additional related work on learning through optimization
Many researchers have addressed learning tasks whose iiput-output pipelines involve optimization steps [4, 47, 1, 13, 42, 36, 3, 20, 45, 19]. While most of them seek to develop practical learning methods, several have studied generalization guarantees. Wang et al. [45] have studied a so-called decision-focused learning method with reparametrization, which is technically the same projection. Their theoretical result focuses on learning of models that generate objective functions, assuming reparametrization matrices to be fixed. By contrast, obtain a generalization bound for learning projection matrices. El Balghiti et al. [19] have studied generalization bounds in the so-called smart ppedict-then-opting setting. While they focus learning of models that generate coefficients of objectives from contextual information as with Wang et al. [45], our interest is in learning projection matrices, which affect both objectives and constraints. On the practical side, the line of work provides useful techniques for differentiating outcomes optimization with respect to input parameters. Our gradient-basee based method for learning projection matrices is partly based the result by Tan et al. [42].
B Proof of the lower bound on (L)
We establish the lower bound on pdim(()) in Theorem 4.5 by constructing set of (n 2 LP instances that U/ can shatter. The instances are written Tr.s (C,, A, b.) IRn 2kxx R2a for 1, ,...., 72 2k and s 1,..., ,,, where
er C O2k
e,
= 2n. n- 2h I2c].
and
b,
02
Here, and e, are the rth and sth standard basis vectors of I= and 12, respectively, and 0,,b is the a x zeros. We consider a projection matrix of the form
Q 1
P
where E (0, (n- is binary matrix that will use as tunable parameters to shatter the set of (n - 2 instances. Let y denote the jth entry of the variable vector E R Since we have
I I
AP-
the constraints, APy S b., imply yj for j 1, 1,...,A , with j * and ys E [0, 1]. Let y be such feasible solution. Then, the objective value written c. Py e, Qy Qr.eWs. where Qr, is the (r, entry Q {0, (= Since Qr. {0, 1} and yE [0. 1]. we have maxf c. Py APy S b, } = Qr.e- Thus, the set of those (n - 2k) instances can be shattered by setting all threshold values to 1/2 and appropriately choosing each entry of Q (0, 1) (n xx)) In other words, all the (nn2kk outcomes of { uuP, xr,a) = Qr. 2 1/2 r 1,...,,.
2k, = 1,..., ....., can (n-(2)))x Thus, obtain 12(kk) lower bound Pe R
realize by changing P E _a (or Q on the pseudo-dimension of = u(P,))
:
C How to remove equality constraints
Suppose that we are given an LP of the form
maximize 2E
subject to Ainq < binqq Aug
boq
which has both inequality and equality constraints. Below, assuming that (trivially) feasible solution 2p is available (i.e., Zg bineq and Auy boy). we transform the LP into equivalent
inequality form. First, we replace the variable vector z with z' + wo obtaining an equivalent LP of the form
maximize 2'
w² TT2' + xo)
subject to Ainon < bineq Aineg Asyz' = 0.
13

---

The equality constraints, Asqz' = O, mean that z' must be in the null space of Aeq. Therefore, z' is always represented as z' (I Acq Aeg) w with some æ IR" where A is the pseudo- inverse of Aeq and - A Aeq is the orthogonal projection matrix onto the null space of Acy. Substituting z' (I Aly into the above LP allows to remove the equality constraints since they are automatically satisfied for every æ. After all, by transforming the variable vector as == (I Asq x + 2o. we can obtain an equivalent LP of the form
maximize #ER
wn' [I Alg Acq
subject to
A Aineg (I
A Acq I binog Ancqq To:
where the additive constant, w T No. in the objective is omitted. This an inequality-form LP (1) with c 4I-4 Acy) " w, A = Ainoq (I Alq Aoy), and b = Dangq Amecy Note that æ = 0 is always feasible for the resulting LP and that we can use this transformation if Aeg and beg are fixed, even if w, Aineq, and bineq can change across instances.
D Derivation of the gradient in SGA
We explain how derive the gradient of ((P, sT) in (5), which indeed follows from Tan et al. [42, Theorem I] (or the implicit function theorem). To focus on computing the gradient, we suppose that the columns of P have already been projected onto the feasible region of by the projection step (6).
Consider computing the gradient Vu(P, π) of u (P, x) max c Py APy S b with respect to P. For convenience, we define new parameters w = P c E² and W = AP E mx and let yy E arg max w y Wy S b). }. Then, we can differentiate the optimal value, u [P x) w Tyy, y",
with respect to w and W by applying the implicit function theorem to the KKT condition. Specifically, du as shown in Tan et al. [42, Theorem 1]. we have due = y" and du aw = x-y y where X E Rg is
the dual optimal solution. From the chain rule, we have
Ou Ser du oW Ow OP aw OP
Vu P. πT)
where the indices for the products are aligned appropriately. By substituting the derivatives into this, we obtain Vu(P, = cy" A X²y When applying the implicit function theorem, we must ensure that the Jacobian matrix is invertible. In the above case, ensuring the regularity condition (i.e., active constraints are linearly independent at y²) is sufficient.
E Running time of learning methods
We discuss the theoretical complexity of the PCA- and SGA- based methods. For convenience, we use Tip (m, n) to represent the time complexity of solving an LP instance with incquality constraints and n variables, as this factor highly depends on problem settings. Also, let (m)))(m) be the time for solving the problem in (6) & times for projecting columns of P E Raxk onto the feasible region specified by inequality constraints. Given the Tip (m, n)-time linear optimization oracle, can implement this projection step with a Frank- Wolfe-style algorithm. In this case, the time for projecting columns of P within an E-error is typically pro (m) (l,,,,n) n.) poly(n, m) (1/))))) [32, 22].
PCA-based method. Computing SVD of X E R xn takes O(Nn²) time. Then, the final projection takes up to (Nm) time. Thus, the total time complexity O(Nn²) +
SGA-based method. We discuss the complexity of a single iteration, which consists of projecting columns of P in (6), solving projected LP for obtaining y² and X and computing the gradient in (5). These take (m))..)). (m, k). and O(n(m + k)) time, respectively. Thus, the per-iteration complexity is (m) + TTpipmm k) + O(n(m + k)). After finishing all the iterations. the final projection takes Tproj (Nm) time, as with the PCA-based method. In the experiments, we ran SGA for a single epoch, i.e., N iterations. Thus, the total time complexity is N (T (m))(m) + [m,, k) (n + k))) + (Pr)).
'We can also represent x' by linear combination of a basis of the null space of Aeg. which we can compute via SVD. However, found that this representation numerically unstable in our experiments.
14

---

PCA
SGA
Padking
MaxFFn
MinCretFloor
GROW
Thaining tio (6)
104
107
10
101
L0M
200
ISRAEL
SC205
SCAGR25
STAIR
Thinnng time (e)
10
102
10P
10/
10P
102
10-1
10P
10
13
Figure Running times PCA and SGA for learning projection matrices on 200 training instances.
We turn the running times of the PCA- and SGA-based methods in the experiments in Section 6. Figure 2 shows the times taken by PCA and SGA for learning projection matrices on training datasets of 200 instances. (Full and ColRand
not included since they do not learn projection matrices.) We assumed that optimal solutions of training instances were computed a priori, and hence the time for solving original LPs was not included. The figure shows that SGA took much longer than PCA. This is natural since SGA iteratively solves LPs for computing gradients (5) and quadratic programs for projection (6), while PCA only requires computing the top-(k 1) right-singular vectors of X
I
as discussed above.
F Results with random initialization of SGA
Figure shows the same plots in Figure but with SGA initialized with ColRand instead PCA, which was mentioned in Footnote 5.
G Objective ratios on synthetic datasets with various noise levels
This section examines the effect of the noise strength on the performance of our data-driven projection methods. We created synthetic datasets, Packing, MaxFlow, and MinCostFlow, in the same way as in Section An important difference from Section is the increased noise level w, which perturbs LP inputs through multiplication by + We draw from uniform distribution over [0, @] with the upper bound w ranging from 0.0 to 2.0 in increments of 0.2; in Section 6, t was fixed at 0.1. The larger @ is, the less consistent the tendencies in the LP input parameters become, making more challenging to learn projection matrices with PCA and SGA. We fixed the dimensionality k of projected LPs 20, which means the size of projection matrices P is n x 20.
Figure 4 presents objective ratios achieved by each method on Packing, MaxFlow, and MinCostFlow datasets. There is notable difference between Packing and the others, which we discuss below.
Packing. The performance of our data-driven methods (PCA and SGA) worsens as @ increases, as expected. While they exhibit clear advantage over the andom-projection baseline (ColRand) at small values, they behave similarly ColRand when 2.0.
MaxFlow and MinCostFlow. In contrast to the Packing case, our data-driven methods, particularly SGA, performed well even with high noise levels, while the performance of ColRand remained poor. The success of data-driven methods is probably due to the fixed graph topology, which creates consistent tendencies across LP instances despite varying edge capacities and costs.
Note that fixed graph topologies are ubiquitous. For example, in daily transportation planning, the is fixed, while the capacities and costs may fluctuate due to congestion.
topology of traffic networks The above results highlight the merit of our data-driven projection methods in such applications.
15

---

Full
ColRand
PCA
SGA
Maxcl'one
MinCortFTorr
1.0
1.0
Chyectvve
0.5
0.5
0.0
20
40
10
ISRAAL
SC206
SCAGH22
STAIR
1.0
1.0
1.0
Objectiv
0.5
0.5
0.5
0.0
0.0
0.0
0.0
10
13
20
40
20
Ramiine of Ghrooa (6)
Parking
MaccF
MinCoetFlooe
GROWT
10a4
10
10
10
10-2
10m0
10a
10-1
10-3
10
Huntime of Chrolii (s)
ISRAEL
SC205
SCAGR25
STAIR
10
10
10a
10
10-2
10
10
10a
10
20
40
Figure 3: The same plots as in Figure but with SGA initialized with ColRand instead PCA, as mentioned in Footnote 5. Compared with Figure 1, the objective ratio of SGA deteriorates particularly MinCostFlow, GROW7, SC205, and SCAGR25.
Full
ColRand
PCA
SGA
Packing
Maxflow
Minerst fow
1.0
1.00
1.00
Objoctive retio
Objective Tetio
Objective ratio
0.8
0.8
0.50
0.50
0.25
0.26
0.00
0.00
02: Upper bound
moiee level
Upper bound moise level
02:
Upper bound on moige level
Figure 4: Objective ratios on synthetic datasets with varying upper bounds w on the noise level.
Except for Full, the LP dimensionality is set to k 20. Other settings the same in Section 6.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clarified the scope (data-driven projection for reducing the dimen- sionality of LPs) and contributions (generalization analysis and learning methods).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please Section 8.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification: Section 3 and Assumption 3.1 describe the assumptions. All theoretical results are supported by complete proofs. (Some of them are deferred the appendix.)
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 6 offers the details for reproducing the experimental results.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification: The supplementary material includes codes for generating data and reproducing experimental results, as well as README document providing specific instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (htips//nniss.c/pubbic
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (htips: SepppuulclggiideSCoeeuuuuuiie
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see Section for training and details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results of ColRand, randomized baseline method, are shown with error bands, which indicate the standard deviation over 10 independent trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide information on compute resources in Section and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpss//cccuiisscccppubilleeeiis
Answer: [Yes]
Justification: This paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper is dedicated to the general goal of advancing the field of optimization and machine learning. While there are many potential societal consequences of our work. we feel none of them must be specifically highlighted.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The license standard dataset.
of Gurobi stated in the reference. Netlib a publicly available
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswitheode httesiiilhooeeccc/aattttttt com/datasets has curated
licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We include README document of our codes in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "4L9qzzsv21", "reviewer": "Reviewer_vPup", "summary": "The paper proposes a data-driven approach to an accelerated solution of linear programming problems belonging to a common family. To this end, the dimensionality of the problems is reduced by a projection learned from a training set of problems. The paper first gives a theoretical generalization bound for this learning problem. Also, the paper proposes two specific projection learning algorithms, based on PCA and stochastic gradient ascent. Finally, the performance of the proposed methods is experimentally illustrated on several test cases.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally quite nicely written and very readable. I could follow it everywhere without difficulty and didn't even notice any typos.\n\nThe theoretical generalization bound (Theorem 4.4) is derived using more or less standard approaches of statistical learning theory, but the result itself is new and the proof seems to be correct. The proof is presented in the main text and is concise and nice. \n\nThe idea of data-driven projection and its implementations based on PCA and gradient ascent seem to be original. The paper includes a comparison of the proposed algorithm on 8 test cases; the proposed algorithms show good performance there.", "weaknesses": "The most significant issue that I see is that the derived generalization bound is vacuous for the LP families experimentally studied in the paper, but this point is for some reason completely ignored by the authors. Specifically, the bound in question is $\\epsilon\\lesssim Hk\\sqrt{n/N}$ (lines 257 and 359). As far as I understand, in the experiments $N\\sim 200, n\\sim 500, k\\sim 20$. Substituting these numbers gives $\\epsilon\\lesssim 20H,$ which is vacuous because the expected performance of a solver is in the interval $[0,H]$ anyway. Not to mention that the $O(\\cdots)$ in the bound may contain additional large constants. In fact, asymptotic generalization bounds are well-known to (significantly) overestimate the true generalization gap and so are more suitable as a mere theoretical assurance of convergence. However, the paper seems to suggest (say, in the end of section 6) that the derived bound has some practical value while making no attempt to actually discuss specific numbers associated with its experiments, which I find completely misleading. (This does not undermine the theoretical merit of Theorem 4.4; on the other hand convergence rates $O(\\sqrt{pdim/N})$ are standard in SLT.) \n\nThe second general significant issue is that the whole setting of data-learnable projected optimization proposed in the paper seems fairly artificial to me. This setting obviously assumes the variables and constraints to be somehow aligned between different LP instances (in contrast, random projections do not require any such alignment). This point is discussed in Remark 3.2, where it is mentioned that such scenarios arise in daily production planning and flight scheduling. It would be interesting to see a particular real scenario of this type. All the example experimentally studied in the paper, even those that the authors call realistic, do not look realistic to me. As far as I understood, each of the 8 considered families is obtained by synthetically perturbing a single LP instance. This artificial setting is obviously very favorable to the proposed algorithms compared to the baselines. If the perturbation goes to 0, the family degenerates into a collection of identical LP instances that can all be perfectly \"solved\" by recalling a single solution, so the proposed training-based methods can be made to look arbitrarily more efficient than the baselines by tuning the perturbation magnitude.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the reviewer's thoughtful and inspiring feedback. Below we present our responses to the comments.\n\n> Weaknesses:\n> \n> The most significant issue that I see is that the derived generalization bound is vacuous for the LP families experimentally studied in the paper, [...] However, the paper seems to suggest (say, in the end of section 6) that the derived bound has some practical value while making no attempt to actually discuss specific numbers associated with its experiments, which I find completely misleading. \n\nWe apologize for any misleading expressions, particularly the sentence at the end of Section 6. The primary purpose of the experiments was to observe the empirical performance of projection matrices learned with the PCA- and SGA-based methods, rather than to evaluate the sharpness of the bound in Theorem 4.4. We intended to communicate that the bound of $\\varepsilon \\lesssim Hk\\sqrt{n/N}$ on the generalization error could be meaningful when $N$ is sufficiently large. Although using such a large training dataset may seem demanding, it is a plausible future scenario given the trend towards accumulating and utilizing more data to advance optimization technologies, as evidenced by projects like AI4OPT. We will revise the manuscript to clarify this point and avoid any misconceptions. We appreciate the reviewer pointing out this issue.\n\nTo merely supplement our revised statements, we conducted an additional experiment, shown in Additional Experiment 2 in the [global response](https://openreview.net/forum?id=jHh804fZ5l&noteId=wB14h9cLk0), using a larger dataset of smaller LP instances for the Packing problem. The dataset consists of $20,000$ training and $20,000$ test LP instances of size $(n, m) = (50, 5)$, and we set the reduced dimensionality $k$ to $2$. Substituting these parameters into the bound implies $\\varepsilon \\lesssim Hk\\sqrt{n/N} = 0.1H$, which is now non-vacuous. We computed approximate generalization errors (the left-hand side in Eq. 4) for projection matrices learned with PCA- and SGA-based methods, where the true expectation is approximated by taking an average over the $20,000$ test instances. Figure 2 in the global response compares these to the reference bound of $k\\sqrt{n/N}$ implied by the theoretical analysis (omitting log and constant factors). While empirical generalization errors are typically much better than what the theory implies, all curves show a decreasing trend, and the theoretical upper bound converges to zero as $N$ increases, which could offer meaningful bounds when $N$ is large. We hope this clarification effectively addresses the reviewer's concern.\n\n> (This does not undermine the theoretical merit of Theorem 4.4; on the other hand convergence rates $O(\\sqrt{pdim/N})$ are standard in SLT.)\n\nJust to clarify, we wish to emphasize that the fact that $O(\\sqrt{{\\rm pdim(\\mathcal{U})}/N})$ is standard in statistical learning theory also does not undermine the contribution of Theorem 4.4. The contribution of Theorem 4.4 lies in establishing the bound on the pseudo-dimension as ${\\rm pdim(\\mathcal{U})}=O(nk^2\\log mk)$, not in asserting the $O(\\sqrt{{\\rm pdim(\\mathcal{U})}/N})$ bound on the generalization error. The latter is used merely as a standard fact in our paper.\n\n> The second general significant issue is that the whole setting of data-learnable projected optimization proposed in the paper seems fairly artificial to me. [...] This artificial setting is obviously very favorable to the proposed algorithms compared to the baselines. If the perturbation goes to 0, the family degenerates into a collection of identical LP instances that can all be perfectly \"solved\" by recalling a single solution, so the proposed training-based methods can be made to look arbitrarily more efficient than the baselines by tuning the perturbation magnitude.\n\nWe acknowledge the reviewer's points and appreciate the insights provided. While attempting to obtain more realistic datasets, we found that publicly available repositories such as Netlib, which we used in our experiments, only offer a single LP instance for each setting and do not provide the volume of data necessary for training. Thus, we created datasets by adding noise. Please note that our realistic datasets include outliers, making them less artificial than the reviewer might have perceived.\n\nTo address the reviewer's concern that our datasets might be too favorable to our proposed methods, we conducted additional experiments with the Packing, Maxflow, and MinCostFlow datasets at higher noise levels; please refer to Additional Experiment 1 in the [global response](https://openreview.net/forum?id=jHh804fZ5l&noteId=wB14h9cLk0) for details. Since data-driven methods can derive no benefit from completely noisy data, increasing the noise level effectively creates more challenging datasets.\n\nFigure 1 in the PDF attached to the global response presents the results. For Packing LPs, higher noise levels led to poorer performance of data-driven methods (PCA and SGA), aligning with the reviewer's perspective regarding our methods applied to less favorable settings. By contrast, for MaxFlow and MinCostFlow LPs, data-driven methods, particularly SGA, continued to perform well even in highly noisy environments. As described in the global response, this robustness is probably attributed to the fixed graph topology. Since fixed graph topologies are prevalent in practical scenarios such as transportation planning on traffic networks, we believe the noise resistance in these datasets indicates substantial additional merit of our methods.\n\nThis unexpected finding underscores the value of the reviewer's feedback, which has helped us present another positive aspect of our approach. We hope our responses adequately address the reviewer's concerns and present our work in a more positive light. Please do not hesitate to reach out during the discussion period if there are any further questions.", "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": "NRAHafSwmz", "reviewer": "Reviewer_nj7Z", "summary": "The paper attempts to theoretically analyze a method called Data-Driven Projections in Linear Programming. As discussed in the paper, projection methods aim to reduce the size of high-dimensional LPs. While random projection methods have improved the efficiency of LPs, data-driven projections have achieved better results. In this paper, it is assumed that the parameters of the LP (parameters in the constraints and the objective) come from some distribution. Based on a set of training samples of these parameters, data-driven methods try to find a subspace where future optimal solutions are expected to appear. The main contribution of the paper is that they propose a generalization bound for the difference between the empirical and statistical performance of the projected LP.", "questions": "Please refer to the weaknesses section.", "limitations": "Please refer to the weaknesses section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and well-motivated.\n- The proofs are rigorous and well-written.", "weaknesses": "- I think the contribution of the paper is marginal.\n- Although it is mentioned in the paper that the generalization is independent of the choice of the projection matrix $P$, the final goal is to minimize the expected value of the objective. To achieve this, it is necessary to choose a good $P$ that minimizes the empirical optimal value. I believe it should be proven somehow that the algorithm proposed by the paper can suggest a projection matrix that captures the subspace where future optimal solutions are expected to appear. I couldn't find a proof for this in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer's valuable feedback. We present our response to the comments below. \n\n> Weaknesses:\n> - I think the contribution of the paper is marginal.\n> - Although it is mentioned in the paper that the generalization is independent of the choice of the projection matrix $P$, the final goal is to minimize the expected value of the objective. To achieve this, it is necessary to choose a good $P$ that minimizes the empirical optimal value. I believe it should be proven somehow that the algorithm proposed by the paper can suggest a projection matrix that captures the subspace where future optimal solutions are expected to appear. I couldn't find a proof for this in the paper.\n\nWe appreciate the reviewer's insights provided. Regarding the second point, finding $\\boldsymbol{P}$ that minimizes the empirical optimal value (i.e., empirical risk minimization, or ERM) is indeed our ultimate goal. We attempted to prove such guarantees, but it turned out challenging as the optimal value of a projected LP, viewed as a function of $\\boldsymbol{P}$, is non-convex and difficult to optimize directly. Please note that this is a general difficulty recognized in the field of *data-driven algorithm design*. Accordingly, the line of work in this area (e.g., Gupta & Roughgarden SICOMP2017; Balcan et al. STOC2021; Bartlett et al. COLT2022), including ours, aims to achieve generalization bounds that are independent of tunable parameters, i.e., *uniform convergence*. This shift from seeking optimality in ERM to embracing uniform convergence is a deliberate strategy reached after careful consideration in this research field. Therefore, we believe that this point should not undermine the extensive body of work, including ours.\n\nJust to make sure, we wish to re-emphasize the discussion in Remark 4.2: uniform convergence ensures that $\\boldsymbol{P}$ performing well on training instances is also expected to perform well on future instances, *even if $\\boldsymbol{P}$ does not minimize the empirical optimal value.* Furthermore, the experiments in Section 6 show that we can empirically find good $\\boldsymbol{P}$ with PCA- and SGA-based methods, whose generalization guarantee follows from uniform convergence. These theoretical and empirical results demonstrate the merit of our data-driven projection approach to LPs, effectively circumventing the aforementioned challenge of optimizing $\\boldsymbol{P}$ to minimize the empirical optimal value.  \n\nWe hope that the above clarifications have adequately addressed the reviewer's concerns.\n\n> Questions:\n> \n> Please refer to the weaknesses section.\n\nIn response to the first comment in the weaknesses section, \"I think the contribution of the paper is marginal,\" we would appreciate it if the reviewer could provide more details about this opinion during the discussion period, particularly if our clarifications above have not fully addressed the reviewer's concern.", "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": "O3xVzm8ast", "reviewer": "Reviewer_E5r3", "summary": "This paper considers data-driven approach for learning projections for LPs. Given an LP with $m$ constraints and $n$ variables, it establishes bound on learning a projection $P\\in \\mathbb{R}^{n\\times k}$ that reduces $n$ to $k$. The main contribution is to establish uniform convergence bound on pseudo-dimension, for an upper bound of $\\tilde O(nk^2)$ and a lower bound of $\\Omega(nk)$. Authors also propose two algorithms for learning the projection, one is based on PCA of the optimal solution of LP instances, the other is a gradient ascent approach.", "questions": "Suppose you learn the projection for both the primal and dual, could this lead to an even more efficient downstream algorithm, as one only needs to handle LP instance of size $k'\\times k$? Or are there obvious reasons this is not a good idea?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper establishes bound on pseudo-dimension of of performance metrics for data-driven projections for LP, the bound is tight up to a factor of $k$. Experiments are also performed for the two methods proposed in this paper, and it provides speed up over the column-randomized approach that is data-oblivious and performance upgrade.", "weaknesses": "The techniques for proving the upper and lower bounds on pseudo-dimension are quite standard, authors should emphasize the technical difficulties for proving these bounds.\n\nEmpirical side, while \"after* learning the projection, it gives good performance, the process of learning the projection is quite slow. Authors might consider adding more discussions on how to learn these projections more efficiently (from an algorithmic perspective).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for providing insightful comments and a positive evaluation. We respond to each comment below.\n\n> Weaknesses:\n>\n> The techniques for proving the upper and lower bounds on pseudo-dimension are quite standard, authors should emphasize the technical difficulties for proving these bounds.\n\nWe appreciate the reviewer's suggestion. A primary technical challenge lies in the proof of Lemma 4.3, which is pivotal to our solver-agnostic analysis of optimal values of LPs. Specifically, we investigate the behavior of the optimal value of the projected LP $(\\boldsymbol{P^\\top c}, \\boldsymbol{AP}, \\boldsymbol{b})$ while addressing the potential issue that $\\boldsymbol{AP}$ may be rank-deficient. This rank deficiency generally hinders the straightforward derivation of an equation system that specifies a vertex optimal solution. To overcome this, the proof of Lemma 4.3 begins by reformulating the LP into an equivalent $2k$-dimensional LP with non-negativity constraints. This adjustment facilitates the determination of equation systems specifying vertex optimal solutions, as in the proof of Korte and Vygen [31, Proposition 3.1]. Although the adjustment is common in the context of mathematical programming, using it for analyzing the pseudo-dimension is our novel idea. We will emphasize this technical nuance in the revised manuscript.\n\n> Empirical side, while \"after* learning the projection, it gives good performance, the process of learning the projection is quite slow. Authors might consider adding more discussions on how to learn these projections more efficiently (from an algorithmic perspective).\n\nWe greatly value this suggestion. We expect that the few-shot learning approach, akin to the method proposed by Indyk et al. (NeurIPS 2021) for data-driven low-rank approximation, is effective for learning projection matrices efficiently. We will expand this discussion, currently only briefly mentioned in the conclusion section, in our revised manuscript.\n\n> Questions:\n>\n> Suppose you learn the projection for both the primal and dual, could this lead to an even more efficient downstream algorithm, as one only needs to handle LP instance of size $k' \\times k$? Or are there obvious reasons this is not a good idea?\n\nWe appreciate this insightful question. Indeed, we have considered applying projections to both the primal and dual and recognize its potential benefits. However, we have opted not to reduce the dual variables (i.e., the number of constraints), as it could result in optimal solutions for projected LPs that are infeasible for the original LPs. While the quality of feasible solutions is naturally evaluated through their objective values, how to assess the quality of infeasible solutions is more controversial. For this reason, we have chosen to focus solely on reducing the number of primal variables, thereby avoiding the issue of infeasibility and maintaining conceptual simplicity. We value this discussion and will highlight it as a promising direction for future research.\n\nWe hope our responses have adequately addressed the reviewer's concerns and questions. Please do not hesitate to contact us during the discussion period if there are any further questions.", "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": "94V8nfpYkr", "reviewer": "Reviewer_hECG", "summary": "On the theoretical side, the paper studies the problem of sample complexity of learning data-driven projection matrices for accelerating high-dimensional LP solving. Given n-dimensional LPs drawn from some problem distribution, the goal is to bound the number of problem instances needed to learn an $n\\times k$ projection matrix such that a good solution to the original LP can be found by (efficiently) solving the k-dimensional projected LP. The main result is a $\\tilde{O}(nk^2)$ upper bound on pseudo-dimension of the class of functions that measure the optimal value of the projected LP, and a corresponding $\\Omega(nk)$ lower bound.\n\nWhile finding optimal projection matrix on a training set is hard, the paper proposes two practical approaches for learning a projection matrix from the training LP instances. The first approach applies Principle Components Analysis to a matrix of optimal solutions of training instances. The second approach uses stochastic gradient updates to learn the projection matrix. Empirically, data-driven projections seem to perform better than random projections, with comparable gains in speed-ups.", "questions": "- How does the proof of Lemma 4.3 differ from the techniques of Balcan et al., NeurIPS 2022?\n- It seems like the proof for upper bound can be simplified by using the GJ framework of Bartlett et al. COLT 2022 (P. L. Bartlett, P. Indyk, and T. Wagner. Generalization bounds for data-driven numerical linear algebra.)\n- The $\\log (H/\\varepsilon)$ term is not needed in the sample complexity bound $N$. (Line 153)\n- Line 209: sign patters", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Speeding up high-dimensional LPs is fundamental to operations research and data-driven projections appears to be a promising tool.\n- A polynomial upper bound on the sample complexity theoretically establishes that projection matrices are learnable from data.\n- There is also a lower bound, with is tight up to a factor of $k$ and logarithmic factors.\n- Even though exact optimization on training LP instances is hard, the paper provides practical solutions that work well empirically. Practical algorithms are often hard to design in the data-driven literature.", "weaknesses": "- The i.i.d. assumption needed in theoretical results may be too strong in practice.\n- The proposed methods for learning the projection matrix are not efficient e.g. PCA approach needs optimal solutions of training problem instances.\n- While the authors provide bounds on the time complexity of their learning methods, there are no guarantees about the quality of solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for providing invaluable comments based on a deep understanding of data-driven algorithm design. We respond to each comment below:\n\n>Weaknesses:\n>- The i.i.d. assumption needed in theoretical results may be too strong in practice.\n>- The proposed methods for learning the projection matrix are not efficient e.g. PCA approach needs optimal solutions of training problem instances.\n>- While the authors provide bounds on the time complexity of their learning methods, there are no guarantees about the quality of solutions.\n\nWe acknowledge these points as limitations of our work. However, we wish to highlight that these significant challenges are not unique to our work but are common in data-driven algorithm design. Most existing research in this area assumes the i.i.d. setting and often does not offer efficient learning methods nor assess the quality of the resulting outputs. There are a few notable exceptions, such as the work by Balcan et al. (2023), titled \"Output-sensitive ERM-based techniques for data-driven algorithm design.\" Such enumeration-based methods can learn parameters that minimize empirical risk but lack polynomial-time guarantees and may be impractical due to their substantial computational demands. In contrast, our methods for learning projection matrices, although not providing guarantees regarding solution quality, have been experimentally demonstrated to perform well. We believe that providing such methods contributes to further investigation into the practical aspect of data-driven algorithm design.\n\n> Questions:\n> - How does the proof of Lemma 4.3 differ from the techniques of Balcan et al., NeurIPS 2022?\n\nWe appreciate this insightful question. While the work of Balcan et al. (NeurIPS 2022), which we cited as [11] in our paper, indeed inspired our analysis, there is an important technical difference between their approach and ours. Balcan et al. focus specifically on the branch-and-cut method, analyzing situations where either (1) new cuts (constraints) do not separate an optimal solution $x^*_{\\rm LP}$ to the original LP or (2) new cuts separate $x^*_{\\rm LP}$ and constitute an equation system specifying a new optimal solution.\n\nIn contrast, our Lemma 4.3 is intended for investigating the behavior of optimal values of projected LPs $(\\boldsymbol{P^\\top c}, \\boldsymbol{AP}, \\boldsymbol{b})$, which can change entirely with projection matrix $\\boldsymbol{P}$. A particular challenge we address is the possibility of $\\boldsymbol{AP}$ becoming rank-deficient, which hinders the standard derivation of an equation system specifying an optimal solution to the projected LP (cf. the proof of Korte and Vygen [31, Proposition 3.1]). We circumvent this issue by reformulating the projected LP into an equivalent $2k$-dimensional LP with non-negativity constraints, as is done at the beginning of the proof of Lemma 4.3. This adjustment, not employed by Balcan et al., justifies the subsequent analysis based on the enumeration of vertex solutions in the feasible region of the projected LP. Although the adjustment is common in mathematical programming, using it for analyzing the pseudo-dimension would be a novel idea.\n\nThus, although both our analysis and that of Balcan et al. employ Cramer’s rule and might seem similar at first glance, there is a notable technical distinction in how we address the specific challenges in analyzing projected LPs.\n\n> - It seems like the proof for upper bound can be simplified by using the GJ framework of Bartlett et al. COLT 2022 (P. L. Bartlett, P. Indyk, and T. Wagner. Generalization bounds for data-driven numerical linear algebra.)\n\nWe greatly value this insightful comment. Indeed, we considered employing the GJ framework of Bartlett et al. (COLT 2022) as an alternative approach, but we encountered a difficulty. The GJ framework requires a *GJ algorithm* that, in our case, computes the optimal value $u(\\boldsymbol{P}, \\pi)$ up to an $\\varepsilon$-error for a sufficiently small $\\varepsilon>0$. Crucially, the *predicate complexity* of a GJ algorithm must be upper bounded independently of projection matrix $\\boldsymbol{P}$ (i.e., learnable parameters). If not, certain parameters $\\boldsymbol{P}$ may cause the predicate complexity to become arbitrarily large, preventing us from bounding the pseudo-dimension with the GJ framework. We attempted to develop such a GJ algorithm using simplex- and interior-point-type methods, yet we were unable to make their predicate complexity independent of $\\boldsymbol{P}$. \n\nWe also appreciate the comments about the $\\log(H/\\varepsilon)$ term and the typo.\n\nWe hope our responses above have adequately addressed the reviewer's concerns and questions. Please do not hesitate to contact us during the discussion period if there are any further questions.", "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:
## **Global response**
We sincerely thank all reviewers for their efforts in reviewing our paper and providing invaluable feedback.

This global response reports the results of two additional experiments. While these were primarily conducted to address the comments by Reviewer vPup, notably, Figure 1 in the attached PDF deserves mention here. We thank Reviewer vPup for providing comments that inspired these interesting experiments.

### **Additional experiment 1 (Figure 1): higher noise levels**
We investigated what would happen if we made the training datasets more challenging for our methods to learn projection matrices. We used the synthetic datasets described in Section 6, namely, Packing, MaxFlow, and MinCostFlow, and fixed the dimensionality $k$ of projected LPs to $20$. An important difference from the original experiments in Section 6 is the increased noise level $\omega$, which perturbs LP inputs through multiplication by $1+\omega$. Here, we draw $\omega$ from a uniform distribution over $[0, \bar\omega]$ with the upper bound $\bar\omega$ ranging from $0.0$ to $2.0$ in increments of $0.2$; originally, $\bar\omega$ was fixed at $0.1$. The larger $\bar\omega$ is, the less consistent the tendencies in the input LPs become, making it more challenging to learn effective projection matrices with our PCA- and SGA-based methods.

### **Results**
Figure 1 in the attached PDF presents the objective ratio (i.e., objective values divided by true optimal values computed with "Full") achieved by each method for Packing, MaxFlow, and MinCostFlow datasets.

**Packing.** The performance of our data-driven methods (PCA and SGA) worsens as $\bar\omega$ increases, as expected. While they exhibit a clear advantage over the random-projection baseline (ColRand) at small $\bar\omega$ values, they behave similarly to ColRand when $\bar\omega=2.0$.

**MaxFlow and MinCostFlow.** In contrast to the Packing case, our data-driven methods, particularly SGA, performed well even with high noise levels, while the performance of ColRand remained poor. We guess the success of data-driven methods is due to the fixed graph topology, which creates consistent tendencies across LP instances despite varying edge capacities and costs. Note that fixed graph topologies are ubiquitous in practice; in daily transportation planning, the topology of traffic networks is fixed, while the edge capacities and costs may fluctuate due to congestion. The results highlight the potential benefits of our data-driven projection methods in such applications, newly discovered through this additional experiment.

### **Additional experiment 2 (Figure 2): visualizing the theoretical bound**
We use this experimental result primarily to address the first weakness comment by Reviewer vPup, and thus we detail the experimental settings there. Our purpose here is to describe that the theoretical bound on generalization errors can be non-vacuous when $N$, the dataset size, is sufficiently large relative to problem-size parameters such as $k$ and $n$. While the theoretical bound presented in Figure 2 may appear loose compared with actual generalization errors (approximated by averaging over $20,000$ instances), the bound converges to zero as $N$ increases, offering a meaningful bound on generalization errors when $N$ is large.

Due to constraints on time and computational resources, the above experiments are limited to synthetic datasets (with smaller sizes in the second experiment). Nevertheless, we believe these results have sufficient implications regarding the behavior of our learning methods (PCA and SGA) on more challenging instances and the connection between theory and practice.

Meta-review: This paper presents a data-driven approach to reducing the dimensionality of linear programming (LP) problems by learning projection matrices, which accelerates the solution of high-dimensional LPs. The authors introduce a new generalization bound and propose two specific methods for learning projection matrices using PCA and gradient-based techniques. Experimental results demonstrate that the data-driven projection methods outperform random projection methods across multiple scenarios.

The paper is well-written and clearly structured. Overall, it makes significant contributions both theoretically and practically. While there are concerns that the theoretical results might be too loose in certain experimental settings, the authors have provided additional experiments that show the effectiveness of the generalization bound under specific conditions.
Decision: Accept (poster)