Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

Kyng, Rasmus; Sulser, Aurelio L.

doi:10.4230/LIPIcs.ICALP.2026.136

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

Rasmus Kyng

ETH Zurich, Switzerland Aurelio L. Sulser

ETH Zurich, Switzerland

Abstract

We present the first polylog-depth, nearly-linear-work parallel algorithm that achieves a $(1+\varepsilon)$ -bicriteria approximation guarantee for undirected minimum-cost flow on expanders. Fix an undirected graph $G=(V,E)$ with unit capacities, unit lengths, and conductance $\phi$ . For any feasible demand vector $\mathbf{d}$ and any $\varepsilon\in(0,1)$ we compute, in $\widetilde{O}\!\big(\frac{|E|}{\varepsilon\phi}\big)$ work and $\widetilde{O}\!\big(\frac{1}{\varepsilon\phi}\big)$ depth, a flow $\mathbf{f}$ that routes $\mathbf{d}$ exactly while satisfying

\|\mathbf{f}\|_{\infty}\leq 1+\varepsilon\qquad\text{and}\qquad\|\mathbf{f}\|_% {1}\leq(1+\varepsilon)\min_{\begin{subarray}{c}\mathbf{Bg}=\mathbf{d}\\ \|\mathbf{g}\|_{\infty}\leq 1\end{subarray}}\|\mathbf{g}\|_{1}.

This bicriteria guarantee simultaneously controls congestion and total cost, strengthens the previously studied notion of throughput error, and matches the best known $\varepsilon$ -dependence for parallel maximum flow/transshipment on general graphs.

Our main contribution is a new saddle-point optimization method for mixed $\ell_{\infty}$ - $\ell_{1}$ optimization. Concretely, we (i) formulate a two-term regression capturing minimum-cost flow as a saddle-point problem that couples $\ell_{\infty}$ and $\ell_{1}$ terms, (ii) construct a small-magnitude area-convex regularizer tailored to the resulting primal–dual domain (building on Sherman’s area-convexity framework [23]), and (iii) implement efficient $\delta$ -approximate maximization/minimization oracles so that Sherman’s extragradient iteration yields low iteration-count convergence.

Beyond the concrete expander result, our mixed $\ell_{\infty}$ - $\ell_{1}$ optimization toolkit appears broadly applicable and suggests a promising route toward $\widetilde{O}(m/\varepsilon)$ work and $\widetilde{O}(1/\varepsilon)$ depth algorithms for approximate undirected minimum-cost flow on general graphs. ¹¹1We use $\widehat{O}(\cdot)$ to hide subpolynomial factors and $\widetilde{O}(\cdot)$ to hide polylogarithmic factors. We allow hiding such factors that depend on $m$ , the size of the input graph, e.g., $\operatorname{polylog}(m)=\widetilde{O}(1)$ . We assume polynomially bounded inputs.

Keywords and phrases:

Approximate Min-Cost-Flow, Parallel, Area-Convexity, Expanders

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Convex optimization

Funding:

The research leading to these results has received funding from the starting grant “A New Paradigm for Flow and Cut Algorithms” (no.

TMSGI2\_218022

) of the Swiss National Science Foundation.

DOI:

10.4230/LIPIcs.ICALP.2026.136

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction: Toward Parallel Flow Algorithms

The last two decades have seen major progress on fundamental graph algorithmic questions, including, prominently, algorithms for solving flow and cut problems. A key driver of progress has been novel uses of continuous optimization. Continuous optimization plays a central role in the nearly-linear electrical flow algorithm of Spielman and Teng [25], the almost-linear time approximate undirected maximum flow and transshipment algorithms of Sherman [22, 24] and Kelner et al. [16], the $\widetilde{O}(m^{3/2})$ time minimum-cost flow algorithm of Daitch and Spielman [7], and the almost-linear time algorithm for minimum-cost flow of Chen et al. [6], and numerous other flow and cut algorithms.

The work of Chen et al. [6] settled the time complexity of single-commodity flow problems up to subpolynomial factors. In the world of parallel algorithms, answers are much less complete. Polynomial capacity maximum flow is in RNC [18, 14] with large polynomial work but all known subquadratic work algorithms need polynomial depth. When restricting to almost or nearly-linear work, only very recently was approximate maximum flow and transshipment shown to be solvable in polylogarithmic depth [17, 2, 1] for $(1+1/\operatorname{polylog}(n))$ approximation. This brings us to the frontiers of parallel flow algorithms. Here a very interesting case is the problem of undirected minimum-cost flow, defined as

\min_{\begin{subarray}{c}\text{flow }\mathbf{f}\text{ routes demand }\mathbf{d% }\\ ||\mathbf{C}^{-1}\mathbf{f}||_{\infty}\leq 1\end{subarray}}\left\|\mathbf{L}% \mathbf{f}\right\|_{1}

(1)

where we seek a flow $\mathbf{f}$ that routes given demands $\mathbf{d}$ in an undirected graph $G=(V,E)$ with positive edge capacities $\bm{\mathit{c}}\in\mathbb{R}^{E}_{+}$ and lengths $\mathbf{l}\in\mathbb{R}^{E}_{+}$ , and $\mathbf{C}=\operatorname*{diag}(\bm{\mathit{c}})$ and $\mathbf{L}=\operatorname*{diag}(\mathbf{l})$ . Here $||\mathbf{C}^{-1}\mathbf{f}||_{\infty}$ measures how much the flow congests the edges w.r.t. capacities $\bm{\mathit{c}}$ and $\left\|\mathbf{L}\mathbf{f}\right\|_{1}$ measures the “length” of the flow w.r.t. edge lengths $\mathbf{l}$ . Note that the congestion threshold $||\mathbf{C}^{-1}\mathbf{f}||_{\infty}\leq 1$ is without loss of generality, even in unit capacity graphs, as we can convert the more general constraint $||\mathbf{C}^{-1}\mathbf{f}||_{\infty}\leq\rho$ into this case by rescaling the demand vector to $\mathbf{d}/\rho$ . A sequential, almost–linear-time approximation algorithm for this problem was first given by Bernstein et al. [5]. Their algorithm runs in $\widehat{O}(m)$ time and achieves throughput error $\epsilon=1/\operatorname{polylog}(n)$ . This result was later parallelized in [11], yielding $\widehat{O}(1)$ depth. Throughput error is a strictly weaker notion of approximation than the guarantees provided by earlier approximate maximum flow and transshipment algorithms. In particular, a throughput-error guarantee does not produce a flow that approximately routes the full set of demands with near-optimal objective value. Instead, it only ensures that a $(1-\epsilon)$ fraction of the total demand is routed with cost no larger than the optimal cost for the full instance. The residual $\epsilon$ fraction of the demand is allowed to sit at any of the original sources/sinks, and is not generally capacity-respecting routable with $\epsilon$ times the optimal length, and hence cannot be used to construct a flow routing the demands with near-optimal objective value. By contrast, a conventional $(1+\epsilon)$ -approximation to the objective value immediately implies throughput error: one can simply scale the flow down by a factor of $(1+\epsilon)$ . The converse, however, does not hold.

To illustrate the limitation of throughput error, consider a graph with two sources $s_{1},s_{2}$ and a single sink $t$ . Suppose the optimal solution routes $(1-\epsilon)$ units of flow from $s_{1}$ to $t$ and $\epsilon$ units from $s_{2}$ to $t$ , with total length $OPT=((1-\epsilon)+\epsilon\cdot n)\cdot c$ while respecting capacities. Assume further that routing $(1-\epsilon)$ units from $s_{1}$ to $t$ with length $(1-\epsilon)c$ is easy, while routing $\epsilon$ units from $s_{2}$ to $t$ requires length $\epsilon nc$ and is the true source of difficulty in the instance. An algorithm with throughput error $\epsilon$ may choose to route only the easy portion of the demand, returning a flow of length $O P T$ that routes exclusively from $s_{1}$ to $t$ , while leaving the $\epsilon$ units at $s_{2}$ unrouted. However, routing this residual demand still requires length $\epsilon nc\ggg\epsilon\cdot OPT$ . Thus, despite satisfying the throughput guarantee, the algorithm effectively sidesteps the hard part of the problem and yields a trivial, uninformative solution. This pathology becomes more pronounced for flow instances with greater number of sources and sinks. In contrast, our algorithm provides a conventional approximation guarantee. In the above example, it returns a flow that routes exactly $(1-\epsilon)$ units from $s_{1}$ to $t$ and $\epsilon$ units from $s_{2}$ to $t$ , respects capacities up to a $(1+\epsilon)$ factor, and has a total cost of at most $(1+\epsilon)OPT$ . In this sense, unlike algorithms with only throughput-error guarantees, our approach produces a strictly nontrivial and globally meaningful solution.

Understanding the optimization landscape: What lies next in parallel flow algorithms?

While constituting striking progress, the work of Haeupler et al. [11] leaves many questions open:

(Q1)

Can we achieve stronger error guarantees beyond throughput error with a low-depth, almost-linear work algorithm?
(Q2)

Can we, for any reasonable notion of $\epsilon$ error, achieve depth $\widehat{O}(\operatorname{poly}(1/\epsilon))$ and work $\widehat{O}(m\operatorname{poly}(1/\epsilon))$ ?
(Q3)

Can the parallel complexity be further improved to $\widetilde{O}(m\operatorname{poly}(1/\epsilon))$ work and $\widetilde{O}(\operatorname{poly}(1/\epsilon))$ depth?

In this work, we answer these questions in the affirmative for expander graphs, while developing tools that we believe could eventually be used to answer the question affirmatively, even on general graphs.

There are major differences between the parallel approximate transshipment algorithms of Li [17], Andoni et al. [2] and maximum flow algorithms of Agarwal et al. [1] on the one hand and, on the other hand, the parallel approximate algorithm for the more general undirected minimum-cost flow of Haeupler et al. [11]. Firstly, in terms of approximation guarantees, former algorithms achieve a stronger notion of approximation in objective for a flow that routes the given demands. Secondly, the former algorithms build on gradient descent techniques for minimizing $\ell_{\infty}$ -norms, while the latter is inherently based on multiplicative weight methods that repeatedly call a low-width $\ell_{1}$ -norm minimizing oracle. The latter oracle needs to produce $(1+\epsilon)$ -approximate $\ell_{1}$ minimizers in every iteration, while gradient descent methods make it possible to convert $\widetilde{O}(1)$ approximate updates into $(1+\epsilon)$ accurate solutions in few iterations. This means that multiplicative weight methods, in this sense, place much more stringent requirements on the oracle/subroutine that is called in every iteration.

So, why not use a gradient descent method instead? Until now, the reason has been a fundamental obstacle on the optimization side: While excellent low iteration count gradient descent methods are known for $\ell_{\infty}$ -norms, no such methods are known for dealing with $\ell_{1}$ -norms or mixed $\ell_{\infty}$ - and $\ell_{1}$ -norm minimization. This is not just an issue for flow algorithms but a well-known obstacle in continuous optimization broadly. More precisely, parallelizable optimization methods for transshipment, an $\ell_{1}$ -norm minimization problem, can all be interpreted as applying $\ell_{\infty}$ -norm minimization methods on the dual of transshipment, which is an $\ell_{\infty}$ -minimization problem over vertex potentials [24, 26]. Thus, the $\ell_{1}$ -norm minimization problem is solved by “escaping” to the dual $\ell_{\infty}$ -norm minimization problem. But, the undirected minimum-cost flow problem does not allow this trick of “escaping to the dual”, because the primal problem contains both $\ell_{1}$ - and $\ell_{\infty}$ -norms, and hence the dual problem does too.

Area-convexity and flow optimization

Area-convexity is a breakthrough continuous optimization technique developed by Sherman [23] to compute $(1+\epsilon)$ -approximate $\ell_{\infty}$ -norm minimizers in $\widetilde{O}(1/\epsilon)$ iterations, improving over the $\widetilde{O}(1/\epsilon^{2})$ iterations obtained by more basic $\ell_{\infty}$ -gradient descent methods [22, 16].

The central issue motivating Sherman’s development of area-convexity was the following: two famous accelerated gradient methods of Nesterov [20] and Nemirovski [19] can be understood as recasting a convex optimization problem as a convex-concave saddle-point minimax problem, also known as a variational approach. These methods suggests writing a problem of the form $\min_{\bm{\mathit{A}}\bm{\mathit{x}}=\bm{\mathit{b}}}\left\|\bm{\mathit{x}}% \right\|_{\infty}$ as

\min_{\bm{\mathit{A}}\bm{\mathit{x}}=\bm{\mathit{b}}}\max_{\left\|\bm{\mathit{% y}}\right\|_{1}\leq 1}\bm{\mathit{y}}^{\top}\bm{\mathit{x}}

But, applying these methods to such a problem requires finding regularizers $\phi_{\infty}(\bm{\mathit{x}})$ and $\phi_{1}(\bm{\mathit{y}})$ which are strongly convex w.r.t. $\ell_{\infty}$ and $\ell_{1}$ -norms respectively, while also being small in magnitude/range. Unfortunately, for the $\ell_{\infty}$ -norm, these properties are irreconcilable: any $\phi_{\infty}(\bm{\mathit{x}})$ that is 1-strongly-convex with respect to $\|\cdot\|_{\infty}$ on $[-1,1]^{d}$ has range at least $\frac{d}{2}$ on the same region (see [23] for a discussion). Sherman introduced the much weaker notion of area-convexity, and proved it suffices to perform alternating gradient ascent/descent in saddle-point optimization. Moreover, he proved that there exists a small magnitude area-convex regularizer for pairs $(\bm{\mathit{x}},\bm{\mathit{y}})\in[-1,1]^{d}\times\Delta_{d}$ where $\Delta_{d}=\left\{\bm{\mathit{y}}\in\mathbb{R}^{d}:\bm{\mathit{y}}\geq 0,\left% \|\bm{\mathit{y}}\right\|_{1}\leq 1\right\}$ denotes the $d$ -dimensional simplex.

Area-convexity has also been used for $\ell_{1}$ -norm minimization, again by “escaping to the dual” [12]. Area-convex optimization for $\ell_{\infty}$ - or $\ell_{1}$ -norm minimization can be used to improve the $\epsilon$ dependence in depth and work to linear in $1/\epsilon$ of the parallel approximate maximum flow and transshipment algorithms of Li [17], Andoni et al. [2], and Agarwal et al. [1]. For transshipment, this requires constructing a $\operatorname{polylog}(n)$ -approximate $\ell_{1}$ cost approximator $\bm{\mathit{P}}$ such that $\bm{\mathit{P}}$ , $\left|\bm{\mathit{P}}\right|$ , $\bm{\mathit{P}}^{\top}$ , and $\left|\bm{\mathit{P}}\right|^{\top}$ can all be applied in $\widetilde{O}(m)$ time and $\widetilde{O}(1)$ depth. Similarly, for maximum flow, a $\operatorname{polylog}(n)$ -approximate $\ell_{\infty}$ congestion approximator $\bm{\mathit{P}}$ s.t. $\bm{\mathit{P}}$ , $\left|\bm{\mathit{P}}\right|$ , $\bm{\mathit{P}}^{\top}$ , and $\left|\bm{\mathit{P}}\right|^{\top}$ can all be applied in $\widetilde{O}(m)$ time and $\widetilde{O}(1)$ depth. Grunau et al. [10] recently gave such constructions, thus achieving $\widetilde{O}(m/\epsilon)$ work and $\widetilde{O}(1/\epsilon)$ depth for $(1+\epsilon)$ -approximate undirected maximum flow or transshipment.

1.1 Our Contributions

Our main contribution is a $(1+\epsilon)$ -bicriteria approximation algorithm for the undirected minimum cost flow (Problem 1) on unit-length, unit capacity $\phi$ -expanders, with work $\widetilde{O}(\frac{m}{\epsilon\phi})$ and depth $\widetilde{O}(\frac{1}{\epsilon\phi})$ . Concretely, we produce a flow $\mathbf{f}$ that routes the given demands exactly while ensuring $||\mathbf{f}||_{\infty}\leq(1+\epsilon)$ and $||\mathbf{f}||_{1}\leq(1+\epsilon)||\mathbf{f}^{*}||_{1}$ where $\mathbf{f}^{*}$ is the optimal flow. Our bicriteria approximation generalizes $(1+\epsilon)$ objective approximation for undirected maximum flow and transshipment and is stronger than throughput error. This answers Q1 and Q2 in the affirmative for such $\phi$ -expanders with $\phi>\Omega(1/n^{o(1)})$ and Q3 when $\phi>\Omega(1/{\operatorname{polylog}(n)})$ . We can state our result formally as:

Theorem 1.1 (Parallel Undirected Minimum-Cost Flow on Expanders).

Let $G=(V,E)$ be an undirected, unit capacity, unit length graph with conductance at least $\phi$ . For any feasible demand $\mathbf{d}$ in the Undirected Minimum Cost Flow Problem (1), one can compute, in $\widetilde{O}\!\Big(\frac{|E|}{\epsilon\cdot\phi}\Big)$ work and $\widetilde{O}\!\Big(\frac{1}{\epsilon\cdot\phi}\Big)$ depth, a flow $\mathbf{f}$ routing $\mathbf{d}$ with

\|\mathbf{f}\|_{\infty}\leq(1+\epsilon)\qquad\text{and}\qquad\|\mathbf{f}\|_{1% }\leq(1+\epsilon)\cdot\min_{\begin{subarray}{c}\mathbf{Bg}=\mathbf{d}\\ \|\mathbf{g}\|_{\infty}\leq 1\end{subarray}}\|\mathbf{g}\|_{1}.

In order to prove Theorem 1.1, our key technical contribution is a novel gradient-descent-like method for simultaneously minimizing $\ell_{1}$ - and $\ell_{\infty}$ -norms, building on Sherman’s theory of area-convexity.

To design this new method, we have to answer a sequence of questions: (a) Does there exist a meaningful saddle-point optimization problem that solves the undirected minimum-cost flow? (b) Does a small-magnitude area-convex regularizer exist for such a saddle-point optimization problem? (c) Can we implement the resulting “update step” efficiently? We answer these questions affirmatively in the context of unit-capacity, unit length expanders.

In attempting to answer Question (a), we encounter a conceptual hurdle. Sherman’s area-convexity approach to maximum flow, as well as follow-up methods for transshipment [12], inherently uses the existence of an appropriate congestion approximator for the problem. The $\kappa$ -congestion approximator $\mathbf{P}$ certifies that if, for a demand $\mathbf{d}$ , we have $\|\mathbf{Pd}\|_{\infty}\leq\rho$ , then a flow routing $\mathbf{d}$ with minimal congestion has congestion between $\frac{\rho}{\kappa}$ and $\rho$ . Likewise, for a length approximator. If we attempt to generalize this to the mixed problem, we hope to have two matrices $\mathbf{P},\mathbf{Q}$ such that $\mathbf{P}$ is a $\kappa$ -congestion approximator and $\|\mathbf{Pd}\|_{\infty}\leq\rho,\|\mathbf{Qd}\|_{1}\leq\sigma$ implies that among all flows $\mathbf{f}$ with congestion $\|\mathbf{C}^{-1}\mathbf{f}\|_{\infty}$ at most $\rho$ , the flow $\mathbf{f}^{*}$ with the minimal length $\|\mathbf{Lf}^{*}\|_{1}$ has a length between $\frac{\sigma}{\kappa}$ and $\sigma$ . In general, we cannot find such matrices $\mathbf{P},\mathbf{Q}$ with small $\kappa$ .

Fact 1.

There is a graph such that any such $\mathbf{P,Q}$ must have $\kappa\geq O(\sqrt{|V|})$ .

But let us consider a special case where we know how to construct an oblivious routing $\mathbf{M}$ , a linear operator mapping demand to flow routing the demand, that is both a $\kappa$ -congestion and a $\kappa$ -length approximator at the same time. Then, we immediately have that $\mathbf{Md}$ certifies that among all flows with $\|\mathbf{C}^{-1}\mathbf{f}\|_{\infty}\leq\rho$ , the optimal flow $\mathbf{f}^{*}$ has length $\|\mathbf{Lf}^{*}\|_{1}$ between $\frac{\sigma}{\kappa}$ and $\sigma$ . In general, such a matrix $M$ cannot exist for small $\kappa$ as it would contradict fact 1 for $\mathbf{P},\mathbf{Q}=\mathbf{M}$ . However, we observe that, for unit length, unit capacity $\phi$ -expanders, an adequate oblivious routing $\mathbf{M}$ does exist. Crucially, this is true because a single flow, namely the electrical flow, on such a graph is simultaneously an $O(\log(m)/\phi)$ oblivious routing for $\ell_{1}$ and $\ell_{\infty}$ , as shown by Florescu et al. [8] (a bound of $O(\log(m)/\phi^{2})$ was shown by Kelner and Maymounkov [15]); electrical flows can be computed by applying a linear operator to the demands $\mathbf{d}$ . In fact, it turns out that there are other even easier choices for $\mathbf{P},\mathbf{Q}$ on expanders. We will therefore use $\mathbf{P}=\mathbf{D}^{-1}\mathbf{B}/2$ and $\mathbf{Q}=\mathbf{B}/2$ instead, where $\mathbf{D}$ denotes the diagonal degree matrix and $\mathbf{B}$ the vertex-edge incidence matrix. This allows us to define a suitable saddle-point optimization problem for solving the undirected minimum-cost flow, and with it, an appropriate area-convex regularizer, thus answering Questions (a) and (b). Finally, we also answer Question (c) in the affirmative by designing $\delta$ -approximate minimization oracles (AMOs) for primal and dual variable updates. Below, we state our version of our main technical result on mixed $\ell_{\infty}$ and $\ell_{1}$ -norm minimization.

Theorem (Mixed $\ell_{\infty}$ - $\ell_{1}$ Optimization).

Given $r>0$ , define $\mathcal{X}=\{\bm{\mathit{x}}:{\left\|\bm{\mathit{x}}\right\|_{\infty}\leq 1}% \allowbreak\text{ and }||\bm{\mathit{x}}||_{1}\leq s\}$ . There exists an algorithm which, given $\mathbf{P}$ , $\mathbf{Q}\in\mathbb{R}^{c\times m}$ with $\|\mathbf{P}\|_{\infty},\|\mathbf{Q}\|_{1}\leq 1$ and $\mathbf{p},\mathbf{q}\in\mathbb{R}^{m}$ with $\|\mathbf{p}\|_{\infty}\leq 1$ , $\|\mathbf{q}\|_{1}\leq s$ , runs in $\tilde{O}\big((\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q})+c+m)% \varepsilon^{-1}\big)$ work, $\tilde{O}\big((\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q})+1)% \varepsilon^{-1}\big)$ depth and outputs either

1.

$\mathbf{x}\in\mathcal{X}$ such that $\|\mathbf{P}\mathbf{x}-\mathbf{p}\|_{\infty}\leq\varepsilon$ and $\|\mathbf{Q}\mathbf{x}-\mathbf{q}\|_{1}\leq\varepsilon\cdot s$ ; or
2.

$\mathbf{y,z}\in\mathbb{R}^{c}:\|\mathbf{y}\|_{1},\|\mathbf{z}\|_{\infty}\leq 1$ certifying infeasibility: $\forall\mathbf{x}\in\mathcal{X}:|\mathbf{y}^{\top}(\mathbf{P}\mathbf{x}-% \mathbf{p})|>0$ or $|\mathbf{z}^{\top}(\mathbf{Q}\mathbf{x}-\mathbf{q})|>0$ .

where $\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q}),\operatorname{dpth_{m/t/a}}(% \mathbf{P},\mathbf{Q})$ denotes the work, depth it takes to multiply an arbitrary vector $\mathbf{x}$ with either one of the matrices $\mathbf{P},\mathbf{P}^{\top},|\mathbf{P}|,|\mathbf{P}|^{\top},\mathbf{Q},% \mathbf{Q}^{\top},|\mathbf{Q}|,|\mathbf{Q}|^{\top}$ .

The theorem above follows immediately from Corollary 2. In Corollary 2 $\mathbf{R}^{-1},\mathbf{P},\mathbf{p},\mathbf{Q},\mathbf{q}$ corresponds to $s\mathbf{I},\mathbf{P},\mathbf{p},\mathbf{Q}/s,\mathbf{q}/s$ in the theorem. Theorem 1.1 is obtained from the theorem above by instantiating the regression problems with $\mathbf{P}=\mathbf{D}^{-1}\mathbf{B}/2$ and $\mathbf{Q}=\mathbf{B}/2$ . We obtain this theorem by developing a low-iteration count optimization approach to solving the following regression problem, which in the positive case should have objective value zero:

\min_{\begin{subarray}{c}\bm{\mathit{x}}\in\mathbb{R}^{m}\\ \left\|\bm{\mathit{x}}\right\|_{\infty}\leq 1\\ \left\|\bm{\mathit{x}}\right\|_{1}\leq s\end{subarray}}\left\|\bm{\mathit{A}}% \bm{\mathit{x}}-\boldsymbol{\mathit{a}}\right\|_{\infty}+\frac{1}{s}\left\|\bm% {\mathit{B}}\bm{\mathit{x}}-\bm{\mathit{b}}\right\|_{1}

(2)

Crucially, we can express this problem as a saddle-point problem:

\min_{\begin{subarray}{c}\bm{\mathit{x}}\in\mathbb{R}^{m}\\ \left\|\bm{\mathit{x}}\right\|_{\infty}\leq 1\\ \left\|\bm{\mathit{x}}\right\|_{1}\leq s\end{subarray}}\max_{\begin{subarray}{% c}\bm{\mathit{y}}\in\mathbb{R}^{c}\\ \bm{\mathit{z}}\in\mathbb{R}^{c}\\ \left\|\bm{\mathit{z}}\right\|_{\infty}\leq 1\\ \left\|\bm{\mathit{y}}\right\|_{1}\leq 1\end{subarray}}\bm{\mathit{y}}^{\top}(% \bm{\mathit{A}}\bm{\mathit{x}}-\boldsymbol{\mathit{a}})+\frac{1}{s}\bm{\mathit% {z}}^{\top}(\bm{\mathit{B}}\bm{\mathit{x}}-\bm{\mathit{b}})

(3)

At this point, we can develop area-convex regularizers for the primal-dual pair $(\bm{\mathit{x}},(\bm{\mathit{y}},\bm{\mathit{z}}))$ .

Why area-convexity?

To our knowledge, all prior works that use area-convexity (e.g. [23, 12, 13, 10]) treat it as a tool for improving the $\epsilon$ -dependence in iteration count of $\ell_{\infty}$ -gradient descent from scaling as $1/\epsilon^{2}$ to $1/\epsilon$ (or by escaping to the dual doing the same for $\ell_{1}$ -norm minimization). This is not why we use area-convexity: we would also obtain affirmative answers to our Questions Q1, Q2, and Q3 using a method that scales as $\operatorname{poly}(1/\epsilon)$ .

Instead, our goal was to develop a saddle-point optimization problem where the primal-dual variable pairs live in domains for which a low-iteration count optimization method is known, and then try to show that even after adding together different such terms, we can solve the problem with low iteration complexity. However, saddle-point optimization generally requires a strongly convex regularizer for the primal or dual variables, or both (see [19, 20, 21] and many other works). This meant we could not apply such methods, because of the non-existence of small range, $\ell_{\infty}$ -strongly convex regularizers. But, Sherman’s area-convexity theory provides precisely a toolset for saddle-point optimization in the presence of of $\ell_{\infty}$ constraints and generalizes to our context. We view this idea as our main contribution.

We note that all core technical ingredients that our result builds on have been available since Sherman introduced area-convexity in 2017²²2Before the work of Florescu et al. [8], the work of Kelner-Maymounkov [15] would have yielded an additional $1/\phi$ factor in our work and depth. [23]. But area-convexity is difficult to work with, which seems to have prevented the realization that it generalizes beyond $\ell_{\infty}$ - or $\ell_{1}$ -norm minimization to simultaneously handle both. Our area-convex regularizers are in some ways simpler than those of Sherman, and we hope this work will increase the accessibility of these tools.

Open problem: $\widetilde{O}(\frac{m}{\epsilon})$ work, $\widetilde{O}(\frac{1}{\epsilon})$ depth undirected minimum-cost flow on general graphs. Our methods suggest an approach to approximate undirected minimum-cost flow on general graphs: Design a suitable saddle-point problem with an area-convex regularizer, and develop a method for solving the corresponding update problems. This theory will have to bypass folklore lower bounds on non-existence of high-quality simultaneous $\ell_{\infty}$ - and $\ell_{1}$ -oblivious routing on general graphs, which might be possible using length-constrained congestion-minimizing oblivious routing [9].

1.2 Organization of the Remaining Paper

After the preliminaries, in Section 3 we assume the mixed $\ell_{\infty}$ – $\ell_{1}$ theorem stated in Contribution 1.1. Under this assumption, we derive our main theorem (Theorem 1.1), which provides a parallel undirected minimum–cost flow solver on expanders.

After this application section, we then “open the black box”: we develop the mixed $\ell_{\infty}$ – $\ell_{1}$ optimization theorem itself. We begin by reviewing the relevant definitions, lemmas, and the extragradient iteration theorem for area–convexity established by Sherman [23] in Section 4. With this machinery in place, we construct in Section 5 an area–convex regularizer tailored to our mixed $\ell_{\infty}$ – $\ell_{1}$ problem, prove that the regularizer is well–behaved (its magnitude is small), and design an approximate maximization oracle for it. These ingredients then allow us to instantiate Sherman’s extragradient iteration Theorem 10, completing the proof of the mixed $\ell_{\infty}$ – $\ell_{1}$ theorem promised in the contribution section.

2 Preliminaries

2.1 Graphs

Throughout the paper all graphs are directed: a graph is a pair $G=(V,E)$ , and $E$ is a set of directed edges. We represent undirected graphs via directed graphs: whenever we refer to an “undirected” graph, we mean a directed graph in which for every edge $e_{1}=(u,v)$ with capacity $\mathbf{c}(e_{1})$ there is also an antiparallel edge $e_{2}=(v,u)$ with capacity $\mathbf{c}(e_{2})$ , and moreover these two antiparallel edges have equal length. We denote by $\mathbf{B}\in\mathbb{R}^{V\times E}$ the directed edge-incidence matrix: $\mathbf{B}_{v,e}=1$ iff $e$ enters $v$ , $\mathbf{B}_{v,e}=-1$ iff $e$ leaves $v$ , and $\mathbf{B}_{v,e}=0$ otherwise. We denote by $\mathbf{D}$ the out–degree matrix. Given an undirected capacitated graph $G=(V,E,\mathbf{c})$ , a flow $\mathbf{f}\in\mathbb{R}^{E}$ routes a demand vector $\mathbf{d}\in\mathbb{R}^{V}$ with $\sum_{v}\mathbf{d}(v)=0$ . The flow is feasible if $\mathbf{f}(e)\leq\mathbf{c}(e)$ for all $e\in E$ . A demand $\mathbf{d}$ with $\sum_{v}\mathbf{d}(v)=0$ is feasible if there exists a feasible flow routing $\mathbf{d}$ . For a graph $G=(V,E,\mathbf{c},\mathbf{l})$ , let $\mathbf{C}$ and $\mathbf{L}$ be the diagonal matrices with $\mathbf{c}$ and $\mathbf{l}$ on the diagonal. We also define $\mathbf{r}=r\cdot(\mathbf{l}_{e}\cdot\mathbf{c}_{e})_{e}$ , where the scaling factor $r$ will always be specified in context, and we let $\mathbf{R}$ be the diagonal matrix with $\mathbf{r}$ on the diagonal.

2.2 Linear Algebra

For the vector space $\mathbb{C}^{n}$ , we denote by $d\mathbf{x}_{i}:\mathbb{C}^{n}\to\mathbb{C}$ the linear form $d\mathbf{x}_{i}(\mathbf{x})=\mathbf{x}_{i}$ . We denote by $\langle\cdot,\cdot\rangle$ the standard Hermitian inner product on $\mathbb{C}^{n}$ . We denote by $\Delta_{d}\;=\;\{\bm{\mathit{y}}\in\mathbb{R}^{d}:\bm{\mathit{y}}\geq 0,\ \|% \bm{\mathit{y}}\|_{1}\leq 1\}$ the $d$ –dimensional simplex. For a matrix $\mathbf{M}\in\mathbb{R}^{d\times n}$ we denote by $|\mathbf{M}|$ the entrywise absolute value of $\mathbf{M}$ . Moreover, for $\mathbf{M}\in\mathbb{R}^{d\times n}$ we write $\operatorname{wrk_{m/t/a}}(\mathbf{M})$ and $\operatorname{dpth_{m/t/a}}(\mathbf{M})$ for the work and depth (respectively) required to compute any of $\mathbf{M}\mathbf{x}$ , $\mathbf{M}^{\top}\mathbf{x}$ , $|\mathbf{M}|\mathbf{x}$ , or $|\mathbf{M}|^{\top}\mathbf{x}$ on an arbitrary vector $\mathbf{x}$ . For matrices $\mathbf{M}_{1},\dots,\mathbf{M}_{k}$ , we set

	$\displaystyle\operatorname{wrk_{m/t/a}}(\mathbf{M}_{1},\dots,\mathbf{M}_{k})\;$	$\displaystyle=\;\max_{i}\operatorname{wrk_{m/t/a}}(\mathbf{M}_{i})$
	$\displaystyle\operatorname{dpth_{m/t/a}}(\mathbf{M}_{1},\dots,\mathbf{M}_{k})\;$	$\displaystyle=\;\max_{i}\operatorname{dpth_{m/t/a}}(\mathbf{M}_{i}).$

3 Application: Flow Algorithms

3.1 Undirected Minimum-Cost Flow on Expanders

We now study how the minimum-cost flow problem can be solved efficiently on expander graphs. To recall, we define the approximate undirected minimum-cost flow problem as the problem: Given an undirected graph $G=(V,E,\mathbf{c},\mathbf{l})$ with capacity $\mathbf{c},$ length $\mathbf{l}$ and a feasible demand $\mathbf{d}\in\mathbb{R}^{d}$ , return a flow $\mathbf{f}\in\mathbb{R}^{E}$ routing $\mathbf{d},$ i.e. $\mathbf{Bf}=\mathbf{d}$ , such that

\|\mathbf{C}^{-1}\mathbf{f}\|_{\infty}\leq 1+\epsilon\qquad\text{and}\qquad\|% \mathbf{Lf}\|_{1}\leq(1+\epsilon)\cdot\min_{\begin{subarray}{c}\mathbf{Bg}=% \mathbf{d}\\ \|\mathbf{C}^{-1}\mathbf{g}\|_{\infty}\leq 1\end{subarray}}\|\mathbf{Lg}\|_{1}.

(4)

We observe that if we know the optimal value

\frac{1}{r}:=\min_{\begin{subarray}{c}\mathbf{Bg}=\mathbf{d}\\ \|\mathbf{C}^{-1}\mathbf{g}\|_{\infty}\leq 1\end{subarray}}\|\mathbf{Lg}\|_{1},

then equation (4) is equivalent to $\|\mathbf{x}\|_{\infty}\leq 1+\epsilon\text{ and }\|\mathbf{Rx}\|_{1}\leq(1+\epsilon)$ , where $\mathbf{R}=r\cdot\mathbf{L}\mathbf{C}$ . The diagonal vector of $\mathbf{R}$ , we denote by $\mathbf{r}$ . In the following, we will not have access to the correct value of $r$ , but we will binary search for an approximation. With this perspective, we aim to find a vector $\mathbf{x}$ in the region

\mathcal{X}=\Big\{\mathbf{x}\in[0,1]^{E}:\sum_{i}\mathbf{r}_{i}\mathbf{x}_{i}% \leq 1\Big\}.

such that $\mathbf{Cx}$ routes the demand $\mathbf{d}$ . To find such a vector and in order to binary search the correct value of $r$ , we state a key corollary that provides such a vector $\mathbf{x}$ or provides a certificate that no such vector exists, in which case we will decrease $r$ . The proof is deferred to Section 5.

Corollary 2.

There exists an algorithm that, given $\mathbf{P},\mathbf{Q}\in\mathbb{R}^{c\times m}$ with $\|\mathbf{P}\|_{\infty},\|\mathbf{Q}\mathbf{R}^{-1}\|_{1}\leq 1$ and $\mathbf{p},\mathbf{q}\in\mathbb{R}^{c}$ with $\|\mathbf{p}\|_{\infty},\|\mathbf{q}\|_{1}\leq 1$ , runs in work $\tilde{O}\big((\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q})+m)\varepsilon% ^{-1}\big)$ , depth $\tilde{O}\big((\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q})+1)% \varepsilon^{-1}\big)$ , and outputs either

1.

$\mathbf{x}\in\mathcal{X}$ such that $\|\mathbf{P}\mathbf{x}-\mathbf{p}\|_{\infty}\leq\varepsilon$ and $\|\mathbf{Q}\mathbf{x}-\mathbf{q}\|_{1}\leq\varepsilon$ ; or
2.

$\mathbf{y,z}\in\mathbb{R}^{c}:\|\mathbf{y}\|_{1},\|\mathbf{z}\|_{\infty}\leq 1$ certifying infeasibility: $\forall\mathbf{x}\in\mathcal{X}:|\mathbf{y}^{\top}(\mathbf{P}\mathbf{x}-% \mathbf{p})|>0$ or $|\mathbf{z}^{\top}(\mathbf{Q}\mathbf{x}-\mathbf{q})|>0$ .

The above corollary provides a way to either approximately satisfy a system of linear inequalities or to produce a dual certificate demonstrating infeasibility. We now instantiate this general result for the specific matrices that arise from routing problems.

Lemma 3.

Let $\mathbf{M}_{p},\mathbf{M}_{q}\in\mathbb{R}^{c\times n}$ satisfy $\|\mathbf{M}_{p}\mathbf{BC}\|_{\infty}\leq 1$ and $\|(\mathbf{M}_{q}\mathbf{BC})\mathbf{R}^{-1}\|_{1}\leq 1$ . Let $\mathbf{d}\in\mathbb{R}^{m}$ satisfy $\|\mathbf{M}_{p}\mathbf{d}\|_{\infty},\ \|\mathbf{M}_{q}\mathbf{d}\|_{1}\leq 1$ . Then there is an algorithm that in work $\widetilde{O}\big((\operatorname{wrk_{m/t/a}}(\mathbf{M}_{p}\mathbf{BC},% \mathbf{M}_{q}\mathbf{BC})+c+m)\varepsilon^{-1}\big)$ and depth $\widetilde{O}\big((\operatorname{dpth_{m/t/a}}(\mathbf{M}_{p}\mathbf{BC},% \mathbf{M}_{q}\mathbf{BC})+1)\varepsilon^{-1}\big)$ outputs either

1.

a feasible flow $\mathbf{f}$ with $\|\mathbf{RC}^{-1}\mathbf{f}\|_{1}\leq 1$ and $\|\mathbf{M}_{p}(\mathbf{B}\mathbf{f}-\mathbf{d})\|_{\infty}\leq\varepsilon,\|% \mathbf{M}_{q}(\mathbf{B}\mathbf{f}-\mathbf{d})\|_{1}\leq\varepsilon$ ; or
2.

a dual certificate $(\mathbf{y},\mathbf{z})$ proving that $\not\exists\mathbf{x}\in\mathcal{X}:\mathbf{f}=\mathbf{Cx}$ such that $\mathbf{Bf}=\mathbf{d}$ .

The next proof simply applies Corollary 2 with a direct substitution of the relevant matrices.

Proof.

The lemma is an immediate instantiation of Corollary 2. Concretely set $\mathbf{P}=\mathbf{M}_{p}\mathbf{BC}$ , $\mathbf{Q}=\mathbf{M}_{q}\mathbf{BC}$ , $\mathbf{p}=\mathbf{M}_{p}\mathbf{d}$ and $\mathbf{q}=\mathbf{M}_{q}\mathbf{d}$ . The stated operator norm bounds imply the hypotheses of the corollary, and the corollary gives either the approximate primal flow (case 1) or the dual infeasibility certificate (case 2) with the claimed work/depth bound. $\hfill\blacktriangleleft$ Having established this lemma, we recall a crucial combinatorial Lemma about flow routings in expanders. It can be considered folklore; a proof can be found in [4]. It states that if the amount of demand on every vertex is bounded by the degree, we can route the demand simultaneously with small congestion and small cost, where the quality scales as the inverse of the expansion factor.

Lemma 4 (Lemma 5.12 in [4]).

Let $G=(V,E)$ be a $\phi$ -expander. Consider any demand $\mathbf{d}\in\mathbb{R}^{V}:\sum_{j}\mathbf{d}_{j}=0$ such that for every vertex $v,|\mathbf{d}(v)|\leq\operatorname{deg}(v)$ . Then, there exists a flow $\mathbf{f}$ in $G$ that routes $\mathbf{d}$ with $\|\mathbf{f}\|_{\infty}=10\log(n)/\phi$ and $\|\mathbf{f}\|_{1}=10\log(n)\cdot\|\mathbf{d}\|_{1}/\phi$ .

We now arrive at the main result of this subsection, which shows that we can efficiently compute a near-optimal minimum-cost flow on an expander graph. See 1.1 We now describe the proof strategy for this theorem. The idea is to repeatedly test the feasibility of routing the demand $\mathbf{d}$ under a guessed congestion scale $r$ , and to use binary search to refine this guess until we achieve an approximately optimal value. The feasibility tests themselves are implemented by invoking Lemma 3 as a black box.

Proof.

Let us denote by $m$ the number of undirected edges in $G$ . The proof proceeds by reducing to Lemma 3 and then binary searching a length scale $r$ . For $\mathbf{R}=r\mathbf{I},\|\mathbf{D}^{-1}\mathbf{B}\|_{\infty},\ \|r\cdot% \mathbf{B}\mathbf{R}^{-1}\|_{1}\leq 2,$ i.e. the operators we will feed into Lemma 3 satisfy the required norm bounds (up to the constant factor $2$ ). We remark for the reader that as mentioned in the preliminaries $\mathbf{D}$ denotes the diagonal degree matrix. Because the demand $\mathbf{d}$ is feasible, $\|\mathbf{D}^{-1}\mathbf{d}\|_{\infty}\leq 1$ , and by choosing $r$ sufficiently small we may ensure $\|r\cdot\mathbf{d}\|_{1}\leq 1$ . As we will see below, we may always choose $r$ sufficiently small to satisfy this inequality.

Feasibility predicate.

Fix a target approximation parameter $\epsilon\in(0,1)$ . We will use Lemma 3 as a black-box feasibility test:

\mathrm{Feasible}(r)\ :=\ \text{``There exists }\mathbf{g}\text{ with }\mathbf% {Bg}=\mathbf{d},\ \|\mathbf{g}\|_{\infty}\leq 1+\frac{\epsilon}{2},\ \text{and% }\|\mathbf{R}\mathbf{g}\|_{1}\leq 1+\frac{\epsilon}{2}\text{?''}

Recall $\mathbf{R}=r\mathbf{I}$ so $\|\mathbf{R}{g}\|_{1}=r\|\mathbf{g}\|_{1}\leq 1$ iff $\|\mathbf{g}\|_{1}\leq 1/r$ . We implement $\mathrm{Feasible}(r)$ by invoking Lemma 3 with the operator matrices

\mathbf{M}_{p}=\frac{1}{2}\cdot\mathbf{\mathbf{D}^{-1}},\qquad\mathbf{M}_{q}=% \frac{r}{2}\cdot\mathbf{I}_{n},

and with the Lemma accuracy parameter

\varepsilon^{\prime}\;=\;\frac{\phi}{10\log m}\cdot\frac{\epsilon}{4}\;=\;% \frac{\phi\epsilon}{40\log m}.

(5)

The choice (5) ensures that the additive errors produced by the lemma translate into multiplicative $(1\pm\epsilon/2)$ guarantees on the final norms; the constant factors are chosen to satisfy the norm bounds. The lemma returns one of two outcomes:

1.

a flow $\mathbf{f}$ with $\|\mathbf{M}_{p}(\mathbf{B}\mathbf{f}-\mathbf{d})\|_{\infty}\leq\varepsilon^{\prime}$ and $\|\mathbf{M}_{q}(\mathbf{B}\mathbf{f}-\mathbf{d})\|_{1}\leq\varepsilon^{\prime}.$ Lemma 4 implies that there exists a correction flow $\mathbf{g}$ routing $\mathbf{Bf-d}$ with $\|\mathbf{g}\|_{\infty},\|\mathbf{Rg}\|_{1}\leq\epsilon/4$ . We can repeat the procedure $k$ many times and obtain a sequence of flows $(\mathbf{f}_{i})_{i\leq k}$ such that the correcting flow of $\sum_{i}\mathbf{f}_{i}$ has congestion and a length of at most $\frac{\epsilon^{k}}{4^{k}}$ . By taking $k=\Omega(\log(|V|))$ large enough, routing the residual demand along any paths by a flow $\mathbf{g}$ incurs additional congestion and a length of at most $\epsilon/2$ ³³3We could, for example, use electrical flow routing, which is computable in parallel. Hence, the returned flow $\hat{\mathbf{f}}=\mathbf{g}+\sum_{i\leq k}\mathbf{f}_{i}$ routes the demand $\mathbf{d}$ and

	$\displaystyle\\|\hat{\mathbf{f}}\\|_{\infty}$	$\displaystyle\leq\\|\mathbf{g}\\|_{\infty}+\sum_{i\leq k}\\|\mathbf{f}_{i}\\|_{% \infty}\leq\epsilon/2+\\|\mathbf{f}_{0}\\|_{\infty}+\epsilon\cdot\sum_{0<i}\frac% {1}{4^{i}}\leq\epsilon/2+1+\frac{\epsilon}{3}\leq 1+\epsilon$
	$\displaystyle\\|\hat{\mathbf{f}}\\|_{1}$	$\displaystyle\leq\\|\mathbf{g}\\|_{1}+\sum_{i\leq k}\\|\mathbf{f}_{i}\\|_{1}\leq% \epsilon/2+\\|\mathbf{f}_{0}\\|_{1}+\epsilon\cdot\sum_{0<i}\frac{1}{4^{i}}\leq% \epsilon/2+1+\frac{\epsilon}{3}\leq 1+\epsilon$

This certifies that $\mathrm{Feasible}(r)$ is true.

2.

a dual certificate $(\mathbf{y},\mathbf{z})$ that there does not exist a flow $\mathbf{g}\text{ with }\mathbf{Bg}=\mathbf{d},\ \|\mathbf{g}\|_{\infty},\|% \mathbf{Rg}\|_{1}\leq 1$ .

Therefore, each invocation of the lemma provides a robust yes/no answer for $\mathrm{Feasible}(r)$ (with the “yes” case producing an approximate primal flow and the “no” case providing a dual witness).

Initialization of the binary search interval.

By Lemma 4, the quantity

T\;:=\;\min_{\begin{subarray}{c}\mathbf{Bg}=\mathbf{d}\\ \|\mathbf{g}\|_{\infty}\leq 1\end{subarray}}\|\mathbf{g}\|_{1}

satisfies the bounds $\|\mathbf{d}\|_{1}\ \leq\ T\ \leq\ 10\log m\cdot\|\mathbf{d}\|_{1}/\phi.$ Equivalently, the threshold value $1/r$ for which $\mathrm{Feasible}(r)$ changes its truth value lies in $[\|\mathbf{d}\|_{1},10\cdot\|\mathbf{d}\|_{1}\log m/\phi)]$ ; hence

r\in\Big[\frac{\phi}{10\|\mathbf{d}\|_{1}\log m},\frac{1}{\|\mathbf{d}\|_{1}}% \Big].

(6)

Thus we may initialize the binary search interval to

s_{\mathrm{low}}\;=\;\|\mathbf{d}\|_{1},\qquad s_{\mathrm{high}}\;=\;\frac{10% \log(m)}{\phi}\|\mathbf{d}\|_{1},

and we are guaranteed that the true threshold lies inside this interval. This in particular establishes the bound $\|r\cdot\mathbf{d}\|_{1}\leq 1$ that we assumed in the beginning.

Binary search and termination.

Let $k$ be maximal such that $(1+\epsilon/4)^{k}\leq(10\log(m))/\phi$ . We perform binary search on the ordered sequence $(s_{low}(1+\epsilon/4)^{i})_{i\leq k}$ . We initialize $i_{low}=0,i_{high}=k$ For a midpoint $i_{\mathrm{mid}}$ we evaluate $\mathrm{Feasible}(1/(s_{low}(1+\epsilon/4)^{i_{\mathrm{mid}}}))$ by calling Lemma 3 with accuracy $\varepsilon^{\prime}$ as in (5). If the lemma returns feasible, then we know that $T\leq s_{low}(1+\epsilon/4)^{i_{mid}+1}$ and we set $i_{\mathrm{high}}\leftarrow i_{\mathrm{mid}}+1$ , otherwise $i_{\mathrm{low}}\leftarrow i_{\mathrm{mid}}$ . We stop when $i_{low}+1=i_{high}$ . This stopping rule guarantees that the final returned value of $s_{high}$ approximates $T$ to multiplicative $(1\pm\epsilon/4)$ accuracy, i.e. $s_{high}(1+\frac{\epsilon}{4})^{-1}\leq T\leq s_{high}$ . Hence, the flow $\mathbf{f}$ associated with $r=1/s_{low}$ satisfies

\|\mathbf{f}\|_{1}\leq\left(1+\frac{\epsilon}{4}\right)s_{low}\leq\left(1+% \frac{\epsilon}{4}\right)\cdot\left(1+\frac{\epsilon}{4}\right)\cdot T\leq% \left(1+\epsilon\right)\cdot T.

Iteration count and work/depth bound.

The initial sequence length is

\frac{\log((10\log(m))/\phi)}{\log(1+\epsilon/4)}\leq\frac{4\cdot\log((10\log(% m))/\phi)}{\epsilon}

Therefore the number of binary search iterations required is

O\Big(\log\frac{10\log m}{\phi}+\log\frac{1}{\epsilon}\Big)\;=\;\widetilde{O}(% 1+\log(1/\epsilon)).

Each invocation of Lemma 3 (with parameter $\varepsilon^{\prime}=\Theta(\phi\epsilon/\log m)$ ) requires

	$\displaystyle\widetilde{O}\!\Big(\big(\operatorname{wrk_{m/t/a}}(\mathbf{D}^{-% 1}\mathbf{B},r\cdot\mathbf{B})+m\big)\cdot(\varepsilon^{\prime})^{-1}\Big)\;=% \;\widetilde{O}\!\Big(\frac{m}{\epsilon}\cdot\frac{10\log m}{\phi}\Big)\text{ work}$
	$\displaystyle\widetilde{O}\!\Big(\big(\operatorname{dpth_{m/t/a}}(\mathbf{D}^{% -1}\mathbf{B},r\cdot\mathbf{B})+1\big)\cdot(\varepsilon^{\prime})^{-1}\Big)\;=% \;\widetilde{O}\!\Big(\frac{1}{\epsilon}\cdot\frac{10\log m}{\phi}\Big)\text{ depth}$

where we used the operator norm bounds from expansion. Multiplying by the $O(\log(1/\epsilon)+\log(10\log m/\phi))$ binary search iterations yields $\widetilde{O}\!\Big(\frac{m}{\epsilon\cdot\phi}\log(1/\epsilon)\Big)$ work and $\widetilde{O}\!\Big(\frac{1}{\epsilon\cdot\phi}\log(1/\epsilon)\Big)$ depth as claimed. $\hfill\blacktriangleleft$

4 Area-Convexity Review

In this section, we provide a brief review of the fundamentals of the concept of area-convexity. These results are crucial for the discussion in the Section 5.

Definition 5.

A $\delta$ -approximate minimization oracle $(\delta$ -AMO) for $\phi:\mathcal{C}\subseteq\mathbb{R}^{d}\rightarrow\mathbb{R}$ takes input $\mathbf{p}\in\mathbb{R}^{d}$ , and outputs $\mathbf{z}\in\mathcal{C}$ such that, $\mathbf{p}\cdot\mathbf{z}-\phi(\mathbf{z})+\delta\geq\sup_{\mathbf{z}^{\prime}% \in\mathcal{C}}\mathbf{p}\cdot\mathbf{z}^{\prime}-\phi\left(\mathbf{z}^{\prime% }\right)=:\phi^{*}(\mathbf{p}).$

A $\delta$ -approximate minimization oracle (AMO) generalizes the idea of computing a convex conjugate or performing an exact minimization. Rather than finding the exact maximizer of $\mathbf{p}\cdot\mathbf{z}-\phi(\mathbf{z})$ , it allows an additive error of $\delta$ .

Definition 6.

A function $\phi$ is area-convex with respect to $\mathbf{J}$ on a convex set $\mathcal{C}$ , iff, for all $\mathbf{x,y,z}\in\mathcal{C}$ ,

\phi\left(\frac{\mathbf{x}+\mathbf{y}+\mathbf{z}}{3}\right)\leq\frac{1}{3}(% \phi(\mathbf{x})+\phi(\mathbf{y})+\phi(\mathbf{z}))-\frac{1}{3\sqrt{3}}(% \mathbf{z}-\mathbf{y})\mathrm{\mathbf{J}}(\mathbf{y}-\mathbf{x})

Area-convexity is a geometric generalization of classical convexity. While standard convexity constrains the value of $\phi$ at the midpoint of two points, area-convexity introduces a third point and a skew-symmetric matrix $\mathbf{J}$ that captures rotational or “area-preserving” behavior. The additional term involving $\mathbf{J}$ modifies convexity to reflect curvature along oriented triangles rather than line segments – this makes it particularly useful in settings involving symplectic or complex geometry.

Definition 7.

We define the complex Loewner order on the Hermitian matrices $\{\mathbf{P}\in\mathbb{C}^{m\times m}:\mathbf{P}^{*}=\mathbf{P}\}$ as $\mathbf{P}\succeq\mathbf{Q}$ iff $\forall\mathbf{x}\in\mathbb{C}^{m}:\mathbf{x}^{*}(\mathbf{P}-\mathbf{Q})% \mathbf{x}\geq 0$ .

The complex Loewner order provides a way to compare Hermitian matrices based on their action on all vectors. If $\mathbf{P}\succeq\mathbf{Q}$ , then $\mathbf{P}$ dominates $\mathbf{Q}$ in a quadratic sense – every vector experiences at least as much “energy” under $\mathbf{P}$ as under $\mathbf{Q}$ . This ordering is central in matrix analysis and is crucial in expressing curvature conditions for area-convex functions.

$\blacktriangleright$ Remark 8.

It is easy to verify that the complex Loewner order defines a partial order. It satisfies, in particular, transitivity.

The Loewner order’s partial ordering structure ensures consistency when reasoning about matrix inequalities – if $\mathbf{P}\succeq\mathbf{Q}$ and $\mathbf{Q}\succeq\mathbf{C}$ , then $\mathbf{P}\succeq\mathbf{C}$ . This makes it a natural tool for linking differential properties of functions (like Hessians) to global convexity properties.

Theorem 9 ([23]).

Let $\phi$ be twice differentiable on a convex set $\mathcal{C}$ and $\mathbf{J}$ skew-Hermitian,

1.

If $\phi$ is area-convex w.r.t. $\mathbf{J}$ on the interior of $\mathcal{C}$ , then $\nabla^{2}\phi(\mathbf{z})\succeq i\mathbf{J}$ for all $\mathbf{z}$ in the interior.
2.

If $\nabla^{2}\phi(\mathbf{z})\succeq i\mathbf{\mathbf{J}}$ for all $\mathbf{z}\in\mathcal{C}$ , then $\phi$ is area-convex w.r.t $\frac{1}{3}\mathbf{\mathbf{J}}$ on $\mathcal{C}$ .

If $\phi$ is continuous on the closure of $\mathcal{C}$ , then $\phi$ is area-convex w.r.t $\frac{1}{3}\mathbf{\nobreak\ \mathbf{J}}$ on the closure of $\mathcal{C}$ .

This theorem bridges the geometric notion of area-convexity with the analytical condition on the Hessian of $\phi$ . The first part says that if $\phi$ behaves in an area-convex way, its curvature (via the Hessian) dominates the imaginary part of $\mathbf{J}$ . The converse connects matrix inequalities to global area-convexity, showing that certain second-order conditions suffice for this generalized convexity to hold. The result thus provides a powerful differential characterization of area-convex functions.

Theorem 10 ([23]).

Let $\mathbf{J}$ be skew-Hermitian, $\mathcal{C}$ compact-convex, and $\phi:\mathcal{C}\to[-\rho,0]$ . Suppose $\phi$ is area-convex with respect to $2\sqrt{3}\mathbf{J}$ on $\mathcal{C}$ , and $\Phi$ is a $\delta$ -AMO for $\phi$ . Define a sequence by $\mathbf{z}(0)=\mathbf{0}$ , $\mathbf{z}(t+1)=\mathbf{z}(t)+\tilde{\Phi}(\mathbf{J}\mathbf{z}(t))$ where $\tilde{\Phi}(\mathbf{p})=\Phi(\mathbf{p}+2\mathbf{J}\Phi(\mathbf{p})).$ Then, for all $t>0$ , we have $\tfrac{1}{t}\mathbf{z}(t)\in\mathcal{C}$ and $\delta+\rho/t\;\geq\;\max_{\mathbf{z}^{\prime}\in\mathcal{C}}\mathbf{z}^{% \prime}\cdot\mathbf{J}(\mathbf{z}(t)/t).$ Each iteration requires $O(1)$ calls to $\Phi$ , $O(1)$ applications of $\mathbf{J}$ , and $O(1)$ vector additions.

This theorem connects area-convexity to algorithmic performance. It shows that if a regularizer $\phi$ satisfies area-convexity with respect to $\mathbf{J}$ and we have access to a $\delta$ -approximate minimization oracle $\Phi$ , then an iterative procedure using $\mathbf{J}$ and $\Phi$ can generate approximate saddle points efficiently. Intuitively, the $\mathbf{J}$ operator introduces a rotational dynamics that stabilizes the update process, while area-convexity ensures convergence bounds on the averaged iterates.

5 Joint L1/Max-Norm Optimization

We begin by describing the feasible set for our optimization problem. This domain captures both the $\ell_{\infty}$ and $\ell_{1}$ constraints simultaneously, allowing us to treat them in a unified framework. In general, we consider the domain

\mathcal{X}_{\tau}\left(\mathbf{r},\prod_{i}[\mathbf{s}_{i},\mathbf{t}_{i}]% \right)=\Big\{\mathbf{x}\in\prod_{i}[\mathbf{s}_{i},\mathbf{t}_{i}]:\sum_{i}% \mathbf{r}_{i}\mathbf{x}_{i}\leq\tau\Big\}

for our primal variable $\mathbf{x}$ , this captures both the $\ell_{\infty}$ and the $\ell_{1}$ constraints. With this definition in place, we now turn to the main algorithmic result establishing the existence of efficient procedures for solving certain joint $\ell_{1}$ / $\ell_{\infty}$ min-max problems.

Theorem 11.

There exists an algorithm, given a non-empty $\mathcal{X}=\mathcal{X}_{2}\left(\mathbf{r},\prod_{i}[\mathbf{s}_{i},\mathbf{t% }_{i}]\right)$ and $\mathbf{P},\mathbf{Q}\in\mathbb{R}^{c\times d}$ with $\|\mathbf{P}\|_{\infty},\|\mathbf{Q}\mathbf{R}^{-1}\|_{1}\leq 2$ , runs in $\tilde{O}\big((\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q})+c+d)\log(% \frac{\min_{i}\mathbf{r}_{i}}{\epsilon})\varepsilon^{-1}\big)$ work, $\tilde{O}\big((\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q})+1)\log(\frac% {\min_{i}\mathbf{r}_{i}}{\epsilon})\varepsilon^{-1}\big)$ depth and outputs $\mathbf{x}\in\mathcal{X}$ , $(\mathbf{y},\mathbf{z})\in\Delta_{c}\times[0,1]^{c}$ such that

\varepsilon\geq\max_{\mathbf{x}^{\prime}\in\mathcal{X},(\mathbf{y}^{\prime},% \mathbf{z}^{\prime})\in\Delta_{c}\times[0,1]^{c}}\mathcal{A}(\mathbf{x},(% \mathbf{y}^{\prime},\mathbf{z}^{\prime}))-\mathcal{A}(\mathbf{x}^{\prime},(% \mathbf{y},\mathbf{z}))

where $\mathcal{A}(\mathbf{x},(\mathbf{y},\mathbf{z}))=\mathbf{y}^{\top}\mathbf{P}% \mathbf{x}+\mathbf{z}^{\top}\mathbf{Q}\mathbf{x}$ .

The theorem guarantees an approximate saddle point under both $\ell_{1}$ and $\ell_{\infty}$ constraints with polylog overhead in work/depth. The next corollary specializes this result to a more concrete case where additional linear terms appear in the objective.

Corollary 12.

There exists an algorithm, given $\mathbf{P},\mathbf{Q}\in\mathbb{R}^{c\times m}$ and $\mathbf{p},\mathbf{q}\in\mathbb{R}^{m}$ with $\|\mathbf{P}\|_{\infty},\|\mathbf{p}\|_{\infty}\leq 1,\|\mathbf{Q}\mathbf{R}^{% -1}\|_{1},\|\mathbf{q}\|_{1}\leq 2$ , runs in $\tilde{O}\big((\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q})+c+m)\log(% \frac{\min_{i}\mathbf{r}_{i}}{\epsilon})\varepsilon^{-1}\big)$ work, $\tilde{O}\big((\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q})+1)\log(\frac% {\min_{i}\mathbf{r}_{i}}{\epsilon})\varepsilon^{-1}\big)$ depth and outputs $\mathbf{x}\in\mathcal{X}=\mathcal{X}_{1}\left(\mathbf{r},[0,1]^{m}\right)$ , $(\mathbf{y},\mathbf{z})\in\Delta_{m}\times[0,1]^{m}$ such that

\varepsilon\geq\max_{\mathbf{x}^{\prime}\in\mathcal{X},(\mathbf{y}^{\prime},% \mathbf{z}^{\prime})\in\Delta_{m}\times[0,1]^{m}}\mathcal{A}(\mathbf{x},(% \mathbf{y}^{\prime},\mathbf{z}^{\prime}))-\mathcal{A}(\mathbf{x}^{\prime},(% \mathbf{y},\mathbf{z}))

where $\mathcal{A}(\mathbf{x},(\mathbf{y},\mathbf{z}))=\mathbf{y}^{\top}\mathbf{P}% \mathbf{x}+\mathbf{z}^{\top}\mathbf{Q}\mathbf{x}-\mathbf{p}^{\top}\mathbf{y}-% \mathbf{q}^{\top}\mathbf{z}$ .

We now explain how this corollary follows as a direct consequence of Theorem 11.

Proof of Corollary 12.

Observe that the matrix $\left[\mathbf{p}|\mathbf{P}\right]$ has $\ell_{\infty}$ -norm at most $2$ , $\left[\mathbf{q}|\mathbf{Q}\mathbf{R}^{-1}\right]$ has $\ell_{1}$ -norm at most $2$ and $[1]\times\mathcal{X}=\mathcal{X}_{2}\left(\binom{1}{\mathbf{r}},[1]\times[0,1]% ^{m}\right)$ , thus Corollary 12 follows immediately from Theorem 11. $\hfill\blacktriangleleft$ Corollary 12 implies Corollary 2.

Proof of Corollary 2.

We call Corollary 12 with the vectors $\left[\begin{array}[]{l}-\mathbf{p}\\ \mathbf{p}\end{array}\right],\left[\begin{array}[]{l}-\mathbf{q}\\ \mathbf{q}\end{array}\right]$ and the matrices $\left[\begin{array}[]{l}-\mathbf{P}\\ \mathbf{P}\end{array}\right],\left[\begin{array}[]{l}-\mathbf{Q}\\ \mathbf{Q}\end{array}\right]$ . Corollary 12 gives the conclusion for $(\mathbf{x},(\mathbf{y}_{1},\mathbf{y}_{2}),(\mathbf{z}_{1},\mathbf{z}_{2}))% \in[0,1]^{m}\times\Delta_{2m}\times[0,1]^{2m}$

	$\displaystyle\max_{(\mathbf{y}_{1}^{\prime},\mathbf{y}_{2}^{\prime})\in\Delta_% {2m}}(\mathbf{y}_{1}^{\prime}-\mathbf{y}_{2}^{\prime})^{\top}\left(\mathbf{Px}% -\mathbf{p}\right)+\max_{\mathbf{z}_{1}^{\prime},\mathbf{z}_{2}^{\prime}\in[0,% 1]^{m}}(\mathbf{z}_{1}^{\prime}-\mathbf{z}_{2}^{\prime})^{\top}\left(\mathbf{% Qx}-\mathbf{q}\right)$
	$\displaystyle=\max_{\mathbf{y}^{\prime}\in\Delta_{2m},\mathbf{z}^{\prime}\in[0% ,1]^{2m}}\mathfrak{A}\left(\mathbf{x},(\mathbf{y}^{\prime},\mathbf{z}^{\prime}% )\right)\leq\epsilon+\max_{\mathbf{x}^{\prime}\in[0,1]^{m}}\mathfrak{A}\left(% \mathbf{x}^{\prime},(\mathbf{y},\mathbf{z})\right)$
	$\displaystyle=\epsilon+\max_{\mathbf{x}\in[0,1]^{m}}(\mathbf{y}_{1}-\mathbf{y}% _{2})^{\top}\left(\mathbf{Px}-\mathbf{p}\right)+(\mathbf{z}_{1}-\mathbf{z}_{2}% )^{\top}\left(\mathbf{Qx}-\mathbf{q}\right).$

Either, we have that $\max_{\mathbf{x}\in[0,1]^{m}}(\mathbf{y}_{1}-\mathbf{y}_{2})^{\top}\left(% \mathbf{Px}-\mathbf{p}\right)+(\mathbf{z}_{1}-\mathbf{z}_{2})^{\top}\left(% \mathbf{Qx}-\mathbf{q}\right)=0$ in which case the chain of inequalities above implies item 1 of Corollary 2 or $\max_{\mathbf{x}\in[0,1]^{m}}(\mathbf{y}_{1}-\mathbf{y}_{2})^{\top}\left(% \mathbf{Px}-\mathbf{p}\right)+(\mathbf{z}_{1}-\mathbf{z}_{2})^{\top}\left(% \mathbf{Qx}-\mathbf{q}\right)>0$ and we can conclude item 2 of Corollary 2. $\hfill\blacktriangleleft$ The next section develops the regularization framework used in proving area-convexity, which is the key analytic ingredient underlying the optimization guarantee.

5.1 An area-convex regularizer for Theorem 11

To control the curvature of the optimization landscape, we define an appropriate regularizer $\phi$ . This regularizer links the primal and dual variables in a structured way and ensures the stability of the algorithm. We introduce the regularizer $\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))=\alpha\cdot\sum_{i,j}\overline{% \mathbf{P}}_{i,j}\operatorname{port}\left(\mathbf{x}_{j},\mathbf{y}_{i}\right)% +\overline{\mathbf{Q}}_{i,j}\mathbf{r}_{j}^{-1}\operatorname{port}\left(% \mathbf{z}_{i},\mathbf{r}_{j}\cdot\mathbf{x}_{j}\right),$ where $\operatorname{port}(x,y)=\frac{x^{2}y}{2}+\beta\cdot y\log y$ and where the matrix $\bar{\mathbf{P}}_{i,j}=\frac{|\mathbf{P}_{ij}|}{\|\mathbf{P}_{i,\cdot}\|_{1}},% \bar{\mathbf{Q}}_{i,j}=\frac{|\mathbf{Q}_{ij}|\cdot\mathbf{r}_{j}}{\|\mathbf{Q% }_{\cdot,j}\|_{1}}$ (w.l.o.g., we may assume that no row of $\mathbf{P}$ and no column of $\mathbf{Q}$ is zero; otherwise, drop them). We note that each row of $\bar{\mathbf{P}}$ and each column of $\bar{\mathbf{Q}}\mathbf{R^{-1}}$ sums to one, that $\|\bar{\mathbf{P}}\|_{\infty},\|\bar{\mathbf{Q}}\mathbf{R}^{-1}\|_{1}=1$ , and that $\bar{\mathbf{P}}_{i,j}\geq|\mathbf{P}_{ij}|/2,\bar{\mathbf{Q}}_{i,j}\geq|% \mathbf{Q}_{ij}|/2$ (since, by assumption, $\|\mathbf{P}\|_{\infty},\|\mathbf{QR}^{-1}\|_{1}\leq 2$ ). To get a handle on the regularizer on the Hessian of the regularizer, we introduce the function $H(\mathbf{x},(\mathbf{y},\mathbf{z}))=\alpha\cdot\sum_{i,j}\bar{\mathbf{P}}_{i% ,j}h_{ji}(\mathbf{x},\mathbf{y})+\bar{\mathbf{Q}}_{i,j}h_{ij}(\mathbf{z},% \mathbf{x})$ where $h_{ji}(\mathbf{x},\mathbf{y})=\mathbf{y}_{i}\cdot\langle d\mathbf{x}_{j},d% \mathbf{x}_{j}\rangle+\frac{\beta}{\mathbf{y}_{i}}\cdot\langle d\mathbf{y}_{i}% ,d\mathbf{y}_{i}\rangle$ . One should understand it as the diagonal terms of the Hessian $\nabla^{2}\phi$ , we will argue that $H$ approximates $\nabla^{2}\phi$ in $\mathbb{C}$ -Loewner order. The outline of the argument is the same as in the paper of Sherman. In Lemma 13, we bound the the image of the regularizer, in Claim 14 we argue that $H$ approximates $\nabla^{2}\phi$ in $\mathbb{C}$ -Loewner order, which will be helpful for arguing that $\phi$ is area-convex in Lemma 15. In Lemma 21, we argue that there exists an $\delta$ -AMO for $\phi$ for this we need to argue for stability in $\mathbf{y}$ in claims 20. No argument for stability is necessary for $\mathbf{x},\mathbf{z}$ .

Lemma 13.

Forall $\mathbf{x}\in\mathcal{X},\mathbf{y}\in\Delta_{c},\mathbf{z}\in[0,1]^{c}:|\phi(% \mathbf{x},(\mathbf{y},\mathbf{z}))|\leq\tilde{O}\left(\alpha\cdot(1+\beta)\right)$

This lemma provides a uniform bound on $\phi$ across the feasible domain, which will be essential when arguing about its curvature properties.

Proof.

	$\displaystyle\|\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))\|$	$\displaystyle=\alpha\cdot\left(\sum_{i,j}\overline{\mathbf{P}}_{i,j}% \operatorname{port}\left(\mathbf{x}_{j},\mathbf{y}_{i}\right)+\overline{% \mathbf{Q}}_{i,j}\mathbf{r}_{j}^{-1}\operatorname{port}\left(\mathbf{z}_{i},% \mathbf{r}_{j}\cdot\mathbf{x}_{j}\right)\right)$
		$\displaystyle=O\left(\alpha\cdot(1+\beta)\cdot\sum_{i}\mathbf{y}_{i}\|\log(% \mathbf{y}_{i})\|\sum_{j}\overline{\mathbf{P}}_{i,j}\right)$
		$\displaystyle+O\left(\alpha\cdot(1+\beta)\cdot\sum_{j}\left(\mathbf{r}_{j}% \cdot\mathbf{x}_{j}\|\log(\mathbf{r}_{j}\cdot\mathbf{x}_{j})\|\sum_{i}\overline{% \mathbf{Q}}_{i,j}\cdot\mathbf{r}_{j}^{-1}\right)\right)$
		$\displaystyle=O\left(\alpha\cdot(1+\beta)\cdot\left(\sum_{i}\mathbf{y}_{i}\|% \log(\mathbf{y}_{i})\|+\sum_{j}\mathbf{r}_{j}\cdot\mathbf{x}_{j}\|\log(\mathbf{r% }_{j}\cdot\mathbf{x}_{j})\|\right)\right)$
		$\displaystyle=\tilde{O}\left(\alpha\cdot(1+\beta)\right).$

where we used in the second equality that $\mathbf{x}\in[0,1]^{m},\mathbf{z}\in[0,1]^{c},(\mathbf{r}_{i}\mathbf{x}_{i})_{% i}\in\Delta_{m},\mathbf{y}\in\Delta_{c}$ , and thus $\operatorname{port}(\mathbf{x}_{j},\mathbf{y}_{i})\leq(1+\beta)\cdot\mathbf{y}% _{i}\cdot|\log(\mathbf{y}_{i})|$ and $\operatorname{port}(\mathbf{z}_{i},\mathbf{r}_{j}\mathbf{x}_{j})\leq(1+\beta)% \cdot\mathbf{r}_{j}\mathbf{x}_{j}\cdot|\log(\mathbf{r}_{j}\mathbf{x}_{j})|$ . in the third, equality we used that $\|\bar{\mathbf{P}}\|_{\infty},\|\bar{\mathbf{Q}}\mathbf{R}^{-1}\|_{1}=1$ . $\hfill\blacktriangleleft$ Next, we show that the quadratic form $H$ closely approximates the Hessian of $\phi$ , which is crucial for establishing curvature control.

Lemma 14.

For $\beta>0$ large enough, $\frac{1}{2}H(\mathbf{x},(\mathbf{y},\mathbf{z}))\preceq\nabla^{2}\phi(\mathbf{% x},(\mathbf{y},\mathbf{z}))\preceq 2H(\mathbf{x},(\mathbf{y},\mathbf{z})).$

Proof.

We can express the Hessian of $\operatorname{port}$ as $\nabla^{2}\operatorname{port}(\mathbf{x}_{j},\mathbf{y}_{i})=h_{ji}(\mathbf{x}% ,\mathbf{y})+\mathbf{x}_{j}\cdot\langle d\mathbf{x}_{j},d\mathbf{y}_{i}\rangle% +\mathbf{x}_{j}\cdot\langle d\mathbf{y}_{i},d\mathbf{x}_{j}\rangle$ . We note that for all $a=a_{1}+i\cdot a_{2},b=b_{1}+i\cdot b_{2}\in\mathbb{C}$

\left(\mathbf{x}_{i}\cdot\langle d\mathbf{x}_{j},d\mathbf{y}_{i}\rangle+% \mathbf{x}_{i}\cdot\langle d\mathbf{y}_{i},d\mathbf{x}_{i}\rangle\right)\left(% \left(\begin{array}[]{l}a\cdot\mathds{1}_{j}\\ b\cdot\mathds{1}_{i}\end{array}\right),\left(\begin{array}[]{l}a\cdot\mathds{1% }_{j}\\ b\cdot\mathds{1}_{i}\end{array}\right)\right)=\mathbf{x}_{j}\cdot\bar{a}b+% \mathbf{x}_{j}\cdot\bar{b}a

and
$\displaystyle h_{ji}(\mathbf{x}_{j},\mathbf{y}_{i})\left(\left(\begin{array}[]% {l}a\cdot\mathds{1}_{j}\\ b\cdot\mathds{1}_{i}\end{array}\right),\left(\begin{array}[]{l}a\cdot\mathds{1% }_{j}\\ b\cdot\mathds{1}_{i}\end{array}\right)\right)$ $\displaystyle=\mathbf{y}_{i}\cdot\bar{a}\cdot a+\frac{\beta}{\mathbf{y}_{i}}% \bar{b}\cdot b=\mathbf{y}_{i}\cdot\left(a_{1}^{2}+a_{2}^{2}\right)+\frac{\beta% }{\mathbf{y}_{i}}\cdot\left(b_{1}^{2}+b_{2}^{2}\right)$ $\displaystyle=\left(\mathbf{y}_{i}\cdot a_{1}^{2}+\frac{\beta}{\mathbf{y}_{i}}% \cdot b_{1}^{2}\right)+\left(\mathbf{y}_{i}\cdot a_{2}^{2}+\frac{\beta}{% \mathbf{y}_{i}}\cdot b_{2}^{2}\right)$

Since $\mathbf{x}_{j}\in[0,1]$ , $-2(|a_{1}b_{1}|+|a_{2}b_{2}|)\leq\mathbf{x}_{j}\cdot\bar{a}b+\mathbf{x}_{j}% \cdot\bar{b}a\leq 2(|a_{1}b_{1}|+|a_{2}b_{2}|)$ . Consider the two terms separately. For the first case, we make a case distinction $\mathbf{y}_{i}\leq\frac{\sqrt{\beta}|b_{1}|}{|a_{1}|}$ and $\mathbf{y}_{i}\geq\frac{\sqrt{\beta}|b_{1}|}{|a_{1}|}$ while for the second case we make a case distinction $\mathbf{y}_{i}\leq\frac{\sqrt{\beta}|b_{2}|}{|a_{2}|}$ and $\mathbf{y}_{i}\geq\frac{\sqrt{\beta}|b_{2}|}{|a_{2}|}$ . This allows one to find that

h_{ji}(\mathbf{x},\mathbf{y})\left(\left(\begin{array}[]{l}a\cdot\mathds{1}_{j% }\\ b\cdot\mathds{1}_{i}\end{array}\right),\left(\begin{array}[]{l}a\cdot\mathds{1% }_{j}\\ b\cdot\mathds{1}_{i}\end{array}\right)\right)\geq\frac{\sqrt{\beta}}{2}\cdot% \left|\bar{a}b+\bar{b}a\right|

Provided that $\beta$ is large enough, we have that $h_{ji}(\mathbf{x},\mathbf{y})/2\leq\nabla^{2}\operatorname{port}(\mathbf{x}_{j% },\mathbf{y}_{i})\leq 2h_{ji}(\mathbf{x},\mathbf{y})$ . Note also that $\nabla^{2}\operatorname{port}(\mathbf{z}_{i},\mathbf{r}_{j}\cdot\mathbf{x}_{j}% )=\mathbf{r}_{j}\cdot\left(h_{ij}(\mathbf{z},\mathbf{x})+\mathbf{z}_{i}\cdot% \langle d\mathbf{z}_{i},d\mathbf{x}_{j}\rangle+\mathbf{z}_{i}\cdot\langle d% \mathbf{x}_{j},d\mathbf{z}_{i}\rangle\right)$ and thus $h_{ij}(\mathbf{z},\mathbf{x})/2\leq\mathbf{r}_{j}^{-1}\nabla^{2}\operatorname{% port}(\mathbf{z}_{i},\mathbf{r}_{j}\mathbf{x}_{j})\leq 2h_{ij}(\mathbf{z},% \mathbf{x})$ . This concludes the argument. $\hfill\blacktriangleleft$ Having controlled the Hessian approximation, we can now prove that $\phi$ is area-convex with respect to an appropriate matrix $\mathbf{J}$ .

Lemma 15.

$\phi$ is area-convex w.r.t. $2\sqrt{3}\cdot\mathbf{J}$ where $\mathbf{J}=\frac{\alpha\sqrt{\beta}}{6\sqrt{3}}\left[\begin{array}[]{l|l}0&% \left[\begin{array}[]{l}-\mathbf{P}^{*}\quad-\mathbf{Q}^{*}\end{array}\right]% \\ \hline\cr\left[\begin{array}[]{l}\mathbf{P}\\ \mathbf{Q}\end{array}\right]&0\end{array}\right]$ .

Proof.

By Lemma 14, it suffices to prove $H(\mathbf{x},\mathbf{y})/3\succeq 2\sqrt{3}\cdot\mathbf{J}$ . We note that the $H$ is a sum of scaled $q$ functions. It thus suffices to verify that

	$\displaystyle\bar{\mathbf{P}}_{ij}\cdot h_{ji}(\mathbf{x},\mathbf{y})+\mathbf{% P}_{ij}\cdot\left(\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{x}_{j},d% \mathbf{y}_{i}\rangle-\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{y}_{i}% ,d\mathbf{x}_{j}\rangle\right)$	$\displaystyle\succeq 0$		(7)
	$\displaystyle\bar{\mathbf{Q}}_{ij}\cdot h_{ij}(\mathbf{z},\mathbf{x})+\mathbf{% Q}_{ij}\cdot\left(\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{z}_{i},d% \mathbf{x}_{j}\rangle-\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{x}_{j}% ,d\mathbf{z}_{i}\rangle\right)$	$\displaystyle\succeq 0$		(8)

Note that this is equivalent to

	$\displaystyle\bar{\mathbf{P}}_{ij}\cdot h_{ji}(\mathbf{x},\mathbf{y})+\|\mathbf% {P}_{ij}\|\cdot\left(\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{x}_{j},d% \mathbf{y}_{i}\rangle-\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{y}_{i}% ,d\mathbf{x}_{j}\rangle\right)$	$\displaystyle\succeq 0$		(9)
	$\displaystyle\bar{\mathbf{Q}}_{ij}\cdot h_{ij}(\mathbf{z},\mathbf{x})+\|\mathbf% {Q}_{ij}\|\cdot\left(\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{z}_{i},d% \mathbf{x}_{j}\rangle-\frac{i\cdot\sqrt{\beta}}{2}\cdot\langle d\mathbf{x}_{j}% ,d\mathbf{z}_{i}\rangle\right)$	$\displaystyle\succeq 0$		(10)

because if $\mathbf{P}_{i,j},\mathbf{Q}_{i,j}<0$ the sesquilinear form on the left hand side of (7),(8) evaluated on $((\mathbf{a,b}),(\mathbf{a,b}))\in(\mathbb{C}^{d}\times\mathbb{C}^{c})\times(% \mathbb{C}^{d}\times\mathbb{C}^{c})$ is the same as the sesquilinear form on left hand side of (9), (10) evaluated on $((\mathbf{-a,b}),(\mathbf{-a,b}))$ . Since $\bar{\mathbf{P}}_{ij}\geq|\mathbf{P}_{ij}|/2$ and $\bar{\mathbf{Q}}_{ij}\geq|\mathbf{Q}_{ij}|/2$ , it suffices to prove that $h_{ji}(\mathbf{x},\mathbf{y})+\left(i\cdot\sqrt{\beta}\cdot\langle d\mathbf{x}% _{j},d\mathbf{y}_{i}\rangle-i\cdot\sqrt{\beta}\cdot\langle d\mathbf{y}_{i},d% \mathbf{x}_{j}\rangle\right)\succeq 0.$ We observe that for any $a,b\in\mathbb{C},\frac{1}{\mathbf{y}_{i}}\cdot(\sqrt{\beta}\cdot\overline{b}+i% \cdot\mathbf{y}_{i}\cdot\overline{a})\cdot(\sqrt{\beta}\cdot b-i\cdot\mathbf{y% }_{i}\cdot a)\geq 0$ implies that

	$\displaystyle h_{ji}(\mathbf{x},\mathbf{y})+\left(i\cdot\sqrt{\beta}\cdot% \langle d\mathbf{x}_{j},d\mathbf{y}_{i}\rangle-i\cdot\sqrt{\beta}\cdot\langle d% \mathbf{y}_{i},d\mathbf{x}_{j}\rangle\right)$	$\displaystyle=$
	$\displaystyle\mathbf{y}_{i}\cdot\overline{d\mathbf{x}_{v}}\otimes d\mathbf{x}_% {v}+\frac{\beta}{\mathbf{y}_{i}}\cdot\overline{d\mathbf{y}_{i}}\otimes d% \mathbf{y}_{i}+i\cdot\sqrt{\beta}\cdot\langle d\mathbf{x}_{j},d\mathbf{y}_{i}% \rangle-i\cdot\sqrt{\beta}\cdot\langle d\mathbf{y}_{i},d\mathbf{x}_{j}\rangle$	$\displaystyle=$
	$\displaystyle\frac{1}{\mathbf{y}_{i}}\cdot\langle\sqrt{\beta}\cdot d\mathbf{y}% _{i}-i\cdot\mathbf{y}_{i}\cdot d\mathbf{x}_{j},\sqrt{\beta}\cdot d\mathbf{y}_{% i}-i\cdot\mathbf{y}_{i}\cdot d\mathbf{x}_{j}\rangle$	$\displaystyle\succeq 0.$

This yields the conclusion of the lemma. $\hfill\blacktriangleleft$

5.2 Approximate Maximum Oracle for Theorem 11

We now turn to the algorithmic aspect – constructing an approximate maximum oracle (AMO) for $\phi$ . The AMO allows us to efficiently compute near-optimal responses in the min-max game. Before, we discuss the actual algorithm, we should discuss how to evaluate the so-called Lambert function as we will use it to compute our primal response.

5.2.1 Lambert Function

The Lambert function $W$ defines for a restricted region the inverse function of $f(w)=w\exp(w)$ . For our purposes, it suffices to restrict the discussion to $W:[0,\infty)\rightarrow[0,\infty)$ . The function is implicitly defined by $W(x)$ is the unique root of the $w\exp(w)-x$ for $w\in[0,1]$ . An very tight bound for large values of $W$ can be found by the following easy lemma:

Lemma 16.

For $x\geq e,\log(x)-\log\log(x)\leq W(x)\leq\log(x)-\log\log(x)+\frac{\log\log(x)}% {\log(x)}$

Proof.

Note that $f(w)$ is strictly monotone and $f(\log(x)+\log\log(x))=\left(1-\frac{\log\log(x)}{\log(x)}\right)\cdot x<x$ and
$f(\log(x)+\log\log(x)+\log\log(x)/\log(x))=\left(1-\frac{\log\log(x)}{\log(x)}% +\frac{\log\log(x)}{\log(x)^{2}}\right)\cdot x\cdot\exp\left(\frac{\log\log(x)% }{\log(x)}\right)>x.$

This implies the bounds. $\hfill\blacktriangleleft$ There does not exist a closed form solution of the Lambert function, but we can evaluate $W(x)$ efficiently using the projected Newton-Raphson method.

Lemma 17.

For all $x\in[0,\infty),$ , we can find $w$ such that $W(x)-\epsilon<w<W(x)+\epsilon$ for $\epsilon>0$ in work and depth $O(\log(1/\epsilon))$ ⁴⁴4Given that we have an $O(\log(1/\epsilon)$ error dependence for computing $W$ , we will, in the following, neglect this error to ease presentation..

Proof.

Recall the projected Newton-Raphson method is given by $w_{i+1}=\operatorname{chop}\left(w_{i}-\frac{f(w_{i})}{f^{\prime}(w_{i})}\right)$ where $\operatorname{chop}(t)=\max\left(0,t\right)$ . Note that $w\exp(w)$ is a strictly increasing function and that $f(0)=0\cdot\exp(0)=0,f(1)=1\cdot\exp(1)=e$ so there exists a unique root in $[0,1]$ . Let $w^{*}$ denote this unique root. By Taylor, we find that

0=f(w^{*})-x=f(w_{i})-x+f^{\prime}(w_{i})(w^{*}-w_{i})+\frac{1}{2}f^{\prime% \prime}(\zeta)(w^{*}-w_{i})^{2}.

Thus,

|w^{*}-w_{i+1}|\leq\left|\left(w_{i}+\frac{1}{f^{\prime}(w_{i})}(x-f(w_{i}))% \right)-w^{*}\right|=\left|\frac{f^{\prime\prime}(\zeta)}{2f^{\prime}(w_{i})}(% w^{*}-w_{i})^{2}\right|.

We observe that $f^{\prime}(w)=\exp(w)(w+1)$ and $f^{\prime\prime}(w)=\exp(w)(w+2)$ . We can thus bound the coefficient by $|w^{*}-w_{i+1}|\leq\left|w^{*}-w_{i}\right|^{2}$ provided our initial guess $w_{0}$ satisfies $|w_{0}-w^{*}|\leq\frac{1}{2}$ , we can conclude that the projected Newton-Raphson method converges fast enough. Observe that by Lemma 16, $\log(x)-\log\log(x)$ is a good enough guess if $x\geq e^{2}$ . For $x$ smaller than $e^{2}$ , we observe that $W(x)\leq 2$ as $f(2)=2\exp(2)>x$ . We may thus try successively the initial guesses $0.5,1.5,2.5,3.5,4.5,5.5,6.5,7.5$ and terminate early if the Newton-Raphson method does not converge fast enough. $\hfill\blacktriangleleft$

5.2.2 Alternating Primal Dual Optimization yields an AMO

Given that we know how to evaluate the Lambert function, we now turn to actually constructing an approximate maximum oracle (AMO) for $\phi$ using alternating primal and dual maximization.

Algorithm 1 Approximate Minimizer for

\phi

.

This algorithm alternates between optimizing over $\mathbf{x}$ and $(\mathbf{y},\mathbf{z})$ , improving the objective until convergence to an approximate minimizer. The next two subroutines describe how to optimize each block efficiently.

Algorithm 2 Maximizing

\mathbf{x}

.

The following lemma guarantees the correctness and work/depth bound for the $\mathbf{x}$ -maximization step.

Lemma 18.

Algorithm 2 returns a $\mathbf{x}\in\mathcal{C}$ such that for all $\mathbf{x}^{\prime}\in\mathcal{C},\mathbf{c}^{\top}\mathbf{x}-\phi(\mathbf{x},% (\mathbf{y},\mathbf{z}))+\delta_{\mathbf{x}}\geq\mathbf{c}^{\top}\mathbf{x}^{% \prime}-\phi(\mathbf{x}^{\prime},(\mathbf{y},\mathbf{z}))$ in $O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(c+d+\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{% Q}))\right)$ work and depth $O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(1+\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q% }))\right).$

Proof.

Note that for fixed $\lambda$ , the optimization problem for each variable decouples. For one variable, we want to maximize $f_{i}(\mathbf{x}_{i})=a_{i}\mathbf{x}_{i}+b_{i}\mathbf{x}_{i}^{2}+c_{i}\,% \mathbf{x}_{i}\log(d_{i}\mathbf{x}_{i}),\mathbf{x}_{i}\in[0,1],$ where $a_{i}=\sum_{j}(\mathbf{c}_{j}-\alpha\cdot\sum_{i}\bar{\mathbf{Q}}_{i,j}\frac{% \mathbf{z}_{i}^{2}}{2})$ , $d_{j}=\mathbf{r}_{j}>0$ , and $b_{i}=\alpha\cdot(\sum_{i}\bar{\mathbf{P}}_{i,j}\cdot\frac{\mathbf{y}_{i}}{2})% ,c_{i}=-\alpha\beta\cdot\mathbf{r}_{j}\cdot\sum_{i}\bar{\mathbf{Q}}_{i,j}% \mathbf{r}_{j}^{-1}=-\alpha\beta\cdot\mathbf{r}_{j}<0$ (where we used that the columns of $\bar{\mathbf{Q}}\mathbf{R}^{-1}$ sum up to one). For the Lagrangian, we write $\mathcal{L}_{i}(\mathbf{x}_{i},\lambda)=f_{i}(\mathbf{x}_{i})-\lambda\cdot% \mathbf{x}_{i}$ . The first and second derivatives are

f_{i}^{\prime}(\mathbf{x}_{i})=a_{i}+2b_{i}\mathbf{x}_{i}+c_{i}\left(\log(d_{i% }\mathbf{x}_{i})+1\right),\qquad f_{i}^{\prime\prime}(\mathbf{x}_{i})=2b_{i}+% \frac{c_{i}}{\mathbf{x}_{i}}.

Stationary points of the Lagrangian satisfy

\frac{d}{d\mathbf{x}_{i}}\mathcal{L}_{i}(\mathbf{x}_{i},\lambda)=0\quad% \Longleftrightarrow\quad 2b_{i}\mathbf{x}_{i}+c_{i}\log(d_{i}\mathbf{x}_{i})+(% a_{i}+\lambda+c_{i})=0.

Rearranging the stationary equation gives $d_{i}\mathbf{x}_{i}=\exp\!\left(-(2b_{i}\cdot\mathbf{x}_{i}+a_{i}+\lambda+c_{i% })/c_{i}\right),$ or equivalently $\mathbf{x}_{i}\exp\!\left(\tfrac{2b_{i}}{c_{i}}\mathbf{x}_{i}\right)=\frac{1}{% d_{i}}\,\exp\!\left(-\tfrac{a_{i}+\lambda+c_{i}}{c_{i}}\right).$ If $b_{i}=0$ , this already defines the answer. Otherwise, we set $u_{i}=\tfrac{2b_{i}}{c_{i}}\mathbf{x}_{i}$ , we obtain $u_{i}e^{u_{i}}=\frac{2b_{i}}{c_{i}d_{i}}\,\exp\!\left(-\tfrac{a_{i}+\lambda+c_% {i}}{c_{i}}\right).$ Hence the stationary solutions are $\mathbf{x}_{i}=\frac{c_{i}}{2b_{i}}\;W\!\left(2b_{i}e^{-(a_{i}+\lambda+c_{i})/% c_{i}}/(c_{i}d_{i})\right),$ where $W$ denotes the Lambert W-function. By Lemma 17, we know how to efficiently evaluate the Lambert W-function up to an error of $\delta_{X}/2$ in work $O\left(m\cdot\log(\frac{1}{\delta_{X}})\right)$ and depth $O\left(\log(\frac{1}{\delta_{X}})\right)$ . Let us denote by $\mathbf{x}_{i}(\lambda)$ the argmax of $\mathcal{L}_{i}(\mathbf{x}_{i},\lambda)=f_{i}(\mathbf{x}_{i})-\lambda\cdot% \mathbf{x}_{i}$ . We note that

\displaystyle f_{i}\left(\mathbf{x}_{i}\left(\lambda^{*}\right)\right)-f_{i}(% \mathbf{x}_{i}(\hat{\lambda}))=\left.\frac{d}{d\lambda}f_{i}\left(\mathbf{x}_{% i}(\lambda)\right)\right|_{\lambda=\tilde{\lambda}}\cdot\left(\lambda^{*}-\hat% {\lambda}\right).

By optimality, we have that $\frac{df_{i}}{d\mathbf{x}_{i}}(\mathbf{x}_{i}(\lambda))=\lambda$ and thus $\frac{d\mathbf{x}_{i}(\lambda)}{d\lambda}=\frac{1}{\frac{df_{i}}{d\mathbf{x}_{% i}}(\mathbf{x}_{i}(\lambda))}\leq\frac{1}{2b_{i}+c_{i}}$ . Combining those two bounds, we obtain
$\displaystyle f_{i}\left(\mathbf{x}_{i}\left(\lambda^{*}\right)\right)-f_{i}(% \mathbf{x}_{i}(\hat{\lambda}))\leq\frac{\tilde{\lambda}}{2b_{i}+c_{i}}\cdot% \left(\lambda^{*}-\hat{\lambda}\right)\leq\frac{\lambda^{*}}{2b_{i}+c_{i}}% \cdot\left(\lambda^{*}-\hat{\lambda}\right)\leq O\left(\frac{\lambda^{*}}{% \alpha\cdot\beta\cdot\mathbf{r}_{i}}\cdot\left(\lambda^{*}-\hat{\lambda}\right% )\right).$

Moreover, $\lambda^{*}=\frac{df_{i}}{d\mathbf{x}_{i}}(\mathbf{x}_{i}(\lambda^{*}))=a_{i}+% 2b_{i}\mathbf{x}_{i}+c_{i}\left(\log(d_{i}\mathbf{x}_{i})+1\right)\leq\|% \mathbf{c}\|_{1}$ . Taking $0\leq\lambda^{*}-\hat{\lambda}\leq\frac{\alpha\beta\cdot\mathbf{r}_{i}}{\|% \mathbf{c}\|_{1}}\frac{\delta_{x}}{2}$ , we incur an error of $\delta_{X}/2$ due to inexact $\lambda$ , which adds to the error coming from inexactly evaluating the Lambert W-function. $\hfill\blacktriangleleft$ Analogously, the next algorithm computes the best response for $(\mathbf{y},\mathbf{z})$ given a fixed $\mathbf{x}$ .

Algorithm 3 Maximizing

(\mathbf{y},\mathbf{z})

.

Lemma 19.

Algorithm 3 returns a $\mathbf{y}\in\Delta_{c},\mathbf{z}\in[0,1]^{c}$ such that for fixed $\mathbf{x}\in\mathcal{C},\mathbf{d}^{\top}\mathbf{y}+\mathbf{e}^{\top}\mathbf{% z}-\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))$ is maximized.

Proof.

The maximizer of $\mathbf{d}^{\top}\mathbf{y}-\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))$ also maximizes $(\mathbf{d}-\alpha\cdot\mathbf{h})^{\top}\mathbf{y}-\alpha\cdot\beta\cdot\sum_% {i}\mathbf{y}_{i}\log(\mathbf{y}_{i})$ , where we used that $\sum_{j}\bar{\mathbf{P}}_{ij}=1$ . A standard computation yields the result. The maximizer of $\mathbf{e}^{\top}\mathbf{z}-\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))$ also maximizes $\mathbf{e}^{\top}\mathbf{z}-\sum_{i}\tilde{\mathbf{z}}_{i}\mathbf{x}_{i}^{2}$ . Since the domain is box-constrained and there are no mixed terms in the objective, the variables decouple and it is straightforward to solve the problem for each variable. $\hfill\blacktriangleleft$ We now study the stability of the dual variables with respect to small perturbations in $\mathbf{x}$ . This property ensures that updates in alternating minimization behave smoothly.

Lemma 20.

Let $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{C}$ . Let $(\mathbf{y},\mathbf{z})$ maximize $\eta(\mathbf{x},(\mathbf{y},\mathbf{z}))$ and $(\mathbf{y}^{\prime},\mathbf{z}^{\prime})$ maximize $\eta(\mathbf{x}^{\prime},\mathbf{y}^{\prime},\mathbf{z}^{\prime})$ . Then, $(1-\gamma)\mathbf{y}\leq\mathbf{y}^{\prime}\leq(1+\gamma)\mathbf{y}$ for $\gamma>0$ small.

Proof.

Note that $\mathbf{h}_{i}$ varies by at most $O(1)$ , indeed we have that $|\mathbf{h}_{i}|=\left|\sum_{j}\bar{\mathbf{P}}_{i,j}\frac{\mathbf{x}_{j}^{2}}% {2}\right|\leq\sum_{j}\left|\bar{\mathbf{P}}_{i,j}\right|=1$ . If we pick $\beta$ large enough, the claim follows by
$\exp\left(\frac{-2\|\mathbf{h}\|_{\infty}}{\beta}\right)\cdot\operatorname{% softmax}\left(\frac{\mathbf{d}}{\alpha\beta}\right)\leq\operatorname{softmax}% \left(\frac{\mathbf{d}}{\alpha\beta}-\frac{\mathbf{h}}{\beta}\right)\leq\exp% \left(\frac{2\|\mathbf{h}\|_{\infty}}{\beta}\right)\cdot\operatorname{softmax}% \left(\frac{\mathbf{d}}{\alpha\beta}\right).\$

$\hfill\blacktriangleleft$ Finally, combining all previous ingredients, we show that a $\delta$ -approximate maximum oracle exists and can be computed efficiently.

Lemma 21.

There is a $\delta$ -AMO for $\phi$ that runs in
$O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(c+d+\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{% Q}))\right)$ work and
$O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(1+\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q% }))\right)$ depth.

Proof.

We introduce the function $\eta(\mathbf{x},(\mathbf{y},\mathbf{z})):=\phi^{*}(\mathbf{c},\mathbf{d},% \mathbf{e})-\mathbf{c}^{\top}\mathbf{x}-\mathbf{d}^{\top}\mathbf{y}-\mathbf{e}% ^{\top}\mathbf{z}+\phi(\mathbf{x},(\mathbf{y},\mathbf{z})).$ We provide an algorithm that runs in $O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(c+d+\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{% Q}))\right)$ work and $O\left(\log\left(\frac{\|\mathbf{c}\|_{1}}{\alpha\beta\min_{i}\mathbf{r}_{i}% \delta_{\mathbf{x}}}\right)(1+\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q% }))\right)$ depth and returns $\delta$ -approximate minimizers to $\eta$ . By Remark 22, $\eta$ is strictly convex and since the domain $\mathcal{X}\times\Delta_{c}\times[0,1]^{c}$ is compact, there exists a unique minimizer. We denote the minimizer by $(\mathbf{x}^{*},(\mathbf{y}^{*},\mathbf{z}^{*}))$ . We denote by $\mathbf{x}^{(t)},\mathbf{y}^{(t)}$ the exact solution to the $t$ -th optimization problem and by $\tilde{\mathbf{x}}^{(t)}$ the inexact returned solution by Algorithm 2. Let us denote by $\bar{\Delta}$ the restricted region of $\Delta_{m}$ that $\mathbf{y}$ can take values in according to Lemma 20. The proof of Lemma 4.3 follows from the general framework for analyzing alternating minimization by [3]. The proof detail below follows from [13]. To simplify notation, we write $\bm{\zeta}=(\mathbf{y},\mathbf{z})$ . We use $\nabla_{\mathbf{x}},\nabla_{\bm{\zeta}}$ and $\nabla^{2}_{\mathbf{x}\mathbf{x}},\nabla^{2}_{\bm{\zeta}\bm{\zeta}}$ to denote the gradient with only the $\mathbf{x}$ and $\bm{\zeta}$ components kept. Let $\mathcal{X}^{(t+1)}=\left\{\mathbf{x}\in\mathcal{X}:\mathbf{x}\geq\frac{1}{2}% \mathbf{x}^{(t+1)}\right\}$ . We will first show that for all $\bm{\zeta},\bar{\bm{\zeta}}\in\bar{\Delta}\times[0,1]^{c}$ and $\bar{\mathbf{x}}\in\mathcal{X}^{(t+1)}$

\nabla^{2}\eta(\bar{\mathbf{x}},\bar{\bm{\zeta}})=\nabla^{2}\phi(\bar{\mathbf{% x}},\bar{\bm{\zeta}})\succeq\frac{1}{2}H(\bar{\mathbf{x}},\bar{\bm{\zeta}})% \succeq\frac{1}{6}\nabla_{\bm{\zeta}\bm{\zeta}}^{2}\eta\left(\mathbf{x}^{(t+1)% },\bm{\zeta}\right),

(11)

where the first Loewner inequality follows from 14. We observe that

	$\displaystyle h_{ji}(\bar{\mathbf{x}},\bar{\mathbf{y}})$	$\displaystyle=\bar{\mathbf{y}}_{i}\cdot\langle d\mathbf{x}_{j},d\mathbf{x}_{j}% \rangle+\frac{\beta}{\bar{\mathbf{y}}_{i}}\cdot\langle d\mathbf{y}_{i},d% \mathbf{y}_{i}\rangle\succeq\frac{\beta}{\bar{\mathbf{y}}_{i}}\cdot\langle d% \mathbf{y}_{i},d\mathbf{y}_{i}\rangle$
		$\displaystyle\succeq\frac{1}{3}\cdot\frac{\beta}{\mathbf{y}_{i}}\cdot\langle d% \mathbf{y}_{i},d\mathbf{y}_{i}\rangle$

where we used claim 20 in the second Loewner inequality and

\displaystyle h_{ij}(\bar{\mathbf{z}},\bar{\mathbf{x}})=\bar{\mathbf{x}}_{j}% \cdot\langle d\mathbf{z}_{i},d\mathbf{z}_{i}\rangle+\frac{\beta}{\bar{\mathbf{% x}}_{j}}\cdot\langle d\mathbf{x}_{j},d\mathbf{x}_{j}\rangle\succeq\bar{\mathbf% {x}}_{j}\cdot\langle d\mathbf{z}_{i},d\mathbf{z}_{i}\rangle\succeq\frac{1}{2}% \mathbf{x}_{j}^{(t+1)}\cdot\langle d\mathbf{z}_{i},d\mathbf{z}_{i}\rangle.

These two together yield the inequality (11). Now we show that for all $\hat{\mathbf{x}}\in\mathcal{X}^{(t+1)}$ and $\hat{\bm{\zeta}}\in\bar{\Delta}\times[0,1]^{c},\eta(\mathbf{x}^{(t+1)},\bm{% \zeta}^{(t)})-\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t+1)})\geq\frac{1}{6}\Big(% \eta(\mathbf{x}^{(t)},\bm{\zeta}^{(t+1)})-\eta(\hat{\mathbf{x}},\hat{\bm{\zeta% }})\Big).$ Let $\tilde{\bm{\zeta}}=\tfrac{5}{6}\bm{\zeta}^{(t)}+\tfrac{1}{6}\hat{\bm{\zeta}}$ . By the optimality of $\bm{\zeta}^{(t+1)}$ we have $\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t+1)})\leq\eta(\mathbf{x}^{(t+1)},\tilde{% \bm{\zeta}}).$ By the optimality of $\mathbf{x}^{(t+1)}$ we have $\big\langle\nabla_{\mathbf{x}}\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)}),% \mathbf{x}^{(t+1)}-\hat{\mathbf{x}}\big\rangle\leq 0$ which gives us
$\displaystyle\big\langle\nabla_{\bm{\zeta}}\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^% {(t)}),\bm{\zeta}^{(t)}-\tilde{\bm{\zeta}}\big\rangle$ $\displaystyle=\tfrac{1}{6}\big\langle\nabla_{\bm{\zeta}}\eta(\mathbf{x}^{(t+1)% },\bm{\zeta}^{(t)}),\bm{\zeta}^{(t)}-\hat{\bm{\zeta}}\big\rangle$ $\displaystyle\geq\tfrac{1}{6}\big\langle\nabla_{\bm{\zeta}}\eta(\mathbf{x}^{(t% +1)},\bm{\zeta}^{(t)}),\bm{\zeta}^{(t)}-\hat{\bm{\zeta}}\big\rangle+\tfrac{1}{% 6}\big\langle\nabla_{\mathbf{x}}\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)}),% \mathbf{x}^{(t+1)}-\hat{\mathbf{x}}\big\rangle$ $\displaystyle=\tfrac{1}{6}\big\langle\nabla\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^% {(t)}),\mathbf{w}^{(t+1)}-\hat{\mathbf{w}}\big\rangle$ (12)

where $\mathbf{w}^{(t+\frac{1}{2})}=(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})$ , $\hat{\mathbf{w}}=(\hat{\mathbf{x}},\hat{\bm{\zeta}})$ . Also define $\bm{\zeta}_{\alpha}=(1-\alpha)\bm{\zeta}^{(t)}+\alpha\hat{\bm{\zeta}}$ , $\tilde{\bm{\zeta}}_{\alpha}=(1-\alpha)\bm{\zeta}^{(t)}+\alpha\tilde{\bm{\zeta}}$ , $\mathbf{x}_{\alpha}=(1-\alpha)\mathbf{x}^{(t+1)}+\alpha\hat{\mathbf{x}}$ . With a slight abuse of notation, we also use $\nabla^{2}_{\bm{\zeta}\bm{\zeta}}$ to also mean the Hessian with respect to the variable $\bm{\zeta}$ . Using Taylor expansion $\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf{x}^{(t+1)},\tilde{\bm{% \zeta}})$
$\displaystyle=\big\langle\nabla_{\bm{\zeta}}\eta(\mathbf{x}^{(t+1)},\bm{\zeta}% ^{(t)}),\bm{\zeta}^{(t)}-\tilde{\bm{\zeta}}\big\rangle-\int_{0}^{1}\int_{0}^{% \beta}\big(\tilde{\bm{\zeta}}-\bm{\zeta}^{(t)}\big)^{\top}\nabla^{2}_{\bm{% \zeta}\bm{\zeta}}\eta(\mathbf{x}^{(t+1)},\tilde{\bm{\zeta}}_{\alpha})\big(% \tilde{\bm{\zeta}}-\bm{\zeta}^{(t)}\big)\,d\alpha d\beta$ $\displaystyle\geq\tfrac{1}{6}\big\langle\nabla\eta(\mathbf{x}^{(t+1)},\bm{% \zeta}^{(t)}),\mathbf{w}^{(t+\frac{1}{2})}-\hat{\mathbf{w}}\big\rangle-\frac{1% }{36}\int_{0}^{1}\int_{0}^{\beta}\big(\hat{\bm{\zeta}}-\bm{\zeta}^{(t)}\big)^{% \top}\nabla^{2}_{\bm{\zeta}\bm{\zeta}}\eta(\mathbf{x}^{(t+1)},\tilde{\bm{\zeta% }}_{\alpha})\big(\hat{\bm{\zeta}}-\bm{\zeta}^{(t)}\big)\,d\alpha d\beta$ $\displaystyle\geq\tfrac{1}{6}\big\langle\nabla\eta(\mathbf{x}^{(t+1)},\bm{% \zeta}^{(t)}),\mathbf{w}^{(t+\frac{1}{2})}-\hat{\mathbf{w}}\big\rangle-\frac{1% }{6}\int_{0}^{1}\int_{0}^{\beta}\big(\hat{\mathbf{w}}-\mathbf{w}^{(t+\frac{1}{% 2})}\big)^{\top}\nabla^{2}\eta(\mathbf{x}_{\alpha},\bm{\zeta}_{\alpha})\big(% \hat{\mathbf{w}}-\mathbf{w}^{(t+\frac{1}{2})}\big)\,d\alpha d\beta$ $\displaystyle=\tfrac{1}{6}\Big(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(% \hat{\mathbf{x}},\hat{\bm{\zeta}})\Big),$

where we used in the first inequality the inequality (5.2.2) and the definition of $\tilde{\bm{\zeta}}$ , in the second inequality we used inequality (11). Hence,

\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{% (t+1)})\geq\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf{x}^{(t+1)},% \tilde{\bm{\zeta}})\geq\tfrac{1}{6}\Big(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t% )})-\eta(\hat{\mathbf{x}},\hat{\bm{\zeta}})\Big).

Taking $\hat{\bm{\zeta}}=\tfrac{1}{2}\big(\bm{\zeta}^{(t)}+\bm{\zeta}^{*}\big)$ , $\hat{\mathbf{x}}=\tfrac{1}{2}\big(\mathbf{x}^{(t+1)}+\mathbf{x}^{*}\big)$ , we find by the optimality of $\mathbf{x}^{(t+2)}$ and the convexity of $\eta$

	$\displaystyle\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf{x}^{(t+2)}% ,\bm{\zeta}^{(t+1)})$	$\displaystyle\geq\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf{x}^{(t% +1)},\bm{\zeta}^{(t+1)})$
		$\displaystyle\geq\tfrac{1}{6}\Big(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-% \eta(\hat{\mathbf{x}},\hat{\bm{\zeta}})\Big)$
		$\displaystyle\geq\tfrac{1}{6}\left(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-% \left(\tfrac{1}{2}\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})+\tfrac{1}{2}\eta(% \mathbf{x}^{},\bm{\zeta}^{})\right)\right)$
		$\displaystyle=\tfrac{1}{12}\Big(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta% (\mathbf{x}^{},\bm{\zeta}^{})\Big).$

Which implies $\eta(\mathbf{x}^{(t+2)},\bm{\zeta}^{(t+1)})-\eta(\mathbf{x}^{*},\bm{\zeta}^{*}% )\leq\tfrac{11}{12}\Big(\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t)})-\eta(\mathbf% {x}^{*},\bm{\zeta}^{*})\Big)$ and therefore $\eta(\mathbf{x}^{(t+1)},\bm{\zeta}^{(t+1)})-\eta(\mathbf{x}^{*},\bm{\zeta}^{*}% )\leq\left(\tfrac{11}{12}\right)^{T}\Big(\eta(\mathbf{x}^{(1)},\bm{\zeta}^{(0)% })-\eta(\mathbf{x}^{*},\bm{\zeta}^{*})\Big).$ This gives us the convergence rate. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 22.

It is easy to see that $\eta$ is convex for $\beta$ large enough, as

\nabla^{2}\operatorname{port}(x,y)=\left(\begin{array}[]{cc}y&x\\ x&\frac{\beta}{y}\end{array}\right)

and hence $\det(\nabla^{2}\operatorname{port}(x,y))=y\cdot\frac{\beta}{y}-x^{2}=\beta-x^{% 2}\geq 0$ .

5.3 Proof of Theorem 11

Proof of Theorem 11.

The Lemmata have established that the conditions of Theorem 10 with $\rho=\tilde{O}(\alpha\cdot(1+\beta))$ . Appealing to Theorem 10, we obtain in $t=\frac{12\sqrt{3}}{\alpha\sqrt{\beta}}\cdot\rho\cdot(\epsilon/2)^{-1}$ iterations of the $\delta$ -AMO, where $\delta=\frac{12\sqrt{3}}{\alpha\sqrt{\beta}}(\epsilon/2)$ , a vector $(\mathbf{x},(\mathbf{y},\mathbf{z}))\in\mathcal{X}\times\Delta_{c}\times[0,1]^% {c}$ such that

	$\displaystyle\epsilon\geq\frac{12\sqrt{3}}{\alpha\sqrt{\beta}}\cdot\left(% \delta+\rho/t\right)\;$	$\displaystyle\geq\frac{12\sqrt{3}}{\alpha\sqrt{\beta}}\cdot\;\max_{(\mathbf{x^% {\prime},(y^{\prime},z^{\prime})})\in\mathcal{X}\times(\Delta_{c}\times[0,1]^{% c})}\left(\begin{array}[]{l}\mathbf{x}^{\prime}\\ \mathbf{y}^{\prime}\\ \mathbf{z}^{\prime}\end{array}\right)^{\top}\mathbf{J}\left(\begin{array}[]{l}% \mathbf{x}\\ \mathbf{y}\\ \mathbf{z}\end{array}\right)$
		$\displaystyle\geq\max_{(\mathbf{x^{\prime},(y^{\prime},z^{\prime})})\in% \mathcal{X}\times(\Delta_{c}\times[0,1]^{c})}\mathfrak{A}\left(\mathbf{x},(% \mathbf{y^{\prime},z^{\prime}})\right)-\mathfrak{A}\left(\mathbf{x}^{\prime},(% \mathbf{y,z})\right)$

where we used in the last inequality the definition of $\mathbf{J}$ from Lemma 15. Using the work/depth bound from Lemma 15 for the $\delta$ -AMO and the work/depth bound from Theorem 10, using that $\|\mathbf{c}\|_{1}$ is strongly-polynomially bounded in $c+d$ , we obtain a work bound $\tilde{O}\left((\operatorname{wrk_{m/t/a}}(\mathbf{P},\mathbf{Q})+c+d)\cdot% \frac{1+\beta}{\sqrt{\beta}}\cdot\log\left(\frac{\alpha\sqrt{\beta}\min_{i}% \mathbf{r}_{i}}{\epsilon}\right)\cdot\epsilon^{-1}\right)$ and a depth bound $\tilde{O}\left((\operatorname{dpth_{m/t/a}}(\mathbf{P},\mathbf{Q})+1)\cdot% \frac{1+\beta}{\sqrt{\beta}}\cdot\log\left(\frac{\alpha\sqrt{\beta}\min_{i}% \mathbf{r}_{i}}{\epsilon}\right)\cdot\epsilon^{-1}\right)$ . $\hfill\blacktriangleleft$

References

[1] Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong. Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 3997–4061. Society for Industrial and Applied Mathematics, January 2024. doi:10.1137/1.9781611977912.140.
[2] Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 322–335, New York, NY, USA, June 2020. Association for Computing Machinery. doi:10.1145/3357713.3384321.
[3] Amir Beck. On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM Journal on Optimization, 25(1):185–209, 2015. doi:10.1137/13094829X.
[4] Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, and Ta-Wei Tu. Maximum flow by augmenting paths in $n^{2+o(1)}$ time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2056–2077. IEEE, 2024. doi:10.1109/FOCS61266.2024.00123.
[5] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1000–1008. IEEE, 2022.
[6] Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, and Maximilian Probst Gutenberg. Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, st shortest path, and minimum-cost flow. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1165–1173, 2024. doi:10.1145/3618260.3649745.
[7] Samuel I Daitch and Daniel A Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 451–460, 2008. doi:10.1145/1374376.1374441.
[8] Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Optimal electrical oblivious routing on expanders. arXiv preprint arXiv:2406.07252, 2024. doi:10.48550/arXiv.2406.07252.
[9] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1208–1220, Virtual Italy, June 2021. ACM. doi:10.1145/3406325.3451098.
[10] Christoph Grunau, Rasmus Kyng, and Goran Zuzic. Acceleration for distributed transshipment and parallel maximum flow, 2025.
[11] Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Parallel $(1+epsilon)$ -approximate multi-commodity mincost flow in almost optimal depth and work. arXiv preprint arXiv:2510.20456, 2025. doi:10.48550/arXiv.2510.20456.
[12] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In DROPS-IDN/v2/Document/10.4230/LIPIcs.ICALP.2022.77. Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.77.
[13] Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. Advances in Neural Information Processing Systems, 36:57583–57596, 2023.
[14] R M Karp, E Upfal, and A Wigderson. Constructing a perfect matching is in random NC. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing - STOC ’85, pages 22–32, Providence, Rhode Island, United States, 1985. ACM Press. doi:10.1145/22145.22148.
[15] Jonathan Kelner and Petar Maymounkov. Electric Routing and Concurrent Flow Cutting. In Algorithms and Computation, Lecture Notes in Computer Science, pages 792–801, Berlin, Heidelberg, 2009. Springer. doi:10.1007/978-3-642-10631-6_80.
[16] 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 multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 217–226. SIAM, 2014. doi:10.1137/1.9781611973402.16.
[17] Jason Li. Faster parallel algorithm for approximate shortest path. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 308–321, Chicago IL USA, June 2020. ACM. doi:10.1145/3357713.3384268.
[18] László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565–574, 1979.
[19] 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 on Optimization, 15(1):229–251, January 2004. doi:10.1137/S1052623403425629.
[20] Yu. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005. doi:10.1007/s10107-004-0552-5.
[21] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319–344, 2007. doi:10.1007/s10107-006-0034-z.
[22] Jonah Sherman. Nearly maximum flows in nearly linear time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 263–269. IEEE, 2013. doi:10.1109/FOCS.2013.36.
[23] Jonah Sherman. Area-convexity, linf regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 452–460, 2017.
[24] Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772–780. SIAM, 2017. doi:10.1137/1.9781611974782.49.
[25] Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pages 81–90, New York, NY, USA, 2004. Association for Computing Machinery. doi:10.1145/1007352.1007372.
[26] Goran Zuzic. A simple boosting framework for transshipment. arXiv preprint arXiv:2110.11723, 2021. arXiv:2110.11723.

[bib.bib1] [1] Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong. Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 3997–4061. Society for Industrial and Applied Mathematics, January 2024. doi:10.1137/1.9781611977912.140.

[bib.bib2] [2] Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 322–335, New York, NY, USA, June 2020. Association for Computing Machinery. doi:10.1145/3357713.3384321.

[bib.bib3] [3] Amir Beck. On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM Journal on Optimization, 25(1):185–209, 2015. doi:10.1137/13094829X.

[bib.bib4] [4] Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, and Ta-Wei Tu. Maximum flow by augmenting paths in $n^{2+o(1)}$ time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2056–2077. IEEE, 2024. doi:10.1109/FOCS61266.2024.00123.

[bib.bib5] [5] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1000–1008. IEEE, 2022.

[bib.bib6] [6] Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, and Maximilian Probst Gutenberg. Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, st shortest path, and minimum-cost flow. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1165–1173, 2024. doi:10.1145/3618260.3649745.

[bib.bib7] [7] Samuel I Daitch and Daniel A Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 451–460, 2008. doi:10.1145/1374376.1374441.

[bib.bib8] [8] Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Optimal electrical oblivious routing on expanders. arXiv preprint arXiv:2406.07252, 2024. doi:10.48550/arXiv.2406.07252.

[bib.bib9] [9] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1208–1220, Virtual Italy, June 2021. ACM. doi:10.1145/3406325.3451098.

[bib.bib10] [10] Christoph Grunau, Rasmus Kyng, and Goran Zuzic. Acceleration for distributed transshipment and parallel maximum flow, 2025.

[bib.bib11] [11] Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Parallel $(1+epsilon)$ -approximate multi-commodity mincost flow in almost optimal depth and work. arXiv preprint arXiv:2510.20456, 2025. doi:10.48550/arXiv.2510.20456.

[bib.bib12] [12] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In DROPS-IDN/v2/Document/10.4230/LIPIcs.ICALP.2022.77. Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.77.

[bib.bib13] [13] Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. Advances in Neural Information Processing Systems, 36:57583–57596, 2023.

[bib.bib14] [14] R M Karp, E Upfal, and A Wigderson. Constructing a perfect matching is in random NC. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing - STOC ’85, pages 22–32, Providence, Rhode Island, United States, 1985. ACM Press. doi:10.1145/22145.22148.

[bib.bib15] [15] Jonathan Kelner and Petar Maymounkov. Electric Routing and Concurrent Flow Cutting. In Algorithms and Computation, Lecture Notes in Computer Science, pages 792–801, Berlin, Heidelberg, 2009. Springer. doi:10.1007/978-3-642-10631-6_80.

[bib.bib16] [16] 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 multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 217–226. SIAM, 2014. doi:10.1137/1.9781611973402.16.

[bib.bib17] [17] Jason Li. Faster parallel algorithm for approximate shortest path. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 308–321, Chicago IL USA, June 2020. ACM. doi:10.1145/3357713.3384268.

[bib.bib18] [18] László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565–574, 1979.

[bib.bib19] [19] 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 on Optimization, 15(1):229–251, January 2004. doi:10.1137/S1052623403425629.

[bib.bib20] [20] Yu. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005. doi:10.1007/s10107-004-0552-5.

[bib.bib21] [21] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319–344, 2007. doi:10.1007/s10107-006-0034-z.

[bib.bib22] [22] Jonah Sherman. Nearly maximum flows in nearly linear time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 263–269. IEEE, 2013. doi:10.1109/FOCS.2013.36.

[bib.bib23] [23] Jonah Sherman. Area-convexity, linf regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 452–460, 2017.

[bib.bib24] [24] Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772–780. SIAM, 2017. doi:10.1137/1.9781611974782.49.

[bib.bib25] [25] Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pages 81–90, New York, NY, USA, 2004. Association for Computing Machinery. doi:10.1145/1007352.1007372.

[bib.bib26] [26] Goran Zuzic. A simple boosting framework for transshipment. arXiv preprint arXiv:2110.11723, 2021. arXiv:2110.11723.

	$\displaystyle\\|\hat{\mathbf{f}}\\|_{\infty}$	$\displaystyle\leq\\|\mathbf{g}\\|_{\infty}+\sum_{i\leq k}\\|\mathbf{f}_{i}\\|_{% \infty}\leq\epsilon/2+\\|\mathbf{f}_{0}\\|_{\infty}+\epsilon\cdot\sum_{0<i}\frac% {1}{4^{i}}\leq\epsilon/2+1+\frac{\epsilon}{3}\leq 1+\epsilon$
	$\displaystyle\\|\hat{\mathbf{f}}\\|_{1}$	$\displaystyle\leq\\|\mathbf{g}\\|_{1}+\sum_{i\leq k}\\|\mathbf{f}_{i}\\|_{1}\leq% \epsilon/2+\\|\mathbf{f}_{0}\\|_{1}+\epsilon\cdot\sum_{0<i}\frac{1}{4^{i}}\leq% \epsilon/2+1+\frac{\epsilon}{3}\leq 1+\epsilon$

	$\displaystyle\|\phi(\mathbf{x},(\mathbf{y},\mathbf{z}))\|$	$\displaystyle=\alpha\cdot\left(\sum_{i,j}\overline{\mathbf{P}}_{i,j}% \operatorname{port}\left(\mathbf{x}_{j},\mathbf{y}_{i}\right)+\overline{% \mathbf{Q}}_{i,j}\mathbf{r}_{j}^{-1}\operatorname{port}\left(\mathbf{z}_{i},% \mathbf{r}_{j}\cdot\mathbf{x}_{j}\right)\right)$
		$\displaystyle=O\left(\alpha\cdot(1+\beta)\cdot\sum_{i}\mathbf{y}_{i}\|\log(% \mathbf{y}_{i})\|\sum_{j}\overline{\mathbf{P}}_{i,j}\right)$
		$\displaystyle+O\left(\alpha\cdot(1+\beta)\cdot\sum_{j}\left(\mathbf{r}_{j}% \cdot\mathbf{x}_{j}\|\log(\mathbf{r}_{j}\cdot\mathbf{x}_{j})\|\sum_{i}\overline{% \mathbf{Q}}_{i,j}\cdot\mathbf{r}_{j}^{-1}\right)\right)$
		$\displaystyle=O\left(\alpha\cdot(1+\beta)\cdot\left(\sum_{i}\mathbf{y}_{i}\|% \log(\mathbf{y}_{i})\|+\sum_{j}\mathbf{r}_{j}\cdot\mathbf{x}_{j}\|\log(\mathbf{r% }_{j}\cdot\mathbf{x}_{j})\|\right)\right)$
		$\displaystyle=\tilde{O}\left(\alpha\cdot(1+\beta)\right).$

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction: Toward Parallel Flow Algorithms

Understanding the optimization landscape: What lies next in parallel flow algorithms?

Area-convexity and flow optimization

1.1 Our Contributions

Theorem 1.1 (Parallel Undirected Minimum-Cost Flow on Expanders).

Fact 1.

Theorem (Mixed ℓ∞-ℓ1 Optimization).

Why area-convexity?

1.2 Organization of the Remaining Paper

2 Preliminaries

2.1 Graphs

2.2 Linear Algebra

3 Application: Flow Algorithms

3.1 Undirected Minimum-Cost Flow on Expanders

Corollary 2.

Lemma 3.

Proof.

Lemma 4 (Lemma 5.12 in [4]).

Proof.

Feasibility predicate.

Initialization of the binary search interval.

Binary search and termination.

Iteration count and work/depth bound.

4 Area-Convexity Review

Definition 5.

Definition 6.

Definition 7.

▶ Remark 8.

Theorem 9 ([23]).

Theorem 10 ([23]).

5 Joint L1/Max-Norm Optimization

Theorem 11.

Corollary 12.

Proof of Corollary 12.

Proof of Corollary 2.

5.1 An area-convex regularizer for Theorem 11

Lemma 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

Proof.

5.2 Approximate Maximum Oracle for Theorem 11

5.2.1 Lambert Function

Lemma 16.

Proof.

Lemma 17.

Proof.

5.2.2 Alternating Primal Dual Optimization yields an AMO

Lemma 18.

Proof.

Lemma 19.

Proof.

Lemma 20.

Proof.

Lemma 21.

Proof.

▶ Remark 22.

5.3 Proof of Theorem 11

Proof of Theorem 11.

References

Theorem (Mixed $\ell_{\infty}$ - $\ell_{1}$ Optimization).

$\blacktriangleright$ Remark 8.

$\blacktriangleright$ Remark 22.