Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming

Authors: shinsaku  sakaue
taihei  oki
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 13:55:16

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.

Main paper: 
 introduction: 
 Linear programming (LP) has been one of the most fundamental tools used in various industrial domains [23, 18] , and how to address high-dimensional LPs efficiently has been a 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 a randomized interior-point method [16] . Besides the improvements in LP solvers, there has been a 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-based approach is 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-point methods.In the context of numerical linear algebra, there has been a notable shift towards learning sketching matrices from data, instead of using random matrices [28, 29, 12, 33, 40] . This data-driven approach is 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-based methods.Drawing inspiration from this background, we study a data-driven projection approach for accelerating 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 LPinstance samples sufficient for bounding the gap between the empirical and expected objective values attained by the data-driven projection approach. Such a generalization bound is known to depend on the pseudo-dimension of the class of performance metrics. We prove an Õ(nk 2 ) upper bound on the pseudo-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 a piecewise polynomial structure of the optimal value of LPs as a function of input parameters. Besides playing a 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 Ω(nk) lower bound on the pseudo-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 Õ(k) gap, is nearly tight.Learning methods. We then explore how to 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-based methods can lead to much higher solution quality than random projection [2] , while greatly reducing the time for solving LPs.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 focus on data-driven projections and discuss generalization bounds.Data-driven algorithm design. Data-driven algorithm design [7] , initiated by Gupta and Roughgarden [25] , has served as a 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-programming (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 n and 0 n be the n × 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. 
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 feasibility issues, we focus on the following inequality-form LP with input parametersc ∈ R n , A ∈ R m×n , and b ∈ R m : maximize x∈R n c ⊤ x subject to Ax ≤ b.(1) When n is large, restricting variables to a low-dimensional subspace can be helpful for computing an approximate solution to (1) quickly. Specifically, given a projection matrix P ∈ R n×k with n > k, we consider solving the following projected LP, instead of (1): maximize y∈R k c ⊤ P y subject to AP y ≤ b.(2) Once we get an optimal solution y * to the projected LP (2), we can recover an n-dimensional solution, x = P y * , to the original LP (1) . Note that the recovered solution is always feasible for (1), although not always optimal. We measure the solution quality with the objective value c ⊤ x = c ⊤ P y * . Ideally, if P 's columns span a linear subspace that contains an optimal solution to (1), the recovered solution x = P y * is optimal to (1) due to the optimality of y * to (2) . Therefore, if we find such a good P close to being ideal with small k, we can efficiently obtain a high-quality solution x = P y * to (1) by solving the smaller projected LP (2). Remark 2.1 (Solver-specific aspects). As mentioned in Section 1, this projection-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 a fixed LP solver, which is a standard choice. Strictly speaking, projections 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. 
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 a statistical learning problem. Let Π denote the set of all possible LP instances and D an unknown distribution on Π. 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 π ∈ Π takes the inequality form (1), (ii) x = 0 n is feasible for all π ∈ Π, and (iii) optimal values of all instances in Π are upper bounded by a finite constant H > 0.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 Π have identical equality constraints. While such LPs in their current form do not satisfy (i), we can convert them into the inequality form (1) by considering the null space of the equality constraints (see Appendix C for details), hence satisfying (i). This conversion is useful for dealing with LPs of maximum-flow and minimum-cost-flow problems on 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 x 0 without loss of generality. This is because we can translate the feasible region so that x 0 coincides with the origin 0 n . Condition (ii) also implies that for any P ∈ R n×k , projected LPs are feasible (i.e., their feasible regions are non-empty) since y = 0 k is always feasible for any projected LPs. Condition (iii) is satisfied simply by focusing on bounded LPs (i.e., 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 as LPs satisfying Assumption 3.1.Due to condition (i), we can identify each LP instance π ∈ Π with its input parameters (c, A, b) in (1), i.e., π = (c, A, b). For an LP instance π ∈ Π and a projection matrix P ∈ R n×k , we defineu(P , π) = max{ c ⊤ P y : AP y ≤ b } (3)as the optimal value of the projected LP. Our goal is to learn P ∈ R n×k from LP instances sampled from D to maximize the expected optimal value on future instances, i.e., Eπ∼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 a realization of input parameters following some distribution. Such a scenario arises in, for example, daily production planning and flight scheduling. Note that the statistical learning setting is also widely used as a foundational framework in data-driven algorithm design [25, 8, 12, 9] . 
generalization bound: 
 This section studies the generalization bound, namely, how many samples from D are sufficient for guaranteeing that the expected optimal value, Eπ∼D[u(P , π)], of learned P is close to the empirical optimal value on sampled instances. First, let us overview the basics of learning theory. Let U ⊆ R Π be a class of functions, where each u ∈ U takes some input π ∈ Π and returns a real value. We use the following pseudo-dimension [38] to measure the complexity of a class of real-valued functions. Definition 4.1. Let N be a positive integer. We say U ⊆ R Π shatters an input set, {π 1 , . . . , π N } ⊆ Π, if there exist threshold values, t 1 , . . . , t N ∈ R, such that each of all the 2 N outcomes of { u(π i ) ≥ t i : i = 1, . . . , N } is realized by some u ∈ U. The pseudo-dimension of U, denoted by pdim(U), is the maximum size of an input set that U can shatter.In our case, the set U consists of functions u(P , •) : Π → R, defined in (3), for all possible projection matrices P ∈ R n×k . Each u(P , •) ∈ U takes an LP instance π = (c, A, b) ∈ Π as input and returns the optimal value of the projected LP. EQUATIONThat is, if a projection matrix P produces high-quality solutions on N ≈ (H/ε) 2 • pdim(U) instances sampled i.i.d. from D, it likely yields high-quality solutions on future instances from D as well. Thus, analyzing pdim(U) of U = { u(P , •) : Π → R : P ∈ R n×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 in data-driven algorithm design, as is also discussed in the literature [8, 10] . Note that (4) holds uniformly for all P ∈ R n×k , 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 no 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.Building upon the above learning theory background, a crucial factor for establishing the generalization bound is pdim(U). 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, 7] .We first overview the general proof idea. Suppose that we have an upper bound on the number of outcomes of { u(P , π i ) ≥ t i : i = 1, . . . , N } that grows more slowly than 2 N . Since shattering N instances requires 2 N outcomes, the largest N , such that the upper bound is at least 2 N , serves as an upper bound on pdim(U) (intuitively, pdim(U) ≲ log 2 ("upper 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? 1 In our case, a projected LP has input parameters(P ⊤ c, AP , b) ∈ R k × R m×k × R m, where P ⊤ c and AP change with P ∈ R n×k . Thus, addressing this question offers insight into the number of outcomes. Lemma 4.3 provides an answer for a more general setting, which might find other applications beyond our case since learning through LPs is not limited to the projection-based approach [47, 13, 42, 20] .Lemma 4.3. Let t ∈ R be a threshold value. Consider an LP π = (c, Ã, b) ∈ R k × R m×k × R msuch that each entry of c, Ã, and b is a polynomial of degree at most d in ν real variables, θ ∈ R ν .Assume that π is bounded and feasible for every θ ∈ R ν . Then, there are up to m+2k 2k (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{ c⊤ y : Ãy ≤ b } ≥ t or not is identical within each region.Proof. First, we rewrite the LP π = (c, Ã, b) as an equivalent 2k-dimensional LP with non-negativity constraints: max{ c⊤ (y +y -) : Ã(y +y -) ≤ b, [y + ; y -] ≥ 0 }. The resulting constraint matrix, A ′ := [ Ã, -Ã; -I 2k ], 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 to m ′ := m + 2k and k ′ := 2k, respectively. Below, we focus on the reformulated LP(c ′ , A ′ , b ′ ) ∈ R k ′ × R m ′ ×k ′ × R m ′ , where c ′ := [c; -c], b ′ := [ b; 0 2k ],and A ′ has full column rank.We consider determining max{ c ′⊤ y : A ′ y ≤ b ′ } ≥ t or not by checking all vertices of the feasible region. For any size-k ′ subset,I ⊆ {1, . . . , m ′ }, of row indices of A ′ ∈ R m ′ ×k ′ , let A ′ I denote the k ′ × k ′ submatrix of A ′ with rows restricted to I and b ′ I ∈ R k ′ the corresponding subvector of b ′ . For every subset I with det A ′ I ̸ = 0, let y I := A ′ I -1 b ′ I .Since the LP is bounded and feasible, and A ′ has full column rank, there is a vertex optimal solution written asy I = A ′ I -1 b ′I for some I (see the proof of Korte and Vygen [31, Proposition 3.1] ). Thus, the optimal value is at least t if and only if there exists at least one size-k ′ subset I with det A ′ I ̸ = 0, A ′ y I ≤ b ′ , and c ′⊤ y I ≥ t. Based on the above observation, we identify polynomials whose sign patterns determine max{ c ′⊤ y :A ′ y ≤ b ′ } ≥ t or not. For any subset I, if det A ′ I ̸ = 0, Cramer's rule implies that y I = A ′ I -1 b ′ I is written as f I (θ)/ det A ′ I , where f I (θ) is some k ′ -valued polynomial vector of θ with degrees at most k ′ d. Thus, we can check A ′ y I ≤ b ′ and c ′⊤ y I ≥ t by examining sign patterns of m ′ + 1 polynomials, A ′ f I (θ) -(det A ′ I )b ′ and c ′⊤ f I (θ) -t det A ′ I , whose degrees are at most (k ′ + 1)d. Considering all the m ′ k ′ choices of I, there are m ′ k ′ (m ′ + 2) polynomials of the form det A ′ I , A ′ f I (θ) -(det A ′ I )b ′ , and c ′⊤ f I (θ) -t det A ′I with degrees at most (k ′ + 1)d such that their sign patterns partition R ν into some regions, and max{ c ′⊤ y : A ′ y ≤ b ′ } ≥ t or not is identical within each region. Substituting m + 2k and 2k into m ′ and k ′ , respectively, completes the proof. Lemma 4.3 states that the outcome of whether u(P , π) = max{ c ⊤ P y : AP y ≤ b } exceeds t or not is determined by sign patterns of polynomials of P , and an 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(U). Theorem 4.4. pdim(U) = O(nk 2 log mk).Proof. Let (π, t) ∈ Π × R be a pair of an LP instance and a threshold value. Setting θ = P and d = 1 in Lemma 4.3, we have up to m+2k k (m + 2k + 2) polynomials of degree at most 2k + 1 whose sign patterns determine whether u(P , π) ≥ t or not. Thus, given N pairs of input instances and threshold values, (π i , t i ) N i=1 , we have up to N × m+2k 2k (m + 2k + 2) polynomials whose sign patterns determine u(P , π i ) ≥ t i or not for all i = 1, . . . , N , i.e., outcomes of N instances.Warren's theorem states that given ℓ polynomials of ν variables with degrees at most ∆, the number of all possible sign patterns is at most (8eℓ∆/ν) ν [46] (see also Goldberg and Jerrum [24, Corollary 2.1]).In our case, the number of polynomials is ℓ = N × m+2k 2k (m + 2k + 2), and each of them has ν = nk variables (P 's entries) and degrees at most ∆ = 2k + 1. Thus, the number of all possible outcomes is at most8eN m+2k 2k (m+2k+2)(2k+1) nk nk ≲ N nk nk poly(m, k) nk 2 .To shatter the set of N instances, the right-hand side must be at least 2 N . Taking the base-2 logarithm, it must hold thatN ≲ nk log 2 N nk + O(nk 2 log mk) ≤ 2 3 N + O(nk 2 log mk), where we used x log 2 1x ≤ 2 3 for x > 0. Therefore, U can shatter O(nk 2 log mk) instances, obtaining the desired bound on pdim(U).We then provide an Ω(nk) lower bound on pdim(U) to complement the above Õ(nk 2 ) upper bound, implying the tightness up to an Õ(k) factor. See Appendix B for the proof. Theorem 4.5. pdim(U) = Ω(nk).Our proof indeed gives the same lower bound on the γ-fat shattering dimension for γ < 1/2, which implies a lower bound of Ω(nk/ε) 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 Õ(k/ε) factor. The 1/ε gap is inevitable in general [5, Section 19.5] , while closing the Õ(k) gap is an interesting open problem. 
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 ±ε from the empirical one, where ε ≲ H pdim(U)/N ≲ Hk n/N due to Theorem 4.4, regardless of how we learn a 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-based methods.Remark 5.1 (Training time). We emphasize that learning methods are used only before addressing future LP instances and not once a projection matrix P is 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.As described in Section 2, a projection matrix P should preferably have columns that span a lowdimensional 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 ×n be a matrix whose ith row is an optimal solution to the ith training instance. We apply PCA to this X. Specifically, we subtract the mean, x = 1 N X ⊤ 1 N , from each row of X and apply the singular value decomposition (SVD) to X -1 N x⊤ , obtaining a decomposition of the form 1) be the submatrix of V whose columns are the top-(k -1) right-singular vectors of X -1 N x⊤ . We use P = [ x, V k-1 ] ∈ R n×k as a projection matrix. Here, x is concatenated due to the following consideration: since V k-1 is designed to satisfyU ΣV ⊤ = X -1 N x⊤ . Let V k-1 ∈ R n×(k-V k-1 Y ′ ≈ X ⊤ -x1 ⊤ N for some Y ′ ∈ R (k-1)×N , we expect [ x, V k-1 ]Y ≈ X ⊤ to hold for some Y ∈ R k×N , hence P = [ x, V k-1]. This method is not so costly when optimal solutions to training LP instances are given, as it only requires finding the top-(k -1) right-singular vectors of X -1 N x⊤ .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 a complementary approach, we provide a gradient-based method that directly improves the optimal value of LPs.As a warm-up, consider maximizing u(P , π) = max{ c ⊤ P y : AP y ≤ b } of a 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 , π) is differentiable in P and the gradient is expressed as follows [42, Theorem 1] (see Appendix D for details of the derivation):EQUATIONwhere λ * ∈ R m is a dual optimal solution. Thus, we can use the gradient ascent method to maximize u(P , π) under the regularity condition. However, this condition is sometimes prone to be violated, particularly when Slater's condition does not hold (i.e., there is no strictly feasible solution). For example, if the original LP has a constraint x ≥ 0 n and every column of P has opposite-sign entries, it is likely that only y = 0 k satisfies P y ≥ 0 n by equality, which is the unique optimal solution but not strictly feasible. In this case, the regularity condition is violated since all rows of P ∈ R n×k are active at 0 k and linearly dependent due to n > k. To alleviate this issue, we apply the following projection for j = 1, . . . , k before computing the gradient in (5):EQUATIONwhere 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 is feasible for the original LP, increasing the chance that there exists a strictly feasible solution in { y ∈ R k : AP y ≤ b }, although it is not guaranteed. This improves the likelihood that the regularity condition is satisfied.Given N training instances, π 1 , . . . , π N , we repeatedly update P as with SGD: for each π i , we iterate to compute the gradient ( 5) and to update P with it. The projection (6) onto the feasible region of π i comes before computing the gradient for π i . We call this method SGA (stochastic gradient ascent).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 a projection matrix P with either the PCA-or gradient-based method, we project each column of P onto the intersection of 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 1 ; . . . ; A N ]x ≤ [b 1 ; . . . ; b N ]. If A 1 , .. . , A N are identical, we can do it more efficiently by replacing the constraints with A 1 x ≤ min{b 1 , . . . , b N }, 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 0 n is always feasible as in Assumption 3.1. 
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. 3Synthetic 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 an LP with non-negative parameters c, A, and b. We created a 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 + ω, 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 arcs and fixed source and sink vertices, denoted by s and t, respectively. We confirmed there was an arc from s to t to ensure feasibility. We set base arc capacities to 1, which we perturbed by multiplying 1 + ω with ω drawn from the uniform distribution on [0, 0.1], thus obtaining 300 MaxFlow instances. For MinCostFlow, we set supply at s and demand at t to 1. We set base arc costs to 1 for all arcs but (s, t), whose cost was fixed to be large enough, and perturbed them similarly using 1 + ω to obtain 300 MinCostFlow instances. We transformed MaxFlow and MinCostFlow instances into equivalent inequality-form LPs with a method given in Appendix C, which requires a (trivially) feasible solution x 0 . For MaxFlow, we used x 0 = 0 (i.e., no flow) as a trivially feasible solution. For MinCostFlow, we let x 0 be all zeros but a single 1 at the entry corresponding to (s, t), which is a trivially feasible (but costly) solution.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.1ω, where ω was drawn from the normal distribution; for 2% outliers, we perturbed them by multiplying 1 + ω, i.e., 10 times larger noises. Except for ISRAEL, the LPs have equality constraints. We transformed them into inequality-form LPs as described in Appendix C, using x 0 found by the initialization procedure of Gurobi's interior-point method. 4Methods. 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-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-randomized method based on the work by Akchen and Mišić [2] , which reduces the dimensionality by selecting k out of n variables randomly and fixing the others to zeros.PCA: the PCA-based method that reduces the dimensionality with a 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 described 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. 5For ColRand, PCA, and SGA, we used increasing values of the reduced dimensionality, k = n 100 , 2 n 100 , . . . , until it reached the maximum value no more than n 10 , 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 k variables and recorded the average and standard deviation.Results. Figure 1 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 4 to 70 times faster than Full. Regarding STAIR, PCA and SGA attained 13.1% and 51.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 , π) is a non-convex problem. 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 ±ε of the empirical one, where ε ≲ H pdim(U)/N ≲ Hk n/N since pdim(U) = Õ(nk 2 ) due to Theorem 4.4. If N 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 realworld 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.  
conclusion: 
 We have studied the data-driven projection approach to LPs. We have established a generalization bound by proving an Õ(nk 2 ) upper bound on the pseudo-dimension and complemented it by an Ω(nk) lower bound. We have also proposed PCA-and gradient-based 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] . 
limitations and discussions: 
 Our work is limited to the statistical learning setting with assumptions on LP instances (see Section 3 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 our setting is a reasonable starting point for developing the datadriven projection approach to LPs, as is also discussed in Remark 3.2 and the paragraph following Assumption 3.1. Overcoming these limitations will require more involved methods, such as training neural networks to extract meaningful low-dimensional subspaces from non-i.i.d. messy LP instances.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.1, and we believe our conceptually simple learning methods are helpful for future research. Regarding the data-driven approach to low-rank approximation, Indyk et al. [29] found that a few-shot learning method is useful for efficiently learning sketching matrices. A key ingredient in their method is a 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 a good sketching matrix. We expect that similar ideas will be effective for learning projection matrices for LPs 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-based 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-based 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, 30] , 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 1 . Moreover, it can be even faster beyond the theoretical implications when GPUs are available. It is noteworthy that the projection-based approach largely benefits from GPUs, as matrix multiplication 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 inequality constraints, which would provide useful insights into this direction. 
safeguards: 
 Question: 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, or scraped datasets)?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 a 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 a 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 of Gurobi is stated in the reference. Netlib is a publicly available standard dataset.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Many researchers have addressed learning tasks whose input-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 as projection.Their theoretical result focuses on learning of models that generate objective functions, assuming reparametrization matrices to be fixed. By contrast, we obtain a generalization bound for learning projection matrices. El Balghiti et al. [19] have studied generalization bounds in the so-called smart predict-then-optimize setting. While they focus on 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 of optimization with respect to input parameters. Our gradient-based method for learning projection matrices is partly based on the result by Tan et al. [42] .We establish the lower bound on pdim(U) in Here, e r and e s are the rth and sth standard basis vectors of R n-2k and R k , respectively, and 0 a,b is the a × b all zeros. We consider a projection matrix of the formP = Q I k -I k ,where Q ∈ {0, 1} (n-2k)×k is a binary matrix that we will use as tunable parameters to shatter the set of (n -2k)k instances. Let y j denote the jth entry of the variable vector y ∈ R k . Since we haveAP = I k -I kthe constraints, AP y ≤ b s , imply y j = 0 for j = 1, . . . , k with j ̸ = s and y s ∈ [0, 1]. Let y be such a feasible solution. Then, the objective value is written as c ⊤ r P y = e ⊤ r Qy = Q r,s y s , where Q r,s is the (r, s) entry of Q ∈ {0, 1} (n-2k)×k . Since Q r,s ∈ {0, 1} and y s ∈ [0, 1], we have max{ c ⊤ r P y : AP y ≤ b s } = Q r,s . Thus, the set of those (n -2k)k instances can be shattered by setting all threshold values to 1/2 and appropriately choosing each entry of Q ∈ {0, 1} (n-2k)×k . In other words, all the 2 (n-2k)k outcomes of { u(P , π r,s ) = Q r,s ≥ 1/2 : r = 1, . . . , n -2k, s = 1, . . . , k } can realize by changing P ∈ R n×k (or Q ∈ {0, 1} (n-2k)×k ). Thus, we obtain an Ω(nk) lower bound on the pseudo-dimension of U = u(P , •) : Π → R : P ∈ R n×k .Suppose that we are given an LP of the form maximizez∈R n w ⊤ z subject to A ineq z ≤ b ineq , A eq z = b eq ,which has both inequality and equality constraints. Below, assuming that a (trivially) feasible solution x 0 is available (i.e., A ineq x 0 ≤ b ineq and A eq x 0 = b eq ), we transform the LP into an equivalent inequality form. First, we replace the variable vector z with z ′ + x 0 , obtaining an equivalent LP of the form maximizez ′ ∈R n w ⊤ (z ′ + x 0 ) subject to A ineq z ′ ≤ b ineq -A ineq x 0 , A eq z ′ = 0.The equality constraints, A eq z ′ = 0, mean that z ′ must be in the null space of A eq . Therefore, z ′ is always represented as z ′ = (I -A † eq A eq )x with some x ∈ R n , where A † eq is the pseudoinverse of A eq and I -A † eq A eq is the orthogonal projection matrix onto the null space of A eq .6 Substituting z ′ = (I -A † eq A eq )x into the above LP allows us to remove the equality constraints since they are automatically satisfied for every x. After all, by transforming the variable vector as z = (I -A † eq A eq )x + x 0 , we can obtain an equivalent LP of the form maximizex∈R n w ⊤ (I -A † eq A eq )x subject to A ineq (I -A † eq A eq )x ≤ b ineq -A ineq x 0 ,where the additive constant, w ⊤ x 0 , in the objective is omitted. This is an inequality-form LP (1) with c = (I -A † eq A eq ) ⊤ w, A = A ineq (I -A † eq A eq ), and b = b ineq -A ineq x 0 . Note that x = 0 is always feasible for the resulting LP and that we can use this transformation if A eq and b eq are fixed, even if w, A ineq , and b ineq can change across instances.We explain how to derive the gradient of u(P , π) in ( 5), which indeed follows from Tan et al. [42, Theorem 1] (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 ∇u(P , π) of u(P , π) = max c ⊤ P y : AP y ≤ b with respect to P . For convenience, we define new parameters w = P ⊤ c ∈ R k and W = AP ∈ R m×k and let y * ∈ arg max w ⊤ y : W y ≤ b . Then, we can differentiate the optimal value, u(P , π) = w ⊤ y * , with respect to w and W by applying the implicit function theorem to the KKT condition. Specifically, as shown in Tan et al. [42, Theorem 1], we have ∂u ∂w = y * and ∂u ∂W = -λ * y * ⊤ , where λ * ∈ R m ≥0 is the dual optimal solution. From the chain rule, we have∇u(P , π) = ∂u ∂w • ∂w ∂P + ∂u ∂W • ∂W ∂P ,where the indices for the products are aligned appropriately. By substituting the derivatives into this, we obtain ∇u(P , π) = cy * ⊤ -A ⊤ λ * 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.We discuss the theoretical complexity of the PCA-and SGA-based methods. For convenience, we use T lp (m, n) to represent the time complexity of solving an LP instance with m inequality constraints and n variables, as this factor highly depends on problem settings. Also, let T proj (m) be the time for solving the problem in (6) k times for projecting columns of P ∈ R n×k onto the feasible region specified by m inequality constraints. Given the T lp (m, n)-time linear optimization oracle, we can implement this projection step with a Frank-Wolfe-style algorithm. In this case, the time for projecting columns of P within an ε-error is typicallyT proj (m) = T lp (m, n) • poly(n, m) log(1/ε) [32, 22]. PCA-based method. Computing SVD of X ∈ R N ×n takes O(N n 2 ) time.Then, the final projection takes up to T proj (N m) time. Thus, the total time complexity is O(N n 2 ) + T proj (N m).SGA-based method. We discuss the complexity of a single iteration, which consists of projecting columns of P as in (6) , solving a projected LP for obtaining y * and λ * , and computing the gradient in (5) . These take T proj (m), T lp (m, k), and O(n(m + k)) time, respectively. Thus, the per-iteration complexity isT proj (m) + T lp (m, k) + O(n(m + k)).After finishing all the iterations, the final projection takes T proj (N m) 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 We turn to the running times of the PCA-and SGA-based methods in the experiments in Section 6.N (T proj (m) + T lp (m, k) + O(n(m + k))) + T proj (N m).Figure 2 shows the times taken by PCA and SGA for learning projection matrices on training datasets of 200 instances. (Full and ColRand are 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 -1 N x⊤ , as discussed above.F Results with random initialization of SGA Figure 3 shows the same plots as in Figure 1 but with SGA initialized with ColRand instead of PCA, which was mentioned in Footnote 5.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 6. An important difference from Section 6 is the increased noise level ω, which perturbs LP inputs through multiplication by 1 + ω. We draw ω from a uniform distribution over [0, ω] with the upper bound ω ranging from 0.0 to 2.0 in increments of 0.2; in Section 6, ω was fixed at 0.1. The larger ω is, the less consistent the tendencies in the LP input parameters become, making it more challenging to learn projection matrices with PCA and SGA. We fixed the dimensionality k of projected LPs to 20, which means the size of projection matrices P is n × 20.Figure 4 presents objective ratios achieved by each method on Packing, MaxFlow, and MinCostFlow datasets. There is a 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 random-projection baseline (ColRand) at small ω values, they behave similarly to ColRand when ω = 2.0.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 topology of traffic networks is fixed, while the capacities and costs may fluctuate due to congestion. The above results highlight the merit of our data-driven projection methods in such applications. NeurIPS Paper Checklist 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 in 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 well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).While a similar question is studied in Balcan et al.[11, Theorem 3.1], their result focuses on the case where new constraints are added to LPs to analyze branch-and-cut 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.The source code is available at https://github.com/ssakaue/data-driven-projection-lp-code.While Gurobi can solve larger LPs, we used the moderate-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 as well.We expect this x0 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 PCA-initialization worked better. We present the results with the random initialization in Figure3in Appendix F for completeness.We can also represent z ′ by a linear combination of a basis of the null space of Aeq, which we can compute via SVD. However, we found that this representation was numerically unstable in our experiments. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.) 

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 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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - I think the contribution of the paper is marginal.
- 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.
questions: questions: Please refer to the weaknesses section.
limitations: limitations: Please refer to the weaknesses section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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).
questions: 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: limitations: Yes.
paper_summary: paper_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.

While 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.
strength_weakness: strength_weakness: - The i.i.d. assumption needed in theoretical results may be too strong in practice.
- The proposed methods for learning the projection matrix are not efficient e.g. PCA approach needs optimal solutions of training problem instances.
- While the authors provide bounds on the time complexity of their learning methods, there are no guarantees about the quality of solutions.
questions: questions: - How does the proof of Lemma 4.3 differ from the techniques of Balcan et al., NeurIPS 2022?
- 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.)
- The $\log (H/\varepsilon)$ term is not needed in the sample complexity bound $N$. (Line 153)
- Line 209: sign patters
limitations: limitations: Yes.

Comments: comment: I thank the authors for their reply and addressing both of my concerns. I'm raising my score.
I thank the authors for their answers. They addressed my questions, so I increased my score accordingly.
Thank you for the detailed response, I appreciate the answers to my questions. I retain my score.
I thank the authors for answering my questions. I'll keep my score as is.