betaFeedback

WorksComputer Science

Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow

Abstract

We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns an O(ε)O(\varepsilon)-approximate solution after O(kρε−2log⁡m)O(kρ\varepsilon^{-2}\log m) oracle calls where kk is the number of blocks and ρρ is the width of the oracle. The same holds for the randomized version with high probability. Previously, such bounds were shown when the coupling constraints have the same sign [Radzik'95; Villavicencio-Grigoriadis'96]. These analyses critically depended on monotonicity arguments that are not available in the mixed case. As an application, we obtain a deterministic (1−ε)(1-\varepsilon)-approximation for maximum multicommodity flow (M-MCF) using O(kε−2log⁡mlog⁡(km/ε))O(k\varepsilon^{-2}\log m\log(km/\varepsilon)) approximate single-commodity min-cost-flow calls. For planar graphs, and more generally for graph families admitting a near-linear-time min-cost-flow algorithm, this gives total running time O~(kmε−2)\widetilde O(km\varepsilon^{-2}). Compared with the O(km1+o(1)ε−1)O(km^{1+o(1)}\varepsilon^{-1}) algorithm of [Chen-Graur-Sidford'25], this improves the dependence on mm for these graph families at the cost of a worse dependence on ε\varepsilon. Finally, we give an exponentiation-free finite-precision implementation of the cyclic algorithm. It represents each internal weight by a logarithmic-bit mantissa and exponent, while every price supplied to the block oracle is rational and has a polynomially bounded common denominator.

Introduction

This paper considers the following block-structured feasibility problem:

findx=(x1,…,xk)∈X1×⋯×Xksatisfying∑i=1kAixi≤b(1)\text{find}\quad x=(x_1,\ldots,x_k)\in\mathcal{X}_1\times\cdots\times\mathcal{X}_k\quad\text{satisfying}\quad\sum_{i=1}^{k} A_i x_i\le b \tag*{(1)}

Here Xi⊂Rni\mathcal{X}_i\subset\mathbb{R}^{n_i} is a convex set, Ai∈Rm×niA_i\in\mathbb{R}^{m\times n_i} is a matrix, and b∈{+1,−1}mb\in\{+1,-1\}^m. Thus, we allow both packing constraints of the form a⊤x≤1a^\top x\le1 and covering constraints of the form a⊤x≥1a^\top x\ge1. We are interested in computing ε\varepsilon-approximate solutions; these are points x∈X1×⋯×Xkx\in\mathcal{X}_1\times\cdots\times\mathcal{X}_k satisfying ∑i=1kAixi≤b+ε1\sum_{i=1}^{k} A_i x_i\le b+\varepsilon\mathbf{1}.

Let us define E+={e∈[m]∣be=1}E^+=\{e\in[m]\mid b_e=1\} and E−={e∈[m]∣be=−1}E^-=\{e\in[m]\mid b_e=-1\}. We assume access to procedure Oracle⁡(i,y)\operatorname{Oracle}(i,y) that has the following specification.

Input. A block i∈[k]i\in[k] and a vector y∈Δmy\in\Delta_m, where Δm\Delta_m is the simplex in Rm\mathbb{R}^m.

Output. A point xi∈Xix_i\in\mathcal{X}_i that satisfies the following:

y⊤Aixi≤min⁡x∈Xiy⊤Aix+ε/k(2)y^\top A_i x_i\le\min_{x\in\mathcal{X}_i} y^\top A_i x+\varepsilon/k \tag*{(2)}
0≤(Aixi)e≤ρ∀e∈E+(3)0\le(A_i x_i)_e\le\rho\qquad\forall e\in E^+ \tag*{(3)}
−ρ≤(Aixi)e≤0∀e∈E−(4)-\rho\le(A_i x_i)_e\le0\qquad\forall e\in E^- \tag*{(4)}

Here ρ≥1\rho\ge1 is the width parameter.

We analyze two natural versions of the Multiplicative Weights Update algorithm for solving this problem: randomized (MWU-R) and deterministic (MWU-D). The first one selects the block i∈[k]i \in[k] uniformly at random at each step, while the second processes the blocks in a cyclic, or round-robin, order. Our main result is

Theorem 1. For any value ε∈(0,1/6]\varepsilon\in(0,1/6], MWU-D either returns an O(ε)O(\varepsilon)-approximate solution or correctly reports that (1) is infeasible after O(kρε−2ln⁡m)O(k\rho\varepsilon^{-2}\ln m) oracle calls. The same holds for MWU-R after O(kρε−2ln⁡mkδ)O(k\rho\varepsilon^{-2}\ln\frac{mk}{\delta}) oracle calls with probability at least 1−δ1-\delta.

Moreover, assuming that all numerical input data and oracle outputs are rational numbers of polynomial bit length, MWU-D can be implemented so that every internal weight is represented with O(log⁡(mkρ/ε))O(\log(mk\rho/\varepsilon)) bits. Its oracle calls can be restricted to vectors y=z/q∈Δmy=z/q\in\Delta_m, where z∈Z≥0mz\in\mathbb{Z}_{\ge0}^m, ∑eze=q\sum_e z_e=q, and q≤(mkρ/ε)O(1)q\le(mk\rho/\varepsilon)^{O(1)}.

Multicommodity flow problem

To motivate our work, consider two applications: the concurrent multicommodity flow problem (C-MCF) and the maximum multicommodity flow problem (M-MCF). Given a capacitated graph GG and pairs of terminals {(si,ti)}i=1k\{(s_i,t_i)\}_{i=1}^k, the goal is to find sis_i-tit_i flows xix_i for each i∈[k]i\in[k] that can be routed in GG simultaneously. In their simplest forms, M-MCF asks to maximize ∑ivalue⁡(xi)\sum_i\operatorname{value}(x_i) while C-MCF additionally imposes the constraint that value⁡(xi)\operatorname{value}(x_i) is the same for all ii.

Using a standard reduction to the feasibility problem (with a binary search on the objective value FF), both problems can be cast in the form (1). Importantly, we have b=(1,…,1)b=(1,\ldots,1) in the case of C-MCF and b=(1,…,1,−1)b=(1,\ldots,1,-1) in the case of M-MCF, where the last coordinate represents the covering constraint ∑ivalue⁡(xi)≥F\sum_i\operatorname{value}(x_i)\ge F. The oracle for a given commodity ii needs to approximately solve a minimum-cost flow problem in a certain graph.

The work of Grigoriadis and Khachiyan [11] and Leighton et al. [20] showed that C-MCF can be solved by a randomized algorithm using O(kε−2log⁡(mk))O(k\varepsilon^{-2}\log(mk)) oracle calls, either with high probability or in expectation. As in MWU-R, they select blocks (i.e. commodities) randomly. Radzik then proved in [27] that replacing uniform sampling with a round-robin selection gives the same bound. The same cyclic derandomization was extended to general problems of the form (1) with b=(1,…,1)b=(1,\ldots,1) by Villavicencio and Grigoriadis [31], who also allowed each sweep to visit the blocks in an arbitrary order. Note that the results of [11, 20, 27, 31, 13] do not cover M-MCF; their analyses rely on the fact that all components of the right-hand side bb in (1) have the same signs.

Our main contribution is the analysis of randomized and cyclic one-block-at-a-time algorithms for mixed packing and covering constraints, with bounds stated in terms of individual block-oracle calls. The analyses of [11, 20, 27, 31, 13] obtain this bound when all coordinates of bb have the same sign. Extending the randomized argument to mixed signs is relatively simple and requires only an additional one-sided residual bound. However, the deterministic extension is much more challenging. The analyses in [27, 31] rely heavily on monotonicity properties that fail in the mixed case. Our proof uses a very different technique, and is the main technical contribution of this work.

By applying Theorem 1 to M-MCF and using binary search we obtain the following result.

Theorem 2. Consider a directed or undirected M-MCF instance with mm edges, O(m)O(m) nodes and kk commodities whose capacities and rewards are polynomially-bounded nonnegative integers. There is a constant εmax⁡>0\varepsilon_{\max}>0 and a deterministic algorithm that for a given ε∈(0,εmax⁡]\varepsilon\in(0,\varepsilon_{\max}] returns a feasible flow of value at least (1−O(ε))OPT⁡(1-O(\varepsilon))\operatorname{OPT} using O(kε−2log⁡mlog⁡(km/ε))O(k\varepsilon^{-2}\log m\log(km/\varepsilon)) single-commodity minimum-cost-flow calls. Every call has nonnegative rational costs of bit length O(log⁡(mk/ε))O(\log(mk/\varepsilon)) and is allowed to return a feasible flow of cost at most 1+ε/k1+\varepsilon/k times the minimum cost.

yearworkflagscomplexityrestrictionstechnique
1987Shahrokhi-Matula [28]Cpoly⁡(n,m,ε−1)\operatorname{poly}(n,m,\varepsilon^{-1})uniform capacitiesMWU precursor
1990Klein et al. [19]CO~(kmε−2+m2ε−3)\widetilde{O}(km\varepsilon^{-2}+m^{2}\varepsilon^{-3})uniform capacities; randomized
1991Plotkin-Shmoys-Tardos [25]CM*O~(km2ε−2)\widetilde{O}(km^{2}\varepsilon^{-2})randomized
CM*O~(k2m2ε−2)\widetilde{O}(k^{2}m^{2}\varepsilon^{-2})
1998Garg-Könemann [10]CMO~(km2ε−2)\widetilde{O}(km^{2}\varepsilon^{-2})MWU
1999Fleischer [8]MO~(m2ε−2)\widetilde{O}(m^{2}\varepsilon^{-2})
2002Karakostas [17]CO~(m2ε−2)\widetilde{O}(m^{2}\varepsilon^{-2})implicit
2010Madry [22]MO~(mnε−2)\widetilde{O}(mn\varepsilon^{-2})randomized
1991Leighton et al. [20]CO~(kε−3Tmincost)\widetilde{O}(k\varepsilon^{-3}T_{\mathrm{mincost}})randomized
CO~(k2ε−2Tmincost)\widetilde{O}(k^{2}\varepsilon^{-2}T_{\mathrm{mincost}})
1995Radzik [27]CO~(kε−2Tmincost)\widetilde{O}(k\varepsilon^{-2}T_{\mathrm{mincost}})block MWU
1995Grigoriadis-Khachiyan [13]C*O~(kε−2Tmincost)\widetilde{O}(k\varepsilon^{-2}T_{\mathrm{mincost}})
2026this workMO~(kε−2Tmincost)\widetilde{O}(k\varepsilon^{-2}T_{\mathrm{mincost}})
MO~(kmε−2)\widetilde{O}(km\varepsilon^{-2})efficient vertex separator
2017Sherman [29]CO~(mkε−1)\widetilde{O}(mk\varepsilon^{-1})undirectedarea-convex
2025Chen-Graur-Sidford [4]CMO(m1+o(1)kε−1)O(m^{1+o(1)}k\varepsilon^{-1})optimization

Table 1. Selected approximation results for concurrent and maximum multicommodity flow. C/M flags indicate whether the complexity applies to C-MCF, M-MCF, or both. A superscript * denotes a cost-constrained or minimum-cost variant. TmincostT_{\mathrm{mincost}} is the complexity of a single-commodity min-cost-flow computation. The O~\widetilde{O} notation also hides factors logarithmic in nn.

The current best-known algorithm for (1−ε)(1-\varepsilon)-approximate maximum weighted multicommodity flow, due to Chen, Graur, and Sidford [4], runs in O(km1+o(1)ε−1)O(km^{1+o(1)}\varepsilon^{-1}). Combining Theorem 2 with the O(m1+o(1))O(m^{1+o(1)})-time exact min-cost-flow algorithm of Chen et al. [5] instead gives O~(km1+o(1)ε−2)\widetilde{O}(km^{1+o(1)}\varepsilon^{-2}) time. This has a worse dependence on ε\varepsilon than the algorithm of [4], but leaves a possibility of improving the dependence on mm from almost linear (O(m1+o(1))O(m^{1+o(1)})) to nearly linear (O~(m)\widetilde{O}(m)), if the complexity of an approximate min-cost flow solver is ever improved to nearly linear time. In fact, a nearly linear time (exact) min-cost flow algorithm is known for planar graphs, or more generally graph families that admit an efficient vertex separator of size O(n)O(\sqrt{n}) [7]. Consequently, our work yields an O~(kmε−2)\widetilde{O}(km\varepsilon^{-2})-time algorithm for (1−ε)(1-\varepsilon)-approximate M-MCF in such families. We remark that our approach is a short black-box reduction to single-commodity min-cost flow, whereas the better dependence on ε\varepsilon in the algorithm of [4] relies on more specialized machinery.

Other related work

Multicommodity-flow algorithms Existing algorithms for C-MCF and M-MCF can be grouped into three categories: MWU-type algorithms that use shortest path computations as the underlying oracle [28, 19, 25, 10, 8, 17, 22], block-MWU algorithms that rely on a min-cost-flow solver [20, 27, 13], and techniques based on optimizing an area-convex functional [29, 4]. Table 1 summarizes the complexities of these approaches. The general exponential-potential and price-directive decomposition frameworks underlying the Grigoriadis-Khachiyan flow result are developed in [12, 14].

Block-oracle models Problem (1) with b=(1,…,1)b=(1,\ldots,1) was studied by Grigoriadis and Khachiyan [11]. For a constant block-solver tolerance, their randomized algorithm uses O(klog⁡m(ε−2+log⁡k))O(k\log m(\varepsilon^{-2}+\log k)) expected block-solver calls. Their deterministic algorithm has the same number of outer iterations, but every iteration makes kk parallel block-solver calls. Leighton et al. [20] instantiate the same principle for concurrent multicommodity flow by randomly selecting a commodity, whereas Radzik [27] replaces random selection by a fixed round-robin order in that setting. Villavicencio and Grigoriadis [31] establish cyclic derandomization for this general block model with nonnegative coupling constraints. Thus, when b=(1,…,1)b=(1,\ldots,1), they obtain the same asymptotic deterministic cyclic bound as Theorem 1; their stated bound is O(klog⁡m(ε−2+log⁡min⁡{k,m}))O(k \log m(\varepsilon^{-2} + \log\min\{k,m\})) block-solver calls.1 This common-sign structure permits a monotone potential argument. The present analysis retains the black-box block oracle and cyclic order while allowing both packing and covering rows.

General packing and covering More generally, multiplicative-weights and Lagrangian-relaxation methods have long been used for packing and covering problems; Arora, Hazan, and Kale [1] give a broad survey. In particular, for k=1k=1, the mixed-sign guarantee follows from their standard MWU framework for convex feasibility with an asymmetric bounded oracle; see [1 Theorems 3.3-3.5]. Alternative width-independent bounds for k=1k=1, under different global oracle specifications and for more general convex packing and concave covering functions, were given by Jansen [15] and Diedrich and Jansen [6]. Plotkin, Shmoys, and Tardos [25] developed an oracle-based framework for fractional packing and covering. Young [32] and Quanrud [26] studied MWU algorithms for explicitly represented mixed packing and covering LPs, without the block-oracle structure assumed here. In particular, Young gave sequential and parallel width-independent algorithms, while Quanrud obtained a deterministic algorithm with nearly linear running time. For pure packing and covering, Klein and Young [18] proved an Ω(ρε−2log⁡m)\Omega(\rho\varepsilon^{-2}\log m) lower bound for Dantzig-Wolfe-type algorithms in the applicable parameter regime. Thus, for k=1k=1, the dependence of Theorem 1 on ρ\rho, ε\varepsilon, and mm is optimal for that class of algorithms; their result does not address the dependence on kk or the restriction to cyclic individual-block updates.

Bit complexity

To achieve the bit-complexity claim in Theorem 1, we store each internal weight as a floating-point number with logarithmic-bit mantissa and exponent, rounding it multiplicatively after every update. This accommodates the potentially exponential dynamic range of the weights. Prices passed to the oracle are instead ordinary rationals with logarithmic-bit numerators and a common denominator, obtained by truncation before normalization. We call this a hybrid weight-price representation. We are not aware of earlier MWU work that explicitly uses this representation.

For MWU variants with exponential updates, an alternative would be to maintain rounded rational logarithms of the weights. The update then consists of rational addition followed by rounding to a fixed grid; exponentiation is needed only when computing the normalized prices. Hedge [9] is a basic example of this exponential-update viewpoint. Implementations of the exponentiation step, including softmax and matrix-exponential computation, have been studied in [2, 16, 30, 24, 23, 3]. In general, these works do not ask whether both the maintained state and the normalized prices supplied to a black-box oracle can be represented by rationals of logarithmic bit length with a short common denominator.

Grigoriadis and Khachiyan [11 Section 9.1] form prices by normalizing exponentials of the current resource loads and explicitly address the price side of this question. They state that their general block algorithm retains its iteration bound when the normalized price components are computed to logarithmic precision; the remaining bit analysis depends on the block solver. Their minimum-cost-flow application rounds prices to a rational grid of logarithmic bit length [13].

An exponentiation-free special case is Weighted Majority with β=1/2\beta=1/2: its weights are powers of two encoded by logarithmic-bit mistake counts and updated by binary shifts [21]. It has no optimization oracle, so it does not address the representation of oracle prices.

Algorithm and guarantees

For a sequence of selected blocks (it)t=1T(i_t)_{t=1}^{T}, write

Ti:={t∈[T]:it=i}\mathcal{T}_i := \{t \in[T] : i_t = i\}
Algorithm 1: MWU for block-separable feasibility.
1  set $w^{(1)} = \mathbf{1} \in \mathbb{R}^{m}$
2  for $t = 1,\ldots,T$ do
3      choose $i_t \in [k]$
4      $x^{(t)} \leftarrow \operatorname{Oracle}(i_t,y^{(t)})$ with $y^{(t)} = w^{(t)}/\sum_e w_e^{(t)}$
5      set $r^{(t)} = A_{i_t}x^{(t)} - b/k$
6      set $w_e^{(t+1)} = w_e^{(t)}(1+\eta r_e^{(t)})$
7  return $x=(x_1,\ldots,x_k)$ where $x_i = |\mathcal{T}_i|^{-1}\sum_{t\in\mathcal{T}_i}x^{(t)}$

MWU-R chooses every iti_t independently and uniformly from [k][k]. MWU-D uses the deterministic rule it=1+((t−1) mod k)i_t = 1 + ((t-1)\bmod k).

Theorem 3. Suppose that (1) is feasible, ε∈(0,1/2]\varepsilon\in(0,1/2], δ∈(0,1)\delta\in(0,1), η=ε10ρ\eta= \frac{\varepsilon}{10\rho}, and T≥48kρε−2(ln⁡2mδ+ln⁡2kδ)T \ge48k\rho\varepsilon^{-2}\left(\ln\frac{2m}{\delta}+\ln\frac{2k}{\delta}\right). Then MWU-R outputs a 3ε3\varepsilon-approximate solution with probability at least 1−δ1-\delta.

Theorem 4. Suppose that (1) is feasible, ε∈(0,1/2]\varepsilon\in(0,1/2], η=ε10ρ\eta= \frac{\varepsilon}{10\rho}, and T≥24kρε−2ln⁡(2m)T \ge24k\rho\varepsilon^{-2}\ln(2m) is a multiple of kk. Then MWU-D outputs a 4ε4\varepsilon-approximate solution.

Bit complexity Vectors ww in Algorithm 1 may grow to rational numbers requiring polynomially many bits to store. Next, we discuss how this can be avoided.

For integers A,B≥1A,B \ge1, define

QA,B:={p2B⋅2a:p,a∈Z, ∣p∣<2B, ∣a∣<2A}.\mathcal{Q}_{A,B}:=\left\{\frac{p}{2^B}\cdot2^a:p,a\in\mathbb{Z},\ |p|<2^B,\ |a|<2^A\right\}.

Thus, numbers in QA,B\mathcal{Q}_{A,B} can be represented with O(A+B)O(A+B) bits (O(A)O(A) bits for the exponent and O(B)O(B) bits for the mantissa). For value z∈Rz\in\mathbb{R} let round⁡B(z)\operatorname{round}_B(z) be a number in ⋃A≥1QA,B\bigcup_{A\ge1}\mathcal{Q}_{A,B} of the form z(1+δ)z(1+\delta) with ∣δ∣≤2−B|\delta|\le2^{-B}; clearly, such number always exists. Finally, define

truncate⁡τ(z)={zif ∣z∣≥τ0if ∣z∣<τ\operatorname{truncate}_{\tau}(z)= \begin{cases} z & \text{if } |z|\ge\tau\\ 0 & \text{if } |z|<\tau \end{cases}

We extend these operations to vectors by applying them componentwise.

Theorem 5. Suppose that (1) is feasible, ε∈(0,1/6]\varepsilon\in(0,1/6], η=3ε/(10ρ)\eta= 3\varepsilon/(10\rho), and T≥3kρε−2ln⁡(2m)T \ge3k\rho\varepsilon^{-2}\ln(2m) is a multiple of kk. Use the block oracle with additive accuracy ε/k\varepsilon/k. Consider the following modification of MWU-D: (1) compute y(t)y^{(t)} at line 4 as follows: set W(t)=∑ewe(t)W^{(t)}=\sum_e w_e^{(t)}, wˉ(t)=truncate⁡τ(w(t))\bar{w}^{(t)}=\operatorname{truncate}_{\tau}(w^{(t)}), and y(t)=wˉ(t)/∑ewˉe(t)y^{(t)}=\bar{w}^{(t)}/\sum_e\bar{w}_e^{(t)}; (2) after computing we(t+1)w_e^{(t+1)} at line 6, update we(t+1):=round⁡B(we(t+1))w_e^{(t+1)}:=\operatorname{round}_B(w_e^{(t+1)}). If B=Θ(log⁡(kρT/ε))B=\Theta(\log(k\rho T/\varepsilon)) and τ=Θ(ε/(mkρ))\tau=\Theta(\varepsilon/(mk\rho)) with appropriate constants, then MWU-D produces a 12ε12\varepsilon-approximate solution after T=Θ(kρε−2log⁡m)T=\Theta(k\rho\varepsilon^{-2}\log m) oracle calls. During the algorithm all weights we(t)w_e^{(t)} belong to QA,B\mathcal{Q}_{A,B} for A=Θ(log⁡(Tηρ+1))A=\Theta(\log(T\eta\rho+1)), while every oracle vector has the form y(t)=z(t)/qty^{(t)}=z^{(t)}/q_t, where z(t)∈Z≥0mz^{(t)}\in\mathbb{Z}_{\ge0}^{m}, ∑eze(t)=qt\sum_e z_e^{(t)}=q_t, and qt≤(mkρT/ε)O(1)q_t\le(mk\rho T/\varepsilon)^{O(1)}.

Note that Theorem 1 follows from the theorems above by running the algorithms for the specified number of iterations, checking the returned point, and reporting infeasibility if the check fails.

Proofs of Theorems 3, 4, and 5

By convexity of sets Xi\mathcal{X}_i, the output of Algorithm 1 satisfies x∈X1×⋯×Xkx\in\mathcal{X}_1\times\cdots\times\mathcal{X}_k.

For t≥1t\ge1 let us define

Φt:=∑e∈[m]we(t)Φt+:=∑e∈E+we(t)Φt−:=∑e∈E−we(t)(5)\Phi_t:=\sum_{e\in[m]}w_e^{(t)} \qquad \Phi_t^+:=\sum_{e\in E_+}w_e^{(t)} \qquad \Phi_t^-:=\sum_{e\in E_-}w_e^{(t)} \tag*{(5)}

The proofs will follow the usual strategy used for MWU: first, we prove that potential Φt\Phi_t does not grow too fast with tt, and then for each e∈[m]e \in[m] we will use condition we(T+1)≤ΦT+1w_e^{(T+1)} \le\Phi_{T+1} to conclude that (Ax)e≤be+O(ε)(Ax)_e \le b_e + O(\varepsilon).

The oracle specification implies that

re(t)∈[−1/k,ρ−1/k]∀e∈E+re(t)∈[−ρ+1/k,1/k]∀e∈E−(6)\begin{aligned} r_e^{(t)} &\in[-1/k,\rho-1/k] && \forall e \in E^+ \\ r_e^{(t)} &\in[-\rho+1/k,1/k] && \forall e \in E^- \tag*{(6)} \end{aligned}

Consequently,

(re(t))2≤ρ(re(t)+2/k)∀e∈E+(re(t))2≤ρ(−re(t)+2/k)∀e∈E−(7)\begin{aligned} (r_e^{(t)})^2 &\le\rho(r_e^{(t)}+2/k) && \forall e \in E^+ \\ (r_e^{(t)})^2 &\le\rho(-r_e^{(t)}+2/k) && \forall e \in E^- \tag*{(7)} \end{aligned}

Analysis of MWU-R

Upper-bounding ΦT+1\Phi_{T+1} Let x∗x^* be a feasible solution. Approximate optimality implies

∑iyi⊤Ai⋅Oracle⁡(i,y)≤∑iyi⊤Aixi∗+ε≤y⊤b+ε(8)\sum_i y_i^{\top}A_i\cdot\operatorname{Oracle}(i,y)\le\sum_i y_i^{\top}A_ix_i^*+\varepsilon\le y^{\top}b+\varepsilon \tag*{(8)}

Let Ft−1\mathcal{F}_{t-1} be the history before iti_t is sampled and set S(t)=⟨y(t),r(t)⟩S^{(t)}=\langle y^{(t)},r^{(t)}\rangle. By (5),

E[S(t)∣Ft−1]=1k(∑iy(t)⊤Ai⋅Oracle⁡(i,y(t))−y(t)⊤b)≤εk\mathbb{E}[S^{(t)}\mid\mathcal{F}_{t-1}]=\frac{1}{k}\left(\sum_i y^{(t)\top}A_i\cdot\operatorname{Oracle}(i,y^{(t)})-y^{(t)\top}b\right)\le\frac{\varepsilon}{k}

Because Φt+1=Φt(1+ηS(t))\Phi_{t+1}=\Phi_t(1+\eta S^{(t)}), it follows that

E[Φt+1∣Ft−1]≤(1+ηε/k)Φt\mathbb{E}[\Phi_{t+1}\mid\mathcal{F}_{t-1}]\le(1+\eta\varepsilon/k)\Phi_t

Iterating from Φ1=m\Phi_1=m gives

E[ΦT+1]≤m(1+ηε/k)T≤mexp⁡(ηεTk)\mathbb{E}[\Phi_{T+1}]\le m(1+\eta\varepsilon/k)^T\le m\exp\left(\frac{\eta\varepsilon T}{k}\right)

Markov’s inequality therefore gives

ΦT+1≤2mδexp⁡(ηεTk)(9)\Phi_{T+1}\le\frac{2m}{\delta}\exp\left(\frac{\eta\varepsilon T}{k}\right) \tag*{(9)}

with probability at least 1−δ/21-\delta/2.

Proof of Theorem 3 Fix e∈[m]e\in[m], and define Re=∑t=1Tre(t)R_e=\sum_{t=1}^{T}r_e^{(t)}. Suppose that Re≥0R_e\ge0. Using eq. (4) and bound ln⁡(1+ηr)≥ηr−η2r2\ln(1+\eta r)\ge\eta r-\eta^2r^2, we get

ln⁡ΦT+1≥ln⁡we(T+1)≥3η4Re−2η2ρTk(10)\ln\Phi_{T+1}\ge\ln w_e^{(T+1)}\ge\frac{3\eta}{4}R_e-\frac{2\eta^2\rho T}{k} \tag*{(10)}

Combining (6) and (7) and then using definitions of η\eta and TT yields

kReT≤38ηρ+43kln⁡(2m/δ)ηT+43ε≤179ε=:s\frac{kR_e}{T}\le\frac{3}{8}\eta\rho+\frac{4}{3}\frac{k\ln(2m/\delta)}{\eta T}+\frac{4}{3}\varepsilon\le\frac{17}{9}\varepsilon=:s

If Re<0R_e<0, then kRe/T≤skR_e/T\le s holds automatically. Thus kRe/T≤skR_e/T\le s for every e∈[m]e\in[m]. Chernoff’s inequality and a union bound show, with probability at least 1−δ/21-\delta/2, that

∣Ti∣=(1±ε/4)T/k∀i∈[k](11)|\mathcal{T}_i|=(1\pm\varepsilon/4)T/k\qquad\forall i\in[k] \tag*{(11)}

Assume that (6) and (8) are both true; this holds with probability at least 1−δ1-\delta. By the definition of r(t)r^{(t)} and ReR_e,

∑t=1T(Aix(t))e=Re+Tbek={Re+T/k,e∈E+Re−T/k,e∈E−\sum_{t=1}^{T}(A_i x^{(t)})_e=R_e+\frac{Tb_e}{k}=\begin{cases}R_e+T/k, & e\in E^+\\ R_e-T/k, & e\in E^-\end{cases}

For e∈E+e\in E^+ we have (Aix(t))e≥0(A_i x^{(t)})_e\ge0 and 1/∣Ti∣≤k/((1−ε/4)T)1/|\mathcal{T}_i|\le k/((1-\varepsilon/4)T). Therefore,

∑i(Aixi)e=∑i1∣Ti∣∑t∈Ti(Aix(t))e≤k(1−ε/4)T(Re+T/k)=1+kRe/T1−ε/4≤1+s1−ε/4≤1+3ε\sum_i(A_i x_i)_e=\sum_i\frac{1}{|\mathcal{T}_i|}\sum_{t\in\mathcal{T}_i}(A_i x^{(t)})_e\le\frac{k}{(1-\varepsilon/4)T}(R_e+T/k)=\frac{1+kR_e/T}{1-\varepsilon/4}\le\frac{1+s}{1-\varepsilon/4}\le1+3\varepsilon

Similarly, for e∈E−e\in E^- we have (Aix(t))e≤0(A_i x^{(t)})_e\le0 and 1/∣Ti∣≥k/((1+ε/4)T)1/|\mathcal{T}_i|\ge k/((1+\varepsilon/4)T). Therefore,

∑i(Aixi)e=∑i1∣Ti∣∑t∈Ti(Aix(t))e≤k(1+ε/4)T(Re−T/k)=−1+kRe/T1+ε/4≤−1+s1+ε/4≤−1+3ε\sum_i(A_i x_i)_e=\sum_i\frac{1}{|\mathcal{T}_i|}\sum_{t\in\mathcal{T}_i}(A_i x^{(t)})_e\le\frac{k}{(1+\varepsilon/4)T}(R_e-T/k)=\frac{-1+kR_e/T}{1+\varepsilon/4}\le\frac{-1+s}{1+\varepsilon/4}\le-1+3\varepsilon

Analysis of MWU-D

Upper-bounding ΦT+1\Phi_{T+1} We start with the following result.

Lemma 6. There exists a vector q=(q1,…,qk)q=(q_1,\ldots,q_k) such that

∑iqi=0(12)\sum_i q_i=0 \tag*{(12)}
qi,e≥−(1+ε)/k∀i∈[k], e∈E+(13)q_{i,e}\ge-(1+\varepsilon)/k \qquad\forall i\in[k],\ e\in E^+ \tag*{(13)}
qi,e≤1/k∀i∈[k], e∈E−(14)q_{i,e}\le1/k \qquad\forall i\in[k],\ e\in E^- \tag*{(14)}
⟨w(t),r(t)⟩≤⟨w(t),qi⟩+2εkΦt∀t∈Ti(15)\langle w^{(t)},r^{(t)}\rangle\le\langle w^{(t)},q_i\rangle+\frac{2\varepsilon}{k}\Phi_t \qquad\forall t\in\mathcal{T}_i \tag*{(15)}

Proof. For each block, define

Ri=conv⁡‾{Ai⋅Oracle⁡(i,y):y∈Δm}\mathcal{R}_i=\overline{\operatorname{conv}}\{A_i\cdot\operatorname{Oracle}(i,y):y\in\Delta_m\}

By the width conditions, Ri\mathcal{R}_i is contained in a bounded box; since it is closed by definition, it is compact. Hence Ri+R+m\mathcal{R}_i+\mathbb{R}^m_+ is a closed convex upper set. For every v∈AiXiv\in A_i\mathcal{X}_i, there is a z∈Riz\in\mathcal{R}_i satisfying z≤v+(ε/k)1z\le v+(\varepsilon/k)\mathbf{1}. Indeed, otherwise strict separation of v+(ε/k)1v+(\varepsilon/k)\mathbf{1} from the closed convex upper set Ri+R+m\mathcal{R}_i+\mathbb{R}^m_+ would give a separating vector y≥0y\ge0, since the set is upper closed. Normalizing yy gives y∈Δmy\in\Delta_m and

yTv+ε/k<min⁡z∈RiyTzy^{\mathsf{T}}v+\varepsilon/k<\min_{z\in\mathcal{R}_i}y^{\mathsf{T}}z

contradicting approximate oracle optimality. Also, for every y∈Δmy\in\Delta_m and z∈Riz\in\mathcal{R}_i, min⁡x∈XiyTAix≤yTz\min_{x\in\mathcal{X}_i}y^{\mathsf{T}}A_i x\le y^{\mathsf{T}}z: this holds for the convex hull because Xi\mathcal{X}_i is convex and extends to its closure by continuity. Fix a feasible tuple x∗x^* and choose zi∈Riz_i\in\mathcal{R}_i with zi≤Aixi∗+(ε/k)1z_i\le A_i x_i^*+(\varepsilon/k)\mathbf{1}. Initially set

qi=zi−b/k−(ε/k)1q_i=z_i-b/k-(\varepsilon/k)\mathbf{1}

Feasibility of x∗x^* and the choice of the ziz_i give

∑iqi=∑izi−b−ε1≤∑iAixi∗−b≤0\sum_iq_i=\sum_i z_i-b-\varepsilon\mathbf{1}\le\sum_iA_i x_i^*-b\le0

Moreover, every vector in Ri\mathcal{R}_i satisfies zi,e≥0z_{i,e} \ge0 on E+E^+ and zi,e≤0z_{i,e} \le0 on E−E^-. Thus the initial vectors satisfy qi,e≥−(1+ε)/kq_{i,e} \ge-(1+\varepsilon)/k on E+E^+ and qi,e≤(1−ε)/kq_{i,e} \le(1-\varepsilon)/k on E−E^-. Increase coordinates of the qiq_i until (9a) holds. On E+E^+ this preserves (9b). On E−E^- it can be done while preserving (9c): the total available increase ∑i(1/k−qi,e)=1−∑iqi,e\sum_i(1/k-q_{i,e})=1-\sum_iq_{i,e} is at least the required increase −∑iqi,e-\sum_iq_{i,e}.

It remains to show (9d). First consider the initial vectors qiq_i, before any coordinates are increased. For t∈Tit\in\mathcal{T}_i, since zi∈Riz_i\in\mathcal{R}_i, we have min⁡x∈Xi⟨y(t),Aix⟩≤⟨y(t),zi⟩\min_{x\in X_i}\langle y^{(t)},A_ix\rangle\le\langle y^{(t)},z_i\rangle. Approximate optimality of x(t)=Oracle⁡(i,y(t))x^{(t)}=\operatorname{Oracle}(i,y^{(t)}) therefore yields

⟨y(t),Aix(t)⟩≤min⁡x∈Xi⟨y(t),Aix⟩+εk≤⟨y(t),zi⟩+εk\langle y^{(t)},A_ix^{(t)}\rangle\le\min_{x\in X_i}\langle y^{(t)},A_ix\rangle+\frac{\varepsilon}{k}\le\langle y^{(t)},z_i\rangle+\frac{\varepsilon}{k}

Since y(t)=w(t)/Φty^{(t)}=w^{(t)}/\Phi_t, multiplying by Φt\Phi_t gives

⟨w(t),Aix(t)⟩≤⟨w(t),zi⟩+εkΦt\langle w^{(t)},A_ix^{(t)}\rangle\le\langle w^{(t)},z_i\rangle+\frac{\varepsilon}{k}\Phi_t

Using r(t)=Aix(t)−b/kr^{(t)}=A_ix^{(t)}-b/k and the initial definition qi=zi−b/k−(ε/k)1q_i=z_i-b/k-(\varepsilon/k)\mathbf{1}, we therefore obtain

⟨w(t),r(t)⟩≤⟨w(t),qi⟩+2εkΦt\langle w^{(t)},r^{(t)}\rangle\le\langle w^{(t)},q_i\rangle+\frac{2\varepsilon}{k}\Phi_t

which is (9d). Increasing qiq_i preserves this condition because w(t)≥0w^{(t)}\ge0.

Fix a vector qq given by Lemma 6. Since ∑i=1kqi,e=0\sum_{i=1}^kq_{i,e}=0 for each e∈[m]e\in[m], we conclude that there exists a kk-periodic sequence {Qt,e}t=0,1,…\{Q_{t,e}\}_{t=0,1,\ldots} satisfying qit,e=Qt,e−Qt−1,eq_{it,e}=Q_{t,e}-Q_{t-1,e}. By adding a constant to Qt,eQ_{t,e} we can assume that max⁡tQt,e=0\max_tQ_{t,e}=0 for e∈E+e\in E^+ and min⁡tQt,e=0\min_tQ_{t,e}=0 for e∈E−e\in E^-. Conditions (9b) and (9c) now imply that Qt,e∈[−(1+ε),0]Q_{t,e}\in[-(1+\varepsilon),0] on E+E^+ and Qt,e∈[0,1]Q_{t,e}\in[0,1] on E−E^-. We can write

∑t=1Twe(t)qit,e=we(T)QT,e−we(1)Q0,e+∑t=1T−1(we(t)−we(t+1))Qt,e\sum_{t=1}^{T}w_e^{(t)}q_{it,e}=w_e^{(T)}Q_{T,e}-w_e^{(1)}Q_{0,e}+\sum_{t=1}^{T-1}(w_e^{(t)}-w_e^{(t+1)})Q_{t,e}

The update rule implies we(t)−we(t+1)=−ηwe(t)re(t)w_e^{(t)}-w_e^{(t+1)}=-\eta w_e^{(t)}r_e^{(t)}, and hence

∑t=1Twe(t)qit,e=we(T)QT,e−we(1)Q0,e−η∑t=1T−1we(t)re(t)Qt,e\sum_{t=1}^{T}w_e^{(t)}q_{it,e}=w_e^{(T)}Q_{T,e}-w_e^{(1)}Q_{0,e}-\eta\sum_{t=1}^{T-1}w_e^{(t)}r_e^{(t)}Q_{t,e}

Conditions Qt,e∈[−(1+ε),0]Q_{t,e}\in[-(1+\varepsilon),0] for e∈E+e\in E^+ and Qt,e∈[0,1]Q_{t,e}\in[0,1] for e∈E−e\in E^- now imply

∑t=1Twe(t)qit,e≤0+(1+ε)we(1)+η(1+ε)∑t=1Twe(t)(re(t))+∀e∈E+(16)\sum_{t=1}^{T}w_e^{(t)}q_{it,e}\le0+(1+\varepsilon)w_e^{(1)}+\eta(1+\varepsilon)\sum_{t=1}^{T}w_e^{(t)}(r_e^{(t)})_+ \qquad\forall e\in E^+ \tag*{(16)}
∑t=1Twe(t)qit,e≤we(T)+0+η∑t=1Twe(t)(−re(t))+∀e∈E−(17)\sum_{t=1}^{T}w_e^{(t)}q_{it,e}\le w_e^{(T)}+0+\eta\sum_{t=1}^{T}w_e^{(t)}(-r_e^{(t)})_+ \qquad\forall e\in E^- \tag*{(17)}

Here we extended both sums from T−1T-1 to TT, which is valid because the added summands are nonnegative. We have we(T+1)=we(T)(1+ηre(T))w_e^{(T+1)}=w_e^{(T)}(1+\eta r_e^{(T)}) and re(T)≥−ρr_e^{(T)}\ge-\rho, and hence we(T)≤we(T+1)1−ηρw_e^{(T)}\le\frac{w_e^{(T+1)}}{1-\eta\rho}. Define

PT+=∑t=1T∑e∈E+we(t)(re(t))+,NT+=∑t=1T∑e∈E+we(t)(−re(t))+P_T^+=\sum_{t=1}^{T}\sum_{e\in E^+}w_e^{(t)}(r_e^{(t)})_+,\qquad N_T^+=\sum_{t=1}^{T}\sum_{e\in E^+}w_e^{(t)}(-r_e^{(t)})_+
PT−=∑t=1T∑e∈E−we(t)(re(t))+,NT−=∑t=1T∑e∈E−we(t)(−re(t))+P_T^-=\sum_{t=1}^{T}\sum_{e\in E^-}w_e^{(t)}(r_e^{(t)})_+,\qquad N_T^-=\sum_{t=1}^{T}\sum_{e\in E^-}w_e^{(t)}(-r_e^{(t)})_+

Thus PT+P_T^{+} and NT+N_T^{+} collect the positive and negative parts, respectively, of the residual contributions. Summing the two bounds in (10) over their respective coordinate sets gives

∑t=1T⟨w(t),qit⟩≤(1+ε)Φ1++Φ‾T+11−ηρ+η((1+ε)PT++NT−)\sum_{t=1}^{T}\langle w^{(t)},q_{i_t}\rangle\le(1+\varepsilon)\Phi_1^{+}+\frac{\overline{\Phi}_{T+1}}{1-\eta\rho}+\eta\bigl((1+\varepsilon)P_T^{+}+N_T^{-}\bigr)

Finally, summing (15) over t=1,…,Tt=1,\ldots,T and substituting the preceding bound yields

∑t=1T⟨w(t),r(t)⟩≤(1+ε)Φ1++ΦT+1−1−ηρ+η((1+ε)PT++NT−)+2εk∑t=1TΦt(18)\sum_{t=1}^{T}\langle w^{(t)},r^{(t)}\rangle\le(1+\varepsilon)\Phi_1^{+}+\frac{\Phi_{T+1}^{-}}{1-\eta\rho}+\eta\bigl((1+\varepsilon)P_T^{+}+N_T^{-}\bigr)+\frac{2\varepsilon}{k}\sum_{t=1}^{T}\Phi_t \tag*{(18)}

The update rule also gives

ΦT+1−Φ1=η∑t=1T⟨w(t),r(t)⟩\Phi_{T+1}-\Phi_1=\eta\sum_{t=1}^{T}\langle w^{(t)},r^{(t)}\rangle
ΦT+1+−Φ1+=η(PT+−NT+)\Phi_{T+1}^{+}-\Phi_1^{+}=\eta(P_T^{+}-N_T^{+})
ΦT+1−−Φ1−=η(PT−−NT−)\Phi_{T+1}^{-}-\Phi_1^{-}=\eta(P_T^{-}-N_T^{-})

The last two identities give PT+=NT++ΦT+1+−Φ1+ηP_T^{+}=N_T^{+}+\frac{\Phi_{T+1}^{+}-\Phi_1^{+}}{\eta} and NT−=PT−+Φ1−−ΦT+1−ηN_T^{-}=P_T^{-}+\frac{\Phi_1^{-}-\Phi_{T+1}^{-}}{\eta}. Substituting these identities into (18) and collecting the ΦT+1+\Phi_{T+1}^{+} and ΦT+1−\Phi_{T+1}^{-} terms yields

(1−η(1+ε))ΦT+1++(1−η2ρ1−ηρ)ΦT+1−≤Φ1++(1+η)Φ1−+η2((1+ε)NT++PT−)+2ηεk∑t=1TΦt(19)\begin{aligned} \left(1-\eta(1+\varepsilon)\right)\Phi_{T+1}^{+}+\left(1-\frac{\eta^{2}\rho}{1-\eta\rho}\right)\Phi_{T+1}^{-} \\ &\le\Phi_1^{+}+(1+\eta)\Phi_1^{-}+\eta^{2}\bigl((1+\varepsilon)N_T^{+}+P_T^{-}\bigr)+\frac{2\eta\varepsilon}{k}\sum_{t=1}^{T}\Phi_t \tag*{(19)} \end{aligned}

We can write

1−η(1+ε)≤1−η2ρ1−ηρ(1+ε)NT++PT−≤1+εk∑t=1TΦtΦ1=m(20)1-\eta(1+\varepsilon)\le1-\frac{\eta^{2}\rho}{1-\eta\rho}\qquad(1+\varepsilon)N_T^{+}+P_T^{-}\le\frac{1+\varepsilon}{k}\sum_{t=1}^{T}\Phi_t\qquad\Phi_1=m \tag*{(20)}

(The first bound holds since ηρ=ε/10≤1/20\eta\rho=\varepsilon/10\le1/20 and hence 1+ε≥ηρ1−ηρ1+\varepsilon\ge\frac{\eta\rho}{1-\eta\rho}.) Dividing (19) by 1−η(1+ε)1-\eta(1+\varepsilon) and using (20) gives

ΦT+1≤αm+β∑t=1TΦtwhereα:=1+η1−η(1+ε)β:=η2(1+ε)+2ηεk[1−η(1+ε)]\Phi_{T+1}\le\alpha m+\beta\sum_{t=1}^{T}\Phi_t\qquad\text{where}\qquad\alpha:=\frac{1+\eta}{1-\eta(1+\varepsilon)}\qquad\beta:=\frac{\eta^{2}(1+\varepsilon)+2\eta\varepsilon}{k[1-\eta(1+\varepsilon)]}

Iterating this recurrence starting from Φ1=m\Phi_1=m gives

ΦT+1≤αm(1+β)T≤αmeβT(21)\Phi_{T+1}\le\alpha m(1+\beta)^T\le\alpha m e^{\beta T} \tag*{(21)}

where the first inequality is proved by induction on TT.

Proof of Theorem 4 Fix e∈[m]e\in[m], and again define Re=∑t=1Tre(t)R_e=\sum_{t=1}^{T}r_e^{(t)}. Suppose that Re≥0R_e\ge0. As in eq. (10), we get

ln⁡ΦT+1≥ln⁡we(T+1)≥3η4Re−2η2ρTk(22)\ln\Phi_{T+1}\ge\ln w_e^{(T+1)}\ge\frac{3\eta}{4}R_e-\frac{2\eta^{2}\rho T}{k} \tag*{(22)}

Comparing (21) with (22) gives

ReT≤8ηρ3k+4β3η+4ln⁡(αm)3ηT(23)\frac{R_e}{T}\le\frac{8\eta\rho}{3k}+\frac{4\beta}{3\eta}+\frac{4\ln(\alpha m)}{3\eta T} \tag*{(23)}

Recall that η≤ηρ=ε/10\eta\le\eta\rho= \varepsilon/10 and ε≤1/2\varepsilon\le1/2. We first claim that

βkη=η(1+ε)+2ε1−η(1+ε)<7ε3\frac{\beta k}{\eta} = \frac{\eta(1+\varepsilon)+2\varepsilon}{1-\eta(1+\varepsilon)} < \frac{7\varepsilon}{3}

This holds since the denominator is positive and the difference of cross products is negative:

3(η(1+ε)+2ε)−7ε(1−η(1+ε))=η(1+ε)(3+7ε)−ε≤ε10⋅394−ε<03(\eta(1+\varepsilon)+2\varepsilon)-7\varepsilon(1-\eta(1+\varepsilon)) = \eta(1+\varepsilon)(3+7\varepsilon)-\varepsilon\le\frac{\varepsilon}{10}\cdot\frac{39}{4}-\varepsilon< 0

We also have η≤ε/10≤1/20\eta\le\varepsilon/10 \le1/20, η(1+ε)≤3/40\eta(1+\varepsilon) \le3/40 and T≥24kρε−2ln⁡(2m)=24k10ηεln⁡(2m)T \ge24k\rho\varepsilon^{-2}\ln(2m) = \frac{24k}{10\eta\varepsilon}\ln(2m), and hence

α=1+η1−η(1+ε)≤21/2037/40<2\alpha= \frac{1+\eta}{1-\eta(1+\varepsilon)} \le\frac{21/20}{37/40} < 2
ln⁡(αm)ηT≤ln⁡(2m)ηT≤512εk\frac{\ln(\alpha m)}{\eta T} \le\frac{\ln(2m)}{\eta T} \le\frac{5}{12}\frac{\varepsilon}{k}

Substituting these bounds into (23) gives

ReT≤83⋅ε10k+43⋅7ε3k+43⋅5ε12k<4εk(24)\frac{R_e}{T} \le\frac{8}{3}\cdot\frac{\varepsilon}{10k}+\frac{4}{3}\cdot\frac{7\varepsilon}{3k}+\frac{4}{3}\cdot\frac{5\varepsilon}{12k}<\frac{4\varepsilon}{k} \tag*{(24)}

We established bound (24) assuming that Re≥0R_e \ge0. If Re<0R_e < 0 then the same bound holds automatically. Thus, (24) holds for all e∈[m]e \in[m]. This finally implies

∑iAixi−b=kT∑t=1Tr(t)≤4ε1\sum_i A_i x_i-b=\frac{k}{T}\sum_{t=1}^{T}r^{(t)}\le4\varepsilon\mathbf{1}

Finite-precision implementation: proof of Theorem 5

Let w~(t)\widetilde{w}^{(t)} and y~(t)\widetilde{y}^{(t)} be the weights and the oracle vectors in the modified algorithm, and x(t)x^{(t)} be the oracle answer in the tt-th step. Let w(t)w^{(t)} and y(t)y^{(t)} be similar quantities in the execution of the original MWU-D algorithm with parameter 3ε3\varepsilon in which the oracle returns x(t)x^{(t)} in the tt-th step. It suffices to show that this answer fits the specification of the approximate oracle, i.e. that

(y(t))⊤Aix(t)≤min⁡x∈Xi(y(t))⊤Aix+3εk(25)\left(y^{(t)}\right)^\top A_i x^{(t)} \le\min_{x\in X_i}\left(y^{(t)}\right)^\top A_i x+\frac{3\varepsilon}{k} \tag*{(25)}

for each t∈[T]t \in[T] and i=iti=i_t. Theorem 4 will then imply that the output is an 4⋅(3ε)4\cdot(3\varepsilon)-approximate solution.

Since the two executions use the same oracle answer x(t)x^{(t)}, they also use the same residual r(t)=Aix(t)−b/kr^{(t)}=A_i x^{(t)}-b/k. By construction, we have we(1)=w~e(1)=1w_e^{(1)}=\widetilde{w}_e^{(1)}=1 and

we(t+1)=we(t)(1+ηre(t))w_e^{(t+1)}=w_e^{(t)}(1+\eta r_e^{(t)})
w~e(t+1)=w~e(t)(1+ηre(t))(1+δt,e)\widetilde{w}_e^{(t+1)}=\widetilde{w}_e^{(t)}(1+\eta r_e^{(t)})(1+\delta_{t,e})

for some δt,e\delta_{t,e} with ∣δt,e∣≤δ:=2−B|\delta_{t,e}|\le\delta:=2^{-B}. This implies that

∣log⁡2w~e(t)we(t)∣≤Tmax⁡{∣log⁡2(1+δ)∣,∣log⁡2(1−δ)∣}≤2Tδ(26)\left|\log_2\frac{\widetilde{w}_e^{(t)}}{w_e^{(t)}}\right|\le T\max\{|\log_2(1+\delta)|,|\log_2(1-\delta)|\}\le2T\delta \tag*{(26)}

for each t∈[T]t\in[T]. Next, we compare y:=y(t)y:=y^{(t)} and y~:=y~(t)\widetilde{y}:=\widetilde{y}^{(t)}. Recall that they are constructed from w:=w(t)w:=w^{(t)} and w~:=w~(t)\widetilde{w}:=\widetilde{w}^{(t)} as follows:

y=w∑eweW~=∑ew~ew‾=truncate⁡τW~(w~)W‾=∑ew‾ey~=w‾W‾y=\frac{w}{\sum_e w_e}\qquad\widetilde{W}=\sum_e\widetilde{w}_e\qquad\overline{w}=\operatorname{truncate}_{\tau\widetilde{W}}(\widetilde{w})\qquad\overline{W}=\sum_e\overline{w}_e\qquad\widetilde{y}=\frac{\overline{w}}{\overline{W}}

We choose the constant in τ=Θ(ε/(mkρ))\tau=\Theta(\varepsilon/(mk\rho)) so that τ<1/m\tau<1/m. Since some coordinate of w~\widetilde{w} is at least W~/m\widetilde{W}/m, at least one coordinate survives the truncation; hence W‾>0\overline{W}>0 and y~\widetilde{y} is well defined.

The definitions of yy and y~\widetilde{y} will not change if vectors ww and w~\widetilde{w} are divided by the same constant; this operation will also preserve (26). We can thus assume w.l.o.g. that ∑ew~e=1\sum_e \widetilde{w}_e = 1. This condition together with (26) implies w~e∈we⋅[2−2Tδ,22Tδ]\widetilde{w}_e \in w_e \cdot[2^{-2T\delta},2^{2T\delta}] and hence ∥w~−w∥1≤22Tδ−1\lVert\widetilde{w}-w\rVert_1 \le2^{2T\delta}-1. Choose the constant in B=Θ(log⁡(kρT/ϵ))B=\Theta(\log(k\rho T/\epsilon)) so that 22Tδ−1≤ϵ/(8kρ)2^{2T\delta}-1\le\epsilon/(8k\rho); then ∣W‾−1∣≤∥w~−w∥1≤ϵ/(8kρ)|\overline{W}-1|\le\lVert\widetilde{w}-w\rVert_1\le\epsilon/(8k\rho). Choose the constant in τ=Θ(ϵ/(mkρ))\tau=\Theta(\epsilon/(mk\rho)) so that ∥w‾−w~∥1=W‾−W≤mτW‾≤ϵ/(8kρ)\lVert\overline{w}-\widetilde{w}\rVert_1=\overline{W}-W\le m\tau\overline{W}\le\epsilon/(8k\rho). We obtain

∣W‾−1∣≤∥w‾−w∥1≤∥w‾−w~∥1+∥w~−w∥1≤ϵ8kρ+ϵ8kρ=ϵ4kρ|\overline{W}-1|\le\lVert\overline{w}-w\rVert_1\le\lVert\overline{w}-\widetilde{w}\rVert_1+\lVert\widetilde{w}-w\rVert_1\le\frac{\epsilon}{8k\rho}+\frac{\epsilon}{8k\rho}=\frac{\epsilon}{4k\rho}

Since y=wy=w and y~=w‾/W‾\widetilde{y}=\overline{w}/\overline{W} under our normalization, we obtain

∥y~−y∥1≤∥w‾W‾−w‾∥1+∥w‾−w∥1=∣1−W‾∣+∥w‾−w∥1≤ϵ2kρ(27)\lVert\widetilde{y}-y\rVert_1\le\left\lVert\frac{\overline{w}}{\overline{W}}-\overline{w}\right\rVert_1+\lVert\overline{w}-w\rVert_1=|1-\overline{W}|+\lVert\overline{w}-w\rVert_1\le\frac{\epsilon}{2k\rho} \tag*{(27)}

Let xi⋆=Oracle⁡ϵ(i,y)x_i^\star=\operatorname{Oracle}_{\epsilon}(i,y) where the subscript indicates the oracle’s accuracy. (Recall that x:=x(t)=Oracle⁡ϵ(i,y~)x:=x^{(t)}=\operatorname{Oracle}_{\epsilon}(i,\widetilde{y}).) The width bounds and (27) imply

∣(y~−y)⊤Aiz∣≤ϵ2kfor z∈{x,xi⋆}\left|(\widetilde{y}-y)^\top A_i z\right|\le\frac{\epsilon}{2k}\qquad\text{for }z\in\{x,x_i^\star\}

Using this estimate and the oracle guarantee at y~\widetilde{y} and yy, we obtain the desired inequality (25):

y⊤Aix≤y~⊤Aix+ϵ2k≤y~⊤Aixi⋆+3ϵ2k≤y⊤Aixi⋆+2ϵk≤min⁡x∈Xiy⊤Aix+3ϵk\begin{aligned} y^\top A_i x&\le\widetilde{y}^\top A_i x+\frac{\epsilon}{2k}\\ &\le\widetilde{y}^\top A_i x_i^\star+\frac{3\epsilon}{2k}\\ &\le y^\top A_i x_i^\star+\frac{2\epsilon}{k}\\ &\le\min_{x\in X_i}y^\top A_i x+\frac{3\epsilon}{k} \end{aligned}

It remains to discuss the ranges of w~(t)\widetilde{w}^{(t)} and y~(t)\widetilde{y}^{(t)} in the modified algorithm. First, ∣log⁡2w~e(t)∣=O(T(ηρ+δ))|\log_2\widetilde{w}_e^{(t)}|=O(T(\eta\rho+\delta)), so the exponent of an internal weight has O(log⁡(Tηρ+1))O(\log(T\eta\rho+1)) bits. Together with the BB-bit mantissa produced by rounding, this gives the stated membership in QA,B\mathbb{Q}_{A,B}.

We next consider y~(t)\widetilde{y}^{(t)}. Any two nonzero coordinates of w‾(t)\overline{w}^{(t)} differ by a factor of at most 1/τ=O(mkρ/ϵ)1/\tau=O(mk\rho/\epsilon): each is at least τW‾\tau\overline{W}, while each is at most W‾\overline{W}. Write every nonzero rounded weight in canonical dyadic form pe2ae−Bp_e2^{a_e-B} with 2B−1≤pe<2B2^{B-1}\le p_e<2^B (absorbing powers of two into aea_e). The preceding ratio bound implies ∣ae−ae′∣=O(log⁡(1/τ))|a_e-a_{e'}|=O(\log(1/\tau)) for nonzero retained coordinates. After factoring out 2min⁡eae−B2^{\min_e a_e-B}, the retained weights are integers ze=pe2ae−min⁡eaez_e=p_e2^{a_e-\min_e a_e} having O(B+log⁡(1/τ))O(B+\log(1/\tau)) bits. Therefore

y~e=zeq,q=∑eze\widetilde{y}_e=\frac{z_e}{q},\qquad q=\sum_e z_e

where both zez_e and qq have O(B+log⁡m+log⁡(1/τ))=O(log⁡(mkρT/ϵ))O(B+\log m+\log(1/\tau))=O(\log(mk\rho T/\epsilon)) bits. This gives the stated polynomially bounded shared denominator.

Maximum weighted multicommodity flow

In this section we apply Theorem 1 to prove Theorem 2. Let G=(V,E)G=(V,E) be a directed or undirected graph with capacities ue>0u_e>0. Commodity ii has terminals (si,ti)(s_i,t_i) and reward γi>0\gamma_i>0 per unit of flow. Edges of zero capacity and commodities of zero reward can be discarded, so these positivity assumptions are without loss of generality. For a candidate objective value F>0F>0, let XiX_i consist of pairs xi=(fi,βi)x_i=(f_i,\beta_i) such that fif_i is an sis_i-tit_i flow of value βi\beta_i, 0≤fi(e)≤ue0\le f_i(e)\le u_e for every e∈Ee\in E, and 0≤γiβi≤F0\le\gamma_i\beta_i\le F. The feasibility problem for value FF can be written as follows:

x=(x1,…,xk)∈X1×⋯×Xk(28)x=(x_1,\ldots,x_k)\in\mathcal{X}_1\times\cdots\times\mathcal{X}_k \tag*{(28)}
∑i=1kfi(e)ue≤1∀e∈E(29)\sum_{i=1}^{k}\frac{f_i(e)}{u_e}\le1 \qquad\forall e\in E \tag*{(29)}
−∑i=1kγiβiF≤−1(30)-\sum_{i=1}^{k}\frac{\gamma_i\beta_i}{F}\le-1 \tag*{(30)}

This target system is feasible if and only if F≤OPTF\le\mathrm{OPT}. The definition of Xi\mathcal{X}_i implies that any vector xi∈Xix_i\in\mathcal{X}_i satisfies conditions (2b), (2c) with width parameter ρ=1\rho=1. Given prices yy, the ii-th oracle needs to solve

min⁡(f,β)∈XiC(f,β),C(f,β):=y∘+∑e∈Eyeuefe−y∘γiFβ(31)\min_{(f,\beta)\in\mathcal{X}_i} C(f,\beta),\qquad C(f,\beta):=y_{\circ}+\sum_{e\in E}\frac{y_e}{u_e}f_e-\frac{y_{\circ}\gamma_i}{F}\beta \tag*{(31)}

where y∘y_{\circ} is the component corresponding to constraint (21c). (We shifted the objective by y∘y_{\circ}, which does not affect the oracle and its additive approximation guarantees). Note that C(f,β)≥0C(f,\beta)\ge0 for any (f,β)∈Xi(f,\beta)\in\mathcal{X}_i since y∘(1−γiFβ)≥0y_{\circ}(1-\frac{\gamma_i}{F}\beta)\ge0.

We can model (22) as a min-cost flow problem as follows. Define D=F/γiD=F/\gamma_i. Add a parallel dummy edge (si,ti)(s_i,t_i) (directed or undirected, depending on the type of the multicommodity flow problem), and seek a minimum-cost sis_i-tit_i flow of value exactly DD in the resulting graph. Give every original edge ee capacity ueu_e and cost ye/uey_e/u_e, and give the dummy edge capacity DD and cost y∘/Dy_{\circ}/D. If β\beta units use the original graph, the remaining D−βD-\beta units use the dummy edge, and the resulting cost is exactly C(f,β)C(f,\beta). Thus all costs in this min-cost-flow instance are nonnegative. In the undirected case, cancel cycles in the returned flow before reading off (f,β)(f,\beta). In particular, any backward use of the dummy edge forms, together with an sis_i-tit_i path in the original graph, a nonnegative-cost cycle and can be removed without increasing cost. We may therefore assume that the dummy edge carries an amount in [0,D][0,D] in the forward direction, so the remaining original flow has value β∈[0,D]\beta\in[0,D] as required.

Sending all DD units through the dummy edge has cost y∘y_{\circ}, so C∗:=min⁡(f,β)∈XiC(f,β)≤y∘≤1C^*:=\min_{(f,\beta)\in\mathcal{X}_i}C(f,\beta)\le y_{\circ}\le1. Hence, if the min-cost-flow solver finds feasible flow (f,β)(f,\beta) within factor 1+ε/k1+\varepsilon/k from the optimum then its additive error is ε/k\varepsilon/k, as needed:

C(f,β)≤(1+ε/k)C∗≤C∗+ε/kC(f,\beta)\le(1+\varepsilon/k)C^*\le C^*+\varepsilon/k

We showed that a feasible target FF can be tested with O(kε−2log⁡m)O(k\varepsilon^{-2}\log m) min-cost-flow calls; if problem (21) is feasible then we find an O(ε)O(\varepsilon)-approximate solution. Scaling all flows uniformly makes the capacity constraints exact while retaining total reward of the flow at least (1−O(ε))F(1-O(\varepsilon))F.

This is a gap test: an infeasibility report implies F>OPTF>\mathrm{OPT}, whereas a returned solution can be scaled to a feasible flow of value (1−O(ε))F(1-O(\varepsilon))F. Treating these outcomes as the upper and lower answers, respectively, gives a multiplicative gap search. If OPT=0\mathrm{OPT}=0, the zero flow is already optimal. Otherwise, polynomial boundedness implies that the optimum is at least (mk)−O(1)(mk)^{-O(1)}, while the elementary bound OPT≤∑iγi∑eue\mathrm{OPT}\le\sum_i\gamma_i\sum_e u_e is at most (mk)O(1)(mk)^{O(1)}. Searching to relative accuracy 1+O(ε)1+O(\varepsilon) uses O(log⁡(km/ε))O(\log(km/\varepsilon)) tests. This establishes Theorem 2.

Remark 1. In the introduction we claimed an efficient algorithm for families with efficient vertex separators via the work [7]. Note that adding the dummy edge does not cause a problem for such families: if SS is a vertex separator of size O(n)O(\sqrt{n}) in the original graph, then S∪{si}S\cup\{s_i\} is a separator of the augmented graph (also of size O(n)O(\sqrt{n})).

Acknowledgements and declaration on the use of generative AI

During the preparation and revision of this manuscript, the author used ChatGPT and Codex by OpenAI as interactive research and writing tools. They were used to generate draft proof arguments, including initial drafts of the proofs of Theorems 3, 4, and 5, and to assist with literature searches, consistency checks, language editing, and presentation.

All research questions, algorithmic framework, and final mathematical arguments were developed and selected by the author. All AI-generated material was independently checked and substantially revised by the author; references and prior-work claims were verified against the cited sources. The author takes full responsibility for the correctness and content of the manuscript.

This work was in part motivated by interactions with Jack Spalding-Jamieson, during which the author learned about the existence of a (less efficient) reduction of M-MCF to min-cost flows.

References

  1. [1]Arora, Sanjeev, Elad Hazan, and Satyen Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(6):121–164, 2012. https://doi.org/10.4086/toc.2012.v008a006.
  2. [2]Blanchard, Pierre, Desmond J. Higham, and Nicholas J. Higham. Accurate computation of the log-sum-exp and softmax functions. IMA Journal of Numerical Analysis, 41(4):2311–2330, 2021. https://doi.org/10.1093/imanum/draa038.
  3. [3]Carmon, Yair, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 sketch for matrix multiplicative weights. In Proceedings of the 32nd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 589–623, 2019. https://proceedings.mlr.press/v99/carmon19a.html.arxiv.org/abs/1903.02675
  4. [4]Chen, Li, Andrei Graur, and Aaron Sidford. Accelerated approximate optimization of multicommodity flows on directed graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2203–2212, 2025. https://doi.org/10.1145/3711823.3718267.
  5. [5]Chen, Li, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Journal of the ACM, 72(3):19:1–19:103, 2025. Conference version at FOCS 2022. https://doi.org/10.1145/3728631.
  6. [6]Diedrich, Florian and Klaus Jansen. An approximation algorithm for the general mixed packing and covering problem. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, volume 4614 of Lecture Notes in Computer Science, pages 128–139, 2007. https://doi.org/10.1007/978-3-540-74450-4_12.
  7. [7]Dong, Sally, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. Nested dissection meets IPMs: Planar min-cost flow in nearly-linear time. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 124–153, 2022. https://doi.org/10.1137/1.9781611977073.7.
  8. [8]Fleischer, Lisa K. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13(4):505–520, 2000. Conference version at FOCS 1999. https://doi.org/10.1137/S0895480199355754.
  9. [9]Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. Conference version at EuroCOLT 1995. https://doi.org/10.1006/jcss.1997.1504.
  10. [10]Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 300–309, 1998. https://doi.org/10.1109/SFCS.1998.743463.
  11. [11]Michael D. Grigoriadis and Leonid G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4(1):86–107, 1994. https://doi.org/10.1137/0804004.
  12. [12]Michael D. Grigoriadis and Leonid G. Khachiyan. An exponential-function reduction method for block-angular convex programs. Networks, 26(2):59–68, 1995. https://doi.org/10.1002/net.3230260202.
  13. [13]Michael D. Grigoriadis and Leonid G. Khachiyan. Approximate minimum-cost multicommodity flows in Õ(ε−2KNM) time. Mathematical Programming, 75(3):477–482, 1996. Technical report published in 1995. https://doi.org/10.1007/BF02592195.
  14. [14]Michael D. Grigoriadis and Leonid G. Khachiyan. Coordination complexity of parallel price-directive decomposition. Mathematics of Operations Research, 21(2):321–340, 1996. https://doi.org/10.1287/moor.21.2.321.
  15. [15]Klaus Jansen. Approximation algorithm for the mixed fractional packing and covering problem. SIAM Journal on Optimization, 17(2):331–352, 2006. Conference version at IFIP TCS 2004. https://doi.org/10.1137/030601570.
  16. [16]Satyen Kale. Efficient Algorithms Using the Multiplicative Weights Update Method. PhD thesis, Princeton University, 2007. Technical Report TR-804-07. https://www.satyenkale.com/papers/thesis.pdf.
  17. [17]George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms, 4(1):13:1–13:17, 2008. Conference version at SODA 2002. https://doi.org/10.1145/1328911.1328924.
  18. [18]Philip Klein and Neal E. Young. On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms. SIAM Journal on Computing, 44(4):1154–1172, 2015. Conference version at IPCO 1999. https://doi.org/10.1137/12087222X.
  19. [19]Philip N. Klein, Serge A. Plotkin, Clifford Stein, and Éva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466–487, 1994. Conference version at STOC 1990. https://doi.org/10.1137/S0097539792241175.
  20. [20]Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Éva Tardos, and Spyros Tragoudas. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2):228–243, 1995. Conference version at STOC 1991. https://doi.org/10.1006/jcss.1995.1020.
  21. [21]Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994. Conference version at FOCS 1989. https://doi.org/10.1006/inco.1994.1009.
  22. [22]Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 121–130, 2010. https://doi.org/10.1145/1806689.1806708.
  23. [23]Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the Lanczos method for matrix function approximation. In Proceedings of the 29th Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1605–1624, 2018. https://doi.org/10.1137/1.9781611975031.105.
  24. [24]Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the Lanczos method and an Õ(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 1141–1160, 2012. https://doi.org/10.1145/2213977.2214080.
  25. [25]Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257–301, 1995. Conference version at FOCS 1991. https://doi.org/10.1287/moor.20.2.257.
  26. [26]Kent Quanrud. Nearly linear time approximations for mixed packing and covering problems without data structures or randomization. In Proceedings of the 2020 ACM–SIAM Symposium on Simplicity in Algorithms, pages 69–80, 2020. https://doi.org/10.1137/1.9781611976014.11.
  27. [27]Tomasz Radzik. Fast deterministic approximation for the multicommodity flow problem. Mathematical Programming, 78(1):43–58, 1997. Conference version at SODA 1995. https://doi.org/10.1007/BF02614505.
  28. [28]Farhad Shahrokhi and David W. Matula. The maximum concurrent flow problem. Journal of the ACM, 37(2):318–334, 1990. Conference version at the ACM Computer Science Conference 1987.DOI
  29. [29]Jonah Sherman. Area-convexity, ℓ∞ regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 452–460, 2017. https://doi.org/10.1145/3055399.3055501.
  30. [30]Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. https://www.jmlr.org/papers/v6/tsuda05a.html.DOI
  31. [31]Jorge Villavicencio and Michael D. Grigoriadis. Approximate structured optimization by cyclic block-coordinate descent. In Herbert Fischer, Bruno Riedmüller, and Stefan Schäffler, editors, Applied Mathematics and Parallel Computing: Festschrift for Klaus Ritter, pages 359–371. Physica-Verlag, Heidelberg, 1996. https://doi.org/10.1007/978-3-642-99789-1.
  32. [32]Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 538–546, 2001. https://doi.org/10.1109/SFCS.2001.959930.

Paper details

vlnc:W_7ch8rpt9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Codex

View statement
Looking for related papers…
Contents