Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations
Authors: Arun Jambulapati
Kevin Tian
Venue: NeurIPS 2023 poster (2023)
Keywords: Optimization
optimal transport
linear programming
semidefinite programming
TL;DR: We give improved solvers and generalizations for box-simplex games, and their applications such as optimal transport, min-mean-cycle, flow, and matching.

Abstract: We investigate area convexity [Sherman17], a mysterious tool introduced to tackle optimization problems under the challenging $\ell_\infty$ geometry. We develop a deeper understanding of its relationship with conventional analyses of extragradient methods [Nemirovski04, Nesterov07]. We also give improved solvers for the subproblems required by variants of the [Sherman17] algorithm, designed through the lens of relative smoothness [BBT17, LFN18}.

Leveraging these new tools, we give a state-of-the-art first-order algorithm for solving box-simplex games (a primal-dual formulation of $\ell_\infty$ regression) in a $d \times n$ matrix with bounded rows, using $O(\log d \cdot \epsilon^{-1})$ matrix-vector queries. As a consequence, we obtain improved complexities for approximate maximum flow, optimal transport, min-mean-cycle, and other basic combinatorial optimization problems. We also develop a near-linear time algorithm for a matrix generalization of box-simplex games, capturing a family of problems closely related to semidefinite programs recently used as subroutines in robust statistics and numerical linear algebra.

Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations
Arun Jambulapati Simons Institute" jmblpati@berkeleey edu
Kevin Tian
University of Texas at Austin kjti an@cs. utexas .dd
edu
Abstract
We investigate different aspects area convexity [She17], a mysterious tool introduced tackle optimization problems under the challenging foo geometry. We develop deeper understanding of its relationship with more conventional analyses of extragradient methods [Nem04 Nes07]. We also give improved solvers for the subproblems required by variants of the 17h algorithm, designed through the lens of relative smoothness [BT177 LFNI8)
Leveraging these new tools, we give a state-of-the-art first-order algorithm for solving box-simplex games (a primal-dual formulation of too regression) in a d x n matrix with bounded rows, using Ollog d e-=) matrix-vector queries. Our solver yields improved runtimes for approximate maximum flow, optimal transport, min-mean-eyy -cccle and other basic combinatorial optimization problems. We also develop near-linear time algorithm for matrix generalization of box-simplex games, capturing a family of problems closely related to semidefinite programs recently used subroutines in robust statistics and numerical linear algebra.
Introduction
Box-simplex, or f60-1, games are a family of optimization problems the form
min max x T Ay - bT y aE[-L1]" yEA"
(1)
These problems are highly expressive, as high-accuracy solutions capture linear programs (LPs) as special case (L155 3 More recently, approximation algorithms for the family T have been applied to improve runtimes for applications captured by LPs naturally bounded in the Loo geometry. The current of-te-of-the-arr first-order method for (I is by Sherman [She17], who used the resulting solver to obtain faster algorithm for the maximum flow problem. As further consequences, solvers for ①1 have sped up runtimes for optimal transport JST19. common task in modern computer vision KP]+17] and min- menn--eeee [AP20. a basic subroutine in solving Markov decision processes (P%6), among other combinatorial optimization problems + [JST22]
The runtimes of first-order methods for approximating [ are parameterized by an additive accuracy 0 and Lipschitz constan L == ||A]] several prominent applications of (I) where the relevant A has favorable structure, e.g. the column-sparse edge-vertex incidence matrix of graph, naturally small. Standard non-Euclidean variants of gradient descent solve a smoothed
variant of (T) using - matrix-vecto products with A and A [es05 KLOS14. Until
Work completed at the University of Washington.
i Work completed at Microsoft Research.
Thii follows as generalizes fos regression min.e[-1.1j" ||Ar - bll.e. see Section 3.1 of (STS..
See Section|
1.3 for notation used throughout the paper. ||A|| 1-11 is the largest E norm of any column of A.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

recently however, the lack of accelerated algorithms for ① (using quadratically smaller O(L matrix-vector products) was a notorious barrier in optimization theory. This barrier arises due to the provable lack of strongly convex regularizer in the &o geometry with dimension-independen a necessary component of standard non-Euclidean acceleration schemes.
additive range [STTE] F
Sherman's 's breakthrough work [She17] overcame this obstacle and gave an algorithm for solving using roughly
(og(Le-))- -)))) matrix-vector products [ Roughly speaking, Sherman exploited the primal-dual nature of the problem ①T to design a smaller regularizer over the &oo ball [-1,1|", which satisfied weaker condition known as area convexity (rather than strong convexity). The algorithm in [She17] combined an extragradient method "outer loop" requiring O log d c iterations, and an alternating minimization subroutine "inner loop" solving the subproblems required by the outer loop in ((log(Le ()) steps. However, Sherman's 's analysis in [Shel7] was quite ad hoc, and its relationship more standard optimization techniques has remained mysterious. These mysteries have made further progress on ① and related problems challenging in several regards.
1. Sherman's 's algorithm pays logarithmic overhead in the complexity of its inner loop to solve subproblems high accuracy. Does tolerate more approximate subproblem solutions?
2. The analysis of Sherman's s alternating minimization scheme relies multiplicative stability properties of the dual variable y. In generalizations of (I) where the dual variable is unstable, how do we design solvers handling instability to maintain fast subproblem solutions?
3. The relationship between the area convexity definition [She17] and more standard Bregman divergence domination conditions used in classical analyses of extragradient methods [Nem04 Nes07] is unclear. Can we unify these extragradient convergence analyses?
A central goal of this work is to answer Question 3 by revisiting the area convexity technique of [She17], and developing a deeper understanding of its relationship to more standard tools in optimization theory such as relative smoothness [BBT17 [FNI8] and the classical extragradient methods of [Nem04] Nes07]. We summarize these insights in Section P and give self-contained expositions in Appendices A and B of the supplement. As hyproducts, our improved understanding of area convexity results in new ofte-of-the-ar runtimes for (T by affirmatively answering Question [ and the first accelerated solver for matrix generalization by affirmatively answering Question
1.1 Our results
Box-simplex games. We give an algorithm for solving [I improving the runtime of [She17] by a logarithmic factor, by removing the need for high-accuracy inner loop solutions
Theorem 1. There an algorithm (stated in full as Algorithm in the supplement) deterministically computing e-approximate saddle point to ① in time
|A log d
0 [nn((A)
We define nnz and ||A in Section 1.3 The most direct comparison to Theorem iis the work
[She]7], which we improve. All other first-order methods for solving ( we are aware of are slower than [She17] by at least an & min(e- vn) factor. Higher-order methods for (I) (e.g. interior point methods) obtain improved dependences on e the cost of polynomial overhead in the dimension.
As byproduct of Theorem [ we improve all the recent applications of (T. including approximate maximum flow [7he optimal transport [SSTI). cain-mean-cyer [AP2 and semi-strcaming variants of bipartite matching and transshipment [AJ 22). These are summarized Section 5 of the supplement. The design of efficient approximate solvers for optimal transport in particular is problem which has received a substantial amount of attention from the learning theory community
For a function f. we call max f min f its additive range.
'The runtime for solving subproblems required by [She17] was not explicitly bounded in that work, a simple initialization strategy bounds the runtime by Óllog( [e (Le-))),, 1)) see Proposition (AJI+22).
TTis statement assumes direct access to the entries of A (as does [Shel7)). More generally, let- ting Tam he the time takes to multiply
vector by the argument, we may replace anz(A) by max(Tmx T (A (A T, Taxe (IA), (IA T ()) where | is entrywise, which may be a significant savings when A implicit and nonnegative. An c-approximate saddle point is point with duality gap e; Section 1.3

---

(see Table 1 and the survey [PC19). The runtime of Theorem 1 represents natural conclusion to this line of work [8) We believe our improvement in Theorem | (avoiding high tigurrcy subproblem solve) takes important step towards bridging the state-of-the-an in the theory and practice of optimal transport, a well-motivated undertaking due to its widespread use in applications.
Table I:
Runtime complexities of first-order algorithms for optimal transport. Stated for a d x d cost matrix with unit-bounded costs, additive error tolerance Results labeled "sequential" require parallel depth which scales polynomially in the problem dimension d.
Method
Runtime
Comments
AWR17
(d log d 3
DGK18
Old logd.e"
DGKI8 18
LHJI9
O Vlgdd-"
BJKS18 Qua20
( log(d) d) log(e ) .6-1)
sequential, randomized
LMR19
Old - +
sequential
( log(d) log(E -1 ) 1)-1)
LH.22
O V/og d. 6 4/3)
Theorem
Old logd
Box-spectraplex games. We initiate the algorithmic study of boe-spectaaplex games of the form
min
max
Y. I,A,
(B, (B.Y)
(2)
YEAoXd
where [Achein). B are d symmetric matrices and Y = O satisfies Tr(Y) = 1 (i.e. Y A dxd
cf. Section 1.3). This family of problems is natural formulation of semidefinite programming (SDP),
and generalizes [b, the special case of (2) where all the matrices {Ar)eem) B, Y are diagonal.
Our main result on solving 2 stated below as Theorem has already found use in [JT233 to obtain faster solvers for spectral sparsification and related seccrepnncy-theoree primitives, where existing approximate SDP solvers do not apply. Beyond the fundamental nature of the problem solved by Theorem we are optimistic that will find use in other applications of structured SDPs.
To motivate our investigation of 2 we first describe some history of the study of the simpler problem ① Many applications captured by (1) are structured settings where optimization at relative scale, i.e. we wish to obtain an (1 + -)-multipicaative approximation to the value of a LP, OPT == Ain c x. We use bipartite matching as an example: x is a fractional matching and A is nonnegative edge-vertex incidence matrix. For LPs with a nonnegative constraint matrix A, custom positive IP solvers achieve (1 + e)-multiplicative approximations at accelerated rates scaling as O(E-)) This result then implies a ((e-))(rra algorithm for approximating bipartite matching and its generalization, optimal transport (where the first such algorithm used positive LP solvers [JKST8]] Qua) However, existing accelerated positive LP solvers [2015] are both sequential and randomized, and whether this is necessary has persisted as a challenging open question.
In several applications with nonnegative constraint matrices [ST19 AP20 AJ this obstacle was circumvented by recasting the problem as box-simplex game (T). for which faster, deterministic. and reduction) In these cases, careful use of box- box-simplex game solvers (and binary searching for the problem scale) match the guarantees of positive LP solvers, with improved parallelism determinism. Notably, simpler primitives such as simplex-siplee game solvers do not apply these settings.
solvers exist (see e.g. Section 4.1 of (AJ)+22) for the bipartite matching
The current state-of-affairs in applications of fast SDP solvers is very similar. For various problems in robust statistics (where the goal is to approximate a covariance matrix or detect a corruption
PPoggess on the historically simpler problem of (simplex-simplex) matrix games, a relative of 4I where both players e constrained, has stalled since [Nem04] almost 20 years ago, which attains deterministic runtime ((nz(() (A) L log - where is appropriate Lipschitz constant, analogously Theorem | "Two notable additional problems captured by box-simplex games, maximum flow [She17] and transshipment AJ)+ do not have nonnegative constraint matrix (as flows are signed), positive LP solvers do not apply.
3

---

spectrally) [CDG19 CMY20
2L and numerical linear algebra (where the goal is to reweight or
sparsify matrix sum) LS17
CGI8
J1M, positive SDP solvers have found utility. However,
these uses appear quite brittle: current positive SDP solvers (Z.O16 PTZI6 JLT20 only handle the special case of packing SDPs (a special class of positive SDP with one-sided constraints), preventing their application in more challenging settings (including pure covering SDPs).
In effort to bypass this potential obstacle when relying on positive SDP solvers more broadly, we therefore develop a nearly-linear time solver for box-spectraplex games in Theorem 2 (we define Tiv.
the time required perform matrix-vector product, in Section 1.3).
Theorem 2. There is algorithm which computes e-approximate saddle point to in time
o ((( Tan (m) (B)+
1,3.5 log
Land
Σ iE/ml
(Tmv (A.) TaN (IA,)))
c..
with probability 2 1 for L = Eie(m) AAillo + |BI|
A deterministic variant uses time
L log
Lnnd de
TmN (B)
Σ (A,) +mm d AE/n]
di )
Theorem 2 follows as a special case of Theorem in the supplement, which has refined guarantees stated in terms of the cost perform certain queries of matrix exponentials required by our algorithm, typical of first-order methods over A Adxd_ The first runtime in Theorem using randomized sketching tools, and the second uses exact implementation. Beyond its generic utility, we find Theorem conceptualyy interesting, as its development used our relative smoothness viewpoint on area convexity in Section (for overcoming instability of dual matrix variables), and new techniques for proving area convexity of a matrix variant of the [She regularizer.
2 implements these queries
To put Theorem in context, we compare it to existing solvers for simplex games, relative of (2) where both players are l constrained. cemplex-spectraple games are more well- studied V05 WK06 AK07 B CDSTI9], and the state-of-the of-the-art algorithms [BBN]3 AL17 CDSTI9 query e 2.5) vector products {Ai)e and slight variant of these algorithms (using separable regularizer in place of area convex techniques) gives a complexity of O(n -.2.5 such queries for the more challenging box-spectraplex games (2). which is the baseline in the literature. In comparison, Theorem 2 access to { [iejn] This is not without loss of generality, as A can be dense even when A is sparse, though in important robust statistics or spectral sparsification applications (where {A, ]eej) are rank-one), it is not restrictive. We find it interesting to understand whether access to {|Ai]) [[)l)) and the Ö(L overhead in Theorem (due to higher-rank randomized sketches) can be avoided.
requires 0 -335. products, but assumes
1.2 Related work
The family of box-simplex games (T) is captured by linear programming [S15), where state-of-the.
art solvers [CLS21 vdBLL*21 run in time Ö((n (n + d) or O(d + min(n, d)2-5), where sv 2.37 These LP solvers run in superlinear time, and practical implementations do not currently exist; on the other hand, the convergence rates depend polylogarithmicaly on the accuracy parameter Le The state-of-the-a approximate solver for (I) (with runtime depending linearly on the input size nnz(A) and polynomially on Lc=') is the accelerated algorithm of [7he which is improved by our Theorem Ty logarithmic factor. Finally, we mention BBWW99 as another recent work which relies on area convexity techniques to design an algorithm a different problem setting: their inner loop also requires high-precision solves (as in [She17)), and this similarly results in logarithmic overhead in the runtime.
the current matrix multiplication constant AAW2IDWZZ2
For the specific application of optimal transport, a problem captured by I receiving significant recent attention from the learning theory community, several alternative solvers have been developed beyond Table T By exploiting relationships between Sinkhorn regularization and faster solvers for matrix scaling (CMTV17 AI ALdWW17), [BJKST8] gave an alternative solver obtaining a Ō(n² -1) rate. These algorithms call specialized graph Laplacian system solvers subroutine, which currently

---

less practical than our methods based on matrix-vector queries. Finally, the recent breakthrough maximum flow algorithm of [CKL=22] extends to solve optimal transport in ((n2+o11) time (though its practicality is unclear). For moderate 2 n - this is slower than Theorem
To our knowledge, there have been no solvers developed tailoring specifically to the family These problems are solved by general-purpose SDP solvers, where the ofate-of-the-ar runtimes of 22] are highly superlinear (though again depend polylogarithmically on the inverse accuracy). We believe our techniques in proving Theorem extend to show that variant of gradient descent in the loo geometry [KLOS14] solves in an unaccelerated (11,6-22) iterations, with the same per-iteration complexity as Theorem
O( vd + nd?26) or Ö(n d + n²vd) [ HIS
1.3 Notation
General notation. We use Ö to suppress polylogarithmic factors in problem parameters for brevity, Throughout [x] = {i E N S i S n and I1-llp is the E norm. We refer to the dual space (bounded linear operators) of a set X' by X The all-zeroes and all-ones vectors in dimension d are denoted O₂ and Ld. When u, are vectors of equal dimension, u denotes their coordinatewise multiplication. For A E Raadd we denote its 7th row (for E [nl) by A; and jth column (for E [d] by A.j. For p. q 2 1 we define || p-0a = sup/ = A The number of nonzero entries in A is denoted nnz( (),, and Tax (A) is the time it takes to multiply a vector by A. We use (., 1) to project onto [-1, 1), where med means median. We define the d-dimensional simplex and the d
spectraplex A = {y E IR ||v|l = 1} and A = (Y E sdxd TrrY = 13. Throughout we reserve hyy) = Σ sEe y5 log Uj (for y E A for negated (vector) entropy.
Optimization. For convex function f. (1) refers to the subgradient set at we sometimes use 0s to denote any (consistently chosen) subgradient. Following [[ENI8], we say f is L-relatively smooth with respect to convex function if Lr f is convex, and we say I is m-strongly convex with respect to if mr is convex. For a differentiable convex function f we define the associated Bregman divergence V (x') == f(z)) f(x) (V)(x), x' z), which satisfies the identity
( -V (s())
V
For convex function f on two variables (z. y), we use 0zf( v) to denote the subgradient set y of the restricted function fx. We call function f of two variables (z. y) E X x y convex- concave if its restrictions the first and second block are respectively convex and concave. We call f'(x, uy.
(1c, y) E X' xxx an e-approximate saddle point if its duality gap, maxy'y I f(, y')- most For differentiable convex-concave function clear from context, its subgradient operator is g(x, y) == (0z y). 0, (x. v)): when f is differentiable, we will call this a gradient operator. We say operator g is monotone if for all w, z in its domain, (g(w) g(2), w 2) 2 O: examples are the subgradient of a convex funcciin or subgradient operator of a convex-concar function.
1.4 Organization
We summarize improved area convexity insights in Section 2 (with extended expositions in the supplement), and showcase how they prove Theorem[[in Section 3 Due to space constraints, we defer proving Theorem 2 and our applications the supplement (Sections 4 and 5, respectively).
2 Revisiting area convexity
In this section and Section we consider box-simplex games of the form ① for A E Ruxd b e Rd. and E R". For simplicity we assume ||A|| S 1, lifting this assumption (by scale invariance) in the proof of Theorem [
We approximate saddle points to (I) by using the family of regularizers:
(0) (x., v) = (IAly. ly. ) + ah(y), where h(y) = Σ yj log Uj is negative entropy, (
(4)
jEld
where the absolute value is applied to A entrywise, and squaring is applied to entrywise. This family was introduced by [STT1), a minor modification to a similar family given by [She17), and has favorable properties for the geometry present in the problem ( In the remainder of the paper,
5

---

we specialize the notation X' := |-,, and for any e R" we let Ix(()) = ee -1,1) be
truncation applied entrywise. We also use ) == A and for any E R2 we let [T = // ||]|
normalize onto y. We let Z : X' y, and define the gradient operator of (
g(r, v) = (Av + c, A AT)
(5)
We refer to the z and components of g( y) by (z v) == Ay + and g² == b - A ATx. Finally, to minimize clutter we denote the Bregman divergence in r by V(o) = V
1. Section 2.1 presents unification of the convergence analysis in [She17] with more standard analyses, by way of interpreting area convexity as Bregman domination 6
2. Section presents several helper results from convex analysis which demonstrates how area convexity implies relative smoothness of the subproblems encountered by [She17], leading simpler subproblem solvers. This also gives way to developments which generalize the matrix setting (and are crucial for our proof of Theorem 2).
Ultimately, our proof of Theorem in Section
will build upon both of these sets of insights.
2.1 Area convexity as Bregman domination
In Appendix B of the supplement, we analyze extragradient algorithms for approximately solving variational inequalities in an operator 9. i.c. which find with small (g(z), - u) for all u in the domain (in the minimax optimization setting where g taken to the gradient operator, e.g. the operator in (5). this corresponds to duality gap). Specifically, we analyze convergence under the following condition, weaker than previous notions in [She17 CST21
Definition 1 (Relaxed relative Lipschitzness). We say an operator g Z + z" is 2 relaxed relatively Lipschitz with respect to + if for all (z, z', 22) Z Z Z,
"
n (g(2')) - -g============' - S V2
This notion is related to and subsumes the notions of relative Lipschitzness [CST2I] and area convexity [She17] which have recently been proposed to analyze extragradient methods, which we define below. In particular, Definitions 2 and 3 were motivated by designing solvers for ①
Definition 2 (Relative Lipschitzness
(ST21)). We say an operator g Z + Z is -reeltiively
Lipschitz with respect to 2 - R for all (z, E 2
2 2,
n ((9(2') g(2), - -2t)
Definition 3 (Area convexity [She17]) )) We say convex 2 - RR is n-area convex with respect to an operator g Z - 2" for all (z,=1,=t) E 2 2 x 2, defining e := [ ( +)),
(g(2z) - g(=), x' - - S r()) - r(=)) + -(=+()+)))))) 3r(c).
Area convexity is monotone in n as the right-hand side is nonnegative for any 2, o
Relaxed relative Lipschitzness simultaneously generalizes relative Lipschitzness and area convexity.
The relationship is obvious for Definition 2 but the generalization of Definition 3 relies on the following simple observation, which has not previously appeared explicitly to our knowledge:
r(z) + r(z') +
(= + VT((z) (v s +
(6)
In Appendix B of the supplement we give framework unifying previous analyses of Nem04 Nes07
Shel7 CST2M) possibly of further utility. The realization (6) that area convexity implies Bregman divergence bound lets us reinterpret the [She17] outer loop to tolerate larger amounts of inexactness in the subproblems, where inexactness is measured in Bregman divergence. We combine our improved outer loop analysis with tools leveraging relative smoothness (to be discussed) to remove alternating minimization from [She17] We will use the following known fact.
Fact 1 (Lemma 2, (CS221) For convex functions frr, if is L-relatively smooth with respect to then o L-relatively Lipschitz with respect to r.
We also summarize some useful properties of (a) adapted from UST19
(a) Lemma 1. For 2 1./ A is jointly convex; for 2,
(a) T is 3/4 arra convex with respect to g 5

---

2.2 Area convexity as relative smoothness
In [7], the second property in Lemma ! was used with an ad hoc outer loop analysis (unified with existing analyses in Appendix B of the supplement) to prove convergence. However, it remains to discuss how to implement steps of the outer loop method, each of which solves a regularized
subproblem of the form, for (g", 9g)) E X x ) (and recalling our regularizer (4)
min z 2E|-1,1] WEA"
F(x, v) = (g" .) (0" u) + (IAl,, ah(y))
These subproblem forms are standard for mirror descent- based methods (including extragradient methods). In contrast to schemes using separable regularizers (admitting closed-form solutions), the subproblems induced by themselves require an iterative method to solve. In [She17] linearly-convergen minimization subroutine for F was given based on multiplicative stability of simplex variables, using a fairly nonstandard analysis (see Lemma 6, )]STT9). Our next observation is that linearly-convergee
subproblem solver follows off off-the-shelf from [LFN18] and viewing area convexity under the lens of relative smoothness, a more standard condition in optimization theory. We use the following convex analysis facts, deferring proof's to Section 3.2 of the supplement.
Lemma 2. Let X S Rm and y S Rh be convex compact subsets. Suppose F X' x y + R is jointly convex over its argument (r, y) E X x x.. For y E y. define For == argmin Frg and f(y) == (( v)). Then for all y E V, F, (xbr 1) C (y)...
Lemma 3. In the setting of Lemma 2 suppose for any X, F(x,,)) .) (as a function over y) always is r y + R plus linear function (where the linear function may depend on x). Then r f is convex, and q is convex for any q y + IR such that q: X y + R is jointly convex.
2: Hence, for a 2, we may apply Lemma with r(y) == 2h(y) to conclude that fly) == min F(z.y) y) is 2-relatively smooth with respect to h, as a function over y = A Moreover, applying Lemma with q(v) == hy), and again using the joint convexity fact in Lemma 1 shows that is further 1-relatively strongly convex with respect to h. At this point, a direct application of Theorem 3.1 in [LFN18] (which gives an algorithm for optimization under relative smoothness and strong convexity) yields a linearly-convergent algorithm for minimizing F. We remark that in light of Lemma [ we can implement gradient queries to f by computing the best response argument for given y.
Recall from Lemma that F is jointly convex over (x,y) for any a 2
Interestingly, this argument used nothing more than Lemma 3 joint convexity of r())) and the ability to tune to induce relative strong convexity (in contrast to [Sh11]], which requires multiplicative stability properties). An important consequence is that the same technique generalizes to the matrix setting via new joint convexity facts we prove in Section 4 of the supplement, where multiplicative stability breaks due to mon-moootty of matrix exponentials; the corresponding subproblem analysis in [She hence does not apply. This gives a simple proof-of-concept matching Theorem 2 up to logarithmic factors, which we improve via our approximation extragradient methods.
3 Box-simplex games without alternating minimization
In this section, we show how to combine the insights regarding area convexity from Section with careful implementation of our inner loop subproblem solvers, to prove Theorem
2 along
3.1 Approximation-tollran extragradient method
We begin by stating two oracles whose guarantees, when combined with Definition give our conceptual algorithm for (I). These oracles can be viewed approximately implementing steps of the extragradient method framework in Appendix B of the supplement. We develop subroutines which satisfy these relaxed definitions in the following Section 3.2 In the following definitions (and
throughout), we let ((a)= = yr be the divergence associated with (()) for notational convenience.
Definition 4 (Gradient step oracle). For a problem (T]. we say O Ogra x - is an (a, B)- gradient step oracle if on input (z, v). it returns z' such that
(0, u) S v((ati(()))
vlo) (2) u Z.
7

---

Definition 5 (Extragradient step oracle). For a problem T. we say Oxgras 2 2 x y - Z is an (a, -etrarrenrr step oracle if on input (z, v. D). returns (2,,8 such that
(u, u) < Vi00 v(a) (u) v( (2 (=*) + 8hh (u") V (ur) all = (u", , E Z. g+
When 8 = 0, Definitions and 5 reduce to the conventional proximal oracle steps used by the extragradient method of [Nem04] In our solver for (T). we use 3 > 0 to compensate for inexact subproblem solves. The asymmetry in Definitions 4 and reflect an asymmetry in the analyses of extragradient methods. In typical analyses, the regret bounded for the "gradient oracle" points, but the regret upper bound is stated in terms of the divergences of the "extragradient oracle" points (which our inexact oracles need compensate for).
The utility of our Definitions and reveals itself through the following lemma.
2 0 and I S 5-- Let z' t- Ognal(z (z, ng(()) and M). where Ognat is an (a, -)gradend step oracle and Oxgrad is an (ax 3, extrugrdddii step oracle. Then for all u E Z,
Lemma 4. Let = E a
(z+,g*) + Orgna(z, ))))
(ng()'), -2)
-w) s (2( 2Vla+>) (u) + 2V7"((²²) (u²) ) 2V zt
g+ (u²)) ²
Proof. By definition of O gnd (with t- + and O Oggrad: have
(ng(z), - =²) $ Vla+ - vl (2+) (()((2"),
u) s 2V (u) 2v(e++0) (u) 2V/aat)) (x+) + 2v² (09)-2211 (ur). (7)
(ng(2'), u))
Combining yields
(ng((=)) 2' - n) s 2 (w) 22((+ zt
(u) (u)) + 2V
- 22
+ (g(((= - g(2), 2' - -2t) (x)) - (2 - (2+)
(2+)
s 2 (u) 2v(0+ (1)) + 2V² (u') - -2V (u²)
(n)
zt
+ ( g(2), - =²) (2') -V(0)
where in the second inequality we used that (o++8) dominates F(a), and v((a (2+) 2 by Lemma The conclusion follows by applying Definition 3 (see (6) and the second fact in Lemmal []
When 3 7 0, Lemma 4 the same as Appendix B of the supplement, and hence yields similar implications as standard extragradient methods: scaling of the left-hand side upper bounds duality gap of z', and the right-hand side telescopes (and is bounded using the following standard fact).
Lemma 5. Let a, O, and let 20 (Io: yo) where To Cn and yo LLd. Then 20 is the minimizer of (() over Z. and (a))) (u) + a log d, Vish (w²) < 7 log d for all (u", w²) Z.
Finally, for convenience to the reader, we put together Lemma and 5 to obtain an analysis of the following conceptual "outer loop" extragradient algorithm (subject to the implementation of gradient and extragradient step oracles), Algorithm Our end-to-end algorithm will be an explicit implementation of the framework in Algorithm|] []] we provide runtime analysis and error guarantee for our complete algorithm in Theorem I well as pscudocode in Algorithm 4 of the supplement.

---

Algorithm 1: ConnepptualBxxSSipleex b, O grad Oxgraal
Input: A E Raxd with L 1-1 desired accuracy (0, L). Ograd (2 28,22-graa graddient step
oracle, Oxgrad a (4, -)xrrrerdaaaaaiiin step oracle
Initialize zo Cn. y0 L Wo - la. + On, 2 Dd. 7
6(8 log d4 1, 11 t
3 Rescale A 4 _ A, -- tb, t
for t 1'' do
It (Att + c. ATx))
2. = (I/ 11) t Orad (2, 19tt)
gi f (Aví + -. C.b-AA A x')
(*++1, 9t-1) = (#++1: Mc+ 9c-1) Oxgrad 3ob Ft)
end
10 Return: (.. - + Et= (2 v6)
Corollary 1. Algorithm deterministicaaly computes an c-approximate saddle point
Proof. First, clearly the rescaling in Line multiplies the entire problem ① by I. so f- approximate saddle point to new problem becomes an e-approximate saddle point for the original. Throughout the rest of the proof it suffices to treat L 1. Next, by telescoping and averaging Lemma with a = = 2, = 4, and = t.4 we have for 2g = (Io. yo) and any = (u", u²) Z
(V%% (u) + Vo (u²))
T Σ (0)4))
SC.
The last inequality used the bounds in Lemma 5 and the definition of T. Moreover since g is bilinear, and 2 (.: ()) the average of the 2f iterates, we have (g(2), & u) S Taking the supremum
over u E Z bounds the duality gap of and gives the conclusion.
3.2 Implementing oracles
In this section, we give generic constructions of gradient and extragradient step oracles
Algorithm 2: GradStepOraclecc.u.a.
Input: = = (x, E 2, (v u E a,
y' <- argmingey Nxy + V (a) (Drr (1). v) - v,rA (2).0) (2),0 + v.th where for all ),
(0)
Tie (V) argmin x (o- ( V.r (2), + (a) (a) where & (á, 1)
x' (3/(3/) Return: (x', ,y)"))
Lemma 6. For B 2 a 2
1 2. Algorithm is an (a, -)radiett step oracle.
Proof. By 3 and the first-order optimality condition for y' we have for any u = (u²,"²) E Z,
N (I)) v Vyr (2). u² ( 8
o' (n") v (s/)
Further, define for any ÿ V,
f = (u, E) + ((() where 2 (ar (V) 1))
(10)
Note that of is partial minimization of function on two variables which is a linear term plus 'A which convex by Lemma For any fixed r, (a) (x, y) itself ad(y) plus a linear function.
(a)
We slightly abuse notation and use 2he in 8 in consistent way with how it is used in Lemma 2 where F in Lemma 2 is taken to be the jointly convex function of (Ir, in ( before minimizing over X.

---

Lemma then shows f is a-relatively smooth with respect to h. We then have for all 0. u² E }
V (n) A (1).0) - (abe (V), v). w²) (af(0) - 0f(u), - u²)
(11)
Va (0) V (u²).
(a) Here the equality used Lemma)) 2 where the linear shift between A and the minimization problem inducing cancels in the expression ( (y), and the inequality used Fact Combining (9) and (with ÿ -- y/) and using V dominates Voh yields
N +
(x')
V (z). w²)
V VVg
(12)
Finally, first-order optimality of with respect to the objective induced by y implies for all u² E X,
(2), - w²) 50
(13)
so combining with 12 we have for u (u",
(a) (z') - -Vr
(0) (z), - u) S VV (u²)
The conclusion follows by using the identity to rewrite (vr (0) (x') Vr (z). 10,u-22 -u)- z2).
Algorithm 3: XGraaSStpOnaaeet.e.....
Input: = = (x, E 3, (v v²) E 2 a.
yt argminges gey
V VyrA (T (v). V (2),0) - V 8h (ú) (following ())
3 x+ + (1r(
yt argmingey Return: (ut,yt,gt)
V Vyrk (2
(xt - (a) (z), 9) + Vgg 8h (g)
We defer proof of the following to Section 3.2 of the supplement, it is similar to Lemma 6 We remark that the auxiliary sequence y. 5/ used in the extragradient step oracle definition is itself inspired by running few steps of descent method divergence sequence used by the outer loop to pay for inaccuracy in the subproblem solution. Lemma 7,
the subproblem, inducing telescoping
For B 2 a 2 3, Algorithm is an (a, -))eerrggrrrriennn step oracle.
3.3 Proof Theorem 1
Theorem 1.
There is an algorithm (stated in full as Algorithm 4 in the supplement) deterministically computing an c-approximate saddle point to ① in time
|All-- log d
Inz((A)
Proof. We briefly describe the algorithm from the supplement for completeness here, as correctness follows straightforwardly from combining Corollary [ with Lemmas [] The algorithm an instance of the conceptual Algorithm 1 Each step of Algorithm then first implements Algorithm 2 (used in Lemma(5), with the parameters required by Lemma[4] to obtain a gradient step oracle. Simi- larly, it next implements Algorithm (used in Lemma 7). with the parameters required by Lemma 4 to obtain an extragradient step oracle. Correctness follows from Corollary [ For the runtime, without
loss of generality nnz( A) 2 max(n, d) (else may drop columns rows appropriately), and each of T iterations is dominated by a constant number of matrix-vector multiplications.
Acknowledgements
We would like thank our long-term collaborators Yujia Jin and Aaron Sidford for many helpful discussions at earlier stages of this project, which improved our understanding of area convexity. We also thank Victor Reis for his collaboration on related ideas this work in [JRT23]. Finally, we thank anonymous reviewers for their helpful suggestions in improving our presentation.
10

---

References
[AJ]*22] Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi- streaming bipartite matching in fewer passes and optimal space. In Proceedings the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 627-669. SIAM, 2022.
[AK07] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pages 227-236, 2007.
[AL17] Zeyuan Allen-Zhu and Yuanzhi Li. Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU, In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, pages 116-125, 2017.
[ALdOW 17] Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 890-901. IEEE Computer Society, 2017.
[AP20] Jason M. Altschuler and Pablo Parrilo. Approximating min-mean-cycle for low- diameter graphs in near-optimal time and memory. CoRR, abs/2094.03114v1, 2020.
[AW21] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms, SODA 202/, pages 522-539, SIAM, 2021.
[AWR17] Jason M. Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time ap- proximation algorithms for optimal transport via sinkhorn iteration. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 1964-1974, 2017.
[BBNI3] Michel Baes, Michael Bürgisser, and Arkadi Nemirovski. A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems. SIAM J. Optim., (342):9349622, 2013.
[BBT17] Heinz H. Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity: First-order methods revisited and applications. Math. Oper. Res., (2(2))3300-34 2017.
[BJKS18] Jose H. Blanchet, Arun Jambulapati, Carson Kent, and Aaron Sidford. Towards optimal running times for optimal transport. CORR, abs/1810.00711 2018.
[BSW19] Digvijay Boob, Saurabh Sawlani, and Di Wang. Faster width-deeendent algorithm for mixed packing and covering lps. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019,
pages 15253-15262. 2019.
[CDG19] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in ninrry-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2755-2771 SIAM, 2019.
[CDST19] Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 I sketch for matrix multiplicative weights. In Conference on Learning Theory. COLT 2019, volume 99 of Proceedings of Machine Learning Research, pages 589-623, PMLR, 2019.
[CG18] Yu Cheng and Rong Ge. Non-convex matrix completion against semi-random adversary. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1362-1394, PMLR, 2018.
[CKL++2]] Li Chen, Rasmus Kyng, Yang Liu, Richard Peng. Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 612-623, IEEE, 2022.

---

[CLS21] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multipiication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
[CMTV17] Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's 's method and interior point methods. In 58th IEEE Annual Symposium Foundations of Computer Science, FOCS 2017, pages 902-913. IEEE Computer Society, 2017.
[CMY20] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. In 61 IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2020, pages 141-148. IEEE, 2020.
[CST21] Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative lipschitzness in extragra- dient methods and a direct recipe for acceleration. In 12th Innovations Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPlcs, pages Schloss Dagstuhl- Aeiiniiz-enntrum für Informatik, 2021.
18.
[DGK18] Pavel E. Dvurechensky, Alexander V. Gasnikov, and Alexey Kroshnin. Computa- tional optimal transport: Complexity by accelerated gradient descent is better than by sinkhorn's 's algorithm. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, volume 80 of Proceedings of Machine Learning Research, pages 1366-1375. PMLR, 2018.
[DW722] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. CoRR, abs/2210.100 10173, 2022.
[2] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving SDP faster: robust IPM framework and efficient implementation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 233 244. IEEE, 2022.
[JIST22] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized box-simplex games and dynamic decremental bipartite matching. In 49th International Colloquium Automata, Languages, and Programming, ICALP 2022, volume 229 of LIPIcs, pages 77:1-77:20. Schloss Dagstuhl- Seibbizz-Zentun für Informatik, 2022.
[JK Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 61 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 910-918, 2020.
[ Arun Jambulapati, Jerry Li, Christopher Musco, Aaron Sidford, and Kevin Tian. Fast and near-optimal diagonal preconditioning. CoRR, abs/2008.01 017222. 2021.
[JL220] Arun Jambulapati, Jerry Li, and Kevin Tian. Robust uub-gaussian principal component analysis and indth-inddeeeneet schatten packing. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, MariiaFlorina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[JT223] Arun Jambulapati, Victor Reis, and Kevin Tian. Linear-sized sparsifiers via near-linear time discrepancy theory. CoRR, abs/2305.08434, 2023.
[JSTI9] Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct Ö(1/E) iteration parallel algorithm for optimal transport. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 11355- 11366, 2019.
[KLOS14] Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost- linear-time algorithm for approximate max flow in undirected graphs, and its multi- commodity generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2014, pages 217-226. SIAM, 2014.
12

---

[KPT* 17] Soheil Kolouri, Se Rim Park. Matthew Thorpe, Dejan Slepcev, and Gustavo K Rohde. Optimal mass transport: signal processing and machine-leaming applications. IEEE Signal Processing Magazine, 34(4):43-59; 59, 2017.
[KV05] Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3):291-377, 2005.
[LFN18] Haihao Lu, Robert M. Freund, and Yurii E. Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim,, 33:333333-34 2018.
[LHJ19] Tianyi Lin, Nhat Ho, and Michael I. Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97 of Proceedings of Machine Learning Research, pages 3982-3991. PMLR, 2019.
[LHJ22] Tianyi Lin, Nhat Ho, and Michael I. Jordan, On the efficiency of entropic regularized algorithms for optimal transport. Journal of Muchine Learning Research, 23(137):1 1-42, 2022.
[LMR19] Nathaniel Lahn, Deepika Mulchandani, and Sharath Raghvendra. A graph theoretic additive approximation of optimal transport. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 13813 13813-13823, 2019.
[LS15] Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium Foundations of Computer Science, FOCS 2015, pages 239.249..0 IEEE Computer Society, 2015.
[LS17] Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing. STOC 2017, pages 678-687 ACM, 2017.
[Nem04] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization. 15(1):229-25 251, 2004.
[Nes05] Yurii Nesterov. Smooth minimization of non-smooth functions. Math. Program., 103(1):127-152, 2005.
[Nes07] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequali- ties and related problems. Math. Program., 109(2-3):319-344 2007.
[PC19] Gabriel Peyré and Marco Cuturi. Computational optimal transport. Found. Trends Mach. Learn., 11(5-6):355 607, 2019.
[TTZ16] Richard Peng, Kanat Tangwongsan, and Peng Zhang. Faster and simpler width- independent parallel algorithms for positive semidefinite programming. CoRR, abs/1201.51 3,33,, 2016.
[Qua20] Kent Quanrud. Nearly linear time approximations for mixed packing and covering problems without data structures or randomization. In 3rd Symposium on Simplicity in Algorithms, SOSA 2020, pages 69-80. SIAM, 2020.
[She17] Jonah Sherman. Arca-convexity, lo regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 452-460. ACM, 2017.
[ST18] Aaron Sidford and Kevin Tian. Coordinate methods for accelerating 6x0 regression and faster approximate maximum flow. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 922-933. IEEE Computer Society, 2018.
13

---

[vdBLL 21] Jan van den Brand, Yin Tat Lee. Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and & rrrressssionn in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 859-869, 2021.
[WK06] Manfred K. Warmuth and Dima Kuzmin. Randomized PCA algorithms with regret bounds that logarithmic in the dimension. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Anmual Conference on Neural Information Processing Systems, 2006, pages 1481-1485 2006.
[ZLO16] Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia. Using optimization obtain width-indeeendent, parallel, simpler, and faster positive SDP solver. In Proceedings of the Twenty-Sevnnth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2016, pages 1824-1831. SIAM, 2016.
[2015] Zeyuan Allen Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 229-236. ACM, 2015.
[ZP96] Uri Zwick and Mike Paterson. The complexity of mean payoff games graphs. Theor. Comput. Sci., 158(18811)))) 158(112)3343333) 1996.
14


Reviews:
[{"review_id": "HFfmAEOdEc", "reviewer": "Reviewer_mAce", "summary": "This paper explores the relationship between area convexity and extragradient methods, and provides improved solvers for subproblems required by variants of the algorithm. The paper also presents a state-of-the-art first-order algorithm for solving box-simplex games and a near-linear time algorithm for a matrix generalization of box-simplex games. The authors demonstrate that their algorithms improve runtimes for combinatorial optimization problems and provide new insights into numerical linear algebra. The contributions of the paper include the development of efficient algorithms with improved convergence rates and computational efficiency, as well as the application of these algorithms to various optimization problems in fields such as optimal transport and min-mean-cycle.", "questions": "Regarding Weakness 1: The author claims to have improved the runtime of multiple applications by solving the Box-simplex problem. However, a detailed comparison with previous results is not provided. Providing such a comparison would help readers better understand the level of improvement and contribution of the paper.\n\nRegarding Weakness 2: The paper mentions the use of a proximal oracle in Algorithm 6. Could the authors provide more details on the implementation and computational complexity of this oracle? It would be helpful to understand how the proximal oracle contributes to the overall efficiency of the algorithm and whether there are any limitations or challenges in its practical implementation.\n", "limitations": "The paper does not discuss the limitations and any potential negative consequences of their work. However, since their algorithm is focused on optimization problems, the impact on society would largely depend on the specific applications and use cases. A brief discussion on the potential real-world implications and ethical considerations would provide valuable context for readers to better understand the broader implications of the research.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Through a deeper understanding of the relationship between box-simplex games and matrix generalization problems, the authors propose improved solvers that leverage the lens of relative smoothness and convex analysis to design efficient algorithms with faster runtimes. These proposed algorithms not only improve runtimes for combinatorial optimization problems but also provide new insights into numerical linear algebra and have applications in various combinatorial optimization problems such as approximate maximum flow, optimal transport, and min-mean-cycle.\n\nIn addition to its technical contributions, the paper is well-written, well-structured, and effectively communicates its main ideas and contributions. The authors present a rigorous analysis of the proposed algorithms, complete with detailed proofs, explanations, and appropriate use of mathematical notation. The inclusion of appendix sections, examples, illustrations, and a comprehensive literature review further enhance the quality, readability, and accessibility of the work.\n\nOverall, the strengths of this paper lie in its thorough exploration of area convexity, its innovative use of relative smoothness, and the development of improved algorithms for solving optimization problems. \n", "weaknesses": "1.\tThe author claims to have improved the runtime for the Box-simplex problem, resulting in increased performance of related applications. However, a detailed comparison with previous results is not provided. Providing such a comparison would help readers better understand the level of improvement and contribution of the paper.\n2.\tThe paper mentions the use of a proximal oracle in Algorithm 6, but more details on its implementation and computational complexity would be helpful. It would be valuable for the authors to discuss how the proximal oracle contributes to the overall efficiency of the algorithm and whether there are any limitations or challenges in its practical implementation.\n3.\tThe paper could benefit from experimental evaluation to validate the proposed approach. Conducting experiments on real-world or synthetic datasets would provide empirical evidence of the effectiveness and efficiency of the alternating minimization scheme.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reviewing efforts. We are glad that you found our technical contributions interesting and our paper easy to read. \n\nRegarding prior box-simplex game solvers, our paper is most directly comparable to [She17], which it improves upon by a logarithmic factor in the runtime by removing the need for high-accuracy alternating minimization. The [She17] result was viewed as a breakthrough in the optimization community (and has not been improved since prior to our work), as previously for box-simplex games, first-order algorithms incurred an additional overhead of $\\min(\\epsilon^{-1},\\sqrt{d})$ in the iteration count. Higher-order algorithms such as interior point methods also incurred polynomial overhead in runtime due to the need to solve linear systems. We agree this comparison is valuable context and not explicit, and will add it in a revision. We also note that we summarize our new results for applications in Section 5 of the supplement, though there too we will add a more explicit comparison to prior work (in all cases, we remove an extraneous log factor).\n\nWhile the improvement of Theorem 1 over [She17] is somewhat modest, it improves the runtime of box-simplex games to be comparable to state-of-the-art deterministic algorithms for the easier simplex-simplex setting (which have not been improved in 20 years) under a more challenging problem geometry, so we conjecture it is optimal up to constant factors; we believe closing this gap has additional merit. Finally, the tools we introduce to obtain our result generalize readily to the box-spectraplex setting, overcoming obstacles from prior analyses as explained in Section 2.2.\n\nRegarding Algorithm 6, we note that this is just a conceptual framework for extragradient algorithm design we introduce, and for specific problems care must be taken to handle any inexactness in the proximal oracle implementation. For the box-simplex and box-spectraplex game applications we study, we follow the framework of Algorithm 6 and provide end-to-end inexactness analyses and (near-linear) runtime guarantees for our results. \n\nRegarding practical implementations, our main motivation in this work was clarifying and improving a theoretical tool, area convexity, which has found use in practical problems we believe are of value to the NeurIPS community (optimal transport, matching, min-mean-cycle, etc.), and showing how the same tool extends to solve semidefinite programming variants. While promising empirical evaluations of area convex algorithms for solving these applications on real-world examples have been conducted in prior works (see e.g. [JST19]), we agree that an important next step is to benchmark our improved algorithm against them.\n\nWe hope this response was clarifying, and elevates your opinion of our paper. Thank you again for your helpful suggestions, and we will take care to incorporate them in future versions."}, {"review_id": "SREwCnnu3M", "reviewer": "Reviewer_Wg5p", "summary": "In this paper, the authors consider box-simplex games, a bilinear min-max optimization problem with box and simplex constraints. The current best-known method for solving such problems is Sherman's algorithm, which is based on the concept of \"area convexity\". The key insight of this work is to reinterpret area convexity as a more general notion of relative Lipschitzness in the optimization literature. Using this new perspective, they streamline the proof of Sherman's algorithm, propose an improved subproblem solver that eliminates the additional log overhead, and further extend the algorithm to box-spectraplex games. ", "questions": "- In Definition 4, the notation $V_z^{\\alpha}$ is undefined. \n- If I understand correctly, both the GradStepOracle and XGradStepOracle are designed for solving the same kind of subproblem (at the bottom of page 6). Could you explain why they are implemented differently? And how are they related to the algorithm in [LFN18]?", "limitations": "The authors addressed the limitations by specifying the considered problem class.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors show that area convexity implies a Bregman divergence bound similar to relative Lipschitzness, which is a simple yet insightful observation. I appreciate that it better clarifies the connection between Sherman's algorithm and the classical extragradient methods, making it conceptually easier to understand and extend. \n- The proposed subproblem solver improves a $\\log(1/\\epsilon)$ factor from the original Sherman's algorithm. As a corollary, it leads to the state-of-the-art runtime complexity for optimal transport among first-order algorithms. ", "weaknesses": "I only wish the presentation of the paper could be more clear. In particular, the proposed extragradient algorithm is not fully described in the main text, but only implicitly in the proof of Theorem 1. It would be better if the authors can present the pseudocode and better explain the steps in the algorithm. Also, it is a bit confusing that the supplement is an extended version of the paper rather than the appendix, which makes it a bit hard to track down the proof.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments, and we are glad that you found our technical contributions insightful. We agree with your suggestions regarding the supplement, and outline some directions for improvement in the global response (though we are happy to incorporate any further suggestions as well). Regarding pseudocode for Theorem 1, our exclusion was largely due to space restrictions (in particular, Algorithm 3 in the supplement contains full pseudocode for our algorithm). However, we will provide a more explicit explanation before the proof for clarity. To our understanding the final conference version would have an additional allowed page, so if our paper is accepted we will use it to add clarity to this section of the paper.\n\nThank you for pointing out our oversight in Definition 4, which we will also address in a revision.\n\nRegarding your question on asymmetry in the steps of our method, this reflects an asymmetry in the analyses of extragradient methods. In these, the regret is bounded for the “gradient oracle” points, but the regret upper bound is stated in terms of the divergences of the “extragradient oracle” points (which our inexact oracles need to compensate for). Our oracle implementations are not directly related to the algorithm in [LFN18], which was designed for iterative convex minimization (as opposed to our method, a one-shot subproblem solver for a minimax optimization problem), but certainly our analysis is inspired by theirs through the commonality of the tool we use (relative smoothness). We will add this discussion for clarity in a revision as well."}, {"review_id": "ahXauOfUtJ", "reviewer": "Reviewer_E7hD", "summary": "This paper looks at the bilinear min-max problem Area Convexity framework proposed by Sherman through the lens of Relative Lipschitzness condition of Cohen et al. which relates to the standard Bregman analysis in mirror-type algorithms in first-order optimization. Leveraging this connection, they provide the standard analysis of two-timescale Extragradient method for area convex regularizer based Bregman divergence. Tuning a parameter in the analysis and using the structure of the area convex regularizer, they implement an approximate version of Extragradient where each approximate iteration requires O(nnz(A)) computations. This allows them to remove the log(1/\\eps) factor Sherman incurred in the analysis of inner loop. The extend similar result to the case where ", "questions": "My questions below are referring to the supplementary material (or actual paper).\n\n1. It would be best if you can explain how steps 7,8,9 relate to steps in Algorithm 1 with exact parameters used for it. Leaving it as \"By observation\" may not work for large fraction of readers. Same goes for steps 14-17. It would also be worthwhile to remind the reader that h is the entropy divergence function used here.\n2. The proof of Lemma 6 needs to deliberate more on what F to use define f(y-hat) in (13) such that Lemma 4 can be applied.\n3. Use x_br for two different purposes in the same section is a bad notation. In particular, Lemma 4 defines x_br as argmin F(x,y) for F defined Section 2.2 of the main paper (again, I could not find it in the supplementary paper). Is this the same used in Lemma 6?\n4. Remind the reader about H at the beginning of Section 4.\n5. In the Proof of Lemma 8, you use Theorem 3.3 of LS01. It would be better if you provide the result as there is already quite a bit of jumping around while reading the paper. I haven't been able to verify the claims in the proof of this lemma.\n6. I have read some of the references in the previous paper of this area. Can you also comment BSW19 paper? As I understand, they also implement Shermans MWU algorithm for inner subproblems and hence incur log(1/\\eps) additional factor similar to Sherman or JST19. \n7. Can you also compare the result for box-spectraplex case with BBN13, AL17, CDST19? In particular, it will be better to state clearly in what regimes Algorithm in Section 4.4 would be better than box-spectraplex variations of the above papers.\n\n\nBSW19: Faster width-dependent algorithm for mixed packing and covering LPs", "limitations": "I am giving this paper borderline accept since it was not very well written and almost seems like reading two papers at a time which borrows/uses existing literature heavily (sometimes without giving context). If properly written, this paper can be improved substantially. But that will require significant rewriting and hence, I don't see how it will be justified in this conference set up.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper had a new ideas. E.g., tuning parameter alpha/beta in the regularizer was critical step that allowed for approximate implementation as done in Line 5-9 and Line 12-17 of Algorithm 3.", "weaknesses": "The main weakness of the paper is in its presentation. The way main paper differs from the supplementary almost feels like reading a new paper with different orders, equation numbers etc. Also, there are concepts introduced which may not be directly relevant to the problem at hand: E.g. Definition 1 is not used throughout the main paper. I had to dig until Appendix B to understand why there was a fuss about it on the very first technical section, i.e., Section 2.1.\nThe paper borrows key ideas developed by Sherman (which are popular by now) and some previous developments such as Lu et al, and Cohen et al. In particular, the idea of Area Convexity is very much exclusively used for bilinear games and there has been no major movement towards general convex-concave problems. In that sense, this is an incremental work in my opinion.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reviewing efforts and many helpful comments. We agree with the revisions suggested by your Questions 1, 2, 3, 4, and 5, and will incorporate them. Regarding Question 1, in the main body of our revision, we will include an “abstract” variant of Algorithm 3 in the supplement which calls Definitions 4 and 5 directly and precisely states what parameters are used in the calls (these parameters are stated in the proof of Theorem 1, though we agree they can be made more explicit). Regarding Question 2, the function $F$ in the application of Lemma 4 is the joint function of $x$ and $y$ defined in (11) of the supplement (before minimizing over $x$), but we will clarify this. Regarding Question 3, we agree the overloaded notation is confusing and this will be clarified; the use of notation $x_{\\text{br}}$ in Lemma 6 is  consistent with the use in Lemma 4 with a specific choice of $F$. Regarding Question 5, we will explain in self-contained terms the result from [LS01], which is that the gradient of a spectral function (on matrices) agrees with its vector gradient on the eigenvalues.\n\nRegarding Question 6, we agree that [BSW19] is a relevant paper to this line of work and will include a citation, and that it suffers from the same logarithmic overhead in runtime due to its reliance on alternating minimization as in [She17]. In the process of completing this work, we actually reached out to the authors of [BSW19] because they did not include a proof of correctness that their alternating minimization converges, which we had some doubts about because their setup has different properties than [She17]. They have not yet gotten back to us with a proof of correctness, so we were unsure how to address this point in the submission.\n\nRegarding Question 7, consider the problem of solving a box-spectraplex game with Lipschitz constant $L$, as defined in Theorem 2 of our paper. Compared to [BBN13, AL17, CDST19], our algorithm incurs an overhead of $L/\\epsilon$ in the runtime, but saves a factor of $d^2$ (the dimension of the matrices) due to the size of $\\ell_1$-strongly convex regularizers over the $\\ell_\\infty$ ball (the box, as opposed to the simplex which [BBN13, AL17, CDST19] are tailored to handle). By using “half-regularized” strategies as discussed in the introduction of [She17], we believe this $d^2$ overhead can be improved to a $d$, but the analysis of low-rank sketches used in [BBN13, AL17, CDST19] becomes more challenging. In summary, we lose a $L/\\epsilon$ factor but save at least a $d$ (and possibly a $d^2$ factor) over these methods, which is favorable in the setting where first-order methods are preferred over e.g. interior point methods in the first place (when $L/\\epsilon$ is small compared to $d$).\n\nWe acknowledge your concerns on readability and will take steps to address them, summarized in our global response. We believe our conceptual contributions and algorithmic improvements can be understood from the shortened version of our paper, and thus our work is appropriate for publication at NeurIPS; we hope that aligning our presentation more closely between the shortened version and the supplement will help bridge the gap in readability. Regarding the incrementality of our results, we conjecture our Theorem 1 is optimal within a constant factor as it matches state-of-the-art deterministic algorithms in the easier simplex-simplex setting (which have not been improved in 20 years) under a more challenging problem geometry; we hence believe there is further merit in closing this gap. Finally, the tools we introduce to obtain our result generalize readily to the box-spectraplex setting, overcoming obstacles from prior analyses as explained in Section 2.2.\n\nWe hope this discussion clarifies and elevates the merits of our paper to you. Thank you again for all the detailed feedback from a reviewer familiar with the line of work on area convexity."}, {"review_id": "EmbCBZlp4F", "reviewer": "Reviewer_Vb7x", "summary": "The authors study first-order algorithms for box-simplex games, a special kind of two-player zero-sum bi-affine constrained games. The constraints of these games dictate that the first player selects an action represented by a vector within the n-dimensional box ($[-1,1]^n$), while the second player chooses an action defined by a vector from the d-dimensional simplex ($\\Delta_d$).\n\nThe authors show an algorithm for the computation of an $\\epsilon$-approximate saddle point of a box-simplex bi-affine game, expressed as $min_{x\\in[-1,1]^n,y\\in\\Delta_d} x^T A y^T - <b,x> + <c,y>$, in time $O(nnz(A)\\cdot L \\cdot\\log(d)/\\epsilon)$, where L is the maximum 1-norm of any column of A, and nnz(A) denotes the number of non-zero entries in matrix A. They advance over the previously best-known first-order method by Sherman, removing logarithmic terms.\n\nBox-simplex games has some important applications, and the authors' algorithm introduces a new state-of-the-art, including applications like approximate max flow and optimal transport.\n\nIn the latter part of the paper, the authors broaden their focus to include a new class of two-player games: box-spectraplex games. This is a generalization of box-simplex games where one player still picks an action in a n-dimensional box ($[-1,1]^n$), but the other player chooses as an action, a positive semi-definite matrix Y with trace equals to 1. An applications of these kind of games include spectral sparcification. The authors present a first-order algorithm to computing an approximate saddle point of a box-spectraplex game.\n\n\nAfter rebuttal: The author's rebuttal successfully addressed my concerns, and as a result, I have chosen to maintain my original score.", "questions": "Could the authors provide more examples of problems that could be simplified to box-spectraplex games?\n\nI was a bit confused in the proof sketch of Theorem 1. For the telescoping sum to be valid, it appears necessary that $\\bar{y}_{t+1}$ must equal $\\bar{y}^+_t$ (where $\\bar{y}_t$ represents the input to the extra gradient step-oracle at step t, and $\\bar{y}^+_t$ indicates the output of the extra gradient oracle at step t). However, upon reviewing Algorithm 3 in the supplementary material, different notation seems to be used. Could the authors provide clarification on this?", "limitations": "The authors list any assumptions for their theorems, and I do not believe this work can have negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper studies an interesting class of games with important applications, thereby contributing to the current state-of-the-art algorithm. Moreover, the authors novel reinterpretation of the area-convexity as the more standard relative smoothness allows for the use of more conventional analysis methods, which is interesting on its own. I looked at the statement of the lemmas and they seem reasonable. I only verified the proofs in the main body.", "weaknesses": "In the spirit of constructive criticism, I believe that the writing could be improved for better readability. Currently, the appendix appears more like a journal version of the paper rather than serving its intended purpose. A few recommendations to enhance the paper include:\n- On line 63, defining the notation nnz(A) and $||A||_{1\\rightarrow 1}$ earlier might improve clarity.\n- On lines 105-16, it could be beneficial to define the operator $T_{mv}$ sooner.\n- Several references to 'outer' and 'inner loop' throughout the paper lacked clarity. Lines 38, 215, and 224 are examples of this.\n\nFinally, the move towards box-spectraplex games seems to be more theoretical than practical, with limited application examples. Please see the question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback; we appreciate that you found both the problems we study and our insights to be interesting. We agree with your suggestions on presentation, and discussed some potential directions for incorporating them in the global response. We are happy to incorporate any of your further suggestions. We also agree with your notation and naming convention suggestions, and will address these in a revision.\n\nRegarding Theorem 1, indeed, $\\bar{y}_{t + 1}$ is set to be the third argument of the output of Algorithm 2 (denoted $\\bar{y}^+$) in each iteration. In Algorithm 3 in the supplement, we performed this computation explicitly in terms of the inputs of Algorithm 2, which can be verified to be consistent. However, we agree it would be more clear to have a “conceptual” variant of Algorithm 3 which simply explains how the points in the analysis of Theorem 1 are derived from the abstract oracles in Definitions 4 and 5 of the main body, and will provide this in a revision.\n\nRegarding further applications of box-spectraplex games, we note that the community has previously not provided any nontrivial algorithms for this problem beyond black-box applications of non-tailored methods (or even defined it explicitly to the best of our knowledge), likely due to the lack of progress even in the box-simplex case until recently [She17]. We find it encouraging that recent work [JRT23] was already able to use our result to obtain improvements for a fundamental problem, and are hopeful that other previous applications of positive SDP solvers (as outlined in Page 3 of the main submission) may also be amenable to our tools. At the moment we do not have other examples of applications of box-spectraplex games, but we believe this is outside the scope of our submission (whose goal was to provide the first near-linear time solver), and consider this an exciting direction opened up by our result."}, {"review_id": "Wr6ltnhw8R", "reviewer": "Reviewer_Cfry", "summary": "This paper focuses on box-simplex games that are min max of degree 2 polynomials being bilinear in the inner and outer optimization variables. The inner problem is over the simplex and the outer problem is over the unit hypercube. The goal of the paper is to unify the previous framework derived in [She17] with standard Bregman divergence domination conditions. \nThis latter framework [She17] consists on exploiting the primal-dual nature of the min-max problem to setup a regularizer over the unit hypercube. This satisfies the so-called \"area convexity\" condition instead of strong convexity. The outer loop method relies on an extragradient method and the inner loop relies on an alternating minimization sub-procedure.\nIn order to analyze this framework, the authors explain the connections with relative smoothness and extragradient methods.\nThis yields an algorithm to solve box-simplex games that improves the one of [She17] by a log factor. \n", "questions": "- after l72 (2): could you please define Delta^(dxd) (the set of trace 1 PSD matrices)? \n\n- In (4) what is h?\n", "limitations": "There is no limitation section provided by the authors in the main submission. \nThe authors do not address any limitation and do not provide any further research directions.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and I believe quite clear for non-experts in this field. \nThe authors are willing to bridge the gap between area convexity and more standard convexity tools, that makes the contribution original. \nThe proof sketches sound correct. \n", "weaknesses": "I am not a specialist in this field and with a very limited amount of time (too short to read the 39 pages of supplementary material), it is completely impossible to judge whether the framework is correct or not. The authors stated the main theorems and did provide proof sketches and hints that could possibly convince some readers. I have doubts that this work, possibly sound and surely interesting, could be a good fit with NeurIPS.\n\nThere are neither concrete algorithmic implementation nor benchmarking in the main submission document.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts. We are happy to hear that you found our paper well-written and interesting, and that you felt it was understandable for non-experts. \n\nWe would like to note to the reviewer that the format and scope of our paper, which addresses a fundamental theoretical problem of interest in machine learning applications, is similar to many of the theoretical papers which have appeared in past NeurIPS conferences, and we believe it is a good fit for the venue. If the reviewer has specific concerns about the correctness of any portion of our paper, we are of course happy to answer any questions or provide an explanation. Our proofs of correctness are self-contained and provided in full in the supplement.\n\nRegarding practical implementations, our main motivation in this work was clarifying and improving a theoretical tool, area convexity, which has found use in practical problems we believe are of value to the NeurIPS community (optimal transport, matching, min-mean-cycle, etc.), and showing how the same tool extends to solve semidefinite programming variants. While promising empirical evaluations of area convex algorithms for solving these applications on real-world examples have been conducted in prior works (see e.g. [JST19]), we agree that an important next step is to benchmark our improved area convex algorithm against them.\n\nThe set name $\\Delta^{d \\times d}$ is reserved for the spectraplex, and the function name $h$ is reserved for entropy; both are defined in Section 1.3, but we will make this more clear when they appear. We agree that the inclusion of $\\Delta^{d \\times d}$ in (2) before it is defined is an oversight which we will address; thank you for pointing this out.\n\nRegarding limitations and extensions, we give a brief outline of how future work can improve Theorem 2 by using low-rank sketching tools after its statement (with an extended discussion in Section 1.2 of the supplement), but agree this can be more explicitly stated. We also believe Theorem 1 may be optimal up to constant factors due to the lack of progress in the historically easier simplex-simplex case (see Footnote 6), which Theorem 1 matches; however, proving a formal lower bound is an important future endeavor. Moreover, area convex algorithms appear to be specialized to bilinear settings such as linear and semidefinite programming currently; finding nonlinear generalizations (as suggested by another reviewer) would be an exciting extension of these tools. Finally, finding more applications and improving practical implementations of our algorithms are important extensions of this line of research. We will add these points in a revision of our paper; thank you for raising them.\n\nWe hope this discussion was clarifying to the reviewer and improves your opinion of our paper."}]

Author rebuttal:
Reviewers Wg5p, E7hD, and Vb7x asked about inconsistencies between our main submission and supplementary material which hindered readability. We thank you for raising this important concern and completely agree; we will make efforts in a revision to make the two more consistent. Specifically, after all deferred proofs or contents in the main submission, we will add an explicit pointer to where the corresponding part of the supplement can be found. We will also order the two parts in a more compatible way (trying to preserve theorem names, etc. whenever possible), and make the main submission more self-contained by eliminating unused parts.

Meta-review: The paper provides new insights into area convexity, and connects it to more standard gradient descent analyses. Building on these insights, the paper obtains modest but meaningful improvements in the running times for well-motivated combinatorial problems. There were concerns about the presentation of the paper and whether the algorithmic framework is correct and theoretically sound, which were sufficiently addressed by the author response and the subsequent discussion.
Decision: Accept (poster)