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.
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.
The 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.
The 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.)
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.