Coordinate Linear Variance Reduction for Generalized Linear Programming
Authors: Chaobing Song
Cheuk Yin Lin
Stephen Wright
Jelena Diakonikolas
Venue: NeurIPS 2022 Accept (2022)
Keywords: Linear Programming
Variance Reduction
Min-max optimization
Distributionally Robust Optimization

Abstract: We study a class of generalized linear programs (GLP) in a large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By reformulating (GLP) as an equivalent convex-concave min-max problem, we show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm, to which we give the name Coordinate Linear Variance Reduction (CLVR; pronounced ``clever''). CLVR yields improved complexity results for (GLP) that depend on the max row norm of the linear constraint matrix in (GLP) rather than the spectral norm. When the regularization terms and constraints are separable, CLVR admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix in (GLP) rather than the matrix dimensions. On the other hand, for the special case of linear programs, by exploiting sharpness, we propose a restart scheme for CLVR to obtain empirical linear convergence. Then we show that Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both $f$-divergence and Wasserstein metrics can be reformulated as (GLPs) by introducing sparsely connected auxiliary variables. We complement our theoretical guarantees with numerical experiments that verify our algorithm's practical effectiveness, in terms of wall-clock time and number of data passes.

Coordinate Linear Variance Reduction for Generalized Linear Programming
Chaobing Song"
Cheuk Yin Lin"
University of Misconsin-Madinn chaobing. song@wisc edu
University of Wisconsin-Madison cylin@cs. wws.. edu
Stephen J. Wright University of Aaaconsin-Madison swright@cs wisc. edu
Jelena Diakonikolas University of Wisconsin-Madiist jelenašcs. visc.edu
Abstract
We study a class of generalized linear programs (GLP) large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By reformulating (GI.P) as an equivalent convex-concave max problem, we show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm, to which we give the name Coordinate Linear Variance Reduction (CLVR; pronounced "clever"). CLVR yields improved complexity results for (GLP) that depend on the max row norm the linear constraint matrix in (GLP) rather than the spectral norm. When the regularization terms and constraints are separable, CLVR admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix (GLP) rather than the matrix dimensions. Further, for the special case of linear programs and by exploiting sharpness, propose a restart scheme for CIVR to obtain empirical linear convergence. Finally, we show that Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both f-divergence and Wasserstein metrics can be reformulated as (GLPs) by introducing sparsely connected auxiliary variables. We complement our theoretical guarantees with numerical experiments that verify our algorithm's 's practical effectiveness terms of wall-clock time and number of data passes.
Introduction
We study the following generalized linear program (GLP): min {er r(x): Ax b, x].
(GLP)
where æ, E Rd, A Raad be R" r Rdd R is a convex regularizer, and C Rd is closed convex set, such that proximal/projection operator involving r and X can be computed efficiently. When Y' the nonnegative orthant (a : x; 0 E [d]} and r = 0, (GLP) reduces to standard form of linear program (LP). When X' is convex cone and = 0. (GLP) reduces to a conic linear program. GLP)) is an important paradigm in traditional engineering disciplines such as transportation, energy, telecommunications, and manufacturing. In modern data science, note the renaissance of (GLP) due to its modeling power in such areas as reinforcement learning [19), optimal transport [57], and neural network verification (39]. For traditional engineering disciplines with moderate scale or exploitable sparsity, off-the-shelf interior point methods that form and factorize matrices in each
"qqual contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

iteration are often good choices as practical solvers [26] In data science applications, however, where the data are often dense or of extreme scale, the amount of computation and/or memory required by matrix factorization is prohibitive. Thus, first-order methods that avoid matrix factorizations are potentially appealing options. In this context, because the presence of the linear equality constraint in (GLP) may complicate projection operations onto the feasible set, we consider an equivalent reformulation of (GLP) as a min-max problem involving the Lagrangian:
min
max
(C(z y) = cf x + r(æ) + 3² Ax - y²
(PD-GLP)
BEXCR WEX"
In data science applications, both and d can be very large. (PD-GLPP) can be viewed structured bilinearly coupled min-max problem, where the linearity of L(ær, y) in the dual variable vector y is vital to our algorithmic development.
1.1 Background
While there have been few papers that directly address (PD-GLP) some special cases have been considered in 14 25 41 60 62 633 there has been significant recent work on first-order methods for general bilinearly coupled convex-concave min-max problems. Deterministic first- order methods include the proximal point method (PPM) [51) the extragradient/mirroo prox method (EGM) [4 (45), the primal-dual hybrid gradient (PDHG) method [15], and the alternating direction method of multipliers (ADMM) [20]. All these methods have per-iteration cost O ((nn((A) (A)) and convergence rate 1/k, where nnz(A) denotes the number of nonzero elements of A and is the number of iterations.
For better scalability, stochastic counterparts of these methods have been proposed. M 33 47
49
have used "vanilla" stochastic gradients to replace the full gradients of their deterministic counterparts.
13 27 have exploited the finite-sum structure of the interaction term (y) Ax) involving both primal and dual variables to perform variance reduction. With separability assumption for the dual variables, 3 and [16] have combined incremental coordinate approaches on the dual variables with an implicit variance reduction strategy on the primal variables. Recently, under separability assumption for dual variables, (55) proposed a new incremental coordinate method with an initialization step that requires a single access to the full data. This approach, known variance reduction via primal-dual accelerated dual averaging (VRPDA²), ?), obtains the first theoretical bounds that are better than their deterministic counterparts the class of incremental coordinate approaches. The VRPDA algorithm serves as the main motivation for our approach.
It is of particular interest to design algorithms that scale with the number of nonzero elements in A for at least two reasons: (i) the data matrix can be sparse; and (ii) when we consider simplified reformulations of certain complicated models, we often need to introduce sparsely connected auxiliary variables. Nevertheless, the randomized coordinate algorithms of B 16 551 have O(d) per-iteration cost regardless of the sparsity of A. To address this issue, 24 351 have proposed incremental primal- dual coordinate methods with per-iteration cost that scales with the number of nonzero elements in the row of A used in each iteration, at the price of needing to take a smaller step than for dense A. Moreover, (5] has proposed a random extrapolation approach that admits both low per-iteration cost and larger step size. Despite these developments, all these algorithms produce less accurate iterates than the methods with (d) per-iteration cost, thus degrading their worst-case complexity.
Finally, for the special case of LP, based on the positive Hoffman constant [30], 10 proved that the primal-dual formulation of LP exhibits a sharpness property that lowerbbounds the growth of a normalized primal-dual gap from the same work. Leveraging this sharpness property, [10] proposed
restart scheme for the deterministic first-order methods discussed above to obtain linear convergence.
o further extended this restart strategy using various heuristics improve practical performance.
1.2 Motivation
We sharpen the focus from general bilinearly coupled convex-concave min-max problems to GLP and its primal-dual formulation (PD-GLP). because many complicated models can be reformulated as GLPP) and because this formulation possesses additional structure that can be exploited in algorithm
SSussequent to this paper. version of the PURE-CT algorithm of [S] that exploits sparsity in A was developed and analyzed in [6.

---

design. Our motivation for focusing on (GLP) is to bridge the large gap between the well-studied stochastic variance reduced first-order methods 7 32
54 55 and the increasingly popular and
complicated, yet highly structured large-scale problems arising in distributionally robust optimization
(DRO) 21 31
52 58
61
see also recent survey by [50) and references therein.
For DRO problems with ambiguity sets defined by f-divergence [3] 37 44]. the original formulation a nonbilinearly coupled convex-concave min-max problem. Even the well constructed reformulation
in 33 does not admit unbiased stochastic gradients, leading to complicated algorithms and analysis.
For DRO problems with ambiguity sets defined by Wasserstein metric 23 29 38
52
61 the original
formulation is in general
-innte-dimmnniionl reformulations 23 52] exist for
special cases of logistic regression and smooth convex losses.) Solvers that have been proposed for DRO with Wasserstein metric are either multiple-loop deterministic ADMM [8 or are designed for general convex-coneen problems 66
By introducing auxiliary variables with sparse connections 3 we show that DRO with ambiguity sets based on both f-divergence and the Wasserstein metric can be reformulated as (GLP). Thus, complicated DRO problems can be addressed by a simple, efficient, and scalable algorithm for (GLP). Our algorithm for solving (GLP) and the proposed reformulations of DRO are our main contributions.
1.3 Contributions
55 we propose simple, efficient, and scalable algorithm for (PD-GLP) Our algorithm combines an incremental coordinate method with exploitation of the linear structure for the dual variables in (PD-GLP) and the implicit variance reduction effect in the algorithm, so we name it coordinate linear variance reduction (CLVR, pronounced "clever"). CLVR is inspired by VRPDA but customized to the particular structure of (PD-GLPJ. In particular, by exploiting the fact that the max problem is linear and unconstrained in the dual variable vector y E R", we find that the expensive initialization step used in VRPDA 2 is not needed and we can take simpler and larger steps. Further, in the structured case in which A is sparse and the convex constraint X' and the regularizer r(x) are fully separable we show that the dual averaging update in CLVR enables us to design an efficient lazy update strategy for which the per-iteration cost of CLVR scales with the number of nonzero elements of the selected row from A in each iteration, which is potentially much lower than the order-d cost in VRPDA?. Finally, CLVR uses extrapolation on dual variables rather than on primal variables considered in VRPDA which significantly reduces implementation complexity of our lazy update strategy for structured variants of (PD-GLP). On the technical side, although both CLVR and VRPDA are randomized algorithms that bound the primal-dual gap in expectation, the guarantee provided by CLVR is stronger as it allows bounding the expectation of the supremum gap as opposed to the supremum of expected gap in VRPDA?
Algorithm. Motivated by VRPDA?
To state our complexity results, we make the following scaling assumption.
Assumption 1. L := |||| and each row of A in GLP)) is normalized with Euclidean norm R.
Preprocessing in modern LP solvers (26) often ensures normalized rows/columns for the data matrix. Observe that R < L vnR. the upper bound being achieved when all elements of A have identical value. Although the latter case is extreme, there exist ill condiitiio practical datasets where we expect significant performance gains if the complexity can be reduced from O(L) to O(R). (We provide empirical comparison between the values of L and R in practical problems in Section 55)
In Table T we give the overall complexity bounds (total number of arithmetic operations) and the per-iteration cost of a representative set of existing algorithms, including our CLVR algorithm, for solving structured form of (PD-GLP) in which the set X' and the function r have separable structure:
X == Xi comparable, we assume further that for the stochastic algorithms [2
Xa with X; E IR (i E [d) and r(w) Σi= r(x²). To make the complexity results
16 55 and our CLVR algorithm, we draw one row of A per iteration uniformly at random. The general convex setting corresponds to r(z) being general convex (a = 0), while the strongly convex setting corresponds to r(æ)) being o-strongly convex (o > O).
""Sparse connections" here means that even though the newly introduced variables may substantially increase the problem dimensions, the number of nonzero entries the constraint matrix remains of the same order. WWe state the results here for the fully separable setting for convenience of comparison; however, our results are also applicable to the block separable setting.
3

---

Table 1: Overall complexity and per-iteration cost for solving structured (DD-GLP
indicates that the corresponding result does not exist or is unknown.)
General Convex
Strongly Convex
Per-Iteration
Algorithm
(Primal- Pral Gap)
(Distance to Solution)
Cost
PDHG
0 nax AM,
0 [nnee A) +n..).
O (A)
CP(2011)
SPDHG
0 Pil.
(
CERS(2018
AM (2022) (nnz((A A) + y Vnnal Allu+t)aR
EVR
O + d)
VRPDA
Olnd log min ( nz + edle
Ond minf /
m. ; ove)
O(d)
2W2(2021
CLVR
O amal ()R
O /unal R)
((nz((row(A))
(This Paper)
0v2
As shown in Table I all the algorithms have optimal dependence on [88] while the dependence on the ambient dimensions n, d, the number of nonzero elements of A (nnz (A)), and the constants L and It are quite different. For both the general convex and strongly convex settings and among coordinate-type methods, CLVR is the first algorithm that reduces the runtime dependence on the input matrix size from nd to nnz( (A). Moreover, the complexity of CLVR depends on the max row norm R rather than the spectral norm L, and the per-iteration cost of CLVR depends only on the nonzero elements of the selected row from A in each iteration, which can be far less than d.
By exploiting the linear structure again, we provide explicit guarantees for both the objective value and the constraint satisfaction of (GLP). Further, the analysis of CLVR applies to the more general block-coordinate update setting, which is better suited to modern parallel computing platforms. Finally, following the restart strategy based on the normalized duality gap for LP introduced in 10.. we propose a more straightforward strategy to restart our CLVR algorithm (as well as other iterative algorithms for (PD-GLP): ): Restart the algorithm every time widely known metric for LP optimality [8] halves. Compared with the normalized duality gap, the LPMetric can be computed more efficiently and in more straightforward fashion.
DRO reformulations. When the loss function is convex, DRO problems with ambiguity sets based on f-divergence 44 or Wasserstein metric (3 are convex. However, because both problems either have complicated constraints or are infnite-dimeesionnll vanilla first-order methods are inapplicable.
For DRO with f-divergence, we show that by using convex conjugates and introducing auxiliary variables, the problem can be reformulated gradients encountered problem has larger dimensions, due to the sparseness of the introduced auxiliary variables and the lazy update strategy of CLVR, it can be solved with complexity scaling only with the number of nonzero elements of the data matrix. Due to being cast as (GLP). the DRO problem can be solved with O(1/e) iteration complexity with CLVR, while existing methods such as (37) have O(1/e²) iteration complexity, with higher iteration cost because of the batch of samples needed to reduce bias. This improvement is enabled in part by considering the primal-dual gap (rather than the primal gap considered in (37) and by allowing the constraints to be approximately satisfied (see Corollary (
(GLP). As result, the issue of biased stochastic 37 does not arise, and CLVR can be applied. Even though the resulting
For DRO with Wasserstein metric, following the reformulation of 52 Theorem 1], we show further that the problem can be cast in the form of GLP).. Compared with the existing reformulations 52 61], our reformulation can handle both smooth and nonsmooth convex loss functions. In fact, our reformulation can provide more compact form for nonsmooth saicewise-linerd convex loss functions (such as hinge loss). Moreover, compared with algorithms customized to this problem (38 and extragradient methods 34 45 61 for general convex-concave min-max problems, our CLVR method
23 38
attains the hest-known iteration complexity and per-iteration cost, as shown in Table
Notation and preliminaries
For any positive integer p. we use [p] to denote (1,2,...,p) We assume that there is a given partition of the set [n] into sets $$.j e [m]] where | = n²' 0 - ne' For
[m]] we use A

---

to denote the submatrix of A with rows indexed by SJ and y to denote the subvector of y indexed by S². We use O2 and 1, to denote the vectors with all ones and all zeros in d dimensions, respectively. Unless otherwise specified, we use I--ll to denote the Euclidean norm for vectors and the spectral norm for matrices. For a given proper convex lower semi-continuous function f + R U (+00), we define the convex conjugate in the standard way as (v) = suPzer {yz - f(z)) (so that f = f). For a vector u, the inequality u 2 0 is applied entry-wise. For a convex function r r(x), we use r (æ) to denote an element of the subdifferential set Ör(z). The proximal operator of r r(z) over X' is
{ x 1 12 + r(x))
prox, (0) arg min =E
Further, we make the following assumptions, which apply throughout the convergence analysis. Assumption 2. (PD-GLP) attains least one primal- dual solution (æ* y²). W denotes the set of all primal-dual solutions.
Due to the convex-concave property of (PD-GLP), W is convex set in X' R
Assumption 3. L maxse[m] | given at the input, where || max| || =l|.
Note that i can be obtained either via preprocessing of the data or by parameter tuning. By combining Assumptions/ 1 and it follows that R S L S /v //maxje(m]] | [. R.
Assumption 4. r(z) is a-strongly convex (a 2 0): that is, for all xı and x2 in X' and all (x22 e (r(z)), we have r(x1)= 2 r(x2) + (x2), æ x2) + / | x2||?
For convex-concave min-max problems, a common metric for measuring solution quality is the primal-dual gap. which, for feasible solution (æ,, y) of (PD-GLP). is defined by
sup (u.))EAXX
{C(x, v) y),
(2)
However, as the domain of v is unbounded, the primal-dual gap can be infinite, which makes it a poor metric for measuring the progress of algorithms. As result, for measuring the progress of our algorithm, we consider the following restricted primal-dual gap instead:
sup [C(x, v) L(u,y)))
(u.u)EW
where W C X' x IR" is compact (i.e., closed and bounded) convex set. The use of restricted version of primal-dual gap is standard in the existing literature; see, e.g., [5 46).
The CLVR algorithm
3.1 Algorithm and analysis for general formulation
Algorithm D specifies CLVR for (PD-GL.P) in the general setting. The algorithm alternates the full update for 2y in Step 4 (Od cost) with an incremental block coordinate update for yı in Steps 5 and (with O1 (d) cost for dense A). The auxiliary variables 2 and qs accumulate the cancellation terms in the estimation sequence and give a pathway to a straightforward development of the lazified CLVR, which appears as Algorithm in in the appendix. The cost of updating auxiliary vectors 24 and Is is O(1S5= (d) and (d), respectively. In essence, CLVR is primal-dual coordinate method that uses a dual averaging update for KK. then updates the state variables {qu} } by a linear recursion, and computes o from qk-1 via a proximal step without direct dependence 03-1- The output æx is a convex combination of the iterates ( {æx K k= as is standard for primal-duee methods. However, ÿK is only an affine (not convex) combination of {3 { as involves the term -(m - 1)20 (whose coefficient is negative) and some of the coefficients ma, - (m 1)ax+1 multiplying yo for & E (1....A K - 1} may also be negative. An affine combination still provides valid bounds because the dual variable vector y appears linearly in (PD-GLP). Moreover, in Step 9, the term maz (z₁= - 1 serves to cancel certain errors from the randomization of the update w.r.t. yk. thus playing key role in implicit variance reduction.
Theorem provides the convergence results for Algorithm T The proof is provided in Appendix B In the theorem (as in the algorithm), ? is positive parameter that can be tuned.
5

---

Algorithm Coordinate Linear Variance Reduction (CLVR)
1: Input: 3o E R. yo
R", 20 A" yo. 7 0, > 0,0 2 0, K, m, 15 Sm.
A'yo.
2: d1 A 2 9o
ai (z + c).
3: for k .., K do
4: 4tk = prox - ( -k-1).
5: Pick ja uniformly random in [m]]
yk-11
i jk
6:
yi
U +
+yman (A Tt. bs");
i= jk
VItOAn/T
7: 0k+1
Ak+1 = A + 0c+11
21m
8: 2k - + A 1hh,7 (yk
32h -V--1)-
9: qk qu-1 + ax+1 (z + c) -max (Zte 2k-1).
10: end for
11: return ãKK Ax
1 E ak ÿK Ax Ek (a:yl + (m 1)ax (y yk--))).
Theorem 1. Let av. yk. k [K], be the iterates of Algorithm 7 and let Tx. yv be defined by
1 k
Ø6 = Ak i=1
o.y: + (m - ()a yi-1)),
(4)
AR
for k E [K]. Let We
X R". ko E [K]. be sequence of compact convex sets such that RR, where W is also convex and compact. Then:
(0k, U E Wr
E
sup (u,))EW,
[L(0k, v) L(u, [(u.ūr))
(5)
1 _ 11 woll?) à xo 21 - -110- + 112== -zoll +
<
A
27
where (á, 6) arg sup W)W () L(,,gi)), Furthermore,
E
7 + o A
. x 21112+
Ilye y'(l]] s =31100 =0ol2 + 27
"1y woll?
(6)
4
27
Define Ko
Then in the bounds above:
18t.my
k
(k- Ko max 20.72/mm/111 }
A 2 max
22 (6Im)22
Observe that (ú, i) in the theorem statement exists because of compactness of W/ and our assump- tions r(.). The parameter "y can be tuned to balance the relative weights of primal and dual initial quantities ||æ= xol and Ily" yoll (or estimates of these quantities), which can significantly influence practical performance of the method.
In addition to the guarantee on the variational form, due to the linear structure, also provide explicit guarantees for both the objective and the constraints in (GLP), stated in the following corollary.
Corollary 1. In Algorithm 7 for all & 2 1, De satisfies
7||x* - voll2 + 2n 1
yoll 2 + ]B[[ yoll²]
Elll"" || bl]] S
A
7||0- xol12
+ 2/1
1yy
yoll 2 [E[[
yoll
[e E4 + r(xx)) (c" x + +r(xx)))
Ax
where v = 2 T bj
11"
(Aæa b).
In CLVR, we allow for arbitrary (æop yo) E X' R" Nevertheless, by setting y = O.. we can obtain 2g 0₂ at no cost useful strategy for large-scale problems since avoids the (potentially expensive) single matrix-vectar multiplication w.r.t. A.

---

3.2 Lazy update for sparse and structured PDD-GLP
In Algorithm [ direct computation of the iterates (æe, yis and the output points (Øx, yt) can be expensive. However, [18] showed that it is possible to only update the averaged vector in the coordinate block chosen for that iteration. This strategy requires us to record the most recent update for each coordinate block and update it only when it is selected again, which is tricky and needs to be implemented carefully. For sparse and block coordinate-sepun separrabe instances of (PD-GLP) we show that by introducing auxiliary variables that are sparsely connected, we can significantly simplify CLVR and make its complexity scale independently of the ambient dimension n d, instead scaling with nnz(A) Due space constraints, defer technical details, including the lazy version of CLVR and associated proofs, to Appendix
3.3 Restart scheme
We now propose a fixed restart strategy with a fixed number of iterations per each restart epoch and discuss adaptive restart strategy for the special case of standard- LP, which corresponds to GLP with r(x) = 0 and = x 2₁ 2 0, E [d]}. We write
min c² x s.t. Ax b, 2 0d:
(LP)
and the primal-dual form
min max (((x = Ax y²b]. 220a MEB"
(PD-LP)
This problem has a sharpness property that can used to obtain linear convergence in first-order methods [10]. For convenience, in the following, we define w (x, y), ~ (œ. y). v (ž. 9) and w = x y Mcanwhile, for ? 0, we denote the weighted norm || ==
V - x 2 V and define the distance to W by dist(w, W*) = min || - 1oo-wwllgg w"'l(y)- When 7 = 1, || ll is the standard Euclidean norm. Then based on (PD-LP), we can use the following classical LPMetric measure the progress of iterative algorithms for LP:
1 Further, we use W to denote the optimal solution set of the LP
LPMetric (z. 3)
max x. 0 + Ar bl2 + ( - c, 03 maxx(cTa bTy,0}? (7)
which can be explicitly and directly computed. For the Euclidean case (? = 1), it is well-known 30 that there exists a Hoffman constant H/, such that
LPMetric(w) 2 Hisist(ue w. W*)()-
Using the equivalence of norms finite dimensions, for general y > O, we can conclude that there exists another constant H,, (to which we refer as the generalized Hoffman's constant) such that
LPMetric (w) ) 2 H,dist(w, (w, W*)
Using Eq. 99) and Theorem we then obtain the following bounds for distance and LPMetric.
Theorem 2. Consider the CLVR algorithm applied to the standard-form LP problem (PD-LP), with input uro and output Wy. Given 7 define w= arg min || wll()) and define
Co = 1/7 + (V2 - 1)llw, w" ll()) + || Thenfor H,, defined as 99. we have
LmCo H / /ddst Nost W))
E V dist( üRn W W))
S 5bV
LmCCo LLMetric((u))
E LPMetric (mx))
< <bV
H.k
'In PD-LPP, we dualize the constraint Ax by y (Ax= b) instead of T (b- (b-Aa)) so in our LPMetric, there exist sign difference for y from the common representation such the [10].
7

---

As result, by Theorem if we know the values of L. 1|w" (l(,) and Hy, then by setting i 1006 H., we can halve the square root of the distance and the LPMetric in expectation. Thus we can obtain linear convergence if we restart the CLVR algorithm after fixed number of iterations. However, the values of [|>)) and H, are often unknown and thus make this strategy unrealistic in practice.
Compared with the above fixed restart strategy, a natural strategy is to restart whenever the LPMetric halves (summarized in Algorithm| the appendix). Since L.Metrii easy to monitor and update, implementation of this strategy is straightforward. However, bounding the number of iterations required to halve the metric (in expectation or with high probability) seems nontrivial. What can be said (based on Theorem Sareemmmaann and denoting by K the number of iterations on CLVR between restarts) is that
P(K
50fmCC 82H4
This follows by Markov inequality, as PPKK > k] = IP [LPMetric((öx) >
/ H,K We provide comparison between the adaptive restart scheme proposed in T0] and our proposed adaptive restart scheme in Section D.I to demonstrate its practical competitivennss. Although we use adaptive restart in our experiments, we defer its convergence analysis to future work. Finally, as an independent and parallel work to ours, [40] proposed a high probability guarantee for scheduled restart for stochastic extragradient-typr methods.
LPMetric(wo))
4 Application: DRO
Consider sample vectors {a1, a....., an) with labels {b b2....,,b,,, The DRO problem with f-divergence based ambiguity set is
bn). where b; E {1,,-1) (i [x]].
min sup PEPp.n
pig(braf x))
(10)
where Pp. - -p R" Σー= = 1, 2 0 [m]), D/(pl S is the ambiguity set, is a convex loss function and D, is an f-divergence defined by Dy(plq)) Σi=1 q.fpp./q) /4) with p.q q E {p E IR" E P: = 1, 2 0} and f being a convex function 44 The formulation (IO) is nonbilinearly coupled convex-concave min-max problem with constraint set Pp... for which efficient projections are not available in general. When is a nonsmooth loss (e.g.. the hinge loss), many well-known methods such the extragradient 34 45 cannot be used even if we could project onto Pp.. efficiently. However, by introducing auxiliary variables, additional linear constraints, and simple convex constraints, can make the interacting term between primal and dual variables bilinear, as shown next. (See Appendix for a proof.)
Theorem 3. Let X be a compact convex set. Then the DRO problem in Eq.
10 is equivalent to
min 2, 44..
(
PM1 7 +
+
Σ
Hif
(
9i H4
}
n
i=1
q
S. w + U
11 = On,
n
u, b.a T x,
E [m]]
P1 = P2 =... pn.
g(u,) S wi.
E [m]
di E μ4 dom()")
E [n]
2 0, #4 2 0,
E [m]
X.
In Theorem 3 the domain of the one-dimensional convex function f*((.) is an interval such as [a, b), so that qi E M4 dom(f") denotes the inequality μıa S q, S μ.b. Since the perspective function (uf"(9) is a simple convex function of two variables, we can assume that the proximal operator for this function on the domain {(1, q) q E dom(()") y 0} can computed efficiently [12]. Similarly, we can assume that the constraint g(u) S w admits an efficiently computable projection operator. a result, the formulation (TO) can be solved by CLVR. When expressing
(TO) in the
form of PD-GLP), the primal and dual variable vectors have dimensions d + 1 + 4n and 3n 1.

---

respectively. However, according to Table I provided that X' is coordinate separable, the overall complexity of CLVR will only be O (unzí A (A)
The original DRO problem with Wasserstein metric based ambiguity set an infinite-dimensional nonbilinearly coupled convex-concave min-max problem defined by
min sup E [g T w)],
(11)
wER PEP
where a E R E -1, is distribution on R4 x {1, -1,, 9 is a convex loss function and P the Wasserstein metric-based ambiguity set [52]. Our reformulation for Eq. (TT) Appendix C.2
p.x
5 Numerical experiments
We provide experimental evaluations of our algorithm for the reformulation of the DRO with Wasser- stein metric based on the -noorm (with x 0.1 and p 10) and hinge loss. For its LP formulation (see Theorem PDHG [5]. SPDHG [16] and PURE-CD [5]. For all algorithms we use LPMetric (7) as the performance measure and use restart strategy based on successive halving of LPMetric (Section (33) to obtain
4 in the Appendix), we compare our CLVR method with three representative methods:
linear convergence. We implemented CLVR and other algorithms in Julial optimizing all implementa- tions to the extent possible. Full details of the experimental setup can be found in Appendix D Our
code available mtlhttps://giiann
com/ erricLincc/ffficceeet--00
Comparison between values of L and R. As described in Section major advantage of CLVR is that the complexity of CLVR depends on the max row norm R instead of the spectral norm L, which in the worst case for ill-conditioned problems can lead to a factor of v improvement. In practical problems where the problem instances are highly structured (e.g.. reformulated DRO problems), R can be much smaller than Table 2 provides empirical evidence for this claim. In all our experiments, we normalize each rows of A to R = 1 as stated in Assumption I so the values of L demonstrate the theoretical improvements for the experiments described Section
Table 2: Values of the spectral norm L in the reformulated DRO problems with Wasserstein metric after each row is normalized to R 1.
Reformulated a9a 130738, n 97929 117.3
Reformulated gisette
Reformulated rev1
Reformulated news20 269914, n 155198 d 5500750, n 2770370
44002,
28000
65.9
196.4
1041.6
690 32561, d 1231
gisette (n GOOD, di 5000
rovl (n 20242, di 47230)
T-EC CD 31
FURE CO Be edkt m-)
Follo cp Bild (i
LF stenti
ment
Numbbrr do13 pascos
Mumiber of d3ta $95005
Number dats pesses
TINI 52561,
gisetle (n 30001
rEVL On 23242, 47235)
FO
FDUIC
rblocedar- 501
Cort Brobaaee-i ii
de
(Tve del biimen 1011
1000
1922
Cecondo
Figure 1: Comparison of numerical results in terms of number of data passes and wall-clock time.

---

Comparison with primal-dual algorithms. Figure provides comparison between algorithms in terms of the number of data passes and wall-clock time. The spikes in all the plots are due to restarts: At the beginning of each restart cycle, the value of LPMetric increases significantly, then decreases rapidly. For the number of data passes (top row), CIVR with block size and PURE-CD perform best on all three datasets, CLVR with block size 10 and SPDHG with block size 50 have second-tier performance, and PDHG worst. For the CLVR algorithm, smaller block size corresponds to smaller in Assumption 3 which corresponds to better complexity in terms of data passes by Theorem II] Nevertheless, the gap between empirical performance and theoretical guarantee for SPDHG and PURE-CD deserves further research because, to date, they have only been shown to have the same iteration complexity as PDHG. Empirically, a9a, CLVR with block size 1 performs better than PURE-CD in terms of data passes.
In terms of wall-clock time (bottom row of Figure I because of different per-iteration costs of each algorithm and instruction-level parallelism in modern processors (28). the plots differ significantly from the plots for number of data passes. Even with block size 50, SPDIIG spends the most wall-clock time for one data pass and is the slowest on sparse datasets a9a and rcv1, but is faster than PDHIG on the dense dataset gisette. Meanwhile, while CLVR with block size 10 is not best in terms of data passes, it remains fastest in terms of wall-clock time on all datasets due to cheaper per per-iteration cost and instruction-lewe level parallelism. On rcv1, the per- per-iteration cost of PURE-CD is about 60% of that of CLVR with block size 1. Hence, despite having similar performance in terms of data passes, PURE-CD is faster than CLVR with block size but is still slower than CLVR with block size 10.
Comparison with production linear programming solvers. Table 3 shows that CLVR is com-
petitive against production-quality linear programming solvers such as GLPK ( and Gurobi (26). We observe that CLVR reached accurate solutions significantly faster than GLPK and Gurobi in the reformulated problems with gisette and rcv1 datasets. Although CLVR is much slower than Gurobi(barrier) on a9a dataset, we believe that much of the performance gap in this case is due to the redundancy the problem formulation with the a9a dataset, much of which is removed by Gurobi presolve We leave presolving and other heuristic speedups of CLVR for future work.
Table 3: Comparison of numerical results between CLVR and three production solvers for linear programming, showing time required (in seconds) for each solver to reach accuracy 10-8
Time (seconds)
Reformulated a9a
Reformulated gisette
Reformulated rev
130738, n 97929 = 44002, n = 28000 d 269914, n = 155198
JuMP+GLPK GuMP:Gurobissinplex)
899
4 10"
> 4 10
893
2182
7008
(urrbbbrbbb(brrrrer))
26
1039.7
1039.5
CLVR
962
697
582
Conclusion. Our preliminary numerical experiments show that CLVR is fastest in both the number of data passes and wall-clock time on considered datasets, among all primal-dual algorithms that we implemented. It is also competitive with production-quality linear programming solvers. Since has a theoretical guarantee that matches or improves the state of the art among primal-dual methods, we believe that CLVR could be a method of choice.
Acknowledgments and Disclosure of Funding
CS was supported in part by the NSF grant 2023239. JD and CYL acknowledge support from the NSF award 2007757. JD was also supported by the Office of Naval Research under contract number N00014-22-1-2544 and the Wisconsin Alumni Research Foundation. SW supported by NSF grants 2023239 and 2224213, the DOE under subcontract 8F-30039 from Argonne National Laboratory, and the AFOSR under subcontract UTA20-001224 from UT-Austin. Part of this work was done while JD, CS, and SW were visiting the Simons Institute for the Theory of Computing.
'The later paper describes complexity results for newly developed version of PURE-CE CD that exploits sparsity A. In our DRO instance with a9a dataset, Gurobi presolver removed 25% of the columns and 58% of the nonzeros.
10

---

References
[1] GLPK (GNU linear programming kit).
2022.
[2] A. Alacaoglu and Y. Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, pages 778-816, 2022.
[3] A. Alacaoglu, Q T. Dinh, O. Fercoq, and V. Cevher. Smooth primal-dual coordinate descent algorithms for nonsmooth convex optimization. In Proc. NIPS' 17, 2017.
[4] A. Alacaoglu, O. Fercoq, and Cevher. On the convergence of stochastic primal-dual hybrid gradient. arXiv preprint arXiv: 1tt.::::11100099,,,, 2019.
[5] A. Alacaoglu, O. Fercoq, and V. Cevher. Random extrapolation for primal-dual coordinate descent. In Proc. ICML'26 (0,,,20,,00 2020.
[6] A. Alacaoglu, V. Cevher, and S. J. Wright. On the complexity a practical primal-dual coordinate method, 2022. URL
07684
[7] 7. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proc. ACM STOC'17, 2017.
[8] E. D. Andersen and K. D. Andersen. The MOSEK interior point optimizer for linear program- ming: implementation of the homogeneous algorithm. In High Performance Optimization, pages 197-232. Springer, 2000.
[9] D. Applegate, M. Díaz, O. Hinder, Lu, M. Lubin, B. O'Donoghue, and Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. Proc. NeurlPS 2021.
[10] D. Applegate, O. Hinder, H. Lu, and M. Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. arXiv preprint arXiv:210S.12715: 2021.
[11] Bianchi. Ergodic convergence of stochastic proximal point algorithm. SIAM Journal on Optimization, 26(4):2235-222 2016.
[12] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge university press, 2004.
[13] Y. Carmon, Y. Jin, A. Sidford, and K. Tian. Variance reduction for matrix games. In Proc. NeurlPS' 19, 2019.
[14] Y. Carmon, Jin, A. Sidford, and K. Tian. Coordinate methods for matrix games. In Proceedings 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 283. November 2020.
[15] A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-145, 201
[16] A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schonlieb. Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM Journal on Optimization, 28(4):2733-2800 2018.
[17) C.-C. Chang and C.-J. Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
[18] C. D. Dang and Lan. Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM Journal on Optimization, 25(2))856-881, 2015.
[19] D. P. De Farias and B. Van Roy. The linear programming approach to approximate dynamic programming. Operations Research, (166)8800-865, 2003.
[20] Douglas and Rachford. On the numerical solution of heat conduction problems two and three space variables. Transactions of the American Mathematical Society, 82(2):421-439, 1956.
[21] Duchi and Namkoong. Learning models with uniform performance via distributionally robust optimization. Annals of Statistics, 4978):1378-14066 2021.

---

[22] J. C. Duchi, P. W. Glynn, and H. Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
[23] M. Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the wasser- stein metrie: Performance guarantees and tractable reformulations. Mathematical Programming. 171(1):115-166, 2018.
[24] O. Fercoq and P. Bianchi. A wordinateedescemm primal-dual algorithm with large step size and possibly nonseparable functions. SIAM Journal on Optimization, 29(1):100-134, 2019.
[25] X. Gao and S.-Z. Zhang. First-order algorithms for convex optimization with nonseparable objective and coupled constraints. Journal of the Operations Research Society of China, 5(2): 131-159, 2017.
[26] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL http:://s://w/ //ww gurobi. com
[27] E. Y. Hamedani and A. Jalilzadeh. A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems. arXiv preprint arX1v:2012.13456, 2020.
[28] Hennessy and D. A. Patterson. Computer architecture: a qquntiiaative approach. Elsevier, 2011.
[29] N. Ho-Nguyen and S. J. Wright. Adversarial classification via distributional robustness with Wasserstein ambiguity. Mathematical Programming, Series B, 2022. / org/ 10. N0.1007/ss11077 017901996-6
[30] A. Hoffman. On approximate solutions of systems of linear inequalities. In Selected Papers Of Alan J Hoffmaan: With Commentary, pages 174-176. World Scientific, 2003.
[31] W. Hu, G. Niu, I. Sato, and M. Sugiyama. Does distributionally robust supervised learning give robust classifiers? In Proc. ICML' 18, 2018.
[32] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proc. NIPS' 2013.
[33] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalitics with stochastic mirror-prox algorithm. Stochastic Systems, 1(1::17-58, 2011.
[34] G. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12(5):747-756 (in Russian; English translation in Matekon), 1976.
[35] Latafat, N. M. Freris, and P. Patrinos. A new randomized block-coordinate primal-dual proximal algorithm for distributed optimization. IEEE Transactions Automatic Control, 64 (10):4050-4065, 2019.
[36] S. Lee and S. J. Wright. Manifold identification in dual averaging for regularized stochastic online learning. Journal of Machine Learning Research, 13(6), 2012.
[37] D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford. Large-scale methods for distributionally robust optimization. In Proc. NeurIPS 20, 2020.
[38] J. Li, S. Huang, and A. M.-C. So. A first-order algorithmic framework for Wasserstein distribu- tionally robust logistic regression. Proc. NeurIPS' 19, 2019.
[39] C. Liu, T. Arnon, C. Lazarus, C. Strong, C. Barrett, M. J. Kochenderfer, et al. Algorithms for verifying deep neural networks. Foundations and Trends@ in Optimization, 4, 2020.
[40] H. Lu and J. Yang. Nearly optimal linear convergence of stochastic primal-dual methods for linear programming. arXiv preprint arXiv:2111.05530 2021.
[41] O. Mangasarian. Newton method for linear programming. Journal of Optimization Theory and Applications, 121(1):1-18, 2004.
12

---

[42] O. L. Mangasarian. Normal solutions of linear programs. In Mathematical Programming at Oberwolfach II. pages 206-216. Springer, 1984.
[43] O. L. Mangasarian and R. Meyer. Nonlinear perturbation linear programs. SIAM Journal on Control and Optimization, 17(6):745-752, 1979.
[44] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. In Proc. NIPS 16, 2016.
[45] A. Nemirovski. Prox-method with rate of convergence 0(1/L) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-255) 2004.
[46] Y. Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. (992-3):319-344 2007.
[47] H. Ouyang, N. He, L. Tran, and A. Gray. Stochastic alternating direction method of multipliers. In Proc. ICML'13 13, 2013.
[48] Y. Ouyang and Y. Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, pages 1-35, 2019.
[49] A. Patrascu and I. Necoara. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization, Journal of Machine Learning Research, 18(1):7004-7245 2017.
[50] H. Rahimian and S. Mehrotra. Distributionally robust optimization: Review. arXiv preprint 190.:0900800559, 2019.
[51] R. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
[52] S. Shafieezadeh Abadeh, P. Mohajerin Esfahani, and D. Kuhn. Distributionally robust logistic regression. In Proc. NIPS' 2015.
[53] A. Shapiro. On duality theory of conic linear problems. In Semi-Infinite Programming, pages 135-165. Springer, 2001.
[54] C. Song, Y. Jiang, and Y. Ma. Variance reduction via accelerated dual averaging for finite-sum optimization, In Proc. NeurIPS'20, 2020.
[55] C. Song, S. J. Wright, and J. Diakonikolas. Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In Proc. (C,L'21, 2021.
[56] Stoer. Duality in nonlinear programming and the minimax theorem. Numerische Mathematik, 5(1):371-379, 1963.
[57] C. Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, 2009.
[58] W. Wiesemann, D. Kuhn, and M. Sim. Distributionally robust convex optimization. Operations Research, 62(6))1338-133) 1376, 2014.
[59] L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 1((0t)):543-2556 2010.
[60] Y. Xu. Primal-dual stochastic gradient method for convex programs with many functional constraints. SIAM Journal on Optimization, 3062)1664 2020.
[61] Y. Yu, T. Lin, E. Mazumdar, and M. I. Jordan. Fast distributionally robust learning with variance reduced min-max optimization. arXiv preprint arXiv:2 /3326, 2021.
[62] I.. Zhao and D.-L. Zhu. On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming. Journal of the Operations Research Society of China, 10(1):53-87, 2022.
13

---

[63] D. Zhu and L. Zhao. Linear convergence of randomized primal-dual coordinate method for large-scale linear constrained convex programminn. In International Conference on Machine Learning, pages 11619-11688 1628.. PMIR, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All theoretical claims are supported by proofs, which, due to space constraints, are provided in the appendix. Numerical results are provided in Section 5 with full technical details of the experiments provided in Appendix [
(b) Did you describe the limitations of your work? [Yes] The three main examples are: (i) the discussion lazy update strategy and guarantees for it versus Øt in Appendix A (ii) the discussion of linear convergence under the restart strategy and theoretical guarantees for scheduled restart versus empirical guarantees for adaptive restart in
Section 3.3 and (iii) comparison to off-the-shelf solvers in Section 3 and use of
preconditioning.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work concerns generic solver for generalized linear programs and such is not tied to any
specific application that could have a potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See assumptions in Section 2
(b) Did you include complete proof's of all theoretical results? [Yes] See Appendix B and for complete proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We include our code in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In Section and Appendix D
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [No] Error bars are not reported due to almost identical behaviors and results from the large number of stochastic iterations.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In Appendix D
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We used datasets from LibSVM, which is a open source machine learning library and cited the creators T7 in Appendix D which provides full experimental details.
(b) Did you mention the license of the assets? [N/A] LibSVM datasets are distributed under the BSD license which is "a low restriction type of license for open source software that does not put requirements
redistribution."
(c) Did you include any new assets either the supplemental material or as URL? [Yes] Our code is provided in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] As mentioned before, the datasets we use are open source. (c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "t3Q-3gWo40", "reviewer": "Reviewer_FrTQ", "summary": "This paper develops a new primal-dual method for solving generalized linear programs (linear programs with regularizers) where each iteration requires cheap block coordinate updates. They claim an improved complexity results for linear programming and provide experiments on DRO problems.", "questions": "Why do you state cost per iteration of O(nnz(A) + n + d) instead of O(nnz(A)) (at many points in the paper, e.g., Line 45, Table 1)? Unless A has empty rows or columns (which can be removed from the problem) then these are equivalent. With this in mind I find the statement \"CLVR is the first algorithm that has no explicit dependence on the ambient dimensions d and n, instead depending on the number of nonzero elements nnz(A)\" (Line 127-128) dubious.\n\n**Update after reading reviewer response**\n\nThanks for the clarification. I have a further question and comment.\n\nHow did you pick the examples? This is a very small number of examples. With such a small number and no explanation how they are picked I worry that they are cherry picked.\n\nI think it would have been better if you'd picked a larger standard set of regression problems and presented aggregated results.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this paper needs lots of work but has potential. In particular, if the authors can clearly demonstrate a useful generic LP solver that uses coordinate-based iterations then that would be of high value to the community. However, there are currently too many issues for me to recommend acceptance.\n\n1. The authors present a new adaptive restart scheme. They do not give a convergence proof for this adaptive restart scheme. Also, they do not compare it empirically with existing restart schemes [9]. To be honest, I think the authors should either reuse existing adaptive restart schemes or demonstrate that their scheme is empirically better than existing schemes. I'd also remark that the results in [9] prove not only that restarts have linear convergence but the associated slope is better than what one gets is better than the linear converge rate one gets from the current iterate, and also stronger results for bilinear systems. I'd suggest the authors carefully read this paper [9] to see what I mean. I'm not sure if your restart metric would achieve these results.\n\n2. For the numerical results please specify if PDHG uses a restart scheme and what restarts scheme it uses. You should also specify how the primal and dual step size is chosen for PDHG as this has a big impact on results e.g., see Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems by Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, and Richard Baraniuk.\n\n3. I would like to have seen a much bigger variety of test problems. Currently, the method is only tested on DRO even though it is claimed to be a method for general linear programming. Ideally, you would test your method on the many standard benchmarks and report aggregate results. At a minimum you need a much larger variety of problems. Indeed, if all your method was useful for was DRO why not compare against specialized methods for DRO? E.g., Large-Scale Methods for Distributionally Robust Optimization. Daniel Levy, Yair Carmon, John Duchi & Aaron Sidford.\n\n4. You need to cite Carmon, Yair, et al. \"Coordinate methods for matrix games.\" 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020, and include it in Table 1. Indeed in the general convex case I believe their complexity is better.\n\n**Minor comments**\n\nOn line 314 you write \"we believe much of the performance gap in this case is due to the poor conditioning of this instance and the use of pre-conditioners in the barrier method\". I don't think this correct, to my knowledge, Gurobi does not use a preconditioner in its barrier method.\n\nOn Line 257-259 you claim [38] has an adaptive scheme. It only contains a fixed frequency restart scheme.\n\n**Update after reading reviewer response**\n\nThanks for the response. I think my initial score was a little harsh and appreciated your clarification. I have updated my score accordingly. I look forward to the new experiments. Please note I have updated my score irrespective of the results of the experiments (e.g., if CVR is better or not for the new instances). My only condition is the promised experiments are included in the final paper (or appendix).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "puv3Rg2bbMe", "reviewer": "Reviewer_bGMS", "summary": "The authors of this paper proposed a scalable first-order algorithm, which is named as Coordinate Linear Variance Reduction (CLVR) for  generalized linear program (GLP). And they improved complexity results for GLP that depend on the max row norm of the linear constraint matrix in GLP rather than the spectral norm. \n", "questions": "See the weakness.", "limitations": "See the weakness.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper is well-written. It illustrates the basic idea of the CLVR method for solving GLP in a clear way. The proposed CLVR algorithm is novel. The authors establish a better complexity bound for GLP. The authors provide nice explanations and discussions for their algorithm design and theoretical analysis.\n\nWeakness: For GLP, these papers proposed primal-dual type methods. Some comparisons are necessary. \n\n[1] http://www.optimization-online.org/DB_FILE/2015/05/4901.pdf\n[2] https://epubs.siam.org/doi/abs/10.1137/18M1229869\n[3] https://arxiv.org/abs/2008.12946\n[4] https://link.springer.com/article/10.1007/s40305-021-00344-x\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NyP7SO3mC8J", "reviewer": "Reviewer_ogmY", "summary": "This work studies the generalized linear programming, which has an additional convex regularizer in the objective, in the primal-dual setting. The algorithm named CLVR was proposed to solve the problem, and its complexity depends on the number of nonzero elements in the linear constraint matrix, which makes the algorithm scalable for large-scale problems. The convergence of the algorithm was proved in the paper as well. In the special case where the problem reduces to the standard LP, a restart scheme that accelerates the algorithm was also proposed. The simulation result shows that the algorithm shows comparable and often better performance than the previous works.", "questions": "* As I pointed out in the weakness, the authors should advertise the originality of CLVR compared to VRPDA in a more careful manner because the problem studied in this paper is less general than [53]. To be specific, I think that the authors should answer the following question: If we change the setting of VRPDA to PD-GLP and apply the lazy update, can we get an algorithm with complexity depending only on nnz(A)?\n* Please add some explanation of the variables z, q in Algorithm 1 in Section 3.1. \n* What was the main difficulty or key idea in the proof of Theorem 1? How is it different from the proof of Theorem 1 or Theorem2 of [53]?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The proposed algorithm is the first one that solves PD-GLP with complexity that only depends on the number of nonzero elements in the constraint and not on any other dimensions of the problem. Theoretical convergence result is also provided.\n\nWeakness: The work is mainly motivated by VRPDA of [53]. It seems like the proposed algorithm is the special case of VRPDA to the case where the Lagrangian is linear with respect to the dual variable, y. Thus the algorithm itself lacks originality. However, I could not check whether the analysis is also a simplification of [53] to the special case.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ADwkhg_Cf8J", "reviewer": "Reviewer_aEEZ", "summary": "There are many highly structured large-scale problems that can be reformulated as generalized linear programs (GLP). Hence, this work focuses on the GLP in a large-scale setting. Inspired by previous work, they proposed an up-gradation version after reformulating (GLP) as an equivalent convex-concave min-max problem, claiming lower complexity and stronger guarantee. Meanwhile, the author shows that modeling framework distributionally robust optimization with ambiguity sets defined by f-divergence and Wasserstein metric can be reformulated to GLP.", "questions": "I put my question in previous section.", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\nThis is a good extension of the previous work (VRPDA). \nAs the author claimed, better per-iteration complexity and bounding.\nThe solid improvement on complexity with respect to nnz(A). It’s potentially a huge improvement for certain applications.\n\nWeaknesses：\nIn one of the experiments that CLVR got defeated by the Gurobi, the author claimed that they believe is due to the preconditioners. It could be better if they could provide further experiments and analyses to make the claim stronger.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept