Introduction
A matching in a graph G = ( V , E ) G=(V,E) G = ( V , E ) is a set of edges no two of which share an endpoint, and ν ( G ) \nu(G) ν ( G ) denotes its maximum size. Maximum matching is a central problem in combinatorial optimization, with applications ranging from assignment problems to sparse matrix computation [21 , 37 ] . Its algorithmic study spans more than six decades, with Edmonds’s polynomial-time algorithm for general graphs as a foundational milestone [23 ] .
We study graphs with n n n vertices and maximum degree at most Δ \Delta Δ , where n n n may be much larger than Δ \Delta Δ . For such graphs, even reading the entire input may be too costly. Our goal is to answer local queries about an almost maximum matching, or to estimate its size, while inspecting only a small part of the graph. The first task is the subject of local computation algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie [52 ] and Alon, Rubinfeld, Vardi, and Xie [3 ] . The second is sublinear-time estimation, studied since the work of Parnas and Ron [50 ] and Nguyen and Onak [46 ] . Matching has received extensive attention in both settings [6 , 8 , 9 , 11 , 12 , 13 , 38 , 40 , 46 , 50 , 54 , 56 ] , and we review the known bounds below. We also consider the distributed LOCAL and CONGEST models, where vertices communicate with their neighbors in synchronous rounds and complexity is measured by the number of communication rounds.
We study both matchings and their classical fractional relaxation. A fractional matching assigns nonnegative weights f e f_e f e to edges such that ∑ e ∋ v f e ≤ 1 \sum_{e\ni v} f_e \le1 ∑ e ∋ v f e ≤ 1 at every vertex. Its value is ∑ e f e \sum_e f_e ∑ e f e , and ν f ( G ) \nu_f(G) ν f ( G ) denotes the maximum possible value. It is half-integral if every weight belongs to { 0 , 1 2 , 1 } \{0,\frac{1}{2},1\} { 0 , 2 1 , 1 } . On bipartite graphs, ν f ( G ) = ν ( G ) \nu_f(G)=\nu(G) ν f ( G ) = ν ( G ) .
The local computation model. The vertices are labeled by [ n ] [n] [ n ] , and n n n and a degree bound Δ ≥ 2 \Delta\ge2 Δ ≥ 2 are known. A degree query at v v v returns deg ( v ) \deg(v) deg ( v ) . A neighbor query at ( v , i ) (v,i) ( v , i ) returns the i i i -th neighbor of v v v , with neighbors listed in a fixed but arbitrary order. An LCA [3 , 52 ] provides query access to a solution without constructing the entire output. For matching, a mate query at a vertex returns its partner or reports that it is unmatched. For fractional matching, an edge query returns the weight assigned to an edge.
Our LCAs do not use preprocessing and do not retain state between invocations. A randomized LCA has access to a random tape shared by all invocations, allowing repeated evaluations to reproduce the same random choices. All answers must be globally consistent: they must agree with one feasible solution, in every query order, including adaptively chosen queries.
We measure an LCA’s query complexity by the worst-case number of graph queries used to answer one solution query. A size estimator returns a numerical estimate of ν ( G ) \nu(G) ν ( G ) or ν f ( G ) \nu_f(G) ν f ( G ) , and its query complexity is the total number of graph queries it makes.
Computation is free when measuring graph-query complexity. We separately bound computational work in the finite-arithmetic model of § 2.1 .
The distributed LOCAL and CONGEST models. In both models [51 ] , each vertex is a processor that communicates with its neighbors in synchronous rounds. The LOCAL model measures information radius and allows messages of unrestricted size; the CONGEST additionally restricts communication bandwidth to O ( log n ) O(\log n) O ( log n ) bits per edge in each direction per round. After r r r rounds, a vertex’s output can depend only on information within its radius-r r r neighborhood. Thus distributed round complexity measures how far information must travel, whereas LCA query complexity measures how much of the input is inspected. An LCA can simulate an r r r -round distributed algorithm by exploring the radius-r r r neighborhood of the queried vertex, using ( 2 Δ ) O ( r ) (2\Delta)^{O(r)} ( 2Δ ) O ( r ) graph queries [50 ] . In addition to query and round complexity, we separately bound the computational work per local query and the message size per edge per round in our distributed implementation.
Approximation guarantees. The optimal matching can depend on information arbitrarily far from the queried vertex, even on paths. We therefore focus on approximation when seeking bounds independent of n n n .
For the matching itself, we seek a multiplicative guarantee: a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximate matching has size at least ( 1 − ε ) ν ( G ) (1-\varepsilon)\nu(G) ( 1 − ε ) ν ( G ) , and analogously at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) for fractional matching. To describe earlier results, we also use additive approximation notation: a matching M M M is ( 1 , ε n ) (1,\varepsilon n) ( 1 , ε n ) -approximate if ∣ M ∣ ≥ ν ( G ) − ε n |M|\ge\nu(G)-\varepsilon n ∣ M ∣ ≥ ν ( G ) − ε n , and more generally ( α , ε n ) (\alpha,\varepsilon n) ( α , ε n ) -approximate if ∣ M ∣ ≥ α ν ( G ) − ε n |M|\ge\alpha\nu(G)-\varepsilon n ∣ M ∣ ≥ α ν ( G ) − ε n . Note that since ν ( G ) , ν f ( G ) ≤ n / 2 \nu(G),\nu_f(G)\le n/2 ν ( G ) , ν f ( G ) ≤ n /2 , a multiplicative ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximate guarantee implies an additive ( 1 , ε n / 2 ) (1,\varepsilon n/2) ( 1 , ε n /2 ) guarantee and hence is stronger.
For size estimation, a multiplicative guarantee with a fixed ε \varepsilon ε requires distinguishing the empty graph from a graph with a single edge, which requires Ω ( n ) \Omega(n) Ω ( n ) queries. For query bounds independent of n n n , we therefore seek additive accuracy.
Known algorithms. Sublinear algorithms for estimating matching size in bounded-degree graphs go back to Parnas and Ron [50 ] , who showed how to simulate a distributed algorithm at a single vertex by exploring its neighborhood. For matching, this gives a ( 1 / 2 , ε n ) (1/2,\varepsilon n) ( 1/2 , ε n ) -estimate with Δ O ( log ( Δ / ε ) ) \Delta^{O(\log(\Delta/\varepsilon))} Δ O ( l o g ( Δ/ ε )) queries. Nguyen and Onak [46 ] introduced recursive local simulation of randomized greedy algorithms, and Yoshida, Yamamoto, and Ito [56 ] improved this approach to obtain a ( 1 , ε n ) (1,\varepsilon n) ( 1 , ε n ) -estimate with Δ O ( 1 / ε 2 ) \Delta^{O(1/\varepsilon^2)} Δ O ( 1/ ε 2 ) queries. Applied to the standard bipartite double cover [1, Lemma 7], this estimator also estimates ν f ( G ) \nu_f(G) ν f ( G ) within ± ε n \pm\varepsilon n ± ε n with the same query bound.
For LCAs, Mansour and Vardi [40 ] gave an approximation scheme with polylogarithmic query complexity for constant Δ \Delta Δ and ε \varepsilon ε . Levi, Rubinfeld, and Yodpinyanee [38 ] adapted the method of [56 ] to obtain a multiplicative ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximation using ( Δ / ε ) O ( 1 / ε 2 ) polylog ( n ) (\Delta/\varepsilon)^{O(1/\varepsilon^2)}\operatorname{polylog}(n) ( Δ/ ε ) O ( 1/ ε 2 ) polylog ( n ) queries per invocation. This remains the best known bound of this form for general-graph matching LCAs. These approximation schemes use the augmenting-path framework of Hopcroft and Karp: in each of Θ ( 1 / ε ) \Theta(1/\varepsilon) Θ ( 1/ ε ) phases, they augment along a maximal collection of vertex-disjoint paths of a prescribed length. Finding this collection amounts to computing a maximal independent set in the conflict graph of candidate paths. In the simulations of [38 , 56 ] , each phase recursively invokes earlier phases, and the costs compound to give the quadratic dependence on 1 / ε 1/\varepsilon 1/ ε in the degree exponent.
A parallel line of work seeks sublinear algorithms without assuming a small maximum degree. For fixed ε \varepsilon ε , Behnezhad [7 ] gave a ( 1 / 2 , ε n ) (1/2,\varepsilon n) ( 1/2 , ε n ) -estimate of matching size in O ~ ( d ˉ + 1 ) \widetilde{O}(\bar d+1) O ( d ˉ + 1 ) time with adjacency-list queries, where d ˉ \bar d d ˉ is the average degree, and in O ~ ( n ) \widetilde{O}(n) O ( n ) time with adjacency-matrix queries. A multiplicative ( 1 / 2 − ε ) (1/2-\varepsilon) ( 1/2 − ε ) -estimate is also possible in O ~ ( n ) \widetilde{O}(n) O ( n ) time with adjacency-list queries. All three bounds are optimal up to polylogarithmic factors for fixed ε \varepsilon ε . Subsequent work improved the approximation ratio in n 2 − Ω ( 1 ) n^{2-\Omega(1)} n 2 − Ω ( 1 ) time [9 , 10 , 12 ] . Finally, Bhattacharya, Kiss, and Saranurak [13 ] obtained a ( 1 , ε n ) (1,\varepsilon n) ( 1 , ε n ) -estimate in n 2 − Ω ε ( 1 ) n^{2-\Omega_\varepsilon(1)} n 2 − Ω ε ( 1 ) time using adjacency-matrix queries.
Known lower bounds. For over fifteen years, the only degree-dependent lower bound for matching LCAs was the Ω ( Δ ) \Omega(\Delta) Ω ( Δ ) bound of Parnas and Ron [50 ] , based on hiding useful matching edges among many irrelevant neighbors. This hiding argument alone cannot give a superlinear dependence on Δ \Delta Δ . Behnezhad, Roghani, and Rubinstein [9 ] first broke this barrier, showing that ( 2 / 3 + Ω ( 1 ) , ε n ) (2/3+\Omega(1),\varepsilon n) ( 2/3 + Ω ( 1 ) , ε n ) -estimation requires n 1.2 − o ( 1 ) n^{1.2-o(1)} n 1.2 − o ( 1 ) queries for sufficiently small constant ε \varepsilon ε . Their construction, with Δ = Θ ( n ) \Delta=\Theta(n) Δ = Θ ( n ) , also yields a Δ 1.2 − o ( 1 ) \Delta^{1.2-o(1)} Δ 1.2 − o ( 1 ) lower bound per LCA query.
Open Problem 39 of sublinear.info [48 ] asked whether poly ( Δ / ε ) \operatorname{poly}(\Delta/\varepsilon) poly ( Δ/ ε ) queries suffice to estimate matching size within additive error ε n \varepsilon n ε n . Behnezhad, Roghani, and Rubinstein [8 ] answered this negatively, proving a Δ Ω ( 1 / ε ) \Delta^{\Omega(1/\varepsilon)} Δ Ω ( 1/ ε ) lower bound for both estimation and local computation, even on bipartite graphs, whenever ε ≤ 0.01 \varepsilon\le0.01 ε ≤ 0.01 and log 4 n ≤ Δ ≤ n ε \log^4 n\le\Delta\le n^\varepsilon log 4 n ≤ Δ ≤ n ε .
For dense graphs, Behnezhad, Roghani, and Rubinstein [11 ] subsequently proved that, for every fixed δ > 0 \delta>0 δ > 0 , there is a constant ε = ε ( δ ) > 0 \varepsilon=\varepsilon(\delta)>0 ε = ε ( δ ) > 0 such that additive ε n \varepsilon n ε n estimation requires Ω ( n 2 − δ ) \Omega(n^{2-\delta}) Ω ( n 2 − δ ) adjacency-list queries. This complements the n 2 − Ω ε ( 1 ) n^{2-\Omega_\varepsilon(1)} n 2 − Ω ε ( 1 ) upper bound of [13 ] . In the bounded-degree regime, the lower bound of [8 ] left a gap between linear and quadratic dependence on 1 / ε 1/\varepsilon 1/ ε in the degree exponent.
Our results
Our randomized algorithms close this gap for bipartite matching and its size estimation. On general graphs, they give the same bounds for half-integral fractional matching and estimation of ν f ( G ) \nu_f(G) ν f ( G ) .
Theorem 1.1 (Randomized local computation and estimation, informal). Let G G G have n ≥ 2 n\ge2 n ≥ 2 vertices and maximum degree at most Δ ≥ 2 \Delta\ge2 Δ ≥ 2 , and let 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 .
(a) There is a single randomized LCA with the following guarantees. On bipartite graphs, it supports mate queries to a matching M M M satisfying
P { ∣ M ∣ ≥ ( 1 − ε ) ν ( G ) } ≥ 0.9. \mathbb{P}\left\{|M| \ge(1-\varepsilon)\nu(G)\right\} \ge0.9. P { ∣ M ∣ ≥ ( 1 − ε ) ν ( G ) } ≥ 0.9.
On arbitrary graphs, the same LCA supports edge queries to a half-integral fractional matching f f f of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) with probability at least 0.9. Each mate or edge query uses ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) graph queries. No bipartition or prior knowledge of whether G G G is bipartite is required.
(b) For every 0 < ζ < 1 / 2 0 < \zeta< 1/2 0 < ζ < 1/2 , a randomized size estimator returns ν ^ \hat{\nu} ν ^ satisfying ∣ ν ^ − ν f ( G ) ∣ ≤ ε n |\hat{\nu}-\nu_f(G)| \le\varepsilon n ∣ ν ^ − ν f ( G ) ∣ ≤ ε n with probability at least 1 − ζ 1-\zeta 1 − ζ , using
( 2 Δ ) O ( 1 / ε ) log ( 2 / ζ ) (2\Delta)^{O(1/\varepsilon)}\log(2/\zeta) ( 2Δ ) O ( 1/ ε ) log ( 2/ ζ )
graph queries. On bipartite graphs, this estimates ν ( G ) \nu(G) ν ( G ) .
The same bounds hold separately for computational work in the model of § 2.1 . All query and work bounds are worst case. The LCA’s feasibility and consistency hold for every realization of the shared randomness and in every query order, including adaptively chosen queries. Only the approximation guarantees are probabilistic.
For constant success probability, our upper bounds match the lower bound of Behnezhad et al. [8 ] , in its applicable regime, up to a constant in the exponent. Thus, in that regime, the query complexity of bipartite matching and its size estimation is Δ Θ ( 1 / ε ) \Delta^{\Theta(1/\varepsilon)} Δ Θ ( 1/ ε ) .
For general graphs, ν ( G ) ≤ ν f ( G ) ≤ 3 2 ν ( G ) \nu(G) \le\nu_f(G) \le\frac{3}{2}\nu(G) ν ( G ) ≤ ν f ( G ) ≤ 2 3 ν ( G ) . Consequently, scaling the estimate in part (b) by 2 / 3 2/3 2/3 gives a ( 2 / 3 , ε n ) (2/3,\varepsilon n) ( 2/3 , ε n ) -estimate of ν ( G ) \nu(G) ν ( G ) : with probability at least 1 − ζ 1-\zeta 1 − ζ ,
2 3 ν ( G ) − ε n ≤ 2 3 ν ^ ≤ ν ( G ) + ε n . \frac{2}{3}\nu(G)-\varepsilon n \le\frac{2}{3}\hat{\nu} \le\nu(G)+\varepsilon n. 3 2 ν ( G ) − ε n ≤ 3 2 ν ^ ≤ ν ( G ) + ε n .
Whether integral ( 1 , ε n ) (1,\varepsilon n) ( 1 , ε n ) -approximate matchings in general graphs admit an LCA using ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) graph queries per mate query remains the main open question left by our work. The lower bound of Behnezhad et al. [8 ] applies, while the general-graph algorithms of Levi et al. [38 ] , Yoshida et al. [56 ] have quadratic dependence on 1 / ε 1/\varepsilon 1/ ε in the degree exponent.
Our construction also gives a deterministic LCA for fractional matching, with a larger query bound.
Theorem 1.2 (Deterministic fractional oracle, informal). Let G G G , Δ \Delta Δ , ε \varepsilon ε be as in Theorem 1.1 . There is a deterministic LCA whose answers are consistent with one fractional matching f f f satisfying
∑ e f e ≥ ( 1 − ε ) ν f ( G ) . \sum_e f_e \ge(1-\varepsilon)\nu_f(G). e ∑ f e ≥ ( 1 − ε ) ν f ( G ) . Each edge query uses at most
( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) (2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} ( 2Δ ) O ( ε − 1 l o g ( 2Δ )) graph queries, all within distance O ( ε − 1 log ( 2 Δ ) ) O(\varepsilon^{-1}\log(2\Delta)) O ( ε − 1 log ( 2Δ )) of the queried edge.
For every 0 < ζ < 1 / 2 0 < \zeta< 1/2 0 < ζ < 1/2 , uniform random vertex sampling combined with this oracle gives an estimate of ν f ( G ) \nu_f(G) ν f ( G ) within ± ε n \pm\varepsilon n ± ε n , with probability at least 1 − ζ 1-\zeta 1 − ζ , using at most
( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) log ( 2 / ζ ) (2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))}\log(2/\zeta) ( 2Δ ) O ( ε − 1 l o g ( 2Δ )) log ( 2/ ζ ) graph queries in total. Only the vertex sampling in this estimator is randomized. The same bounds hold separately for computational work in the model of § 2.1 . All query and work bounds are worst case.
The locality and structure of the deterministic updates give the following distributed consequence.
Corollary 1.3 (Deterministic distributed algorithm, informal). *Under the same assumptions, a deterministic distributed algorithm computes a fractional matching of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) in
O ( log ( 2 Δ ) ε ) O\left(\frac{\log(2\Delta)}{\varepsilon}\right) O ( ε log ( 2Δ ) ) rounds. Each edge carries O ( log ( 2 Δ / ε ) ) O(\log(2\Delta/\varepsilon)) O ( log ( 2Δ/ ε )) bits in each direction per round. The total computational work at a vertex v v v is
( deg ( v ) + 1 ) poly ( log ( 2 Δ ) ε ) . (\deg(v)+1)\operatorname{poly}\left(\frac{\log(2\Delta)}{\varepsilon}\right). ( deg ( v ) + 1 ) poly ( ε log ( 2Δ ) ) . All bounds are worst case. This gives the stated round bound in LOCAL for every 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 , and in CONGEST when ε ≥ n − O ( 1 ) \varepsilon\ge n^{-O(1)} ε ≥ n − O ( 1 ) .*
Fractional matching is a special case of fractional packing, which has been studied in distributed computing [36 ] . The deterministic algorithm of Li et al. [39 ] gives a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximate fractional matching in O ( ε − 2 log ( 2 Δ ) ) O(\varepsilon^{-2}\log(2\Delta)) O ( ε − 2 log ( 2Δ )) rounds. Simulating it by neighborhood exploration [50 ] gives a deterministic LCA using ( 2 Δ ) O ( ε − 2 log ( 2 Δ ) ) (2\Delta)^{O(\varepsilon^{-2}\log(2\Delta))} ( 2Δ ) O ( ε − 2 l o g ( 2Δ )) graph queries per edge query. Compared with these bounds, our construction improves the dependence on 1 / ε 1/\varepsilon 1/ ε from quadratic to linear, both in the LOCAL round complexity and in the exponent of the LCA query complexity.
Technical overview and roadmap
We first formulate fractional matching as a saddle-point problem and derive a deterministic optimization method with local updates (§ 3 –§ 5 ). After T = O ( ε − 1 log ( 2 Δ ) ) T=O(\varepsilon^{-1}\log(2\Delta)) T = O ( ε − 1 log ( 2Δ )) rounds, the method defines a nearly maximum fractional matching whose edge weights depend only on radius-O ( T ) O(T) O ( T ) neighborhoods. Evaluating the updates in these neighborhoods gives a deterministic LCA using ( 2 Δ ) O ( T ) = ( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) (2\Delta)^{O(T)}=(2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} ( 2Δ ) O ( T ) = ( 2Δ ) O ( ε − 1 l o g ( 2Δ )) queries and operations per edge query, and a deterministic distributed algorithm using O ( T ) O(T) O ( T ) communication rounds.
The key to improving the LCA bound is to sample from the distributions used by the optimizer without computing them explicitly. In § 6 , we construct a recursive sampler that follows the optimization round by round. Producing a sample for a new round uses an expected constant number of calls to the preceding round’s sampling procedures. This replaces the recursive exploration of all neighbors by constant expected branching, giving 2 O ( T ) = ( 2 Δ ) O ( 1 / ε ) 2^{O(T)}=(2\Delta)^{O(1/\varepsilon)} 2 O ( T ) = ( 2Δ ) O ( 1/ ε ) expected queries and operations per sample.
We then use these samples to construct a fractional matching that can be queried consistently with ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) worst-case work per query (§ 7 ). Rounding gives an integral matching on bipartite graphs and a half-integral fractional matching on general graphs (§ 9 ). The same sampler also gives our size estimator, without the rounding step (§ 8 ). The finite-precision implementation and its message-size bound are established in Section B. We next describe each ingredient and the challenges it addresses.
A saddle-point formulation of fractional matching
In § 3 , we express fractional matching as a min–max problem over distributions and prices at the vertices. Every vertex acts both as a proposer, sending mass to its neighbors, and as a receiver, accepting mass from its neighbors. Its proposal distribution describes the mass it sends, while its price is associated with its role as a receiver.
Each vertex u u u distributes one unit of mass among its neighbors and a private dummy, which represents unused mass. We call this probability vector q u q_u q u its proposal distribution . The quantities q u v q_{uv} q uv and q v u q_{vu} q v u represent mass sent in opposite directions and need not agree. Each vertex sends at most one unit to its neighbors, but may receive more than one unit. Write
ℓ v ( q ) = ∑ u ∈ N ( v ) q u v , P ( q ) = ∑ v min { 1 , ℓ v ( q ) } \ell_v(q)=\sum_{u\in N(v)}q_{uv},\qquad P(q)=\sum_v\min\{1,\ell_v(q)\} ℓ v ( q ) = u ∈ N ( v ) ∑ q uv , P ( q ) = v ∑ min { 1 , ℓ v ( q )}
for the incoming load at v v v and the total accepted mass when every vertex can accept at most one unit.
To obtain a feasible fractional matching, divide all incoming assignments at each vertex v v v with ℓ v ( q ) > 1 \ell_v(q)>1 ℓ v ( q ) > 1 by ℓ v ( q ) \ell_v(q) ℓ v ( q ) . Every vertex now sends and receives at most one unit. Assign each undirected edge the average of its two accepted directed assignments. The incident weights at each vertex sum to at most one, and the total edge weight is P ( q ) / 2 P(q)/2 P ( q ) /2 . Conversely, any fractional matching defines proposal distributions by sending its edge weights in both directions and putting unused mass on dummies. The resulting accepted mass is twice the matching’s value. Thus max q P ( q ) = 2 ν f ( G ) \max_q P(q)=2\nu_f(G) max q P ( q ) = 2 ν f ( G ) .
The cap makes P ( q ) P(q) P ( q ) nonsmooth. We introduce a price x v ∈ [ − 1 , 1 ] x_v\in[-1,1] x v ∈ [ − 1 , 1 ] at each vertex v v v , associated with its incoming load, and use the objective
F ( x , q ) = ∑ v [ x v + ℓ v ( q ) ( 1 − x v ) ] , min x F ( x , q ) = 2 P ( q ) − n . F(x,q)=\sum_v[x_v+\ell_v(q)(1-x_v)],\qquad\min_x F(x,q)=2P(q)-n. F ( x , q ) = v ∑ [ x v + ℓ v ( q ) ( 1 − x v )] , x min F ( x , q ) = 2 P ( q ) − n .
The second identity follows by minimizing separately at each vertex: an overloaded vertex chooses price + 1 +1 + 1 , and an underloaded vertex chooses price − 1 -1 − 1 . For fixed prices, proposal mass prefers lower-priced neighbors. Maximizing accepted mass is therefore equivalent to maximizing over proposal distributions and minimizing over prices. This is a saddle-point problem , with an objective affine in either set of variables when the other is fixed.
The multi-pass semi-streaming algorithm of Assadi et al. [4 ] also uses a saddle-point formulation of matching. Their formulation uses a single simplex over all edges, scaled by an estimate of the optimum, so normalization involves the whole graph. Our formulation uses a product of simplices, one for each vertex. Each proposal distribution is normalized separately at its source, which allows the local updates described next. The formulation also does not require an estimate of ν f ( G ) \nu_f(G) ν f ( G ) .
Optimization via local updates
§ 4 –§ 5 develop a deterministic optimization method for nearly maximizing accepted mass. Observe that simply alternating between best proposal distributions and best prices can oscillate the state: proposal mass moves to cheap receivers, making them overloaded and expensive, and then moves away again. We control these changes by penalizing movement away from the current state using a Bregman divergence derived from our regularizer. The regularizer combines negative entropy of the proposal distributions with an entropy-based price term that depends on the incoming loads.
We initialize each nonisolated vertex with price − 1 + 1 / Δ -1+1/\Delta − 1 + 1/Δ and assign probability 1 / ( 2 Δ 2 ) 1/(2\Delta^2) 1/ ( 2 Δ 2 ) to each of its neighbors, putting the remaining probability on its dummy.
Starting from this state, we perform T T T rounds of an extragradient method [45 ] . Each round first computes a tentative state using the gradient at the current state. It then evaluates the gradient at the tentative state and uses this gradient to form the next state, again starting from the original state. Both stages use penalties measured relative to the state at the start of the round.
The proposal updates have a multiplicative-weights form, with normalization performed separately at each vertex. Prices are updated by explicit formulas using the old prices and the relevant loads. The final output q ^ \hat q q ^ is the average of the tentative proposal distributions over all T T T rounds.
Our regularizer satisfies area convexity [30 , 55 ] , an inequality controlling the interaction between changes in prices and changes in proposal distributions. With the initialization above, the analysis of the two-stage method gives
2 ν f ( G ) − P ( q ^ ) ≤ O ( ν f ( G ) log ( 2 Δ ) T ) . 2\nu_f(G)-P(\hat{q}) \le O\left(\frac{\nu_f(G)\log(2\Delta)}{T}\right). 2 ν f ( G ) − P ( q ^ ) ≤ O ( T ν f ( G ) log ( 2Δ ) ) .
Since q ^ \hat{q} q ^ defines a fractional matching of value P ( q ^ ) / 2 P(\hat{q})/2 P ( q ^ ) /2 , taking T = O ( ε − 1 log ( 2 Δ ) ) T=O(\varepsilon^{-1}\log(2\Delta)) T = O ( ε − 1 log ( 2Δ )) gives a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximate fractional matching. Note that the optimization, including the choice of T T T , does not require an estimate of ν f ( G ) \nu_f(G) ν f ( G ) .
The state at each vertex in a new round depends only on the preceding round’s states within a constant number of hops. Since the initialization also uses only local information, each final edge weight is determined by a radius-O ( T ) O(T) O ( T ) neighborhood.
A deterministic LCA can explore this neighborhood and evaluate the updates, using
( 2 Δ ) O ( T ) = ( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) (2\Delta)^{O(T)}=(2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} ( 2Δ ) O ( T ) = ( 2Δ ) O ( ε − 1 l o g ( 2Δ ))
graph queries and arithmetic operations per edge query. This gives the deterministic LCA bound in Theorem 1.2 . Each optimization round uses a constant number of exchanges between neighboring vertices. Executing these updates gives an O ( T ) = O ( ε − 1 log ( 2 Δ ) ) O(T)=O(\varepsilon^{-1}\log(2\Delta)) O ( T ) = O ( ε − 1 log ( 2Δ )) -round distributed algorithm. The finite implementation in Section B.1 bounds the message sizes and local computational work, giving the distributed guarantees in Theorem 1.3.
The regularizer is also designed to support the sampling method described next.
Sampling: following the optimization without evaluating it
The deterministic LCA computes q ^ u \hat{q}_u q ^ u explicitly by exploring an entire radius-O ( T ) O(T) O ( T ) neighborhood of u u u , containing up to Δ O ( T ) \Delta^{O(T)} Δ O ( T ) vertices. In § 6 , we show how to draw an exact sample from q ^ u \hat{q}_u q ^ u without computing its probabilities, using only 2 O ( T ) 2^{O(T)} 2 O ( T ) expected graph queries and arithmetic operations.
Our multiplicative-weights updates form a new proposal distribution h u h_u h u by reweighting an existing distribution q u q_u q u :
h u a = q u a A u a Z u , Z u = ∑ b q u b A u b . h_{ua}=\frac{q_{ua}A_{ua}}{Z_u},\qquad Z_u=\sum_b q_{ub}A_{ub}. h u a = Z u q u a A u a , Z u = b ∑ q u b A u b .
By design, the reweighting factors in our update formulas have fixed positive lower and upper bounds. Multiplying them all by a common factor leaves h u h_u h u unchanged. We can therefore choose a fixed rescaling that puts every A u a A_{ua} A u a between two constants in ( 0 , 1 ) (0,1) ( 0 , 1 ) , so these weights can serve as acceptance probabilities.
Suppose we have a sampler for q u q_u q u and, for any sampled target a a a , an acceptance coin that returns one with probability A u a A_{ua} A u a . Draw a ∼ q u a\sim q_u a ∼ q u and flip this coin. On heads, return a a a ; on tails, repeat with a fresh draw and coin flip. A trial accepts and returns a a a with probability q u a A u a q_{ua}A_{ua} q u a A u a , so the returned sample has law h u h_u h u . The acceptance probability Z u Z_u Z u is bounded below by a constant, giving a constant expected number of trials. Thus an existing sampler and acceptance coins suffice to construct the new sampler, without evaluating either distribution or its normalizer.
The remaining task is to construct the acceptance coins. Their biases depend on prices and loads, and evaluating these quantities numerically would bring back the recursive exploration of all neighbors. We instead maintain coin procedures for the numerical quantities needed by the updates. For example, a price x v ∈ [ − 1 , 1 ] x_v\in[-1,1] x v ∈ [ − 1 , 1 ] can be represented by a coin whose probability of heads is ( 2 + x v ) / 4 (2+x_v)/4 ( 2 + x v ) /4 . The update formulas can then be expressed as functions of these coin biases.
These constructions use Bernoulli factories . Given independent flips of coins with unknown biases, a factory produces a new coin whose bias is a prescribed function of those biases [28 , 29 , 34 , 43 , 44 ] . We use factories to implement the scalar update formulas on coin representations. A new acceptance or price coin is constructed from available coins and samplers. Each input flip uses fresh randomness and may itself invoke earlier procedures.
The price updates also use incoming loads. At a nonisolated vertex v v v , the incoming proposal masses q u v q_{uv} q uv sum to the load ℓ v ( q ) \ell_v(q) ℓ v ( q ) , which may not be equal to one. Normalizing these masses defines the incoming distribution , assigning probability q u v / ℓ v ( q ) q_{uv}/\ell_v(q) q uv / ℓ v ( q ) to proposer u u u . We maintain a sampler for this distribution as well.
When q q q changes to h h h , the incoming distribution is reweighted by h u v / q u v h_{uv}/q_{uv} h uv / q uv . Factories construct coins for scaled versions of these ratios from the available samplers and acceptance coins. The same rejection-sampling construction then gives the new incoming sampler. An incoming rejection trial also supplies a coin whose bias is a fixed constant times the ratio of the new load to the old load. Thus the construction gives both samplers and load-ratio coins. Factories combine these load coins with coins for the old state to construct the updated price coins.
Constant expected branching requires a constant number of rejection trials, which is given by the bounded reweighting factors, and a constant expected number of input flips per factory, which follow from our regularizer design and coin representations together with a constant expected number of input flips and additional arithmetic operations. These bounds hold uniformly over vertices and rounds.
At initialization, all the required samplers and coins are directly available. For each new round, one sample or coin flip uses an expected constant number of calls to the preceding round’s procedures. Expanding these calls gives expected total work
2 O ( T ) = ( 2 Δ ) O ( 1 / ε ) , 2^{O(T)}=(2\Delta)^{O(1/\varepsilon)}, 2 O ( T ) = ( 2Δ ) O ( 1/ ε ) ,
including graph queries and arithmetic operations. The calls stay within a radius-O ( T ) O(T) O ( T ) neighborhood, exploring it only as needed to generate the draw. To sample from the optimizer’s final average q ˉ u \bar q_u q ˉ u , we choose a round uniformly from the T T T rounds and sample its tentative distribution at u u u .
From samples to a consistent fractional matching
Section 7 uses K = Θ ( ε − 2 ) K=\Theta(\varepsilon^{-2}) K = Θ ( ε − 2 ) samples per vertex to construct a random fractional matching whose edge weights can be queried consistently with ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) worst-case graph queries and arithmetic operations.
The first issue is that the sampler’s work is bounded only in expectation, whereas the final oracle requires a worst-case bound. We address this by imposing a work budget on each sampler invocation, with aborted draws returning the dummy. By Markov’s inequality, a budget of Θ ( Δ / ε ) \Theta(\Delta/\varepsilon) Θ ( Δ/ ε ) times the bound on expected work makes the abort probability O ( ε / Δ ) O(\varepsilon/\Delta) O ( ε /Δ ) . Let q ~ \tilde q q ~ denote the resulting proposal distributions. For every real edge u v uv uv , q ~ u v ≤ q u v \tilde q_{uv}\leq q_{uv} q ~ uv ≤ q uv , with the removed probability mass transferred to the dummy. If n 0 n_0 n 0 is the number of nonisolated vertices, the work budget reduces accepted mass by at most O ( ε n 0 / Δ ) O(\varepsilon n_0/\Delta) O ( ε n 0 /Δ ) . Since n 0 ≤ 2 Δ ν f ( G ) n_0\leq2\Delta\nu_f(G) n 0 ≤ 2Δ ν f ( G ) (Theorem 2.4), this loss is O ( ε ν f ( G ) ) O(\varepsilon\nu_f(G)) O ( ε ν f ( G )) .
We next construct a random fractional matching on G G G from samples of q ~ \tilde q q ~ . Let each vertex u u u send K K K independent proposals drawn from q ~ u \tilde q_u q ~ u , ignoring dummy outcomes. Each receiver keeps the K K K proposals with smallest IDs, or all its proposals if K K K or fewer arrive. Regard each kept proposal as a separate edge copy in a multigraph and give it weight 1 / ( 2 K ) 1/(2K) 1/ ( 2 K ) . Every vertex has at most K K K kept outgoing copies and K K K kept incoming copies, so these weights always form a fractional matching. Summing the weights of parallel copies gives a random fractional matching on G G G .
We bound the expected loss from discarding proposals at each receiver relative to its accepted mass under q ~ \tilde q q ~ . If receiver v v v has incoming load ℓ = ℓ v ( q ~ ) \ell= \ell_v(\tilde q) ℓ = ℓ v ( q ~ ) and receives N N N proposals, then E N = K ℓ \mathbb{E}N = K\ell E N = K ℓ and
E min { K , N } K ≥ ( 1 − O ( K − 1 / 2 ) ) min { 1 , ℓ } . \frac{\mathbb{E}\min\{K,N\}}{K} \ge(1-O(K^{-1/2}))\min\{1,\ell\}. K E min { K , N } ≥ ( 1 − O ( K − 1/2 )) min { 1 , ℓ } .
Summing over receivers, the expected fractional value is therefore at least ( 1 − O ( K − 1 / 2 ) ) P ( q ~ ) / 2 (1-O(K^{-1/2}))P(\tilde q)/2 ( 1 − O ( K − 1/2 )) P ( q ~ ) /2 . The earlier work-budget bound gives P ( q ~ ) ≥ P ( q ~ b ) − O ( ε ν f ( G ) ) P(\tilde q) \ge P(\tilde q_b)-O(\varepsilon\nu_f(G)) P ( q ~ ) ≥ P ( q ~ b ) − O ( ε ν f ( G )) , and the deterministic optimizer guarantees P ( q ~ b ) / 2 ≥ ( 1 − O ( ε ) ) ν f ( G ) P(\tilde q_b)/2 \ge(1-O(\varepsilon))\nu_f(G) P ( q ~ b ) /2 ≥ ( 1 − O ( ε )) ν f ( G ) . With K = Θ ( ε − 2 ) K=\Theta(\varepsilon^{-2}) K = Θ ( ε − 2 ) , the three losses—from sampling and the receiver cap, aborted sampler runs, and the optimizer’s approximation error—sum to O ( ε ν f ( G ) ) O(\varepsilon\nu_f(G)) O ( ε ν f ( G )) . Thus the resulting random fractional matching has expected value at least ( 1 − O ( ε ) ) ν f ( G ) (1-O(\varepsilon))\nu_f(G) ( 1 − O ( ε )) ν f ( G ) .
For consistency in an LCA implementation, give each proposal ID its own independent random seed. Whenever a query needs that proposal, it reruns the same capped invocation with the same seed. The receiver decisions are determined by the proposal IDs, so all queries access one multigraph of kept proposals, regardless of their order.
Finding the proposals received by a vertex requires examining its neighbors and their K K K proposals. Listing all kept copies incident to the vertex also checks which of its outgoing proposals were kept by their receivers. This takes O ( Δ K 2 ) O(\Delta K^2) O ( Δ K 2 ) capped sampler invocations. The neighborhood exploration occurs outside the recursive sampler and adds only a polynomial overhead in Δ \Delta Δ and 1 / ε 1/\varepsilon 1/ ε . Together with the work budget, this gives the stated ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) worst-case work per local query.
For the rounding in § 9 , we choose K K K to be a power of two, preserving K = Θ ( ε − 2 ) K=\Theta(\varepsilon^{-2}) K = Θ ( ε − 2 ) .
Rounding: integral on bipartite graphs, half-integral in general
The kept proposals define a multigraph H H H , with one edge copy per kept proposal. Its maximum degree is at most D = 2 K D=2K D = 2 K , and each edge copy has weight 1 / D 1/D 1/ D . Recall that K K K was chosen as a power of two, so D D D is also a power of two. In § 9 , we adapt the degree-halving methods of Ahmadi et al. [1 ] , Fischer [25 ] to round this representation with bounded local work. Each step halves the degree bound and doubles the weight of every remaining edge copy.
First consider a bipartite multigraph. At each vertex, pair incident copies in ID order, leaving one unpaired if the degree is odd. These pairings link the copies into paths and even cycles. Keeping the larger of the two alternating classes of copies in each component retains at least half the copies while halving the degree bound. After doubling the remaining weights, each pair contributes the same total weight at its shared endpoint. The halved degree bound ensures that every vertex’s total incident weight remains at most one, including vertices with an unpaired copy. Thus this step preserves feasibility without decreasing the total value.
The paths and cycles may be long, so deciding which class to keep cannot require exploring an entire component. This is addressed by deleting sparsely marked copies to break these components into short pieces. A further local rule deletes copies whose sufficiently large neighborhood along the path or cycle contains no mark. This ensures bounded exploration for every choice of marks. We choose the parameters so that the accumulated expected loss from deletions over the log 2 D = O ( log ( 2 / ε ) ) \log_2 D=O(\log(2/\varepsilon)) log 2 D = O ( log ( 2/ ε )) halving steps is at most an O ( ε ) O(\varepsilon) O ( ε ) fraction of the starting value. The remaining copies then form a matching. The extra factor in worst-case work per query is exp ( O ( log 2 ( 2 / ε ) ) ) \exp(O(\log^2(2/\varepsilon))) exp ( O ( log 2 ( 2/ ε ))) , which is absorbed into our LCA bound.
To handle all graphs with one construction, we apply this rounding to the bipartite double cover of H H H . It has a left and a right copy of each vertex and replaces each edge copy u v uv uv of H H H by two lifted edges, u L v R u_Lv_R u L v R and v L u R v_Lu_R v L u R . Each matched lifted edge contributes weight 1 / 2 1/2 1/2 to its original edge, using the standard double-cover projection [1 Lemma 7] . Each original vertex has two lifts, each incident to at most one matched edge. Thus, after summing contributions from parallel copies, the projected weights are feasible and belong to { 0 , 1 / 2 , 1 } \{0, 1/2, 1\} { 0 , 1/2 , 1 } . The double cover has twice the initial fractional value, and projection divides the rounded value by two, so the relative-loss bound is unchanged.
The two lifts of each edge copy of H H H share the same random mark at every level. Pairings and ties are resolved by ordering lifted copies first by their original IDs, with a side index used only to distinguish the two lifts of the same copy. For bipartite input, the double cover consists of two isomorphic copies of each connected component of H H H . Each original edge ID appears only once in either component copy, so the secondary side indices do not affect the ordering there. The shared marks and corresponding orders therefore give corresponding rounding decisions: each edge copy of H H H has either both lifts in the final matching or neither. Its projected weight is therefore integral. The algorithm gives a matching on bipartite graphs without receiving a bipartition or testing bipartiteness. On general graphs it gives a half-integral fractional matching.
Note that feasibility and consistency hold for every choice of the budget-capped proposal samples and rounding marks. Only the value guarantee is probabilistic. By assigning a sufficiently small constant fraction of the error allowance to each stage, we make the expected deficit from the optimum at most ε ν f ( G ) / 10 \varepsilon\nu_f(G)/10 ε ν f ( G ) /10 . Markov’s inequality then gives a single consistent global output of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) with probability at least 0.9. On bipartite graphs, ν f ( G ) = ν ( G ) \nu_f(G)=\nu(G) ν f ( G ) = ν ( G ) and the output is integral, giving the claimed matching guarantee.
Size estimation: sample the accepted mass.
The size of the matching can be estimated by a black box use of our LCA by uniformly sampling random vertices and querying their total incident matching weight. Multiplying the average by n / 2 n/2 n /2 estimates the value of the LCA’s output, which approximates ν f ( G ) \nu_f(G) ν f ( G ) whenever its value guarantee holds. In § 8 we present an algorithm with a simpler construction, which requires only the budget-capped sampler, with fresh independent randomness in each trial. In particular, it does not require rounding or consistency across queries. The direct approach estimates the expected mass accepted at a uniformly random receiver over the random construction of H H H , using only capped proposal samples from that receiver’s neighbors.
The algorithm is very simple. In one trial, choose a uniformly random receiver v v v and generate K K K capped proposals from each of its neighbors. Let N v N_v N v be the number of these proposals that land at v v v , and return min { K , N v } / K \min\{K,N_v\}/K min { K , N v } / K . The expectation of this quantity, multiplied by n / 2 n/2 n /2 , is the expected value of the random fractional matching constructed above, averaging over the proposal samples. Note that the estimator does not need proposal IDs or decisions about which incoming copies are kept.
We return the average of O ( ε − 2 log ( 2 / ζ ) ) O(\varepsilon^{-2}\log(2/\zeta)) O ( ε − 2 log ( 2/ ζ )) trials. Concentration of independent bounded variables, together with the small expected loss in the fractional construction, gives additive error ε n \varepsilon n ε n with probability at least 1 − ζ 1-\zeta 1 − ζ . The total work remains ( 2 Δ ) O ( 1 / ε ) log ( 2 / ζ ) (2\Delta)^{O(1/\varepsilon)}\log(2/\zeta) ( 2Δ ) O ( 1/ ε ) log ( 2/ ζ ) . This estimates ν f ( G ) \nu_f(G) ν f ( G ) on every graph and ν ( G ) \nu(G) ν ( G ) on bipartite graphs.
The estimator in Theorem 1.2 follows directly: sample vertices uniformly, evaluate their total incident fractional weight using the deterministic oracle, and multiply the average by n / 2 n/2 n /2 . Only the choice of sampled vertices is random.
AI assistance. AI tools contributed to the development of the initial proof and subsequent refinements of the results, as detailed in the AI methodology statement at the end of the paper.
Broader context
Continuous optimization for matching and flows. Closest to our optimization approach, Assadi et al. [4 ] use a box–simplex formulation and area-convex optimization to obtain a deterministic semi-streaming ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximation for bipartite matching in O ( ε − 1 log ( 1 / ε ) log n ) O(\varepsilon^{-1}\log(1/\varepsilon)\log n) O ( ε − 1 log ( 1/ ε ) log n ) passes and O ( n ) O(n) O ( n ) space. Their space bound improves on the earlier linear-programming approach of Ahn and Guha [2 ] .
Our optimizer builds on area convexity, introduced by Sherman [55 ] for box–simplex games and approximate undirected multicommodity flow. Subsequent applications include optimal transport [31 ] , mixed packing and covering [14 ] , and dynamic bipartite matching [32 ] . Cohen et al. [18 ] relate this approach to relative Lipschitzness, and Jambulapati and Tian [30 ] simplify the optimization method by removing the high-accuracy inner loop. Our changes to the formulation and regularizer support local updates and exact recursive sampling; Theorems 3.4 and 4.6 discuss these choices.
Sampling and local simulation. Sampling can provide access to an implicitly represented object without constructing it explicitly. Early examples include reachability sketches [16 ] and sampling methods for finding large dot products [17 ] . Related ideas accelerate approximate matrix multiplication [20 ] and sublinear optimization [15 ] .
Sampling has also been used to simulate iterative local algorithms without exploring their full dependency neighborhoods. Kapralov et al. [33 ] recursively sample a fractional peeling process to estimate matching size from uniform edge samples, and obtain a constant-factor matching LCA using O ( Δ log n ) O(\Delta\log n) O ( Δ log n ) queries. For maximal independent set, Ghaffari [26 ] develops an efficient local simulation of a randomized marking process, obtaining an LCA with poly ( Δ ) log n \operatorname{poly}(\Delta)\log n poly ( Δ ) log n query complexity.
Our sampler also explores the graph adaptively, choosing subsequent probes based on earlier outcomes. Such adaptivity can be essential for efficiency: Azarmehr et al. [5 ] show that non-adaptive LCAs require Δ Ω ( log Δ / log log Δ ) \Delta^{\Omega(\log\Delta/\log\log\Delta)} Δ Ω ( l o g Δ/ l o g l o g Δ ) queries even for constant-factor approximations of maximum matching.
Bernoulli factories. Bernoulli factories provide exact sampling from distributions whose parameters are available only through samples. They have been used to sample exponential-weight distributions in mechanism design and entropy-regularized matching [22 ] , to round fractional points while preserving their marginals [47 ] , and to resample particles whose weights cannot be evaluated explicitly [53 ] .
Here we use factories to implement the smooth update formulas of a deterministic local optimization method. The samplers and coins for each round use an expected constant number of calls to those of the preceding round. This gives exact access to the optimizer’s distributions with 2 O ( T ) 2^{O(T)} 2 O ( T ) expected work after T T T rounds, without numerically evaluating the iterates or accumulating estimation error through the recursion.
Preliminaries
Query and computation model
The input is a finite simple graph G = ( V , E ) G=(V,E) G = ( V , E ) with vertices labeled by [ n ] [n] [ n ] , known n = ∣ V ∣ n=|V| n = ∣ V ∣ , and a known integer Δ ≥ 2 \Delta\ge2 Δ ≥ 2 bounding the maximum degree. A degree query returns deg ( w ) \deg(w) deg ( w ) ; a neighbor query returns the i i i -th neighbor of w w w in a fixed arbitrary order, for 1 ≤ i ≤ deg ( w ) 1\le i\le\deg(w) 1 ≤ i ≤ deg ( w ) . Each costs one graph query. An algorithm may also sample a uniformly random vertex. The query complexity counts only graph queries. For n ≤ 1 n \le1 n ≤ 1 , the answers are trivial.
Computational work. Numerical computations use finite binary representations, with precision chosen as needed. We charge for the bit operations used in arithmetic, comparisons, and numerical evaluations of elementary functions. Each graph query, random-bit draw, and uniform vertex sample costs one unit of work. Operations on vertex identifiers and the known value n n n have unit machine-word cost. In particular, elementary-function evaluations and coins whose biases are specified by formulas are implemented by finite procedures whose numerical work is charged.
The optimizer and sampler are specified by real-valued formulas. Section B gives finite implementations that preserve the stated guarantees and asymptotic work bounds. All work bounds for the final LCAs and estimators refer to these implementations. The final algorithms terminate within their worst-case query and work budgets on every execution. The uncapped sampler of § 6 terminates almost surely and has expected query and work bounds.
For the initial sampler analysis in § 6 and the factory proofs in Section A, we use an auxiliary operation count that charges one unit for each graph query, scalar arithmetic operation, comparison, integer rounding, elementary-function evaluation, and ideal random draw, including a known-bias coin. This is an intermediate measure used in the analysis. The final computational-work bounds use the finite-precision convention above.
Randomness. Randomness is supplied by an oracle. The estimator uses fresh independent randomness. The LCA instead gives each proposal its own random seed, which is reused whenever that proposal is needed (§ 7.3 ). A seed identifies a stream of independent unbiased bits. A proposal is drawn by a recursive procedure that may visit many vertices. All of its coins, at every vertex it visits and in every recursive call, use fresh bits from the proposal’s own stream. The outcome is therefore a deterministic function of its seed, and every query that needs the proposal recomputes the same outcome. Different proposals have independent seeds, and their computations need not agree on the random choices made at vertices they both visit.
Rounding decisions are likewise reproducible: each original proposal copy has an independent seed for its marks across levels, reused by every query. Seeds supply as many bits as needed; we neither bound their length nor charge for their storage or addressing.
Tools
Theorem 2.1 (König [35 ] ; see also Egerváry [24 ] ). In a bipartite graph the maximum size of a matching equals the minimum size of a vertex cover.
A fractional matching of G G G is a vector f ≥ 0 f \ge0 f ≥ 0 on E E E with ∑ e ∋ v f e ≤ 1 \sum_{e \ni v} f_e \le1 ∑ e ∋ v f e ≤ 1 at every vertex v v v , and the fractional matching number ν f ( G ) \nu_f(G) ν f ( G ) is the largest value ∑ e f e \sum_e f_e ∑ e f e . A matching is a fractional matching, so ν f ( G ) ≥ ν ( G ) \nu_f(G) \ge\nu(G) ν f ( G ) ≥ ν ( G ) .
Corollary 2.2. Let G G G be bipartite and let f f f be a fractional matching of G G G . Then ∑ e f e ≤ ν ( G ) \sum_e f_e \le\nu(G) ∑ e f e ≤ ν ( G ) . Hence ν f ( G ) = ν ( G ) \nu_f(G) = \nu(G) ν f ( G ) = ν ( G ) .
Proof. Let C C C be a minimum vertex cover, so ∣ C ∣ = ν ( G ) |C| = \nu(G) ∣ C ∣ = ν ( G ) by Theorem 2.1 . Every edge has an endpoint in C C C , so ∑ e f e ≤ ∑ v ∈ C ∑ e ∋ v f e ≤ ∣ C ∣ \sum_e f_e \le\sum_{v \in C} \sum_{e \ni v} f_e \le|C| ∑ e f e ≤ ∑ v ∈ C ∑ e ∋ v f e ≤ ∣ C ∣ .
The bipartite double cover B ( G ) B(G) B ( G ) of a graph G G G has vertex set V × { 1 , 2 } V \times\{1,2\} V × { 1 , 2 } and, for each edge u v uv uv of G G G , the two edges ( u , 1 ) ( v , 2 ) (u,1)(v,2) ( u , 1 ) ( v , 2 ) and ( v , 1 ) ( u , 2 ) (v,1)(u,2) ( v , 1 ) ( u , 2 ) . It reduces fractional matching in G G G to matching in a bipartite graph.
Lemma 2.3 (Double cover; cf. [1 Lemma 7] and [19 ] ). For every graph G G G :
(a) ν ( B ( G ) ) = 2 ν f ( G ) \nu(B(G)) = 2\nu_f(G) ν ( B ( G )) = 2 ν f ( G ) ;
(b) every matching M M M of B ( G ) B(G) B ( G ) induces the half-integral fractional matching
x u v = 1 2 ( 1 [ ( u , 1 ) ( v , 2 ) ∈ M ] + 1 [ ( v , 1 ) ( u , 2 ) ∈ M ] ) x_{uv} = \frac{1}{2}\bigl(\mathbf{1}[(u,1)(v,2) \in M] + \mathbf{1}[(v,1)(u,2) \in M]\bigr) x uv = 2 1 ( 1 [( u , 1 ) ( v , 2 ) ∈ M ] + 1 [( v , 1 ) ( u , 2 ) ∈ M ] ) of G G G , of value ∣ M ∣ / 2 |M|/2 ∣ M ∣/2 ;
(c) B ( G ) B(G) B ( G ) has 2 n 2n 2 n vertices and maximum degree at most Δ \Delta Δ , and each degree or neighbor query to B ( G ) B(G) B ( G ) is answered by one query to G G G .
Proof. (b) At each vertex u u u of G G G , the copy ( u , 1 ) (u,1) ( u , 1 ) contributes at most 1 2 \frac{1}{2} 2 1 and the copy ( u , 2 ) (u,2) ( u , 2 ) at most 1 2 \frac{1}{2} 2 1 .
(a) A fractional matching f f f of G G G gives the fractional matching of B ( G ) B(G) B ( G ) with weight f u v f_{uv} f uv on both ( u , 1 ) ( v , 2 ) (u,1)(v,2) ( u , 1 ) ( v , 2 ) and ( v , 1 ) ( u , 2 ) (v,1)(u,2) ( v , 1 ) ( u , 2 ) , of value 2 ∑ e f e 2\sum_e f_e 2 ∑ e f e ; since B ( G ) B(G) B ( G ) is bipartite, Theorem 2.2 gives ν ( B ( G ) ) ≥ 2 ν f ( G ) \nu(B(G)) \ge2\nu_f(G) ν ( B ( G )) ≥ 2 ν f ( G ) . Part (b) gives the reverse inequality.
(c) The i i i -th neighbor of ( u , j ) (u,j) ( u , j ) is ( w , 3 − j ) (w,3-j) ( w , 3 − j ) , where w w w is the i i i -th neighbor of u u u .
Lemma 2.4 (Nonisolated vertices). If G G G has n 0 n_0 n 0 nonisolated vertices and maximum degree at most Δ \Delta Δ , then
n 0 ≤ 2 Δ ν f ( G ) , ∣ E ∣ ≤ 2 Δ ν f ( G ) . n_0 \le2\Delta\nu_f(G), \qquad|E| \le2\Delta\nu_f(G). n 0 ≤ 2Δ ν f ( G ) , ∣ E ∣ ≤ 2Δ ν f ( G ) .
Proof. The endpoints of a maximal matching form a vertex cover. Every nonisolated vertex has a neighbor in this cover, and every edge meets it. The sum of the degrees of the cover vertices is at most 2 Δ 2\Delta 2Δ times the matching size, which is at most 2 Δ ν f ( G ) 2\Delta\nu_f(G) 2Δ ν f ( G ) .
Theorem 2.5 (Bounded differences; McDiarmid [41 ] ). Let Y 1 , … , Y m Y_1,\ldots,Y_m Y 1 , … , Y m be independent and W = f ( Y 1 , … , Y m ) W=f(Y_1,\ldots,Y_m) W = f ( Y 1 , … , Y m ) , where changing only Y i Y_i Y i changes f f f by at most c i c_i c i . If V = ∑ i c i 2 > 0 V=\sum_i c_i^2>0 V = ∑ i c i 2 > 0 , then for every t > 0 t>0 t > 0 ,
P { W − E W ≥ t } ≤ e − 2 t 2 / V , P { W − E W ≤ − t } ≤ e − 2 t 2 / V . \mathbb{P}\{W-\mathbb{E}W \ge t\} \le e^{-2t^2/V}, \qquad\mathbb{P}\{W-\mathbb{E}W \le-t\} \le e^{-2t^2/V}. P { W − E W ≥ t } ≤ e − 2 t 2 / V , P { W − E W ≤ − t } ≤ e − 2 t 2 / V . In particular (Hoeffding’s inequality [27 ] ), independent Z 1 , … , Z m ∈ [ 0 , 1 ] Z_1,\ldots,Z_m \in[0,1] Z 1 , … , Z m ∈ [ 0 , 1 ] satisfy
P { ∣ 1 m ∑ i ( Z i − E Z i ) ∣ > a } ≤ 2 e − 2 m a 2 . \mathbb{P}\left\{\left|\frac{1}{m}\sum_i(Z_i-\mathbb{E}Z_i)\right|>a\right\} \le2e^{-2ma^2}. P { m 1 i ∑ ( Z i − E Z i ) > a } ≤ 2 e − 2 m a 2 .
Matching as a saddle-point problem
We formulate fractional matching as a min–max problem with two sets of variables: proposal distributions q q q , which maximize an objective F ( x , q ) F(x,q) F ( x , q ) , and prices x x x , which minimize it. The objective is affine in either set of variables when the other is fixed. A solution is a saddle point ( x ∗ , q ∗ ) (x^*,q^*) ( x ∗ , q ∗ ) , satisfying
F ( x ∗ , q ) ≤ F ( x ∗ , q ∗ ) ≤ F ( x , q ∗ ) F(x^*,q) \le F(x^*,q^*) \le F(x,q^*) F ( x ∗ , q ) ≤ F ( x ∗ , q ∗ ) ≤ F ( x , q ∗ )
for every feasible x , q x,q x , q .
Thus, with prices fixed at x ∗ x^* x ∗ , no change to the proposal distributions can increase the objective; with these distributions fixed at q ∗ q^* q ∗ , no change to the prices can decrease it.
Variables. For each vertex u u u , let I u = N ( u ) ∪ { ⊥ u } I_u = N(u) \cup\{\bot_u\} I u = N ( u ) ∪ { ⊥ u } , where ⊥ u \bot_u ⊥ u is a private dummy target. Every vertex u u u holds two variables:
a proposal distribution q u = ( q u a ) a ∈ I u q_u = (q_{ua})_{a\in I_u} q u = ( q u a ) a ∈ I u , a probability vector on I u I_u I u : vertex u u u puts mass q u v q_{uv} q uv on each neighbor v v v and the remaining mass q u ⊥ q_{u\bot} q u ⊥ on its dummy;
a price x u ∈ [ − 1 , 1 ] x_u \in[-1,1] x u ∈ [ − 1 , 1 ] , associated with the proposal mass that u u u receives.
Terminology wise, we will refer to a draw from a proposal distribution q u q_u q u (a neighbor of u u u or the dummy) as a proposal . Note that the coordinates q u v q_{uv} q uv and q v u q_{vu} q v u are distinct, representing proposal mass sent in opposite directions.
Let I = { ( u , a ) : u ∈ V , a ∈ I u } I = \{(u,a) : u \in V,\ a \in I_u\} I = {( u , a ) : u ∈ V , a ∈ I u } . Combining the proposal distributions of vertices gives a vector q ∈ R I q \in\mathbb{R}^{I} q ∈ R I , and combining the prices gives a vector x ∈ R V x \in\mathbb{R}^{V} x ∈ R V . Their feasible sets are
Q = { q ∈ R ≥ 0 I : ∑ a ∈ I u q u a = 1 for every u ∈ V } , X = [ − 1 , 1 ] V . Q = \left\{q \in\mathbb{R}_{\ge0}^{I} : \sum_{a\in I_u} q_{ua} = 1\text{ for every }u \in V\right\}, \qquad X = [-1,1]^{V}. Q = { q ∈ R ≥ 0 I : a ∈ I u ∑ q u a = 1 for every u ∈ V } , X = [ − 1 , 1 ] V .
Thus, Q Q Q is a product of simplices, one for each vertex. We write Z = X × Q Z = X \times Q Z = X × Q for the joint feasible set.
Loads and accepted mass. The load of v v v is the total proposal mass it receives,
ℓ v ( q ) = ∑ u ∈ N ( v ) q u v . (1) \ell_v(q) = \sum_{u\in N(v)} q_{uv}. \tag*{(1)} ℓ v ( q ) = u ∈ N ( v ) ∑ q uv . (1)
Each vertex can accept at most one unit, so the total accepted mass is the sum of the loads capped at one,
P ( q ) = ∑ v ∈ V min { 1 , ℓ v ( q ) } . P(q) = \sum_{v\in V} \min\{1,\ell_v(q)\}. P ( q ) = v ∈ V ∑ min { 1 , ℓ v ( q )} .
If f f f is a fractional matching and every vertex u u u assigns mass f u v f_{uv} f uv to each neighbor v v v , with the rest on its dummy, then every load is at most one and P ( q ) = 2 ∑ e f e P(q) = 2\sum_e f_e P ( q ) = 2 ∑ e f e , because each edge’s weight is counted once from each endpoint. Hence the largest accepted mass is at least 2 ν f ( G ) 2\nu_f(G) 2 ν f ( G ) . Theorem 3.1 shows that it is exactly 2 ν f ( G ) 2\nu_f(G) 2 ν f ( G ) .
Prices. Our goal is to maximize the accepted mass P ( q ) P(q) P ( q ) . We introduce prices to express this optimization as a saddle-point problem to which we can apply the area-convex method of § 4 –§ 5 [30 , 55 ] . § 6 then samples the resulting proposal distributions locally. For a load ℓ \ell ℓ , the capped load min { 1 , ℓ } \min\{1,\ell\} min { 1 , ℓ } is concave and nonsmooth. The following identity expresses it, up to scaling and an additive constant, as the minimum of affine functions:
2 min { 1 , ℓ } − 1 = min x ∈ [ − 1 , 1 ] [ x + ℓ ( 1 − x ) ] . (2) 2\min\{1,\ell\} - 1 = \min_{x\in[-1,1]} \left[x + \ell(1-x)\right]. \tag*{(2)} 2 min { 1 , ℓ } − 1 = x ∈ [ − 1 , 1 ] min [ x + ℓ ( 1 − x ) ] . (2)
The minimizing price is + 1 +1 + 1 when the vertex is overloaded (ℓ > 1 \ell> 1 ℓ > 1 ) and − 1 -1 − 1 when it is underloaded (ℓ < 1 \ell< 1 ℓ < 1 ); when ℓ = 1 \ell= 1 ℓ = 1 , every price in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] is a minimizer.
The objective. Applying (2) at every vertex v v v , with load ℓ v ( q ) \ell_v(q) ℓ v ( q ) and price x v x_v x v , gives
F ( x , q ) = ∑ v ∈ V [ x v + ℓ v ( q ) ( 1 − x v ) ] (3) F(x,q)=\sum_{v\in V}\left[x_v+\ell_v(q)(1-x_v)\right] \tag*{(3)} F ( x , q ) = v ∈ V ∑ [ x v + ℓ v ( q ) ( 1 − x v ) ] (3)
Thus, min x ∈ X F ( x , q ) = 2 P ( q ) − n \min_{x\in X} F(x,q)=2P(q)-n min x ∈ X F ( x , q ) = 2 P ( q ) − n . Maximizing this quantity over the proposal distributions is equivalent to maximizing the accepted mass, so our target is
max q ∈ Q min x ∈ X F ( x , q ) = 2 max q ∈ Q P ( q ) − n = 4 ν f ( G ) − n . \max_{q\in Q}\min_{x\in X}F(x,q)=2\max_{q\in Q}P(q)-n=4\nu_f(G)-n. q ∈ Q max x ∈ X min F ( x , q ) = 2 q ∈ Q max P ( q ) − n = 4 ν f ( G ) − n .
The following lemma verifies this value and shows that the minimum and maximum can also be interchanged.
Lemma 3.1 (Saddle-point value). For every graph G G G :
(a) P ( q ) ≤ 2 ν f ( G ) P(q)\le2\nu_f(G) P ( q ) ≤ 2 ν f ( G ) for every q ∈ Q q\in Q q ∈ Q .
(b) min x ∈ X F ( x , q ) = 2 P ( q ) − n \min_{x\in X}F(x,q)=2P(q)-n min x ∈ X F ( x , q ) = 2 P ( q ) − n for every q ∈ Q q\in Q q ∈ Q .
(c) There is q ∗ ∈ Q q^*\in Q q ∗ ∈ Q with F ( x , q ∗ ) ≥ 4 ν f ( G ) − n F(x,q^*)\ge4\nu_f(G)-n F ( x , q ∗ ) ≥ 4 ν f ( G ) − n for every x ∈ X x\in X x ∈ X , in which each vertex puts all of its mass on a single neighbor or on its dummy.
(d)
min x ∈ X max q ∈ Q F ( x , q ) = max q ∈ Q min x ∈ X F ( x , q ) = 4 ν f ( G ) − n . \min_{x\in X}\max_{q\in Q}F(x,q)=\max_{q\in Q}\min_{x\in X}F(x,q)=4\nu_f(G)-n. x ∈ X min q ∈ Q max F ( x , q ) = q ∈ Q max x ∈ X min F ( x , q ) = 4 ν f ( G ) − n .
Proof. (a) For each ordered pair with u v ∈ E uv\in E uv ∈ E put f u v = q u v / max { 1 , ℓ v ( q ) } f_{uv}=q_{uv}/\max\{1,\ell_v(q)\} f uv = q uv / max { 1 , ℓ v ( q )} . Then ∑ u f u v = min { 1 , ℓ v ( q ) } ≤ 1 \sum_u f_{uv}=\min\{1,\ell_v(q)\}\le1 ∑ u f uv = min { 1 , ℓ v ( q )} ≤ 1 and ∑ v f u v ≤ ∑ v q u v ≤ 1 \sum_v f_{uv}\le\sum_v q_{uv}\le1 ∑ v f uv ≤ ∑ v q uv ≤ 1 . The symmetric weights w { u , v } = ( f u v + f v u ) / 2 w_{\{u,v\}}=(f_{uv}+f_{vu})/2 w { u , v } = ( f uv + f v u ) /2 therefore form a fractional matching of G G G , of total weight 1 2 ∑ f = P ( q ) / 2 \frac{1}{2}\sum f=P(q)/2 2 1 ∑ f = P ( q ) /2 . Hence P ( q ) / 2 ≤ ν f ( G ) P(q)/2\le\nu_f(G) P ( q ) /2 ≤ ν f ( G ) .
(b) Apply (2) at each vertex; the coordinates of x x x separate.
(c) Fix a maximum matching M ∗ M^* M ∗ of B ( G ) B(G) B ( G ) , so ∣ M ∗ ∣ = 2 ν f |M^*|=2\nu_f ∣ M ∗ ∣ = 2 ν f by Theorem 2.3(a). Let u u u put unit mass on v v v if ( u , 1 ) ( v , 2 ) ∈ M ∗ (u,1)(v,2)\in M^* ( u , 1 ) ( v , 2 ) ∈ M ∗ , and on its dummy if ( u , 1 ) (u,1) ( u , 1 ) is unmatched. Then ℓ v ( q ∗ ) = 1 \ell_v(q^*)=1 ℓ v ( q ∗ ) = 1 if ( v , 2 ) (v,2) ( v , 2 ) is matched and 0 0 0 otherwise, so ℓ v ( q ∗ ) = 1 \ell_v(q^*)=1 ℓ v ( q ∗ ) = 1 at exactly 2 ν f 2\nu_f 2 ν f vertices and
F ( x , q ∗ ) = 2 ν f + ∑ v : ℓ v ( q ∗ ) = 0 x v ≥ 2 ν f − ( n − 2 ν f ) . F(x,q^*)=2\nu_f+\sum_{v:\ell_v(q^*)=0}x_v\ge2\nu_f-(n-2\nu_f). F ( x , q ∗ ) = 2 ν f + v : ℓ v ( q ∗ ) = 0 ∑ x v ≥ 2 ν f − ( n − 2 ν f ) .
For bipartite G G G one can choose M ∗ M^* M ∗ to consist of both copies of each edge of a maximum matching of G G G ; then each matched vertex assigns unit mass to its partner.
(d) Parts (a)–(c) give max q ∈ Q min x ∈ X F ( x , q ) = 4 ν f − n \max_{q\in Q}\min_{x\in X}F(x,q)=4\nu_f-n max q ∈ Q min x ∈ X F ( x , q ) = 4 ν f − n . Moreover, F ( x , q ∗ ) ≥ 4 ν f − n F(x,q^*)\ge4\nu_f-n F ( x , q ∗ ) ≥ 4 ν f − n for every x x x , so min x ∈ X max q ∈ Q F ( x , q ) ≥ 4 ν f − n \min_{x\in X}\max_{q\in Q}F(x,q)\ge4\nu_f-n min x ∈ X max q ∈ Q F ( x , q ) ≥ 4 ν f − n .
For the reverse inequality, let C C C be a minimum vertex cover of B ( G ) B(G) B ( G ) , and write C L = { u : ( u , 1 ) ∈ C } C_L=\{u:(u,1)\in C\} C L = { u : ( u , 1 ) ∈ C } and C R = { v : ( v , 2 ) ∈ C } C_R=\{v:(v,2)\in C\} C R = { v : ( v , 2 ) ∈ C } . Set x v = 1 x_v=1 x v = 1 for v ∈ C R v\in C_R v ∈ C R and x v = − 1 x_v=-1 x v = − 1 otherwise. If u ∉ C L u\notin C_L u ∈ / C L , all its neighbors belong to C R C_R C R , so its proposal mass contributes zero to ∑ u , v q u v ( 1 − x v ) \sum_{u,v}q_{uv}(1-x_v) ∑ u , v q uv ( 1 − x v ) . Each u ∈ C L u\in C_L u ∈ C L contributes at most two. Thus, for every q ∈ Q q\in Q q ∈ Q ,
F ( x , q ) ≤ 2 ∣ C R ∣ − n + 2 ∣ C L ∣ = 2 ∣ C ∣ − n = 4 ν f − n . F(x,q)\le2|C_R|-n+2|C_L|=2|C|-n=4\nu_f-n. F ( x , q ) ≤ 2∣ C R ∣ − n + 2∣ C L ∣ = 2∣ C ∣ − n = 4 ν f − n .
Remark 3.2 (The double cover). Each real coordinate q u v q_{uv} q uv corresponds to the edge ( u , 1 ) ( v , 2 ) (u,1)(v,2) ( u , 1 ) ( v , 2 ) of the double cover B ( G ) B(G) B ( G ) . The proposal distributions enforce the capacities on the proposer side V × { 1 } V\times\{1\} V × { 1 } , while the prices represent the capacity constraints on the receiver side V × { 2 } V\times\{2\} V × { 2 } .
Remark 3.3 (Optimization over prices). For fixed prices, the term ∑ v x v \sum_v x_v ∑ v x v in F ( x , q ) F(x,q) F ( x , q ) is constant. Each unit of proposal mass sent to a neighbor v v v contributes 1 − x v 1-x_v 1 − x v to the objective, whereas mass sent to the dummy contributes zero. Thus, u u u can maximize its contribution by assigning all its mass to the lowest-priced options, treating the dummy as an option of price 1 1 1 .
Maximizing independently at each vertex gives a convex, generally nonsmooth function of the prices alone,
F ‾ ( x ) = max q ∈ Q F ( x , q ) = ∑ v ∈ V x v + ∑ u ∈ V max { 0 , max v ∈ N ( u ) ( 1 − x v ) } . (4) \overline{F}(x) = \max_{q\in Q} F(x,q) = \sum_{v\in V} x_v + \sum_{u\in V} \max\left\{0,\ \max_{v\in N(u)}(1-x_v)\right\}. \tag*{(4)} F ( x ) = q ∈ Q max F ( x , q ) = v ∈ V ∑ x v + u ∈ V ∑ max { 0 , v ∈ N ( u ) max ( 1 − x v ) } . (4)
To interpret this function, set λ v = ( 1 + x v ) / 2 \lambda_v=(1+x_v)/2 λ v = ( 1 + x v ) /2 . These are the nonnegative Lagrange multipliers for the receiver-capacity constraints ℓ v ( q ) ≤ 1 \ell_v(q)\le1 ℓ v ( q ) ≤ 1 . If the receiver copy ( v , 2 ) (v,2) ( v , 2 ) has cover weight λ v \lambda_v λ v , the least feasible weight on the proposer copy ( u , 1 ) (u,1) ( u , 1 ) is max { 0 , max v ∈ N ( u ) ( 1 − λ v ) } \max\{0,\max_{v\in N(u)}(1-\lambda_v)\} max { 0 , max v ∈ N ( u ) ( 1 − λ v )} . Hence ( F ‾ ( x ) + n ) / 2 (\overline{F}(x)+n)/2 ( F ( x ) + n ) /2 is the cost of the cheapest fractional vertex cover of B ( G ) B(G) B ( G ) with these receiver weights. Minimizing F ‾ \overline{F} F over X X X therefore solves the fractional vertex cover problem on B ( G ) B(G) B ( G ) .
An area-convex regularizer
We now develop the ingredients of an optimization step that updates a state that comprises prices x x x and proposal distributions q q q . The update directions aim to decrease F F F in the prices and increase it in the proposal distributions. To control the movement from the current state, we use a convex scalar-valued function called a regularizer . Its associated Bregman divergence , defined below, provides the penalty for changing the state. We then derive an explicit formula for the regularized price update. In § 5 , we combine this price update with multiplicative updates of the proposal distributions to obtain the full iterative method.
We choose the regularizer to satisfy two requirements. First, we require area convexity , which controls the interaction between price and distribution updates and allows us to apply the extragradient methods of Jambulapati and Tian [30 ] , Sherman [55 ] . In § 5 , these give an O ( δ − 1 log ( 2 Δ ) ) O(\delta^{-1}\log(2\Delta)) O ( δ − 1 log ( 2Δ )) iteration bound for accepted-mass error δ v f ( G ) \delta v_f(G) δ v f ( G ) . The initialization is chosen so that the potential is proportional to the optimum, which gives this multiplicative guarantee. Second, we require explicit price-update formulas with uniform bounds that support exact simulation from samples in § 6 . We next fix the notation, and then define our regularizer and establish these two properties.
Optimization notation
We use the standard Euclidean inner products on R V \mathbb{R}^{V} R V and R I \mathbb{R}^{I} R I . On pairs, the inner product is the sum of those on the two components:
⟨ ( x , p ) , ( y , h ) ⟩ = ⟨ x , y ⟩ + ⟨ p , h ⟩ . \langle(x,p),(y,h)\rangle= \langle x,y\rangle+ \langle p,h\rangle. ⟨( x , p ) , ( y , h )⟩ = ⟨ x , y ⟩ + ⟨ p , h ⟩ .
Gradients are taken with respect to these inner products. We write 1 ∈ R V \mathbf{1}\in\mathbb{R}^{V} 1 ∈ R V for the vector with every coordinate equal to one. Products and division of vectors are coordinatewise; for example, ( x / y ) v = x v / y v (x/y)_v = x_v/y_v ( x / y ) v = x v / y v and ( q q ˉ ) u a = q u a q ˉ u a (q\bar q)_{ua} = q_{ua}\bar q_{ua} ( q q ˉ ) u a = q u a q ˉ u a . Powers, logarithms and exponentials are also applied coordinatewise.
The load map. The load map L : R I → R V L : \mathbb{R}^{I} \to\mathbb{R}^{V} L : R I → R V sums the proposal mass arriving at each vertex:
( L q ) v = ℓ v ( q ) = ∑ u ∈ N ( v ) q u v . (Lq)_v = \ell_v(q) = \sum_{u \in N(v)} q_{uv}. ( L q ) v = ℓ v ( q ) = u ∈ N ( v ) ∑ q uv .
As a matrix, L L L has a row for each vertex v v v and a column for each pair ( u , a ) ∈ I (u,a) \in I ( u , a ) ∈ I , with entry one when a = v a=v a = v and zero otherwise. Its transpose, also called its adjoint , L ∗ : R V → R I L^* : \mathbb{R}^{V} \to\mathbb{R}^{I} L ∗ : R V → R I , copies each vertex’s price to the coordinates that send mass to it: ( L ∗ x ) u v = x v (L^*x)_{uv} = x_v ( L ∗ x ) uv = x v for v ∈ N ( u ) v \in N(u) v ∈ N ( u ) , and ( L ∗ x ) u ⊥ = 0 (L^*x)_{u\perp} = 0 ( L ∗ x ) u ⊥ = 0 . Thus,
⟨ L q , x ⟩ = ⟨ q , L ∗ x ⟩ = ∑ u ∈ V ∑ v ∈ N ( u ) q u v x v . \langle Lq,x\rangle= \langle q,L^*x\rangle= \sum_{u \in V} \sum_{v \in N(u)} q_{uv}x_v. ⟨ L q , x ⟩ = ⟨ q , L ∗ x ⟩ = u ∈ V ∑ v ∈ N ( u ) ∑ q uv x v .
Let b = L ∗ 1 b = L^*1 b = L ∗ 1 , the indicator of the non-dummy coordinates. Then the objective can be written as
F ( x , q ) = ⟨ 1 , x ⟩ + ⟨ b − L ∗ x , q ⟩ . (5) F(x,q) = \langle1,x\rangle+ \langle b-L^*x,q\rangle. \tag*{(5)} F ( x , q ) = ⟨ 1 , x ⟩ + ⟨ b − L ∗ x , q ⟩ . (5)
This is a box–simplex game in the sense of Jambulapati and Tian [30 ] , with a product of simplices in place of a single simplex; Theorem 3.4 compares this casting with that of Assadi et al. [4 ] .
Gradients and the optimality gap. The descent–ascent operator stacks the gradient of F F F in the prices and minus its gradient in the proposal distributions:
g ( x , q ) = ( ∇ x F , − ∇ q F ) = ( 1 − L q , L ∗ x − b ) . (6) g(x,q) = (\nabla_x F,-\nabla_q F) = (1-Lq,L^*x-b). \tag*{(6)} g ( x , q ) = ( ∇ x F , − ∇ q F ) = ( 1 − L q , L ∗ x − b ) . (6)
The signs encode descent in the prices and ascent in the proposal distributions. Price descent lowers the prices of underloaded vertices and raises those of overloaded vertices, while distribution ascent favors cheaper neighbors.
For z = ( x , q ) z=(x,q) z = ( x , q ) and a comparison point w = ( y , h ) w=(y,h) w = ( y , h ) in Z Z Z , expanding (5) and using adjointness gives
⟨ g ( z ) , z − w ⟩ = F ( x , h ) − F ( y , q ) . (7) \langle g(z),z-w\rangle= F(x,h)-F(y,q). \tag*{(7)} ⟨ g ( z ) , z − w ⟩ = F ( x , h ) − F ( y , q ) . (7)
Maximizing over w = ( y , h ) ∈ Z w=(y,h)\in Z w = ( y , h ) ∈ Z gives the saddle-point gap
max h ∈ Q F ( x , h ) − min y ∈ X F ( y , q ) . \max_{h \in Q} F(x,h) - \min_{y \in X} F(y,q). h ∈ Q max F ( x , h ) − y ∈ X min F ( y , q ) .
This is the sum of the improvement available by changing the proposal distributions alone and the improvement available by changing the prices alone. It is nonnegative and vanishes exactly at a saddle point. The analysis in § 5 bounds the sum of the inner products in (7) over iterations by changes in a potential, which telescope.
The regularizer
We choose a regularizer R α R_\alpha R α . We use the negative entropy
H ( q ) = ∑ ( u , a ) ∈ I q u a log q u a , H(q) = \sum_{(u,a) \in I} q_{ua}\log q_{ua}, H ( q ) = ( u , a ) ∈ I ∑ q u a log q u a ,
with natural logarithms and the convention 0 log 0 = 0 0 \log0 = 0 0 log 0 = 0 . For the prices, use shifted negative binary entropy:
ψ ( x ) = ( 1 + x ) log ( 1 + x ) + ( 1 − x ) log ( 1 − x ) 2 , − 1 ≤ x ≤ 1. (8) \psi(x) = \frac{(1+x)\log(1+x)+(1-x)\log(1-x)}{2}, \qquad-1 \le x \le1. \tag*{(8)} ψ ( x ) = 2 ( 1 + x ) log ( 1 + x ) + ( 1 − x ) log ( 1 − x ) , − 1 ≤ x ≤ 1. (8)
Thus ψ ( 0 ) = 0 \psi(0)=0 ψ ( 0 ) = 0 , ψ ( ± 1 ) = log 2 \psi(\pm1)=\log2 ψ ( ± 1 ) = log 2 , and, in the interior,
ψ ′ ( x ) = atanh x = 1 2 log 1 + x 1 − x , ψ ′ ′ ( x ) = 1 1 − x 2 . \psi'(x)=\operatorname{atanh}x=\frac{1}{2}\log\frac{1+x}{1-x}, \qquad\psi''(x)=\frac{1}{1-x^2}. ψ ′ ( x ) = atanh x = 2 1 log 1 − x 1 + x , ψ ′′ ( x ) = 1 − x 2 1 .
For α > 0 \alpha>0 α > 0 , define R α : Z → R R_\alpha: Z \to\mathbb{R} R α : Z → R by
R α ( x , q ) = 2 ∑ v ( 1 + ℓ v ( q ) ) ψ ( x v ) + α H ( q ) . R_\alpha(x,q)=2\sum_v(1+\ell_v(q))\psi(x_v)+\alpha H(q). R α ( x , q ) = 2 v ∑ ( 1 + ℓ v ( q )) ψ ( x v ) + α H ( q ) .
The entropy term leads to multiplicative updates of proposal probabilities: probabilities are reweighted and then normalized at each vertex. The first term couples each price to its incoming load. Its curvature in x v x_v x v is larger when the load is larger and as x v x_v x v approaches either endpoint of [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . The choice of ψ \psi ψ also gives the smooth price response derived in § 4.4 .
The update penalty. Let Q ∘ Q^\circ Q ∘ denote the relative interior of Q Q Q : all proposal probabilities are positive, including those of the dummies. For an interior base z = ( x , q ) ∈ ( − 1 , 1 ) V × Q ∘ z=(x,q)\in(-1,1)^V\times Q^\circ z = ( x , q ) ∈ ( − 1 , 1 ) V × Q ∘ and w ∈ Z w\in Z w ∈ Z , the Bregman divergence generated by R α R_\alpha R α is
D z α ( w ) = R α ( w ) − R α ( z ) − ⟨ ∇ R α ( z ) , w − z ⟩ . D^\alpha_z(w)=R_\alpha(w)-R_\alpha(z)-\langle\nabla R_\alpha(z),w-z\rangle. D z α ( w ) = R α ( w ) − R α ( z ) − ⟨ ∇ R α ( z ) , w − z ⟩ .
It measures how far R α ( w ) R_\alpha(w) R α ( w ) lies above the tangent plane at z z z . For the choices α ≥ 10 \alpha\ge10 α ≥ 10 used below, Theorem 4.3 establishes convexity, so D z α ( w ) ≥ 0 D^\alpha_z(w)\ge0 D z α ( w ) ≥ 0 , with equality when w = z w=z w = z . For comparison, the regularizer R ( z ) = 1 2 ∥ z ∥ 2 R(z)=\frac{1}{2}\lVert z\rVert^2 R ( z ) = 2 1 ∥ z ∥ 2 gives the squared-distance penalty D z ( w ) = 1 2 ∥ w − z ∥ 2 D_z(w)=\frac{1}{2}\lVert w-z\rVert^2 D z ( w ) = 2 1 ∥ w − z ∥ 2 used in ordinary gradient descent.
The Bregman divergence generated by H H H is the relative entropy
K p ( h ) = ∑ ( u , a ) ∈ I h u a log h u a p u a ( p ∈ Q ∘ , h ∈ Q ) , K_p(h)=\sum_{(u,a)\in I}h_{ua}\log\frac{h_{ua}}{p_{ua}}\qquad(p\in Q^\circ,\ h\in Q), K p ( h ) = ( u , a ) ∈ I ∑ h u a log p u a h u a ( p ∈ Q ∘ , h ∈ Q ) ,
where a term with h u a = 0 h_{ua}=0 h u a = 0 is zero. This is the sum of the per-vertex Kullback–Leibler (KL) divergences; it is nonnegative and vanishes exactly when h = p h=p h = p . Thus, the entropy contribution to D z α ( y , h ) D^\alpha_z(y,h) D z α ( y , h ) is α K q ( h ) \alpha K_q(h) α K q ( h ) , which measures changes in the proposal distributions relative to their current probabilities. In particular, for β ≥ 0 \beta\ge0 β ≥ 0 ,
D z α + β ( w ) = D z α ( w ) + β K q ( w q ) , D^{\alpha+\beta}_z(w)=D^\alpha_z(w)+\beta K_q(w^q), D z α + β ( w ) = D z α ( w ) + β K q ( w q ) ,
where w q w^q w q is the Q Q Q -component of w w w .
The update subproblems are built from expressions of the form
⟨ v , w − z ⟩ ⏟ descent–ascent term + D z α ( w ) ⏟ penalty for changing the state , (9) \underbrace{\langle v,w-z\rangle}_{\text{descent--ascent term}}
+
\underbrace{D^\alpha_z(w)}_{\text{penalty for changing the state}}, \tag*{(9)} descent–ascent term ⟨ v , w − z ⟩ + penalty for changing the state D z α ( w ) , (9)
where v v v is a scaled descent–ascent vector, such as η g ( z ) \eta g(z) η g ( z ) . The method of § 5 handles these subproblems with a fixed number of price responses and multiplicative distribution updates. The price response for fixed distribution is derived in § 4.4 .
Differentiation gives
∇ x R α = 2 ( 1 + L q ) atanh x , ∇ q R α = 2 L ∗ ψ ( x ) + α ( 1 + log q ) . (10) \nabla_xR_\alpha=2(1+Lq)\operatorname{atanh}x,\qquad\nabla_qR_\alpha=2L^*\psi(x)+\alpha(1+\log q). \tag*{(10)} ∇ x R α = 2 ( 1 + L q ) atanh x , ∇ q R α = 2 L ∗ ψ ( x ) + α ( 1 + log q ) . (10)
Area convexity
Area convexity relates the curvature of the regularizer to the bilinear coupling in F F F . The form we will use in the convergence proof is (11) : it bounds the interaction of two updates by their divergences from a common base.
Definition 4.1 (Area convexity [55 ] ). A continuous convex R R R on Z Z Z is η \eta η -area convex for g g g if, for all z , z ′ , z + ∈ Z z,z',z^+ \in Z z , z ′ , z + ∈ Z with centroid c = ( z + z ′ + z + ) / 3 c = (z + z' + z^+)/3 c = ( z + z ′ + z + ) /3 ,
η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ ≤ R ( z ) + R ( z ′ ) + R ( z + ) − 3 R ( c ) . \eta\langle g(z') - g(z), z' - z^+ \rangle\le R(z) + R(z') + R(z^+) - 3R(c). η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ ≤ R ( z ) + R ( z ′ ) + R ( z + ) − 3 R ( c ) .
Lemma 4.2 (Scalar area inequality; cf. [30 Lemma 1] and [31 Lemma 4] ). Let r 8 ( x , q ) = q x 2 + 8 q log q r_8(x,q) = qx^2 + 8q\log q r 8 ( x , q ) = q x 2 + 8 q log q for ∣ x ∣ ≤ 1 |x| \le1 ∣ x ∣ ≤ 1 , q ≥ 0 q \ge0 q ≥ 0 . Then r 8 r_8 r 8 is convex, and for any three points ( x i , q i ) (x_i,q_i) ( x i , q i ) with centroid ( x ˉ , q ˉ ) (\bar{x},\bar{q}) ( x ˉ , q ˉ ) ,
∑ i = 1 3 r 8 ( x i , q i ) − 3 r 8 ( x ˉ , q ˉ ) ≥ 1 3 ∣ ( x 2 − x 1 ) ( q 3 − q 1 ) − ( q 2 − q 1 ) ( x 3 − x 1 ) ∣ . \sum_{i=1}^{3} r_8(x_i,q_i) - 3r_8(\bar{x},\bar{q}) \ge\frac{1}{3}\left|(x_2-x_1)(q_3-q_1)-(q_2-q_1)(x_3-x_1)\right|. i = 1 ∑ 3 r 8 ( x i , q i ) − 3 r 8 ( x ˉ , q ˉ ) ≥ 3 1 ∣ ( x 2 − x 1 ) ( q 3 − q 1 ) − ( q 2 − q 1 ) ( x 3 − x 1 ) ∣ .
Proof. Assume first q i > 0 q_i > 0 q i > 0 . Let r 4 ( x , q ) = q x 2 + 4 q log q r_4(x,q) = qx^2 + 4q\log q r 4 ( x , q ) = q x 2 + 4 q log q . In a direction ( a , b ) (a,b) ( a , b ) its Hessian gives
2 q a 2 + 4 x a b + 4 b 2 / q ≥ q a 2 , 2qa^2 + 4xab + 4b^2/q \ge qa^2, 2 q a 2 + 4 x ab + 4 b 2 / q ≥ q a 2 ,
because the difference is
( q a + 2 x b / q ) 2 + 4 ( 1 − x 2 ) b 2 / q ≥ 0. (\sqrt{q}a + 2xb/\sqrt{q})^2 + 4(1-x^2)b^2/q \ge0. ( q a + 2 x b / q ) 2 + 4 ( 1 − x 2 ) b 2 / q ≥ 0.
So r 4 r_4 r 4 and r 8 = r 4 + 4 q log q r_8 = r_4 + 4q\log q r 8 = r 4 + 4 q log q are convex.
Write a i = x i − x ˉ a_i = x_i - \bar{x} a i = x i − x ˉ , b i = q i − q ˉ b_i = q_i - \bar{q} b i = q i − q ˉ . Since the a i a_i a i and b i b_i b i sum to zero, the left side of the claimed inequality equals the sum of the Bregman divergences of r 8 r_8 r 8 from the centroid to the three points. Along the segment from the centroid to point i i i , Taylor’s formula and the Hessian bound give a divergence of r 4 r_4 r 4 of at least
a i 2 ∫ 0 1 ( 1 − t ) ( ( 1 − t ) q ˉ + t q i ) d t ≥ q ˉ a i 2 / 3. a_i^2\int_0^1 (1-t)((1-t)\bar{q}+tq_i)\,dt \ge\bar{q}a_i^2/3. a i 2 ∫ 0 1 ( 1 − t ) (( 1 − t ) q ˉ + t q i ) d t ≥ q ˉ a i 2 /3.
For q log q q\log q q log q , the second derivative 1 / q 1/q 1/ q and q ≤ max ( q i , q ˉ ) ≤ 3 q ˉ q \le\max(q_i,\bar{q}) \le3\bar{q} q ≤ max ( q i , q ˉ ) ≤ 3 q ˉ give a divergence of at least b i 2 / ( 6 q ˉ ) b_i^2/(6\bar{q}) b i 2 / ( 6 q ˉ ) . Hence the left side is at least
q ˉ 3 ∑ i a i 2 + 2 3 q ˉ ∑ i b i 2 ≥ 2 2 3 ( ∑ i a i 2 ∑ i b i 2 ) 1 / 2 . \frac{\bar{q}}{3}\sum_i a_i^2 + \frac{2}{3\bar{q}}\sum_i b_i^2 \ge\frac{2\sqrt{2}}{3}\left(\sum_i a_i^2\sum_i b_i^2\right)^{1/2}. 3 q ˉ i ∑ a i 2 + 3 q ˉ 2 i ∑ b i 2 ≥ 3 2 2 ( i ∑ a i 2 i ∑ b i 2 ) 1/2 .
Up to sign, the oriented area equals ∑ i a i ( b i + 1 − b i − 1 ) \sum_i a_i(b_{i+1}-b_{i-1}) ∑ i a i ( b i + 1 − b i − 1 ) (indices mod 3). Since ∑ i b i = 0 \sum_i b_i = 0 ∑ i b i = 0 ,
∑ i ( b i + 1 − b i − 1 ) 2 = 3 ∑ i b i 2 . \sum_i(b_{i+1}-b_{i-1})^2 = 3\sum_i b_i^2. i ∑ ( b i + 1 − b i − 1 ) 2 = 3 i ∑ b i 2 .
Thus, by Cauchy–Schwarz, the area is at most 3 ( ∑ i a i 2 ∑ i b i 2 ) 1 / 2 \sqrt{3}(\sum_i a_i^2\sum_i b_i^2)^{1/2} 3 ( ∑ i a i 2 ∑ i b i 2 ) 1/2 . As 2 2 / 3 ≥ 3 / 3 2\sqrt{2}/3 \ge\sqrt{3}/3 2 2 /3 ≥ 3 /3 , the claim follows. Continuity extends convexity and the inequality to q i = 0 q_i = 0 q i = 0 . □
The standard regularizer, which combines a quadratic price term with negative entropy, is area convex [30 Lemma 1] . We extend this property to R α R_\alpha R α by proving that its difference from the standard regularizer, with entropy coefficient 8 8 8 , is convex for α ≥ 10 \alpha\ge10 α ≥ 10 . Adding a convex function preserves area convexity.
Lemma 4.3 (Area convexity of R α R_\alpha R α ). For α ≥ 10 \alpha\ge10 α ≥ 10 , R α R_\alpha R α is convex and 1 3 \frac{1}{3} 3 1 -area convex for g g g . Moreover, for every interior z z z and all z ′ , z + ∈ Z z^{\prime}, z^{+} \in Z z ′ , z + ∈ Z ,
1 3 ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ ≤ D z α ( z ′ ) + D z α ( z + ) . (11) \frac{1}{3}\langle g(z^{\prime})-g(z),z^{\prime}-z^{+}\rangle\le D^\alpha_z(z^{\prime})+D^\alpha_z(z^{+}). \tag*{(11)} 3 1 ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ ≤ D z α ( z ′ ) + D z α ( z + ) . (11)
Proof. For every ordered pair ( u , v ) (u,v) ( u , v ) with u v ∈ E uv \in E uv ∈ E , apply Theorem 4.2 to the points ( x v , q u v ) (x_v,q_{uv}) ( x v , q uv ) , and add the nonnegative Jensen gaps of the dummy terms 8 q u ⊥ log q u ⊥ 8q_{u\perp}\log q_{u\perp} 8 q u ⊥ log q u ⊥ . A direct expansion shows that ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ \langle g(z^{\prime})-g(z),z^{\prime}-z^{+}\rangle ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ equals, up to sign, the sum over pairs of the oriented areas; the constant parts of g g g cancel. Hence
r ( x , q ) = ∑ v ℓ v ( q ) x v 2 + 8 H ( q ) r(x,q)=\sum_v \ell_v(q)x_v^2+8H(q) r ( x , q ) = v ∑ ℓ v ( q ) x v 2 + 8 H ( q )
is convex and 1 3 \frac{1}{3} 3 1 -area convex. This part is Jambulapati and Tian [30 Lemma 1] with ∣ A ∣ = L |A|=L ∣ A ∣ = L ; they state it for a single simplex, but the argument is entrywise, and we include it for completeness. The rest of the proof, which handles the ψ \psi ψ term, is new.
Next, put h ( x ) = 2 ψ ( x ) − x 2 h(x)=2\psi(x)-x^2 h ( x ) = 2 ψ ( x ) − x 2 . Then
h ′ ( x ) = 2 ( atanh x − x ) , h ′ ′ ( x ) = 2 x 2 1 − x 2 , h ′ ( x ) 2 ≤ 2 h ′ ′ ( x ) . h^{\prime}(x)=2(\operatorname{atanh}x-x),\qquad h^{\prime\prime}(x)=\frac{2x^2}{1-x^2},\qquad h^{\prime}(x)^2\le2h^{\prime\prime}(x). h ′ ( x ) = 2 ( atanh x − x ) , h ′′ ( x ) = 1 − x 2 2 x 2 , h ′ ( x ) 2 ≤ 2 h ′′ ( x ) .
For the last inequality, use 0 ≤ atanh x − x ≤ x / 1 − x 2 0\le\operatorname{atanh}x-x\le x/\sqrt{1-x^2} 0 ≤ atanh x − x ≤ x / 1 − x 2 for 0 ≤ x < 1 0\le x<1 0 ≤ x < 1 and symmetry. The upper bound follows by integrating ( atanh x ) ′ ≤ x / 1 − x 2 (\operatorname{atanh}x)^{\prime}\le x/\sqrt{1-x^2} ( atanh x ) ′ ≤ x / 1 − x 2 . So the Hessian ( q h ′ ′ h ′ h ′ 2 / q ) \begin{pmatrix} qh^{\prime\prime} & h^{\prime} \\ h^{\prime} & 2/q \end{pmatrix} ( q h ′′ h ′ h ′ 2/ q ) of q h ( x ) + 2 q log q qh(x)+2q\log q q h ( x ) + 2 q log q is positive semidefinite. Continuity extends this convexity to the boundary. Therefore
R α − r = 2 ∑ v ψ ( x v ) + ∑ ( u , v ) : u v ∈ E [ q u v h ( x v ) + 2 q u v log q u v ] + 2 ∑ u q u ⊥ log q u ⊥ + ( α − 10 ) H ( q ) R_\alpha-r=2\sum_v\psi(x_v)+\sum_{(u,v):uv\in E}\left[q_{uv}h(x_v)+2q_{uv}\log q_{uv}\right]
+2\sum_u q_{u\perp}\log q_{u\perp}+(\alpha-10)H(q) R α − r = 2 v ∑ ψ ( x v ) + ( u , v ) : uv ∈ E ∑ [ q uv h ( x v ) + 2 q uv log q uv ] + 2 u ∑ q u ⊥ log q u ⊥ + ( α − 10 ) H ( q )
is convex. Adding a convex function preserves area convexity by Jensen’s inequality, which proves the first claim.
Finally, for an interior base z z z and c = ( z + z ′ + z + ) / 3 c=(z+z^{\prime}+z^{+})/3 c = ( z + z ′ + z + ) /3 ,
R α ( z ) + R α ( z ′ ) + R α ( z + ) − 3 R α ( c ) = D z α ( z ′ ) + D z α ( z + ) − 3 D z α ( c ) ≤ D z α ( z ′ ) + D z α ( z + ) . \begin{aligned}
R_\alpha(z)+R_\alpha(z^{\prime})+R_\alpha(z^{+})-3R_\alpha(c)=D^\alpha_z(z^{\prime})+D^\alpha_z(z^{+})-3D^\alpha_z(c) \\
&\le D^\alpha_z(z^{\prime})+D^\alpha_z(z^{+}).
\end{aligned} R α ( z ) + R α ( z ′ ) + R α ( z + ) − 3 R α ( c ) = D z α ( z ′ ) + D z α ( z + ) − 3 D z α ( c ) ≤ D z α ( z ′ ) + D z α ( z + ) .
Together with area convexity, this gives (11) .
The price update: a box response
We derive the price update by minimizing (9) over prices while holding the candidate proposal distributions fixed. Fix an interior base state z = ( x , q ) z=(x,q) z = ( x , q ) , a vector v = ( v x , v q ) ∈ R V × R I v=(v^x,v^q)\in\mathbb{R}^{V}\times\mathbb{R}^{I} v = ( v x , v q ) ∈ R V × R I , and candidate distributions h ∈ Q h\in\mathcal{Q} h ∈ Q . Writing w = ( y , h ) w=(y,h) w = ( y , h ) and dropping terms independent of y y y gives the subproblem
min y ∈ X { ⟨ v x , y ⟩ + D z α ( y , h ) } , α ≥ 10. (12) \min_{y\in X}\{\langle v^x,y\rangle+D^\alpha_z(y,h)\},\qquad\alpha\ge10. \tag*{(12)} y ∈ X min {⟨ v x , y ⟩ + D z α ( y , h )} , α ≥ 10. (12)
We call its minimizing price vector y y y the box response , since X = [ − 1 , 1 ] V X=[-1,1]^V X = [ − 1 , 1 ] V . The only α \alpha α -dependent term is α K q ( h ) \alpha K_q(h) α K q ( h ) , which is constant in y y y , so the response does not depend on α \alpha α for fixed z , v , h z,v,h z , v , h . The subroutine Resp z , v ( h ) \operatorname{Resp}_{z,v}(h) Resp z , v ( h ) in Algorithm 1 returns the updated prices. Each stage of § 5 calls it before and after updating the proposal distributions. The change of variables τ = ψ ′ ( x ) = atanh x \tau=\psi^{\prime}(x)=\operatorname{atanh}x τ = ψ ′ ( x ) = atanh x makes the price optimality condition linear.
Algorithm 1: Box response Resp z , v ( h ) \operatorname{Resp}_{z,v}(h) Resp z , v ( h )
Input: Interior base state z = ( x , q ) z=(x,q) z = ( x , q ) ; vector v = ( v x , v q ) v=(v^{x},v^{q}) v = ( v x , v q ) ; candidate distributions h ∈ Q h\in Q h ∈ Q .
Output: Updated prices y y y .
A ← 1 + ℓ ( q ) 1 + ℓ ( h ) , B ← − v x 2 ( 1 + ℓ ( h ) ) A\leftarrow\frac{1+\ell(q)}{1+\ell(h)},\qquad B\leftarrow-\frac{v^{x}}{2(1+\ell(h))} A ← 1 + ℓ ( h ) 1 + ℓ ( q ) , B ← − 2 ( 1 + ℓ ( h )) v x \hfill // loads from (1)
y ← tanh ( A atanh x + B ) y\leftarrow\tanh(A\operatorname{atanh}x+B) y ← tanh ( A atanh x + B )
return y y y
Lemma 4.4 (Box response). Algorithm 1 returns the unique minimizer y y y of (12) . The minimizer lies in ( − 1 , 1 ) V (-1,1)^{V} ( − 1 , 1 ) V . Writing τ = atanh x \tau=\operatorname{atanh}x τ = atanh x and τ ′ = atanh y \tau'=\operatorname{atanh}y τ ′ = atanh y , its optimality condition is
( 1 + ℓ ( h ) ) τ ′ = ( 1 + ℓ ( q ) ) τ − 1 2 v x . (13) (1+\ell(h))\tau'=(1+\ell(q))\tau-\frac{1}{2}v^{x}. \tag*{(13)} ( 1 + ℓ ( h )) τ ′ = ( 1 + ℓ ( q )) τ − 2 1 v x . (13) Equivalently, τ ′ = A τ + B \tau'=A\tau+B τ ′ = A τ + B and y = tanh τ ′ y=\tanh\tau' y = tanh τ ′ .
Proof. Up to a term independent of y y y , the objective is
2 ∑ j ∈ V ( 1 + ℓ j ( h ) ) ψ ( y j ) + ⟨ v x − ∇ x R α ( z ) , y ⟩ . 2\sum_{j\in V}(1+\ell_j(h))\psi(y_j)+\langle v^{x}-\nabla_xR_{\alpha}(z),y\rangle. 2 j ∈ V ∑ ( 1 + ℓ j ( h )) ψ ( y j ) + ⟨ v x − ∇ x R α ( z ) , y ⟩ .
The coordinates separate. Since ψ ′ = atanh \psi'=\operatorname{atanh} ψ ′ = atanh is strictly increasing from − ∞ -\infty − ∞ to + ∞ +\infty + ∞ on ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) , each coordinate has a unique interior minimizer. Its first-order condition, using (10) , is (13) . Solving for τ ′ \tau' τ ′ and applying tanh \tanh tanh gives the algorithm.
Uniform bounds. For the sampling implementation in § 6 , we need uniform bounds on the coefficients A , B A,B A , B in Algorithm 1. The next lemma obtains these bounds when the relevant loads are within constant factors of the base load. Theorem 5.9 will verify this condition for every call to Resp.
All price-gradient vectors used below have the form
v x = λ ( 1 − L k ) , k ∈ Q ∘ , λ ∈ { 1 / 3 , 1 / 6 } . v^{x}=\lambda(1-Lk),\qquad k\in Q^{\circ},\qquad\lambda\in\{1/3,1/6\}. v x = λ ( 1 − L k ) , k ∈ Q ∘ , λ ∈ { 1/3 , 1/6 } .
Here k k k denotes the proposal distributions used to evaluate the gradient; these may differ from both the base distributions q q q and the candidate distributions h h h . At a nonisolated vertex j j j , define
r = ℓ j ( q ) 1 + ℓ j ( q ) , z h = ℓ j ( h ) ℓ j ( q ) , z k = ℓ j ( k ) ℓ j ( q ) . (14) r=\frac{\ell_j(q)}{1+\ell_j(q)},\qquad z_h=\frac{\ell_j(h)}{\ell_j(q)},\qquad z_k=\frac{\ell_j(k)}{\ell_j(q)}. \tag*{(14)} r = 1 + ℓ j ( q ) ℓ j ( q ) , z h = ℓ j ( q ) ℓ j ( h ) , z k = ℓ j ( q ) ℓ j ( k ) . (14)
Thus r ∈ ( 0 , 1 ) r\in(0,1) r ∈ ( 0 , 1 ) represents the base load by a bounded quantity, while z h , z k z_h,z_k z h , z k express the other loads relative to it. In the following lemma, we suppress the vertex subscripts on A , B A,B A , B .
Lemma 4.5 (Box coefficients). The coefficients in Algorithm 1 can be written as
w = 1 − r + r z h , A = 1 w , B = λ ( r ( z k + 1 ) − 1 ) 2 w . w=1-r+rz_h,\qquad A=\frac{1}{w},\qquad B=\frac{\lambda(r(z_k+1)-1)}{2w}. w = 1 − r + r z h , A = w 1 , B = 2 w λ ( r ( z k + 1 ) − 1 ) . If z h , z k ∈ [ e − 1 , e ] z_h,z_k\in[e^{-1},e] z h , z k ∈ [ e − 1 , e ] , then
w , A ∈ [ e − 1 , e ] , ∣ B ∣ < 2. w,A\in[e^{-1},e],\qquad|B|<2. w , A ∈ [ e − 1 , e ] , ∣ B ∣ < 2. At an isolated vertex, A = 1 A=1 A = 1 and B = − λ / 2 B=-\lambda/2 B = − λ /2 .
Proof. Multiplying the numerators and denominators in the definitions of A A A and B B B by 1 − r = 1 / ( 1 + ℓ j ( q ) ) 1-r=1/(1+\ell_j(q)) 1 − r = 1/ ( 1 + ℓ j ( q )) gives the stated formulas. Since w w w is a convex combination of 1 1 1 and z h z_h z h , both w w w and A = 1 / w A=1/w A = 1/ w lie in [ e − 1 , e ] [e^{-1},e] [ e − 1 , e ] . Also,
∣ r ( z k + 1 ) − 1 ∣ ≤ e , ∣ B ∣ ≤ e 2 / 6 < 2. \lvert r(z_k+1)-1\rvert\le e,\qquad\lvert B\rvert\le e^2/6<2. ∣ r ( z k + 1 ) − 1 ∣ ≤ e , ∣ B ∣ ≤ e 2 /6 < 2.
At an isolated vertex all loads vanish, giving A = 1 A=1 A = 1 and B = − λ / 2 B=-\lambda/2 B = − λ /2 , which satisfy the same bounds on A A A and B B B .
Remark 4.6 (Why not the standard regularizer). The standard area-convex regularizer for box–simplex games [30 , 31 , 55 ] specializes in our setting to ∑ v ℓ v ( q ) x v 2 + α H ( q ) \sum_v \ell_v(q)x_v^2+\alpha H(q) ∑ v ℓ v ( q ) x v 2 + α H ( q ) . For positive candidate load ℓ v ( h ) \ell_v(h) ℓ v ( h ) , its box response is a quotient with denominator $2\ell_v(h), c l i p p e d t o , clipped to , c l i pp e d t o [-1,1] {citep}[30 Algorithm 4] . This response is nonsmooth at the clipping points, and its load denominator can be arbitrarily small or zero. These features prevent a direct application of the smooth exact sampling primitives in {xref}Section 6`.
Our regularizer replaces ℓ v ( q ) x v 2 \ell_v(q)x_v^2 ℓ v ( q ) x v 2 by 2 ℓ v ( q ) ψ ( x v ) 2\ell_v(q)\psi(x_v) 2 ℓ v ( q ) ψ ( x v ) and adds 2 ∑ v ψ ( x v ) 2\sum_v\psi(x_v) 2 ∑ v ψ ( x v ) . The choice of ψ \psi ψ gives a smooth price response without clipping, while the added term changes the load denominator to 1 + ℓ v ( h ) 1+\ell_v(h) 1 + ℓ v ( h ) , keeping the formula defined at zero load. Under constant bounds on relative loads, Theorem 4.5 also bounds the response coefficients. The sampler uses a bounded representation of the transformed price to evaluate this response, as described in § 6.2 .
Binary entropy also supports the multiplicative convergence guarantee: with prices initialized near − 1 -1 − 1 , Theorem 5.8 bounds the initial potential by O ( ν f ( G ) log ( 2 Δ ) ) O(\nu_f(G)\log(2\Delta)) O ( ν f ( G ) log ( 2Δ )) . Theorem 4.3 establishes area convexity for the modified regularizer. The locality of normalization comes separately from our product of vertex simplices, as explained in Theorem 3.4.
The optimization method
We present the optimization algorithm that constructs proposal distributions with nearly maximum accepted mass. Algorithm 2 gives the complete procedure, and Algorithm 3 specifies a single round. At round t t t , the state consists of main proposal distributions q t q_t q t , auxiliary proposal distributions q ˉ t \bar{q}_t q ˉ t , and prices x t x_t x t . Starting from a fixed initialization, the algorithm updates this state over T T T rounds.
We run the optimizer only on nonisolated vertices. Isolated vertices always return their dummy and have no effect on accepted mass or fractional matching. Thus the state coordinates and potential sums in this section omit isolated vertices; the graph still has its original n n n vertex labels. This restriction requires only a local degree query, not knowledge of the number n 0 n_0 n 0 of nonisolated vertices.
Each round has two stages. A gradient stage computes tentative prices and main proposal distributions. An extragradient stage then evaluates the gradient at that tentative state and uses it to form the next state. Each stage performs a fixed number of price and proposal-distribution updates. Our final output is the average of the tentative proposal distributions over all T T T rounds.
The regularizer of § 4 supplies the Bregman penalties used in these updates. Within each stage, we first compute a provisional price response and use it to update the proposal distributions by multiplicative reweighting and normalization. We then compute the price response for the updated distributions. The extragradient stage also updates the auxiliary distributions. Every price response uses the state at the start of the round as its Bregman base. The area-convex analysis controls the interaction between the two stages [30 , 55 ] .
The optimization is deterministic given G G G . After describing the algorithm and stating its convergence guarantee, we establish bounds for the two stages of a round and combine them to prove convergence.
Each round is local in the sense that the updated state at a vertex depends only on the previous-round state within six hops. With our initialization, the state and output proposal distribution at a vertex after T T T rounds are determined by a neighborhood of radius O ( T ) O(T) O ( T ) . Therefore, Algorithm 2 already gives a direct local algorithm for its output proposal distributions. Each round consists of a constant number of updates involving neighboring states, so computing the final q ^ u \widehat{q}_u q u at a specified vertex requires exploring only a neighborhood of radius O ( T ) O(T) O ( T ) . This gives a worst-case deterministic query bound of Δ O ( T ) = Δ O ( δ − 1 log Δ ) \Delta^{O(T)} = \Delta^{O(\delta^{-1}\log\Delta)} Δ O ( T ) = Δ O ( δ − 1 l o g Δ ) .
In § 6 , we show that for the more limited task of drawing one exact sample from q ^ u \widehat{q}_u q u , without constructing the full state, we can reduce the cost to Δ O ( 1 / δ ) \Delta^{O(1/\delta)} Δ O ( 1/ δ ) expected queries. § 5.4 prepares for § 6 by bounding changes of the state between consecutive rounds. In § 6 , we use these bounds to sample the proposal distributions recursively across rounds. Generating a sample for one round requires only an expected constant number of samples and coin flips from the preceding round, avoiding exploration of all neighbors.
Algorithm 2: Computing proposal distributions with nearly maximum accepted mass
Input: Graph G G G , degree bound Δ ≥ 2 \Delta\ge2 Δ ≥ 2 , and number of rounds T ≥ 1 T \ge1 T ≥ 1 .
Output: Proposal distributions q ^ ∈ Q \widehat{q} \in Q q ∈ Q .
// Initialization for the potential bound in Theorem 5.8
Set the output at each isolated vertex to its dummy
x 0 ← ( − 1 + 1 / Δ ) 1 x_0 \leftarrow(-1 + 1/\Delta)\mathbf{1} x 0 ← ( − 1 + 1/Δ ) 1 on nonisolated vertices
foreach nonisolated u ∈ V u \in V u ∈ V do
q 0 , u v ← 1 / ( 2 Δ 2 ) q_{0,uv} \leftarrow1/(2\Delta^2) q 0 , uv ← 1/ ( 2 Δ 2 ) for every v ∈ N ( u ) v \in N(u) v ∈ N ( u )
q 0 , u ⊥ ← 1 − deg ( u ) / ( 2 Δ 2 ) q_{0,u\perp} \leftarrow1 - \deg(u)/(2\Delta^2) q 0 , u ⊥ ← 1 − deg ( u ) / ( 2 Δ 2 )
q ‾ 0 ← q 0 \overline{q}_0 \leftarrow q_0 q 0 ← q 0
for t = 0 , … , T − 1 t = 0,\ldots,T-1 t = 0 , … , T − 1 do
( x t + 1 , q t + 1 , q ‾ t + 1 , q t ′ ) ← Round ( x t , q t , q ‾ t ) (x_{t+1},q_{t+1},\overline{q}_{t+1},q'_t) \leftarrow\operatorname{Round}(x_t,q_t,\overline{q}_t) ( x t + 1 , q t + 1 , q t + 1 , q t ′ ) ← Round ( x t , q t , q t ) \hfill // Algorithm 3
q ^ ← 1 T ∑ t = 0 T − 1 q t ′ \widehat{q} \leftarrow\frac{1}{T}\sum_{t=0}^{T-1}q'_t q ← T 1 ∑ t = 0 T − 1 q t ′ \hfill // average the tentative distributions
return q ^ \widehat{q} q
The round routine uses the normalization map N \mathcal{N} N . For a positive weight vector r ∈ R > 0 I r \in\mathbb{R}^{I}_{>0} r ∈ R > 0 I , define
( N ( r ) ) u a = r u a ∑ b ∈ I u r u b . (15) \bigl(\mathcal{N}(r)\bigr)_{ua} = \frac{r_{ua}}{\sum_{b\in I_u} r_{ub}}. \tag*{(15)} ( N ( r ) ) u a = ∑ b ∈ I u r u b r u a . (15)
Thus, normalization is performed separately at each vertex.
Algorithm 3: Round: one optimization round
Input: Current state $(x,q,\bar{q})$.
Output: Next state $(x^{+},q^{+},\bar{q}^{+})$ and tentative proposal distributions $q'$.
$\eta \leftarrow 1/3$
$z \leftarrow (x,q)$ // fixed base for every price response
Gradient stage // {xref}`Theorem 5.5`, $\alpha=\beta=16$
$v \leftarrow \eta g(x,q)$ // See {xref}`(4.2)`
$x^{*} \leftarrow \operatorname{Resp}_{z,v}(q)$ // provisional price response; {xref}`Algorithm 1`
$q' \leftarrow \mathcal{N}\left(q\exp\left(-\frac{v^{q}+2L^{*}(\psi(x^{*})-\psi(x))}{16}\right)\right)$ // update distributions; {xref}`(5.1)`
$x' \leftarrow \operatorname{Resp}_{z,v}(q')$ // price response for $q'$; {xref}`Algorithm 1`
Extragradient stage // {xref}`Theorem 5.6`, $\alpha=32$, $\beta=64$
$\tilde{v} \leftarrow \frac{\eta}{2}g(x',q')$ // See {xref}`(4.2)`
$x_{a} \leftarrow \operatorname{Resp}_{z,\tilde{v}}(\bar{q})$ // provisional price response; {xref}`Algorithm 1`
$a \leftarrow \frac{1}{64}\left(\tilde{v}^{q}+2L^{*}(\psi(x_{a})-\psi(x))\right)$
$q^{+} \leftarrow \mathcal{N}\left(\sqrt{q\bar{q}}e^{-a}\right)$ // update main distributions; {xref}`(5.1)`
$x^{+} \leftarrow \operatorname{Resp}_{z,\tilde{v}}(q^{+})$ // price response for $q^{+}$; {xref}`Algorithm 1`
$\hat{s} \leftarrow \frac{1}{64}\left(\tilde{v}^{q}+2L^{*}(\psi(x^{+})-\psi(x))\right)$
$\bar{q}^{+} \leftarrow \mathcal{N}\left(\bar{q}\sqrt{q/q^{+}}e^{-\hat{s}}\right)$ // update auxiliary distributions; {xref}`(5.1)`
return $(x^{+},q^{+},\bar{q}^{+},q')$
The initialization gives interior prices and positive proposal probabilities. By Theorem 4.4, every price response remains in ( − 1 , 1 ) V (-1,1)^{V} ( − 1 , 1 ) V , and multiplicative reweighting and normalization preserve positive probabilities. Thus all subsequent updates are well defined, with the main and auxiliary distributions remaining in Q ∘ Q^{\circ} Q ∘ . The target saddle point may lie on the boundary of Z Z Z : the regularizer is finite there, while its steep derivatives keep the finite iterates in the interior.
Convergence guarantee
The output of Algorithm 2 satisfies the following bound.
Theorem 5.1 (Convergence rate). Let G G G be a graph of maximum degree at most Δ \Delta Δ , and let q ^ \hat{q} q ^ be the output of Algorithm 2 after T T T rounds. With B Δ : = 200 + 400 log ( 2 Δ ) B_{\Delta}:=200+400\log(2\Delta) B Δ := 200 + 400 log ( 2Δ ) ,
0 ≤ 2 ν f ( G ) − P ( q ^ ) ≤ 3 B Δ ν f ( G ) T . 0 \le2\nu_f(G)-P(\hat{q}) \le\frac{3B_{\Delta}\nu_f(G)}{T}. 0 ≤ 2 ν f ( G ) − P ( q ^ ) ≤ T 3 B Δ ν f ( G ) . Consequently, setting
T = ⌈ 3 B Δ δ ⌉ = O ( δ − 1 log ( 2 Δ ) ) T=\left\lceil\frac{3B_{\Delta}}{\delta}\right\rceil=O\left(\delta^{-1}\log(2\Delta)\right) T = ⌈ δ 3 B Δ ⌉ = O ( δ − 1 log ( 2Δ ) ) gives accepted mass P ( q ^ ) ≥ ( 2 − δ ) ν f ( G ) P(\hat{q})\ge(2-\delta)\nu_f(G) P ( q ^ ) ≥ ( 2 − δ ) ν f ( G ) . The proof is in § 5.3 .
The deterministic iteration also gives algorithms for fractional matching by evaluating its updates directly. For q ∈ Q q\in Q q ∈ Q , define
f { u , v } ( q ) = 1 2 ( q u v max { 1 , ℓ v ( q ) } + q v u max { 1 , ℓ u ( q ) } ) . (16) f_{\{u,v\}}(q)=\frac{1}{2}\left(\frac{q_{uv}}{\max\{1,\ell_v(q)\}}+\frac{q_{vu}}{\max\{1,\ell_u(q)\}}\right). \tag*{(16)} f { u , v } ( q ) = 2 1 ( max { 1 , ℓ v ( q )} q uv + max { 1 , ℓ u ( q )} q v u ) . (16)
As in the proof of Theorem 3.1(a), these weights form a fractional matching, with
∑ e ∈ E f e ( q ) = 1 2 P ( q ) . \sum_{e\in E} f_e(q)=\frac{1}{2}P(q). e ∈ E ∑ f e ( q ) = 2 1 P ( q ) .
Corollary 5.2 (Deterministic LOCAL algorithm). Let G G G be a graph on n n n vertices with maximum degree at most a known Δ ≥ 2 \Delta\ge2 Δ ≥ 2 , and let 0 < ε < 1 / 2 0 < \varepsilon< 1/2 0 < ε < 1/2 . There is a deterministic LOCAL algorithm that computes a fractional matching of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) in
O ( log ( 2 Δ ) ε ) O\left(\frac{\log(2\Delta)}{\varepsilon}\right) O ( ε log ( 2Δ ) ) rounds. Each endpoint of an edge outputs the same edge weight.
Proof. Run Algorithm 2 for T = ⌈ 3 B Δ / ε ⌉ T=\lceil3B_\Delta/\varepsilon\rceil T = ⌈ 3 B Δ / ε ⌉ rounds and let f ∗ = f ( q ^ ) f^*=f(\widehat q) f ∗ = f ( q ) . By Theorem 5.1 ,
∑ e f e ∗ = 1 2 P ( q ^ ) ≥ ( 1 − ε / 2 ) ν f ( G ) . \sum_e f_e^*=\frac{1}{2}P(\widehat q)\ge(1-\varepsilon/2)\nu_f(G). e ∑ f e ∗ = 2 1 P ( q ) ≥ ( 1 − ε /2 ) ν f ( G ) .
Each optimization round consists of a constant number of local updates and exchanges between neighbors: loads are incoming sums, proposal distributions are normalized at their source, and price updates are computed at their vertex. The final averaging and (16) add only constant locality. Thus each f e ∗ f_e^* f e ∗ depends on a neighborhood of radius O ( T ) O(T) O ( T ) around e e e .
Each vertex gathers the required neighborhood in O ( T ) O(T) O ( T ) LOCAL rounds. To obtain finite outputs, the endpoints use the same deterministic procedure to compute a certified rational approximation f ~ e \widetilde f_e f e satisfying
0 ≤ f ~ e ≤ f e ∗ , f e ∗ − f ~ e ≤ ε / ( 4 Δ ) . 0\le\widetilde f_e\le f_e^*,\qquad f_e^*-\widetilde f_e\le\varepsilon/(4\Delta). 0 ≤ f e ≤ f e ∗ , f e ∗ − f e ≤ ε / ( 4Δ ) .
Such approximations can be computed from the explicit update formulas. Decreasing edge weights preserves feasibility, and the total decrease is at most ∣ E ∣ ε / ( 4 Δ ) ≤ ε ν f ( G ) / 2 |E|\varepsilon/(4\Delta)\le\varepsilon\nu_f(G)/2 ∣ E ∣ ε / ( 4Δ ) ≤ ε ν f ( G ) /2 by Theorem 2.4. □
Corollary 5.3 (Deterministic fractional-matching LCA). Under the same assumptions, there is a deterministic LCA answering edge queries consistently with one fractional matching of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) , using
( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) (2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} ( 2Δ ) O ( ε − 1 l o g ( 2Δ )) graph queries and computational work per edge query, in the model of § 2.1 . Both bounds are worst case. No preprocessing or persistent memory is required.
Proof. Use the finite implementation in Theorem B.1, with T = O ( ε − 1 log ( 2 Δ ) ) T=O(\varepsilon^{-1}\log(2\Delta)) T = O ( ε − 1 log ( 2Δ )) optimization rounds. Its output is a feasible fractional matching of value at least ( 1 − ε ) ν f ( G ) (1-\varepsilon)\nu_f(G) ( 1 − ε ) ν f ( G ) . An edge query evaluates this construction within the radius-O ( T ) O(T) O ( T ) neighborhood on which its answer depends. The precision and computational-work bounds in that proposition give ( 2 Δ ) O ( T ) (2\Delta)^{O(T)} ( 2Δ ) O ( T ) graph queries and computational work. All answers use the same initialization, update rules, and numerical rounding rules, so they describe one fractional matching independently of the query order. □
For bipartite graphs, the algorithms of Theorems 5.2 and 5.3 can be combined with deterministic rounding in the corresponding model to obtain integral matchings. For example, combining Theorem 5.2 with Ahmadi et al. [1 Theorem 3] gives a deterministic LOCAL algorithm that computes a matching of size at least ( 1 − ε ) ν ( G ) (1-\varepsilon)\nu(G) ( 1 − ε ) ν ( G ) , splitting the error allowance between optimization and rounding, in O ( ( log 2 ( Δ / ε ) + log ∗ n ) / ε ) O((\log^2(\Delta/\varepsilon)+\log^* n)/\varepsilon) O (( log 2 ( Δ/ ε ) + log ∗ n ) / ε ) rounds.
Mirror descent and update inequalities
For current proposal distributions p ∈ Q ∘ p \in Q^\circ p ∈ Q ∘ , a score vector a a a and β > 0 \beta> 0 β > 0 , an entropic mirror-descent step is
p + = arg min h ∈ Q { ⟨ a , h ⟩ + β K p ( h ) } = N ( p e − a / β ) = : MD p β ( a ) . p^+ = \arg\min_{h \in Q} \{\langle a,h\rangle+ \beta K_p(h)\} = \mathcal{N}(p e^{-a/\beta}) =: \operatorname{MD}^{\beta}_p(a). p + = arg h ∈ Q min {⟨ a , h ⟩ + β K p ( h )} = N ( p e − a / β ) =: MD p β ( a ) .
Thus the update favors smaller scores while penalizing deviation from p p p . It multiplies probabilities by score-dependent factors and normalizes separately at each vertex: this is the multiplicative-weights form of mirror descent. The identity used in the analysis is, for all h ∈ Q h \in Q h ∈ Q ,
⟨ a , p + − h ⟩ = β [ K p ( h ) − K p + ( h ) − K p ( p + ) ] . (17) \langle a,p^+ - h\rangle= \beta[K_p(h) - K_{p^+}(h) - K_p(p^+)]. \tag*{(17)} ⟨ a , p + − h ⟩ = β [ K p ( h ) − K p + ( h ) − K p ( p + )] . (17)
because log ( p + / p ) = − a / β \log(p^+/p) = -a/\beta log ( p + / p ) = − a / β plus block constants, which vanish against p + − h p^+ - h p + − h .
To combine this distribution update with a price update, fix an interior base z = ( x , q ) z = (x,q) z = ( x , q ) and a vector v = ( v x , v q ) v = (v^x,v^q) v = ( v x , v q ) and α ≥ 10 \alpha\ge10 α ≥ 10 . For each candidate h h h , minimize over the prices using y ( h ) = Resp z , v ( h ) y(h) = \operatorname{Resp}_{z,v}(h) y ( h ) = Resp z , v ( h ) . The remaining regularized objective and its score vector are
f ( h ) = ⟨ v , ( y ( h ) , h ) ⟩ + D z α ( y ( h ) , h ) , a ( h ) = v q + 2 L ∗ ( ψ ( y ( h ) ) − ψ ( x ) ) + α log ( h / q ) . f(h) = \langle v,(y(h),h)\rangle+ D^\alpha_z(y(h),h), \qquad a(h) = v^q + 2L^*(\psi(y(h)) - \psi(x)) + \alpha\log(h/q). f ( h ) = ⟨ v , ( y ( h ) , h )⟩ + D z α ( y ( h ) , h ) , a ( h ) = v q + 2 L ∗ ( ψ ( y ( h )) − ψ ( x )) + α log ( h / q ) .
Lemma 5.4 (Partial minimization; cf. [30 Lemmas 4–5] and [18 ] ). Both f f f and α H − f \alpha H - f α H − f are convex, ∇ f = a \nabla f = a ∇ f = a on Q ∘ Q^\circ Q ∘ up to block constants, and for p , p ′ ∈ Q ∘ p,p' \in Q^\circ p , p ′ ∈ Q ∘ , h ∈ Q h \in Q h ∈ Q ,
⟨ a ( p ′ ) − a ( p ) , p ′ − h ⟩ ≤ α [ K p ( p ′ ) + K p ′ ( h ) ] . (18) \langle a(p') - a(p),p' - h\rangle\le\alpha[K_p(p') + K_{p'}(h)]. \tag*{(18)} ⟨ a ( p ′ ) − a ( p ) , p ′ − h ⟩ ≤ α [ K p ( p ′ ) + K p ′ ( h )] . (18) Proof. f f f is a partial minimum of a jointly convex function (Theorem 4.3), hence convex. For fixed y y y the minimized expression is α H ( h ) \alpha H(h) α H ( h ) plus an affine function of h h h , so f − α H f - \alpha H f − α H is an infimum of affine functions and is concave. By the envelope theorem and (4.6), ∇ f ( h ) = a ( h ) \nabla f(h) = a(h) ∇ f ( h ) = a ( h ) up to block constants. Convexity of f f f and of α H − f \alpha H - f α H − f gives 0 ≤ D p f ( h ) ≤ α K p ( h ) 0 \le D^f_p(h) \le\alpha K_p(h) 0 ≤ D p f ( h ) ≤ α K p ( h ) . The three-point identity ⟨ ∇ f ( p ′ ) − ∇ f ( p ) , p ′ − h ⟩ = D p f ( p ′ ) + D p ′ f ( h ) − D p f ( h ) \langle\nabla f(p') - \nabla f(p),p' - h\rangle= D^f_p(p') + D^f_{p'}(h) - D^f_p(h) ⟨ ∇ f ( p ′ ) − ∇ f ( p ) , p ′ − h ⟩ = D p f ( p ′ ) + D p ′ f ( h ) − D p f ( h ) then gives (5.4); continuity covers boundary h h h .
Lemma 5.5 (Gradient update; cf. [30 Definition 4] ). Let β ≥ α ≥ 10 \beta\ge\alpha\ge10 β ≥ α ≥ 10 , q ′ = MD q β ( a ( q ) ) q' = \operatorname{MD}^{\beta}_q(a(q)) q ′ = MD q β ( a ( q )) , x ′ = y ( q ′ ) x' = y(q') x ′ = y ( q ′ ) and z ′ = ( x ′ , q ′ ) z' = (x',q') z ′ = ( x ′ , q ′ ) . For every w ∈ Z w \in Z w ∈ Z ,
⟨ v , z ′ − w ⟩ ≤ D z α + β ( w ) − D z ′ α ( w ) − D z α ( z ′ ) . \langle v,z' - w\rangle\le D^{\alpha+\beta}_z(w) - D^\alpha_{z'}(w) - D^\alpha_z(z'). ⟨ v , z ′ − w ⟩ ≤ D z α + β ( w ) − D z ′ α ( w ) − D z α ( z ′ ) . Proof. Add (5.3) for a ( q ) a(q) a ( q ) to (5.4) with ( p , p ′ , h ) = ( q , q ′ , w q ) (p,p',h) = (q,q',w^q) ( p , p ′ , h ) = ( q , q ′ , w q ) ; since β ≥ α \beta\ge\alpha β ≥ α , this gives ⟨ a ( q ′ ) , q ′ − w q ⟩ ≤ β K q ( w q ) \langle a(q'),q' - w^q\rangle\le\beta K_q(w^q) ⟨ a ( q ′ ) , q ′ − w q ⟩ ≤ β K q ( w q ) . Stationarity of the box response gives v x + ∇ x R α ( z ′ ) − ∇ x R α ( z ) = 0 v^x+\nabla_x R_\alpha(z')-\nabla_x R_\alpha(z) = 0 v x + ∇ x R α ( z ′ ) − ∇ x R α ( z ) = 0 , and the q q q -component of v + ∇ R α ( z ′ ) − ∇ R α ( z ) v+\nabla R_\alpha(z')-\nabla R_\alpha(z) v + ∇ R α ( z ′ ) − ∇ R α ( z ) is a ( q ′ ) a(q') a ( q ′ ) up to block constants. So ⟨ v + ∇ R α ( z ′ ) − ∇ R α ( z ) , z ′ − w ⟩ ≤ β K q ( w q ) \langle v+\nabla R_\alpha(z')-\nabla R_\alpha(z),z' - w\rangle\le\beta K_q(w^q) ⟨ v + ∇ R α ( z ′ ) − ∇ R α ( z ) , z ′ − w ⟩ ≤ β K q ( w q ) . The three-point identity for R α R_\alpha R α and D z α + β = D z α + β K q D^{\alpha+\beta}_z = D^\alpha_z + \beta K_q D z α + β = D z α + β K q finish the proof.
Lemma 5.6 (Extragradient update; cf. [30 Definition 5] ). Let β ≥ α ≥ 10 \beta\ge\alpha\ge10 β ≥ α ≥ 10 and q ˉ ∈ Q ∘ \bar q \in Q^\circ q ˉ ∈ Q ∘ . Set q + = MD q ˉ β ( a ( q ˉ ) ) q^+ = \operatorname{MD}^{\beta}_{\bar q}(a(\bar q)) q + = MD q ˉ β ( a ( q ˉ )) , x + = y ( q + ) x^+ = y(q^+) x + = y ( q + ) , z + = ( x + , q + ) z^+ = (x^+,q^+) z + = ( x + , q + ) and q ˉ + = MD q ˉ β ( a ( q + ) ) \bar q^+ = \operatorname{MD}^{\beta}_{\bar q}(a(q^+)) q ˉ + = MD q ˉ β ( a ( q + )) . For every w ∈ Z w \in Z w ∈ Z ,
⟨ v , z + − w ⟩ ≤ D z α ( w ) − D z + α ( w ) − D z α ( z + ) + β K q ˉ ( w q ) − β K q ˉ + ( w q ) . \langle v,z^+ - w\rangle\le D^\alpha_z(w) - D^\alpha_{z^+}(w) - D^\alpha_z(z^+) + \beta K_{\bar q}(w^q) - \beta K_{\bar q^+}(w^q). ⟨ v , z + − w ⟩ ≤ D z α ( w ) − D z + α ( w ) − D z α ( z + ) + β K q ˉ ( w q ) − β K q ˉ + ( w q ) . Proof. Apply (5.3) to the first update with comparator q ˉ + \bar q^+ q ˉ + and to the second with comparator w q w^q w q , and add:
⟨ a ( q + ) , q + − w q ⟩ = β [ K q ˉ ( w q ) − K q ˉ + ( w q ) − K q ˉ ( q ˉ + ) − K q ˉ ( q + ) ] + ⟨ a ( q + ) − a ( q ˉ ) , q + − q ˉ + ⟩ . \langle a(q^+),q^+ - w^q\rangle= \beta[K_{\bar q}(w^q) - K_{\bar q^+}(w^q) - K_{\bar q}(\bar q^+) - K_{\bar q}(q^+)] + \langle a(q^+) - a(\bar q),q^+ - \bar q^+\rangle. ⟨ a ( q + ) , q + − w q ⟩ = β [ K q ˉ ( w q ) − K q ˉ + ( w q ) − K q ˉ ( q ˉ + ) − K q ˉ ( q + )] + ⟨ a ( q + ) − a ( q ˉ ) , q + − q ˉ + ⟩ . By (5.4) the last term is at most α [ K q ˉ ( q + ) + K q + ( q ˉ + ) ] \alpha[K_{\bar q}(q^+) + K_{q^+}(\bar q^+)] α [ K q ˉ ( q + ) + K q + ( q ˉ + )] , which is absorbed since β ≥ α \beta\ge\alpha β ≥ α . Conclude as in Theorem 5.5.
In the extragradient stage of Algorithm 3, α / β = 1 / 2 \alpha/\beta= 1/2 α / β = 1/2 . The term α log ( h / q ) \alpha\log(h/q) α log ( h / q ) in a ( h ) a(h) a ( h ) therefore gives the square-root factors in the two distribution updates.
Convergence analysis
Our proof adapts the potential argument of Jambulapati and Tian [30 Corollary 1] to the regularizer R α R_{\alpha} R α and the product of vertex simplices Q Q Q . We use the update inequalities established in § 5.2 , bound the initial potential for our initialization, and translate the resulting bound into an accepted-mass guarantee.
For each fixed comparison point w w w , we bound the accumulated quantity ∑ t < T ⟨ g ( z t ′ ) , z t ′ − w ⟩ \sum_{t<T}\langle g(z'_t),z'_t-w\rangle ∑ t < T ⟨ g ( z t ′ ) , z t ′ − w ⟩ by changes in a potential. The identity (7) then translates this bound into an accepted-mass guarantee. The potential combines divergences for the main and auxiliary states.
For z t = ( x t , q t ) z_t=(x_t,q_t) z t = ( x t , q t ) and z t ′ = ( x t ′ , q t ′ ) z'_t=(x'_t,q'_t) z t ′ = ( x t ′ , q t ′ ) let Φ t ( w ) = D z t 32 ( w ) + 64 K q ˉ t ( w q ) \Phi_t(w)=D^{32}_{z_t}(w)+64K_{\bar q_t}(w^q) Φ t ( w ) = D z t 32 ( w ) + 64 K q ˉ t ( w q ) .
Lemma 5.7 (Per-round regret; cf. [30 Lemma 2] ). For all w ∈ Z w\in Z w ∈ Z and all t t t , η ⟨ g ( z t ′ ) , z t ′ − w ⟩ ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) \eta\langle g(z'_t),z'_t-w\rangle\le2\Phi_t(w)-2\Phi_{t+1}(w) η ⟨ g ( z t ′ ) , z t ′ − w ⟩ ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) .
Proof. Write z = z t z=z_t z = z t , z ′ = z t ′ z'=z'_t z ′ = z t ′ , z + = z t + 1 z^+=z_{t+1} z + = z t + 1 . Theorem 5.5 with comparator z + z^+ z + , and twice Theorem 5.6 with comparator w w w , give
⟨ η g ( z ) , z ′ − z + ⟩ ≤ D z 32 ( z + ) − D z ′ 16 ( z + ) − D z 16 ( z ′ ) , ⟨ η g ( z ′ ) , z + − w ⟩ ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) − 2 D z 32 ( z + ) . \begin{aligned}
\langle\eta g(z),z'-z^+\rangle&\le D^{32}_z(z^+)-D^{16}_{z'}(z^+)-D^{16}_z(z'),\\
\langle\eta g(z'),z^+-w\rangle&\le2\Phi_t(w)-2\Phi_{t+1}(w)-2D^{32}_z(z^+).
\end{aligned} ⟨ η g ( z ) , z ′ − z + ⟩ ⟨ η g ( z ′ ) , z + − w ⟩ ≤ D z 32 ( z + ) − D z ′ 16 ( z + ) − D z 16 ( z ′ ) , ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) − 2 D z 32 ( z + ) .
Adding these and η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ \eta\langle g(z')-g(z),z'-z^+\rangle η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ gives η ⟨ g ( z ′ ) , z ′ − w ⟩ \eta\langle g(z'),z'-w\rangle η ⟨ g ( z ′ ) , z ′ − w ⟩ on the left. The excess on the right is at most η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ − D z ′ 16 ( z ′ ) − D z 32 ( z + ) ≤ 0 \eta\langle g(z')-g(z),z'-z^+\rangle-D^{16}_{z'}(z')-D^{32}_z(z^+)\le0 η ⟨ g ( z ′ ) − g ( z ) , z ′ − z + ⟩ − D z ′ 16 ( z ′ ) − D z 32 ( z + ) ≤ 0 by (11) and D z 32 ≥ D z 16 D^{32}_z\ge D^{16}_z D z 32 ≥ D z 16 . □
Lemma 5.8 (Initial potential). Let q ∗ q^* q ∗ be the comparison distributions constructed in Theorem 3.1(c). If y ∈ { − 1 , 1 } V y\in\{-1,1\}^{V} y ∈ { − 1 , 1 } V has at most 2 ν f ( G ) 2\nu_f(G) 2 ν f ( G ) positive coordinates among the nonisolated vertices, then Φ 0 ( y , q ∗ ) ≤ B Δ ν f ( G ) \Phi_0(y,q^*)\le B\Delta\nu_f(G) Φ 0 ( y , q ∗ ) ≤ B Δ ν f ( G ) .
Proof. Write b = − 1 + 1 / Δ b=-1+1/\Delta b = − 1 + 1/Δ and ν = ν f ( G ) \nu=\nu_f(G) ν = ν f ( G ) within this proof. The comparison loads lie in { 0 , 1 } \{0,1\} { 0 , 1 } and sum to 2 ν 2\nu 2 ν . The initial total load satisfies
μ 0 : = ∑ v ℓ v ( q 0 ) = ∣ E ∣ Δ 2 ≤ ν , \mu_0:=\sum_v \ell_v(q_0)=\frac{|E|}{\Delta^2}\le\nu, μ 0 := v ∑ ℓ v ( q 0 ) = Δ 2 ∣ E ∣ ≤ ν ,
using Theorem 2.4 and Δ ≥ 2 \Delta\ge2 Δ ≥ 2 . For the scalar Bregman divergence d ψ ( y , b ) = ψ ( y ) − ψ ( b ) − ψ ′ ( b ) ( y − b ) d_{\psi}(y,b)=\psi(y)-\psi(b)-\psi'(b)(y-b) d ψ ( y , b ) = ψ ( y ) − ψ ( b ) − ψ ′ ( b ) ( y − b ) , direct substitution gives
d ψ ( − 1 , b ) = − log ( 1 − 1 2 Δ ) ≤ 1 Δ , d ψ ( 1 , b ) = log ( 2 Δ ) . d_{\psi}(-1,b)=-\log\left(1-\frac{1}{2\Delta}\right)\le\frac{1}{\Delta},\qquad d_{\psi}(1,b)=\log(2\Delta). d ψ ( − 1 , b ) = − log ( 1 − 2Δ 1 ) ≤ Δ 1 , d ψ ( 1 , b ) = log ( 2Δ ) .
Thus most coordinates can be compared with − 1 -1 − 1 cheaply; only the at most 2 ν 2\nu 2 ν positive coordinates pay a logarithmic cost.
Expanding the potential, with sums over nonisolated vertices, gives
Φ 0 ( y , q ∗ ) = 2 ∑ v ( 1 + ℓ v ( q ∗ ) ) d ψ ( y v , b ) + 2 ψ ′ ( b ) ∑ v ( ℓ v ( q ∗ ) − ℓ v ( q 0 ) ) ( y v − b ) + 96 K q 0 ( q ∗ ) . \Phi_0(y,q^*)=2\sum_v(1+\ell_v(q^*))d_{\psi}(y_v,b)+2\psi'(b)\sum_v(\ell_v(q^*)-\ell_v(q_0))(y_v-b)+96K_{q_0}(q^*). Φ 0 ( y , q ∗ ) = 2 v ∑ ( 1 + ℓ v ( q ∗ )) d ψ ( y v , b ) + 2 ψ ′ ( b ) v ∑ ( ℓ v ( q ∗ ) − ℓ v ( q 0 )) ( y v − b ) + 96 K q 0 ( q ∗ ) .
The first term is at most 8 ν + 8 ν log ( 2 Δ ) 8\nu+8\nu\log(2\Delta) 8 ν + 8 ν log ( 2Δ ) : use n 0 ≤ 2 Δ ν n_0\le2\Delta\nu n 0 ≤ 2Δ ν for negative coordinates and 1 + ℓ v ( q ∗ ) ≤ 2 1+\ell_v(q^*)\le2 1 + ℓ v ( q ∗ ) ≤ 2 for positive ones. The absolute value of the second term is at most 6 ν log ( 2 Δ ) 6\nu\log(2\Delta) 6 ν log ( 2Δ ) , since ∣ y v − b ∣ ≤ 2 |y_v-b|\le2 ∣ y v − b ∣ ≤ 2 , 2 ∣ ψ ′ ( b ) ∣ = log ( 2 Δ − 1 ) 2|\psi'(b)|=\log(2\Delta-1) 2∣ ψ ′ ( b ) ∣ = log ( 2Δ − 1 ) , and the two total loads are at most 2 ν 2\nu 2 ν and ν \nu ν .
Finally, q ∗ q^* q ∗ assigns mass one to 2 ν 2\nu 2 ν real coordinates; the remaining mass is on dummies. Therefore
K q 0 ( q ∗ ) ≤ 2 ν log ( 2 Δ 2 ) + ∑ u − log ( 1 − deg ( u ) 2 Δ 2 ) ≤ 2 ν log ( 2 Δ 2 ) + 2 ν . K_{q_0}(q^*) \le2\nu\log(2\Delta^2) + \sum_u -\log\left(1-\frac{\deg(u)}{2\Delta^2}\right) \le2\nu\log(2\Delta^2)+2\nu. K q 0 ( q ∗ ) ≤ 2 ν log ( 2 Δ 2 ) + u ∑ − log ( 1 − 2 Δ 2 deg ( u ) ) ≤ 2 ν log ( 2 Δ 2 ) + 2 ν .
For the last step, use − log ( 1 − a ) ≤ 2 a -\log(1-a)\le2a − log ( 1 − a ) ≤ 2 a for 0 ≤ a ≤ 1 / 2 0\le a\le1/2 0 ≤ a ≤ 1/2 and ∑ u deg ( u ) / Δ 2 = 2 μ 0 \sum_u \deg(u)/\Delta^2=2\mu_0 ∑ u deg ( u ) / Δ 2 = 2 μ 0 . Combining the bounds gives Φ 0 ( y , q ∗ ) ≤ [ 200 + 398 log ( 2 Δ ) ] ν ≤ B Δ ν \Phi_0(y,q^*)\le[200+398\log(2\Delta)]\nu\le B\Delta\nu Φ 0 ( y , q ∗ ) ≤ [ 200 + 398 log ( 2Δ )] ν ≤ B Δ ν . □
Proof of Theorem 5.1 . Let q ∗ q^* q ∗ be as in Theorem 3.1(c). Choose the minimizing price w v x = 1 w_v^x=1 w v x = 1 when ℓ v ( q ^ ) > 1 \ell_v(\widehat q)>1 ℓ v ( q ) > 1 and w v x = − 1 w_v^x=-1 w v x = − 1 otherwise, and put w = ( w x , q ∗ ) w=(w^x,q^*) w = ( w x , q ∗ ) . The number of positive coordinates is at most P ( q ^ ) ≤ 2 ν f ( G ) P(\widehat q)\le2\nu f(G) P ( q ) ≤ 2 ν f ( G ) , so Theorem 5.8 applies. Summing Theorem 5.7 over t < T t<T t < T , using Φ T ( w ) ≥ 0 \Phi_T(w)\ge0 Φ T ( w ) ≥ 0 , (4.3), and the fact that F F F is affine in q q q , gives
η T [ 1 T ∑ t < T F ( x t ′ , q ∗ ) − F ( w x , q ^ ) ] ≤ 2 Φ 0 ( w ) . \eta T\left[\frac{1}{T}\sum_{t<T}F(x'_t,q^*)-F(w^x,\widehat q)\right]\le2\Phi_0(w). η T [ T 1 t < T ∑ F ( x t ′ , q ∗ ) − F ( w x , q ) ] ≤ 2 Φ 0 ( w ) .
By Theorem 3.1(b,c), the bracket is at least
( 4 ν f ( G ) − n 0 ) − ( 2 P ( q ^ ) − n 0 ) = 2 ( 2 ν f ( G ) − P ( q ^ ) ) . (4\nu f(G)-n_0)-(2P(\widehat q)-n_0)=2(2\nu f(G)-P(\widehat q)). ( 4 ν f ( G ) − n 0 ) − ( 2 P ( q ) − n 0 ) = 2 ( 2 ν f ( G ) − P ( q )) .
Therefore, using η = 1 / 3 \eta=1/3 η = 1/3 and Theorem 5.8,
2 ν f ( G ) − P ( q ^ ) ≤ Φ 0 ( w ) η T ≤ 3 B Δ ν f ( G ) T . 2\nu f(G)-P(\widehat q)\le\frac{\Phi_0(w)}{\eta T}\le\frac{3B\Delta\nu f(G)}{T}. 2 ν f ( G ) − P ( q ) ≤ η T Φ 0 ( w ) ≤ T 3 B Δ ν f ( G ) .
The lower bound follows from Theorem 3.1(a). □
Properties used by the sampler
We next show that each round changes proposal probabilities and loads by only constant factors. We also express the auxiliary proposal distributions through ratios to the main distributions. Together with Theorem 4.5, these bounds allow the sampler in § 6 to generate samples for each new round using an expected constant number of samples and coin flips from the preceding round.
We call the quantities negated in the exponential factors of the proposal updates the scores : a score c c c gives a multiplier e − c e^{-c} e − c . For the three proposal updates in Algorithm 3, the scores on a real coordinate ( u , v ) (u,v) ( u , v ) are
c u v = 1 16 [ 1 3 ( x v − 1 ) + 2 ( ψ ( x v ∗ ) − ψ ( x v ) ) ] (gradient stage), c_{uv}=\frac{1}{16}\left[\frac{1}{3}(x_v-1)+2\bigl(\psi(x_v^*)-\psi(x_v)\bigr)\right]
\qquad\text{(gradient stage),} c uv = 16 1 [ 3 1 ( x v − 1 ) + 2 ( ψ ( x v ∗ ) − ψ ( x v ) ) ] (gradient stage),
a u v = 1 64 [ 1 6 ( x v ′ − 1 ) + 2 ( ψ ( x a , v ) − ψ ( x v ) ) ] (extragradient stage, main distributions), a_{uv}=\frac{1}{64}\left[\frac{1}{6}(x'_v-1)+2\bigl(\psi(x_{a,v})-\psi(x_v)\bigr)\right]
\qquad\text{(extragradient stage, main distributions),} a uv = 64 1 [ 6 1 ( x v ′ − 1 ) + 2 ( ψ ( x a , v ) − ψ ( x v ) ) ] (extragradient stage, main distributions),
s ^ u v = 1 64 [ 1 6 ( x v ′ − 1 ) + 2 ( ψ ( x v + ) − ψ ( x v ) ) ] (extragradient stage, auxiliary distributions). \widehat{s}_{uv}=\frac{1}{64}\left[\frac{1}{6}(x'_v-1)+2\bigl(\psi(x_v^+)-\psi(x_v)\bigr)\right]
\qquad\text{(extragradient stage, auxiliary distributions).} s uv = 64 1 [ 6 1 ( x v ′ − 1 ) + 2 ( ψ ( x v + ) − ψ ( x v ) ) ] (extragradient stage, auxiliary distributions).
All three scores vanish on dummy coordinates.
For a vector c ∈ R I c\in\mathbb{R}^I c ∈ R I , define its oscillation by
osc ( c ) = max u ∈ V ( max a ∈ I u c u a − min a ∈ I u c u a ) . \operatorname{osc}(c)=\max_{u\in V}\left(\max_{a\in I_u}c_{ua}-\min_{a\in I_u}c_{ua}\right). osc ( c ) = u ∈ V max ( a ∈ I u max c u a − a ∈ I u min c u a ) .
This is the largest range of coordinate values within a single vertex’s block. Adding the same constant to every coordinate in a block leaves the oscillation unchanged. This lets us ignore the additive constants introduced by per-vertex normalization when analyzing updates in logarithmic coordinates.
Define the coordinatewise ratio of the auxiliary to the main proposal distributions by
ρ t = q ˉ t / q t . \rho_t=\bar q_t/q_t. ρ t = q ˉ t / q t .
Lemma 5.9 (Bounded tilts). For all t t t :
(a) every coordinate of the scores satisfies ∣ a ∣ , ∣ s ^ ∣ < 1 / 24 |a|, |\hat{s}| < 1/24 ∣ a ∣ , ∣ s ^ ∣ < 1/24 , hence ∣ 3 2 a − s ^ ∣ < 5 / 48 |\frac{3}{2}a-\hat{s}| < 5/48 ∣ 2 3 a − s ^ ∣ < 5/48 , and the gradient-stage score lies in ( − 1 / 6 , 1 / 8 ) (-1/6,1/8) ( − 1/6 , 1/8 ) ;
(b) osc ( log ρ t ) ≤ 5 / 18 \operatorname{osc}(\log\rho_t) \le5/18 osc ( log ρ t ) ≤ 5/18 ;
(c) every coordinate of q ˉ t / q t \bar{q}_t/q_t q ˉ t / q t , q t ′ / q t q'_t/q_t q t ′ / q t , q t + 1 / q t q_{t+1}/q_t q t + 1 / q t and q ˉ t + 1 / q ˉ t \bar{q}_{t+1}/\bar{q}_t q ˉ t + 1 / q ˉ t lies in [ e − 1 , e ] [e^{-1},e] [ e − 1 , e ] , and so does the corresponding load ratio at every nonisolated vertex.
Proof. (a) All prices appearing in the updates lie in ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) , and their regularizer values lie in [ 0 , log 2 ] ⊆ [ 0 , 1 ] [0,\log2] \subseteq[0,1] [ 0 , log 2 ] ⊆ [ 0 , 1 ] . The bounds follow from the score formulas above.
(b) In logarithmic coordinates, normalization adds a constant within each vertex’s block. Thus the main update gives
log ( q t + 1 / q t ) = 1 2 log ρ t − a + block constants . \log(q_{t+1}/q_t) = \frac{1}{2}\log\rho_t-a+\text{block constants}. log ( q t + 1 / q t ) = 2 1 log ρ t − a + block constants . Substituting this into the auxiliary update gives
log ρ t + 1 = 1 4 log ρ t + 3 2 a − s ^ + block constants . \log\rho_{t+1} = \frac{1}{4}\log\rho_t+\frac{3}{2}a-\hat{s}+\text{block constants}. log ρ t + 1 = 4 1 log ρ t + 2 3 a − s ^ + block constants . Oscillation ignores these constants. By (a), osc ( a ) , osc ( s ^ ) < 1 / 12 \operatorname{osc}(a),\operatorname{osc}(\hat{s}) < 1/12 osc ( a ) , osc ( s ^ ) < 1/12 , so
osc ( log ρ t + 1 ) ≤ 1 4 osc ( log ρ t ) + 5 24 . \operatorname{osc}(\log\rho_{t+1}) \le\frac{1}{4}\operatorname{osc}(\log\rho_t)+\frac{5}{24}. osc ( log ρ t + 1 ) ≤ 4 1 osc ( log ρ t ) + 24 5 . Since ρ 0 = 1 \rho_0=1 ρ 0 = 1 , induction gives osc ( log ρ t ) ≤ 5 / 18 \operatorname{osc}(\log\rho_t) \le5/18 osc ( log ρ t ) ≤ 5/18 .
(c) For p , h ∈ Q ∘ p,h\in Q^\circ p , h ∈ Q ∘ , each block of log ( h / p ) \log(h/p) log ( h / p ) contains a nonnegative and a nonpositive coordinate, because both distributions sum to one on that block. Thus every coordinate has absolute value at most osc ( log ( h / p ) ) \operatorname{osc}(\log(h/p)) osc ( log ( h / p )) .
By (a), (b), and the update formulas, the relevant oscillations satisfy
osc ( log ( q ˉ t / q t ) ) ≤ 5 18 , \operatorname{osc}(\log(\bar{q}_t/q_t)) \le\frac{5}{18}, osc ( log ( q ˉ t / q t )) ≤ 18 5 , osc ( log ( q t ′ / q t ) ) ≤ 7 24 , \operatorname{osc}(\log(q'_t/q_t)) \le\frac{7}{24}, osc ( log ( q t ′ / q t )) ≤ 24 7 , osc ( log ( q t + 1 / q t ) ) ≤ 1 2 ⋅ 5 18 + 1 12 = 2 9 , \operatorname{osc}(\log(q_{t+1}/q_t)) \le\frac{1}{2}\cdot\frac{5}{18}+\frac{1}{12}=\frac{2}{9}, osc ( log ( q t + 1 / q t )) ≤ 2 1 ⋅ 18 5 + 12 1 = 9 2 , osc ( log ( q ˉ t + 1 / q ˉ t ) ) ≤ 1 2 ⋅ 2 9 + 1 12 = 7 36 . \operatorname{osc}(\log(\bar{q}_{t+1}/\bar{q}_t)) \le\frac{1}{2}\cdot\frac{2}{9}+\frac{1}{12}=\frac{7}{36}. osc ( log ( q ˉ t + 1 / q ˉ t )) ≤ 2 1 ⋅ 9 2 + 12 1 = 36 7 . All are below one, so exponentiating gives the coordinate ratio bounds. Finally, at a nonisolated vertex v v v ,
ℓ v ( h ) ℓ v ( p ) = ∑ u ∈ N ( v ) p u v ℓ v ( p ) h u v p u v \frac{\ell_v(h)}{\ell_v(p)}=\sum_{u\in N(v)}\frac{p_{uv}}{\ell_v(p)}\frac{h_{uv}}{p_{uv}} ℓ v ( p ) ℓ v ( h ) = u ∈ N ( v ) ∑ ℓ v ( p ) p uv p uv h uv is a weighted average of coordinate ratios, giving the same bounds for the load ratios. □ \square □
In every box response of a round, h ∈ { q , q ′ , q ˉ , q + } h\in\{q,q',\bar{q},q^+\} h ∈ { q , q ′ , q ˉ , q + } and k ∈ { q , q ′ } k\in\{q,q'\} k ∈ { q , q ′ } , all relative to the same base q q q . Thus Theorem 5.9(c) verifies the hypotheses of Theorem 4.5 for every response.
Proposition 5.10 (Reduced auxiliary update). Let ρ = q ˉ / q \rho=\bar{q}/q ρ = q ˉ / q . Then q + = N ( q ρ e − a ) q^+=\mathcal{N}(q\sqrt{\rho}e^{-a}) q + = N ( q ρ e − a ) and q ˉ + = q + ρ + \bar{q}^+=q^+\rho^+ q ˉ + = q + ρ + , where
W = ρ 1 / 4 e 3 2 a − s ^ , ρ u a + = W u a ∑ b ∈ I u q u b + W u b . W=\rho^{1/4}e^{\frac{3}{2}a-\hat{s}},\qquad\rho^+_{ua}=\frac{W_{ua}}{\sum_{b\in I_u}q^+_{ub}W_{ub}}. W = ρ 1/4 e 2 3 a − s ^ , ρ u a + = ∑ b ∈ I u q u b + W u b W u a .
Proof. On one block let Z = ∑ b q b ρ b e − a b Z=\sum_b q_b\sqrt{\rho_b}e^{-a_b} Z = ∑ b q b ρ b e − a b , so U a : = q a + / q a = ρ a e − a a / Z U_a:=q_a^+/q_a=\sqrt{\rho_a}e^{-a_a}/Z U a := q a + / q a = ρ a e − a a / Z . The auxiliary update divided by q a + q_a^+ q a + is proportional to ρ a U a − 3 / 2 e − s ^ a = Z 3 / 2 W a \rho_a U_a^{-3/2}e^{-\hat{s}_a}=Z^{3/2}W_a ρ a U a − 3/2 e − s ^ a = Z 3/2 W a . A ratio of two distributions has mean one under the denominator, which fixes the normalization.
Thus the sampler can represent the auxiliary proposal distributions by the ratio ρ t \rho_t ρ t to the main proposal distributions q t q_t q t , without a separate sampler for q ˉ t \bar{q}_t q ˉ t .
Exact local sampling
We now implement a recursive sampler from the proposal distributions of § 5 . Given a vertex u u u , the sampler returns one exact draw from the averaged distribution q ^ u \hat{q}_u q ^ u , without computing that distribution or the optimization state.
The sampling algorithm follows a simple rule: draw from the previous proposal distribution and correct the draw by rejection sampling. The bounds of § 5.4 ensure that each trial succeeds with probability at least an absolute constant. The additional ingredient that we need is a way to make the acceptance decision without computing its probability.
To see the idea, consider a bounded reweighting of q q q to obtain h h h at vertex u u u :
h u a = q u a A u a Z u , Z u = ∑ b ∈ I u q u b A u b , κ ≤ A u a ≤ 1 , (19) h_{ua}=\frac{q_{ua}A_{ua}}{Z_u}, \qquad Z_u=\sum_{b\in I_u}q_{ub}A_{ub}, \qquad\kappa\le A_{ua}\le1, \tag*{(19)} h u a = Z u q u a A u a , Z u = b ∈ I u ∑ q u b A u b , κ ≤ A u a ≤ 1 , (19)
where κ > 0 \kappa>0 κ > 0 is an absolute constant. If the weights were available numerically, we could sample h u h_u h u as follows:
Draw a ∼ q u a\sim q_u a ∼ q u and an independent U ∼ Unif [ 0 , 1 ] U\sim\operatorname{Unif}[0,1] U ∼ Unif [ 0 , 1 ] .
Return a a a if U ≤ A u a U\le A_{ua} U ≤ A u a ; otherwise repeat.
A trial accepts and returns a a a with probability q u a A u a q_{ua}A_{ua} q u a A u a , so the accepted draw has law h u h_u h u . The acceptance probability is Z u ≥ κ Z_u\ge\kappa Z u ≥ κ , giving at most 1 / κ 1/\kappa 1/ κ trials in expectation. There is no need to compute the normalizer Z u Z_u Z u .
Computing the weight A u a A_{ua} A u a exactly is the obstacle: Our update formulas depend on prices and loads, and evaluating even one load ℓ v ( q ) = ∑ u ∈ N ( v ) q u v \ell_v(q)=\sum_{u\in N(v)}q_{uv} ℓ v ( q ) = ∑ u ∈ N ( v ) q uv can require a recursive evaluation for every neighbor. This can introduce Δ \Delta Δ -fold branching, whereas we seek constant expected branching in our recursive sampler.
We replace the acceptance test in step (2) by a procedure that returns one with probability exactly A u a A_{ua} A u a , using fresh flips of previously available coins. Bernoulli factories (§ 6.1 ) let us construct this acceptance coin with an expected constant number of input flips, without computing its bias.
Our sampler follows the optimization round by round, representing distributions by samplers and numerical quantities by coins. Assume recursively that the preceding round’s samplers and coins are available. We implement the scalar update formulas by Bernoulli factories, which construct new coin procedures from the available ones. For the reweighting in (19) , we combine a draw a ∼ q u a\sim q_u a ∼ q u with the newly constructed acceptance coin, repeating with fresh randomness until acceptance. The resulting sampler for h u h_u h u is then available for subsequent updates.
Each input-coin flip may itself invoke earlier coins or samplers. We show below that producing one sample or coin flip for a new round uses an expected constant number of calls to the preceding round’s procedures. This yields the constant expected branching that we seek. The total cost is obtained by expanding these calls recursively. § 6.4 specifies the sampler; § 6.5 proves its exactness, and § 6.6 bounds its query cost and arithmetic work.
Bernoulli factories
A p p p -coin is a procedure returning an independent Bern ( p ) \operatorname{Bern}(p) Bern ( p ) bit on each call. A Bernoulli factory for a function f f f constructs an f ( p 1 , … , p k ) f(p_1,\ldots,p_k) f ( p 1 , … , p k ) -coin using independent flips of input p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k -coins and auxiliary randomness, without knowing the input biases.
The next two lemmas give factory constructions for two classes of functions: fixed elementary formulas and smooth functions of one variable. Under their respective assumptions, each construction uses an expected constant number of input flips and expected constant additional work.1 The constructions simulate the acceptance decision directly, without estimating the unknown biases of the input coins.
The elementary-formula construction combines the linear Bernoulli factory of Huber [29 ] , the fractional-power factory of Mendo [43 ] , and operations on bounded unbiased random variables. Both proofs are in Section A.
Lemma 6.1 (Elementary-formula factories). Let Φ ( p 1 , … , p k ) \Phi(p_1,\ldots,p_k) Φ ( p 1 , … , p k ) be a fixed finite formula built from input coordinates and real constants using addition, subtraction, multiplication, division, exponentials, square roots, and fourth roots. Let S ⊆ [ 0 , 1 ] k S \subseteq[0,1]^k S ⊆ [ 0 , 1 ] k be a set of valid inputs. Suppose that, for known constants β > 0 \beta> 0 β > 0 and 0 < γ < 1 / 2 0 < \gamma< 1/2 0 < γ < 1/2 , every p ∈ S p \in S p ∈ S satisfies:
(a) every denominator and every root argument in the formula is at least β \beta β ;
(b) Φ ( p ) ∈ [ γ , 1 − γ ] \Phi(p) \in[\gamma,1-\gamma] Φ ( p ) ∈ [ γ , 1 − γ ] .
Given independent coins of biases p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k , with p ∈ S p \in S p ∈ S , there is an exact Φ ( p ) \Phi(p) Φ ( p ) -coin that terminates almost surely. Its expected number of input flips and expected additional work are bounded by constants depending only on Φ \Phi Φ , β \beta β , γ \gamma γ , uniformly over p ∈ S p \in S p ∈ S .
Lemma 6.2 (Smooth one-variable factory; cf. [28 , 44 ] ). Fix 0 < γ < 1 / 2 0 < \gamma< 1/2 0 < γ < 1/2 and a function f : [ 0 , 1 ] → [ γ , 1 − γ ] f : [0,1] \to[\gamma,1-\gamma] f : [ 0 , 1 ] → [ γ , 1 − γ ] with four continuous derivatives on [ 0 , 1 ] [0,1] [ 0 , 1 ] (a C 4 C^4 C 4 function). Suppose bounds on these derivatives are known, and f f f and f ′ ′ f'' f ′′ have fixed formulas that can be evaluated in constant work at rational points. Given independent flips of a p p p -coin, there is an exact f ( p ) f(p) f ( p ) -coin that terminates almost surely and uses an expected constant number of input flips and expected constant additional work. These constants depend only on f f f and γ \gamma γ , not on p p p .
The factory constructions simulate the acceptance decision directly, without estimating the unknown biases. Our applications below use a fixed formula with a fixed number of inputs, so the expected number of calls is an absolute constant.
Coin notation and the box response
This subsection specifies Box λ \operatorname{Box}_\lambda Box λ , the coin implementation of the price response Resp \operatorname{Resp} Resp from Algorithm 1. We first make explicit how each input and output coin represents its quantity.
Coins and their biases. We write C : Coin [ p ] C : \operatorname{Coin}[p] C : Coin [ p ] to mean that each call to C C C , called a flip , returns an independent Bern ( p ) \operatorname{Bern}(p) Bern ( p ) bit. The expression p p p specifies the bias; its numerical value need not be known. In pseudocode, an assignment C ← Coin [ f ( p 1 , … , p k ) ] C \leftarrow\operatorname{Coin}[f(p_1,\ldots,p_k)] C ← Coin [ f ( p 1 , … , p k )] defines a new coin procedure using the appropriate factory and the indicated input coins.
For a bounded quantity b ∈ [ − 1 , 1 ] b \in[-1,1] b ∈ [ − 1 , 1 ] , define enc ( b ) = ( b + 2 ) / 4 \operatorname{enc}(b)=(b+2)/4 enc ( b ) = ( b + 2 ) /4 . Thus Coin [ enc ( b ) ] \operatorname{Coin}[\operatorname{enc}(b)] Coin [ enc ( b )] represents b b b with a bias in [ 1 / 4 , 3 / 4 ] [1/4,3/4] [ 1/4 , 3/4 ] . Other quantities, including load ratios, use the biases specified explicitly below. For the rest of this section, fix κ = 1 / 64 \kappa=1/64 κ = 1/64 . The reweighting factors A u a A_{ua} A u a used below lie in [ κ , 1 − κ ] [\kappa,1-\kappa] [ κ , 1 − κ ] , and all load-ratio coins will have bias κ \kappa κ times the ratio. These encodings specify the factory formulas: a bounded quantity is replaced by 4 p − 2 4p-2 4 p − 2 and a load ratio by p / κ p/\kappa p / κ , where p p p is the corresponding input bias.
Representing the price. By (13) , the box response updates the transformed price by
τ ′ = A τ + B , τ = atanh x , τ ′ = atanh y . \tau' = A\tau+B,\qquad\tau=\operatorname{atanh}x,\qquad\tau'=\operatorname{atanh}y. τ ′ = A τ + B , τ = atanh x , τ ′ = atanh y .
with A , B A,B A , B as defined in Algorithm 1. Although x , y ∈ ( − 1 , 1 ) x,y\in(-1,1) x , y ∈ ( − 1 , 1 ) , their transformed values need not have a uniform constant bound. We therefore represent τ \tau τ by the bounded pair
ξ = τ 1 + τ 2 , σ = 1 1 + τ 2 , ξ 2 + σ 2 = 1. (20) \xi=\frac{\tau}{\sqrt{1+\tau^2}},\qquad\sigma=\frac{1}{\sqrt{1+\tau^2}},\qquad\xi^2+\sigma^2=1. \tag*{(20)} ξ = 1 + τ 2 τ , σ = 1 + τ 2 1 , ξ 2 + σ 2 = 1. (20)
Since τ = ξ / σ \tau=\xi/\sigma τ = ξ / σ , this pair determines the price.
The box-response interface. Fix a nonisolated vertex j j j and use the load parameters r , z h , z k r,z_h,z_k r , z h , z k from (14) , suppressing the vertex subscript. The routine
Box λ ( Ξ , S , R ; L h , L k ) (21) \operatorname{Box}_{\lambda}(\Xi,S,R;L_h,L_k) \tag*{(21)} Box λ ( Ξ , S , R ; L h , L k ) (21)
takes five coin procedures and the known step size λ ∈ { 1 / 3 , 1 / 6 } \lambda\in\{1/3,1/6\} λ ∈ { 1/3 , 1/6 } . Their types are
Ξ : Coin [ enc ( ξ ) ] , S : Coin [ enc ( σ ) ] , R : Coin [ enc ( r ) ] , \Xi:\operatorname{Coin}[\operatorname{enc}(\xi)],\quad S:\operatorname{Coin}[\operatorname{enc}(\sigma)],\quad R:\operatorname{Coin}[\operatorname{enc}(r)], Ξ : Coin [ enc ( ξ )] , S : Coin [ enc ( σ )] , R : Coin [ enc ( r )] ,
L h : Coin [ κ z h ] , L k : Coin [ κ z k ] . L_h:\operatorname{Coin}[\kappa z_h],\quad L_k:\operatorname{Coin}[\kappa z_k]. L h : Coin [ κ z h ] , L k : Coin [ κ z k ] .
The semicolon separates the base-state coins from the load-ratio coins. In particular, a ratio equal to 1 is represented by the known coin L 1 : Coin [ κ ] L_1:\operatorname{Coin}[\kappa] L 1 : Coin [ κ ] .
Let y y y be the corresponding price returned by Resp z , v ( h ) \operatorname{Resp}_{z,v}(h) Resp z , v ( h ) , with v x = λ ( 1 − L k ) v^x=\lambda(1-L_k) v x = λ ( 1 − L k ) . The routine returns
( Ξ ′ , S ′ , X ′ , V ′ ) (\Xi',S',X',V') ( Ξ ′ , S ′ , X ′ , V ′ )
with respective biases
enc ( ξ ′ ) , enc ( σ ′ ) , enc ( y ) , enc ( ψ ( y ) ) . \operatorname{enc}(\xi'),\qquad\operatorname{enc}(\sigma'),\qquad\operatorname{enc}(y),\qquad\operatorname{enc}(\psi(y)). enc ( ξ ′ ) , enc ( σ ′ ) , enc ( y ) , enc ( ψ ( y )) .
Here ( ξ ′ , σ ′ ) (\xi',\sigma') ( ξ ′ , σ ′ ) is the bounded representation (20) of atanh y \operatorname{atanh}y atanh y .
Defining the output coins. We first rewrite the price update τ ′ = A τ + B \tau'=A\tau+B τ ′ = A τ + B from (13) as an update of the bounded pair in (20) . Since τ = ξ / σ \tau=\xi/\sigma τ = ξ / σ , we have τ ′ = ( A ξ + B σ ) / σ \tau'=(A\xi+B\sigma)/\sigma τ ′ = ( A ξ + B σ ) / σ . Applying (20) to τ ′ \tau' τ ′ gives
u = A ξ + B σ , ( ξ ′ , σ ′ ) = ( u , σ ) u 2 + σ 2 . (22) u=A\xi+B\sigma,\qquad(\xi',\sigma')=\frac{(u,\sigma)}{\sqrt{u^2+\sigma^2}}. \tag*{(22)} u = A ξ + B σ , ( ξ ′ , σ ′ ) = u 2 + σ 2 ( u , σ ) . (22)
Substituting the expressions for A A A and B B B from Theorem 4.5 writes this update in terms of the load parameters r , z h , z k r,z_h,z_k r , z h , z k from (14) :
w = 1 − r + r z h , u = ξ + λ 2 ( r ( z k + 1 ) − 1 ) σ w , D = u 2 + σ 2 , w=1-r+rz_h,\qquad u=\frac{\xi+\frac{\lambda}{2}\bigl(r(z_k+1)-1\bigr)\sigma}{w},\qquad D=\sqrt{u^2+\sigma^2}, w = 1 − r + r z h , u = w ξ + 2 λ ( r ( z k + 1 ) − 1 ) σ , D = u 2 + σ 2 ,
ξ ′ = u / D , σ ′ = σ / D . (23) \xi'=u/D,\qquad\sigma'=\sigma/D. \tag*{(23)} ξ ′ = u / D , σ ′ = σ / D . (23)
The elementary-formula factory in Theorem 6.1 constructs Ξ ′ , S ′ \Xi', S' Ξ ′ , S ′ with these encoding biases. The smooth one-variable factory in Theorem 6.2 then constructs X ′ , V ′ X', V' X ′ , V ′ from Ξ ′ \Xi' Ξ ′ . In § 6.5 , we give the two conversion functions and verify the conditions needed to apply both factory lemmas, including the lower bounds on denominators and root arguments and the smoothness of the conversion functions. This proves the following guarantee.
Lemma 6.3 (Box-response coins). For every box response used by the optimizer, Box λ \operatorname{Box}_{\lambda} Box λ supplies the four coin procedures specified above, with their exact biases. Each output flip uses an expected constant number of input-coin flips and expected constant additional work, uniformly over all such responses.
Samplers for a reweighted distribution
The routine Tilt implements one proposal reweighting. Fix any q ∈ Q ∘ q \in Q^{\circ} q ∈ Q ∘ and weights A u a ∈ [ κ , 1 − κ ] A_{ua} \in[\kappa,1-\kappa] A u a ∈ [ κ , 1 − κ ] , and let q u + = N ( q u A u a ) q_u^+ = \mathcal{N}(q_u A_{ua}) q u + = N ( q u A u a ) . Write Out q ( u ) \operatorname{Out}_q(u) Out q ( u ) for a draw from q u q_u q u . For nonisolated v v v , In q ( v ) \operatorname{In}_q(v) In q ( v ) draws u ∈ N ( v ) u \in N(v) u ∈ N ( v ) with probability q u v / ℓ v ( q ) q_{uv}/\ell_v(q) q uv / ℓ v ( q ) .
Given these two samplers and acceptance coins A ( u , a ) : Coin [ A u a ] A(u,a):\operatorname{Coin}[A_{ua}] A ( u , a ) : Coin [ A u a ] , the routine returns
( Out q + , In q + , L ) ← Tilt ( Out q , In q , A ) , (24) (\operatorname{Out}_{q^+},\operatorname{In}_{q^+},L) \leftarrow\operatorname{Tilt}(\operatorname{Out}_q,\operatorname{In}_q,A), \tag*{(24)} ( Out q + , In q + , L ) ← Tilt ( Out q , In q , A ) , (24)
where L ( v ) L(v) L ( v ) has bias κ ℓ v ( q + ) / ℓ v ( q ) \kappa\ell_v(q^+)/\ell_v(q) κ ℓ v ( q + ) / ℓ v ( q ) .
Incoming samples provide load-ratio coins through the identity
ℓ v ( q + ) ℓ v ( q ) = E u ∼ In q ( v ) [ q u v + q u v ] . (25) \frac{\ell_v(q^+)}{\ell_v(q)} = \mathbb{E}_{u\sim\operatorname{In}_q(v)}\left[\frac{q_{uv}^+}{q_{uv}}\right]. \tag*{(25)} ℓ v ( q ) ℓ v ( q + ) = E u ∼ In q ( v ) [ q uv q uv + ] . (25)
Thus one call to In q ( v ) \operatorname{In}_q(v) In q ( v ) followed by a coin flip with bias κ q u v + / q u v \kappa q_{uv}^+/q_{uv} κ q uv + / q uv gives the required load-ratio coin, without evaluating either load.
Construction of Tilt. First define two helper coins. The normalizer coin Z ( u ) Z(u) Z ( u ) draws a ← Out q ( u ) a \leftarrow\operatorname{Out}_q(u) a ← Out q ( u ) and returns A ( u , a ) A(u,a) A ( u , a ) , so its bias is Z u = ∑ a q u a A u a Z_u=\sum_a q_{ua}A_{ua} Z u = ∑ a q u a A u a . The coordinate-ratio coin C ( u , a ) : Coin [ κ A u a / Z u ] C(u,a):\operatorname{Coin}[\kappa A_{ua}/Z_u] C ( u , a ) : Coin [ κ A u a / Z u ] uses Theorem 6.1 with input coins A ( u , a ) A(u,a) A ( u , a ) , Z ( u ) Z(u) Z ( u ) . Its bias is κ q u a + / q u a \kappa q_{ua}^+/q_{ua} κ q u a + / q u a .
The routine returns the following three procedures, each using fresh draws and flips when invoked:
(a) Out q + ( u ) \operatorname{Out}_{q^+}(u) Out q + ( u ) draws a ← Out q ( u ) a \leftarrow\operatorname{Out}_q(u) a ← Out q ( u ) and returns a a a if A ( u , a ) A(u,a) A ( u , a ) returns one; otherwise it repeats.
(b) In q + ( v ) \operatorname{In}_{q^+}(v) In q + ( v ) draws u ← In q ( v ) u \leftarrow\operatorname{In}_q(v) u ← In q ( v ) and returns u u u if C ( u , v ) C(u,v) C ( u , v ) returns one; otherwise it repeats.
(c) L ( v ) L(v) L ( v ) draws u ← In q ( v ) u \leftarrow\operatorname{In}_q(v) u ← In q ( v ) and returns the bit C ( u , v ) C(u,v) C ( u , v ) .
The next lemma gives the guarantee for this construction; its proof is in § 6.5 .
Lemma 6.4 (Bounded tilt). For every q ∈ Q ∘ q \in Q^{\circ} q ∈ Q ∘ and weights A u a ∈ [ κ , 1 − κ ] A_{ua} \in[\kappa,1-\kappa] A u a ∈ [ κ , 1 − κ ] , Tilt supplies Out q + , In q + , L \operatorname{Out}_{q^+},\operatorname{In}_{q^+},L Out q + , In q + , L with the specified laws. Each invocation of a returned procedure uses an expected O ( 1 ) O(1) O ( 1 ) calls to Out q , In q , A \operatorname{Out}_q,\operatorname{In}_q,A Out q , In q , A and expected O ( 1 ) O(1) O ( 1 ) additional work, uniformly over q q q , A A A and the queried vertex.
The recursive sampling round
We now implement one round of the optimizer in Algorithm 3 using Box λ \operatorname{Box}_{\lambda} Box λ from (21) and Tilt from (24) . Given the current samplers and coins, we construct a sampler for the proposal distribution q t ′ q'_t q t ′ produced by the gradient stage, and the samplers and coins representing the next state.
What a round receives and returns. Write S t S_t S t for the following family of procedures:
S t = ( Out t , In t , Ξ t , S t , X t , V t , R t , P t ) . (26) S_t = (\operatorname{Out}_t,\operatorname{In}_t,\Xi_t,S_t,X_t,V_t,R_t,P_t). \tag*{(26)} S t = ( Out t , In t , Ξ t , S t , X t , V t , R t , P t ) . (26)
Their laws are specified below, where r t , v = ℓ v ( q t ) / ( 1 + ℓ v ( q t ) ) r_{t,v}=\ell_v(q_t)/(1+\ell_v(q_t)) r t , v = ℓ v ( q t ) / ( 1 + ℓ v ( q t )) and ρ t = q ˉ t / q t \rho_t=\bar q_t/q_t ρ t = q ˉ t / q t .
Table 1.
One round defines
S t ⟼ ( Out t ′ , S t + 1 ) , Out t ′ ( u ) ∼ q t , u ′ . S_t \longmapsto(\operatorname{Out}'_t,S_{t+1}), \qquad\operatorname{Out}'_t(u)\sim q'_{t,u}. S t ⟼ ( Out t ′ , S t + 1 ) , Out t ′ ( u ) ∼ q t , u ′ .
Only S t + 1 S_{t+1} S t + 1 is passed to the next round. The other coins and samplers defined during the round serve its internal computations. All target laws are deterministic functions of G G G ; every invocation uses fresh independent randomness. Incoming samplers and state coins are needed only at nonisolated vertices.
Generating one proposal. To sample from the optimizer’s average proposal distribution, we choose a round t t t uniformly and draw from q t ′ q'_t q t ′ using Out t ′ \operatorname{Out}'_t Out t ′ . For 0 < δ < 1 0<\delta<1 0 < δ < 1 , let
T δ = ⌈ 3 B Δ δ ⌉ , q ( δ ) = 1 T δ ∑ t < T δ q t ′ . T_\delta=\left\lceil\frac{3B\Delta}{\delta}\right\rceil,\qquad q^{(\delta)}=\frac{1}{T_\delta}\sum_{t<T_\delta}q'_t. T δ = ⌈ δ 3 B Δ ⌉ , q ( δ ) = T δ 1 t < T δ ∑ q t ′ .
Algorithm 4: Out^(δ)(u): one exact proposal
Input: Vertex u, degree bound Δ, and accuracy δ.
Output: A neighbor or dummy with law q_u^(δ).
if deg(u) = 0 then return ⊥_u
T ← ⌈3B_Δ/δ⌉
Choose t uniformly from {0, ..., T − 1}
return Out′_t(u) // invoke the recursive procedure in Algorithm 5
An invocation evaluates only the procedures it calls, recursing to earlier rounds until it reaches the explicit initial procedures below. There is no loop over all vertices or preprocessing of the rounds. Internal rejection trials repeat until acceptance, so the output is one exact neighbor-or-dummy sample. The dummy is an ordinary outcome of the proposal distribution.
Initialization. After a degree query, Out 0 ( u ) \operatorname{Out}_0(u) Out 0 ( u ) returns a uniformly random neighbor with probability deg ( u ) / ( 2 Δ 2 ) \deg(u)/(2\Delta^2) deg ( u ) / ( 2 Δ 2 ) , and returns ⊥ u \bot_u ⊥ u otherwise. The sampler In 0 ( v ) \operatorname{In}_0(v) In 0 ( v ) returns a uniformly random neighbor. Since ℓ v ( q 0 ) = deg ( v ) / ( 2 Δ 2 ) \ell_v(q_0)=\deg(v)/(2\Delta^2) ℓ v ( q 0 ) = deg ( v ) / ( 2 Δ 2 ) , the bias of R 0 ( v ) R_0(v) R 0 ( v ) is known after one degree query. The initial transformed price is τ 0 = − 1 2 log ( 2 Δ − 1 ) \tau_0=-\frac{1}{2}\log(2\Delta-1) τ 0 = − 2 1 log ( 2Δ − 1 ) . It gives known biases for Ξ 0 \Xi_0 Ξ 0 , S 0 S_0 S 0 , X 0 X_0 X 0 , V 0 V_0 V 0 , while P 0 P_0 P 0 has bias 1 / ( 2 e ) 1/(2e) 1/ ( 2 e ) . Each initial procedure uses at most two graph queries and constant work.
How the four price responses are used. All four box calls use the interface (21) with the base coins Ξ ‾ t \overline{\Xi}_t Ξ t , S t S_t S t , R t R_t R t . The first response supplies the coin for ψ ( x ∗ ) \psi(x^*) ψ ( x ∗ ) used to reweight q t q_t q t into q t ′ q'_t q t ′ . The second supplies the tentative-price coin for x ′ x' x ′ used in the extragradient scores. The third supplies the coin for ψ ( x a ) \psi(x_a) ψ ( x a ) used in the main proposal update. The fourth supplies the price coins carried into S t + 1 S_{t+1} S t + 1 ; its coin for ψ ( x t + 1 ) \psi(x_{t+1}) ψ ( x t + 1 ) is also used in the auxiliary update.
For clarity, the three scores from § 5.4 are repeated here. On a real coordinate ( u , v ) (u,v) ( u , v ) they are
c u v g = 1 16 [ x t , v − 1 3 + 2 ( ψ ( x v ∗ ) − ψ ( x t , v ) ) ] , a u v = 1 64 [ x v ′ − 1 6 + 2 ( ψ ( x a , v ) − ψ ( x t , v ) ) ] , s ^ u v = 1 64 [ x v ′ − 1 6 + 2 ( ψ ( x t + 1 , v ) − ψ ( x t , v ) ) ] . (27) \begin{aligned}
c^g_{uv} &= \frac{1}{16}\left[\frac{x_{t,v}-1}{3}+2\left(\psi(x^*_v)-\psi(x_{t,v})\right)\right],\\
a_{uv} &= \frac{1}{64}\left[\frac{x'_v-1}{6}+2\left(\psi(x_{a,v})-\psi(x_{t,v})\right)\right],\\
\hat{s}_{uv} &= \frac{1}{64}\left[\frac{x'_v-1}{6}+2\left(\psi(x_{t+1,v})-\psi(x_{t,v})\right)\right]. \tag*{(27)}
\end{aligned} c uv g a uv s ^ uv = 16 1 [ 3 x t , v − 1 + 2 ( ψ ( x v ∗ ) − ψ ( x t , v ) ) ] , = 64 1 [ 6 x v ′ − 1 + 2 ( ψ ( x a , v ) − ψ ( x t , v ) ) ] , = 64 1 [ 6 x v ′ − 1 + 2 ( ψ ( x t + 1 , v ) − ψ ( x t , v ) ) ] . (27)
All three scores are zero on dummy coordinates. These formulas specify the biases of the acceptance coins; the scores are not evaluated numerically.
One round. Algorithm 5 gives the recursive definitions. A dash denotes an unused output procedure. Beside each acceptance-coin definition we list the coins whose biases occur in its formula. The known coin L 1 : Coin [ κ ] L_1:\operatorname{Coin}[\kappa] L 1 : Coin [ κ ] represents load ratio 1. The other load ratios are
z ′ = ℓ ( q t ′ ) ℓ ( q t ) , z ‾ = ℓ ( q ‾ t ) ℓ ( q t ) , z + = ℓ ( q t + 1 ) ℓ ( q t ) . z'=\frac{\ell(q'_t)}{\ell(q_t)},\qquad\overline{z}=\frac{\ell(\overline{q}_t)}{\ell(q_t)},\qquad z^+=\frac{\ell(q_{t+1})}{\ell(q_t)}. z ′ = ℓ ( q t ) ℓ ( q t ′ ) , z = ℓ ( q t ) ℓ ( q t ) , z + = ℓ ( q t ) ℓ ( q t + 1 ) .
All definitions are pointwise at the indicated vertex or proposal coordinate.
Algorithm 5: One sampling round: defining ( Out t ′ , S t + 1 ) (\operatorname{Out}'_t,S_{t+1}) ( Out t ′ , S t + 1 )
Input: The samplers and coins S t S_t S t in (26) .
Output: A sampler Out t ′ \operatorname{Out}'_t Out t ′ for q t ′ q'_t q t ′ , and the next family S t + 1 S_{t+1} S t + 1 .
Gradient stage: proposals q t ′ q'_t q t ′
( − , − , − , V ∗ ) ← Box 1 / 3 ( Ξ ‾ t , S t , R t ; L 1 , L 1 ) (\mathord{-},\mathord{-},\mathord{-},V^*)\leftarrow\operatorname{Box}_{1/3}(\overline{\Xi}_t,S_t,R_t;L_1,L_1) ( − , − , − , V ∗ ) ← Box 1/3 ( Ξ t , S t , R t ; L 1 , L 1 ) // (21)
A g ( u , a ) ← Coin [ e c u a g − 1 ] A^g(u,a)\leftarrow\operatorname{Coin}[e^{c^g_{ua}-1}] A g ( u , a ) ← Coin [ e c u a g − 1 ] // uses X t , V t , V ∗ X_t,V_t,V^* X t , V t , V ∗
( Out t ′ , − , L ′ ) ← Tilt ( Out t , Int t , A g ) (\operatorname{Out}'_t,\mathord{-},L')\leftarrow\operatorname{Tilt}(\operatorname{Out}_t,\operatorname{Int}_t,A^g) ( Out t ′ , − , L ′ ) ← Tilt ( Out t , Int t , A g ) // (24) ; L ′ : Coin [ κ z ′ ] L':\operatorname{Coin}[\kappa z'] L ′ : Coin [ κ z ′ ]
( − , − , X ′ , − ) ← Box 1 / 3 ( Ξ ‾ t , S t , R t ; L ′ , L 1 ) (\mathord{-},\mathord{-},X',\mathord{-})\leftarrow\operatorname{Box}_{1/3}(\overline{\Xi}_t,S_t,R_t;L',L_1) ( − , − , X ′ , − ) ← Box 1/3 ( Ξ t , S t , R t ; L ′ , L 1 )
Extragradient stage: next main state
Define L ‾ ( v ) \overline{L}(v) L ( v ) : draw u ← Int t ( v ) u\leftarrow\operatorname{Int}_t(v) u ← Int t ( v ) and return the product of the bit returned by P t ( u , v ) P_t(u,v) P t ( u , v ) and an independent Bern ( 2 e κ ) \operatorname{Bern}(2e\kappa) Bern ( 2 e κ ) bit // bias κ z ‾ v \kappa\overline{z}_v κ z v
( − , − , − , V a ) ← Box 1 / 6 ( Ξ ‾ t , S t , R t ; L ‾ , L ′ ) (\mathord{-},\mathord{-},\mathord{-},V_a)\leftarrow\operatorname{Box}_{1/6}(\overline{\Xi}_t,S_t,R_t;\overline{L},L') ( − , − , − , V a ) ← Box 1/6 ( Ξ t , S t , R t ; L , L ′ )
A m ( u , a ) ← Coin [ ρ t , u a 2 e e − a u a − 1 ] A^m(u,a)\leftarrow\operatorname{Coin}\left[\sqrt{\frac{\rho_{t,ua}}{2e}}e^{-a_{ua}-1}\right] A m ( u , a ) ← Coin [ 2 e ρ t , u a e − a u a − 1 ] // uses P t , X ′ , V a , V t P_t,X',V_a,V_t P t , X ′ , V a , V t
( Out t + 1 , Int t + 1 , L + ) ← Tilt ( Out t , Int t , A m ) (\operatorname{Out}_{t+1},\operatorname{Int}_{t+1},L^+)\leftarrow\operatorname{Tilt}(\operatorname{Out}_t,\operatorname{Int}_t,A^m) ( Out t + 1 , Int t + 1 , L + ) ← Tilt ( Out t , Int t , A m ) // L + : Coin [ κ z + ] L^+:\operatorname{Coin}[\kappa z^+] L + : Coin [ κ z + ]
( Ξ ‾ t + 1 , S t + 1 , X t + 1 , V t + 1 ) ← Box 1 / 6 ( Ξ ‾ t , S t , R t ; L + , L ′ ) (\overline{\Xi}_{t+1},S_{t+1},X_{t+1},V_{t+1})\leftarrow\operatorname{Box}_{1/6}(\overline{\Xi}_t,S_t,R_t;L^+,L') ( Ξ t + 1 , S t + 1 , X t + 1 , V t + 1 ) ← Box 1/6 ( Ξ t , S t , R t ; L + , L ′ )
R t + 1 ← Coin [ enc ( r z + 1 − r + r z + ) ] R_{t+1}\leftarrow\operatorname{Coin}\left[\operatorname{enc}\left(\frac{rz^+}{1-r+rz^+}\right)\right] R t + 1 ← Coin [ enc ( 1 − r + r z + r z + ) ] // uses R t , L + R_t,L^+ R t , L +
Extragradient stage: next auxiliary ratio
A ρ ( u , a ) ← Coin [ ( ρ t , u a 2 e ) 1 / 4 e 3 a u a / 2 − s ^ u a − 1 ] A^\rho(u,a)\leftarrow\operatorname{Coin}\left[\left(\frac{\rho_{t,ua}}{2e}\right)^{1/4}e^{3a_{ua}/2-\hat{s}_{ua}-1}\right] A ρ ( u , a ) ← Coin [ ( 2 e ρ t , u a ) 1/4 e 3 a u a /2 − s ^ u a − 1 ]
// Uses P t , X ′ , V a , V t , V t + 1 P_t,X',V_a,V_t,V_{t+1} P t , X ′ , V a , V t , V t + 1 .
Define Z ρ ( u ) Z^\rho(u) Z ρ ( u ) : draw a ← Out t + 1 ( u ) a\leftarrow\operatorname{Out}_{t+1}(u) a ← Out t + 1 ( u ) and return the bit from A ρ ( u , a ) A^\rho(u,a) A ρ ( u , a )
P t + 1 ( u , a ) ← Coin [ A u a ρ 2 e Z u ρ ] P_{t+1}(u,a)\leftarrow\operatorname{Coin}\left[\frac{A^\rho_{ua}}{2eZ^\rho_u}\right] P t + 1 ( u , a ) ← Coin [ 2 e Z u ρ A u a ρ ] // uses A ρ , Z ρ A^\rho,Z^\rho A ρ , Z ρ
return ( Out t ′ , S t + 1 ) (\operatorname{Out}'_t,S_{t+1}) ( Out t ′ , S t + 1 )
The extra known-probability flip in L ‾ \overline{L} L puts its bias on the same scale as L ′ L' L ′ and L + L^+ L + . The definitions of S t + 1 S_{t+1} S t + 1 refer to their input procedures, which are evaluated on demand in later invocations. No sampled bits are stored as the state.
Exactness of the recursive sampler
We first justify the two subroutine interfaces, then prove that their composition follows the optimizer exactly.
Box-response coins. The coefficient bounds from § 5.4 keep the normalization in (6.5) away from zero.
Lemma 6.5 (Bounded normalization). For every box response used by the optimizer,
1 400 ≤ u 2 + σ 2 ≤ 21. (28) \frac{1}{400} \le u^2 + \sigma^2 \le21. \tag*{(28)} 400 1 ≤ u 2 + σ 2 ≤ 21. (28) Proof. By Theorems 4.5 and 5.9, A ∈ [ e − 1 , e ] A \in[e^{-1},e] A ∈ [ e − 1 , e ] and ∣ B ∣ < 2 |B| < 2 ∣ B ∣ < 2 . Using ξ 2 + σ 2 = 1 \xi^2+\sigma^2=1 ξ 2 + σ 2 = 1 , Cauchy–Schwarz gives
u 2 + σ 2 ≤ A 2 + B 2 + 1 < 21. u^2+\sigma^2 \le A^2+B^2+1<21. u 2 + σ 2 ≤ A 2 + B 2 + 1 < 21. Conversely, ξ = ( u − B σ ) / A \xi=(u-B\sigma)/A ξ = ( u − B σ ) / A gives
1 ≤ ( 1 + B 2 A 2 + 1 ) ( u 2 + σ 2 ) ≤ ( 5 e 2 + 1 ) ( u 2 + σ 2 ) < 400 ( u 2 + σ 2 ) . 1 \le\left(\frac{1+B^2}{A^2}+1\right)(u^2+\sigma^2)\le(5e^2+1)(u^2+\sigma^2)<400(u^2+\sigma^2). 1 ≤ ( A 2 1 + B 2 + 1 ) ( u 2 + σ 2 ) ≤ ( 5 e 2 + 1 ) ( u 2 + σ 2 ) < 400 ( u 2 + σ 2 ) .
Proof of Theorem 6.3. The normalization represents the price response exactly: ξ ′ / σ ′ = A ξ / σ + B = τ ′ \xi'/\sigma'=A\xi/\sigma+B=\tau' ξ ′ / σ ′ = A ξ / σ + B = τ ′ . By Theorems 4.5 and 6.5, w ≥ e − 1 w\ge e^{-1} w ≥ e − 1 , the root argument is at least 1 / 400 1/400 1/400 , and D ≥ 1 / 20 D\ge1/20 D ≥ 1/20 . The output encoding biases lie in [ 1 / 4 , 3 / 4 ] [1/4,3/4] [ 1/4 , 3/4 ] , so Theorem 6.1 constructs Ξ ′ , Υ ′ \Xi',\Upsilon' Ξ ′ , Υ ′ .
To construct the price coins, use the fixed functions
ξ ↦ tanh ( ξ 1 − ξ 2 ) , ξ ↦ ψ ( tanh ( ξ 1 − ξ 2 ) ) . (29) \xi\mapsto\tanh\left(\frac{\xi}{\sqrt{1-\xi^2}}\right),\qquad
\xi\mapsto\psi\left(\tanh\left(\frac{\xi}{\sqrt{1-\xi^2}}\right)\right). \tag*{(29)} ξ ↦ tanh ( 1 − ξ 2 ξ ) , ξ ↦ ψ ( tanh ( 1 − ξ 2 ξ ) ) . (29)
Applied to ξ ′ \xi' ξ ′ , they give y y y and ψ ( y ) \psi(y) ψ ( y ) . At ξ = ± 1 \xi=\pm1 ξ = ± 1 and beyond, extend the first function by ± 1 \pm1 ± 1 , respectively, and the second by log 2 \log2 log 2 on both sides. These extensions are smooth. Indeed, writing τ = ξ / 1 − ξ 2 \tau=\xi/\sqrt{1-\xi^2} τ = ξ / 1 − ξ 2 gives
ψ ( tanh τ ) = τ tanh τ − log cosh τ . \psi(\tanh\tau)=\tau\tanh\tau-\log\cosh\tau. ψ ( tanh τ ) = τ tanh τ − log cosh τ .
Both functions approach their endpoint values exponentially fast in ∣ τ ∣ |\tau| ∣ τ ∣ . Differentiating with respect to ξ \xi ξ applies ( 1 + τ 2 ) 3 / 2 d / d τ (1+\tau^2)^{3/2}\,d/d\tau ( 1 + τ 2 ) 3/2 d / d τ , so every positive-order derivative still tends to zero at the endpoints. In particular, the extensions have four continuous derivatives with fixed bounds. Their values and second derivatives have fixed formulas, with the constant branches supplying the endpoint values and derivatives.
Applying either extended function to ξ = 4 p − 2 \xi=4p-2 ξ = 4 p − 2 and encoding the result gives a fixed smooth function of p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] with values in [ 1 / 4 , 3 / 4 ] [1/4,3/4] [ 1/4 , 3/4 ] . Thus Theorem 6.2 constructs X ′ , V ′ X',V' X ′ , V ′ from Ξ ′ \Xi' Ξ ′ . Each factory has constant expected input and additional cost, as does their composition.
Updating proposal samplers. The bounded-tilt routine combines the rejection step with the load-ratio identity (25) .
Proof of Theorem 6.4. The outgoing sampler is the rejection step in (19) . Its acceptance probability is Z u Z_u Z u , which is also the bias of Z ( u ) Z(u) Z ( u ) . Since A u a , Z u ∈ [ κ , 1 − κ ] A_{ua}, Z_u \in[\kappa, 1-\kappa] A u a , Z u ∈ [ κ , 1 − κ ] , the bias of C ( u , a ) C(u,a) C ( u , a ) satisfies
κ 2 ≤ κ A u a Z u ≤ 1 − κ . \kappa^2 \le\frac{\kappa A_{ua}}{Z_u} \le1-\kappa. κ 2 ≤ Z u κ A u a ≤ 1 − κ .
The denominator is at least κ \kappa κ , and the bias has margin at least κ 2 \kappa^2 κ 2 from both endpoints. Thus Theorem 6.1 applies with constant parameters. An incoming trial accepts u u u with mass
q u v ℓ v ( q ) q u v + q u v = κ q u v + ℓ v ( q ) . \frac{q_{uv}}{\ell_v(q)} \frac{q_{uv}^{+}}{q_{uv}} = \frac{\kappa q_{uv}^{+}}{\ell_v(q)}. ℓ v ( q ) q uv q uv q uv + = ℓ v ( q ) κ q uv + .
Its conditional law is In q + ( v ) \operatorname{In}_{q^{+}}(v) In q + ( v ) . Its acceptance probability, also the bias of L ( v ) L(v) L ( v ) , is κ ℓ v ( q + ) / ℓ v ( q ) ≥ κ 2 \kappa\ell_v(q^{+})/\ell_v(q) \ge\kappa^2 κ ℓ v ( q + ) / ℓ v ( q ) ≥ κ 2 . Both rejection loops therefore use an expected constant number of trials, proving the exactness and cost claims.
One recursive round. It remains to check the acceptance coins and the two state coins R t + 1 , P t + 1 R_{t+1}, P_{t+1} R t + 1 , P t + 1 .
Lemma 6.6 (Exactness). For every t t t , Algorithm 5 defines Out t ′ \operatorname{Out}'_t Out t ′ with law q t q_t q t and a procedure family S t + 1 \mathcal{S}_{t+1} S t + 1 representing the next optimization state exactly. Every intermediate coin has its stated bias.
Proof. Induct on t t t , starting from the explicit initialization and following the dependency order in the algorithm. All target laws are deterministic functions of G G G , and every invocation uses fresh randomness.
By Theorem 5.9(c), the load ratios z , z ˉ , z + z,\bar{z},z^{+} z , z ˉ , z + and the coordinate ratios lie in [ e − 1 , e ] [e^{-1},e] [ e − 1 , e ] . The auxiliary load coin has the stated bias:
E [ L ‾ ( v ) ] = 2 e κ E u ∼ In t ( v ) [ ρ t , u v 2 e ] = κ ℓ v ( q ‾ t ) ℓ v ( q t ) . \mathbb{E}[\overline{L}(v)] = 2e\kappa\,\mathbb{E}_{u\sim\operatorname{In}_t(v)}\left[\frac{\rho_{t,uv}}{2e}\right] = \kappa\frac{\ell_v(\overline{q}_t)}{\ell_v(q_t)}. E [ L ( v )] = 2 e κ E u ∼ In t ( v ) [ 2 e ρ t , uv ] = κ ℓ v ( q t ) ℓ v ( q t ) .
Thus Theorem 6.3 supplies the exact price coins for each response.
The root arguments ρ / ( 2 e ) \rho/(2e) ρ / ( 2 e ) are at least 1 / ( 2 e 2 ) 1/(2e^2) 1/ ( 2 e 2 ) . The score bounds in Theorem 5.9(a) give
A g ∈ ( e − 9 / 8 , e − 5 / 6 ) , A^{g} \in(e^{-9/8},e^{-5/6}), A g ∈ ( e − 9/8 , e − 5/6 ) ,
A m ∈ [ 2 − 1 / 2 e − 49 / 24 , 2 − 1 / 2 e − 23 / 24 ] , A^{m} \in[2^{-1/2}e^{-49/24},2^{-1/2}e^{-23/24}], A m ∈ [ 2 − 1/2 e − 49/24 , 2 − 1/2 e − 23/24 ] ,
A ρ ∈ [ 2 − 1 / 4 e − 77 / 48 , 2 − 1 / 4 e − 43 / 48 ] . A^{\rho} \in[2^{-1/4}e^{-77/48},2^{-1/4}e^{-43/48}]. A ρ ∈ [ 2 − 1/4 e − 77/48 , 2 − 1/4 e − 43/48 ] .
These intervals lie in [ κ , 1 − κ ] [\kappa,1-\kappa] [ κ , 1 − κ ] . Consequently Theorem 6.1 constructs the exact weight coins from the listed inputs, and Theorem 6.4 gives the outgoing and incoming samplers and the load-ratio coins.
For the load-state update, 1 − r + r z + ∈ [ e − 1 , e ] 1-r+rz^{+}\in[e^{-1},e] 1 − r + r z + ∈ [ e − 1 , e ] and r + = r z + / ( 1 − r + r z + ) ∈ [ 0 , 1 ) r^{+}=rz^{+}/(1-r+rz^{+})\in[0,1) r + = r z + / ( 1 − r + r z + ) ∈ [ 0 , 1 ) . Thus the denominator has a constant lower bound and the encoding bias lies in [ 1 / 4 , 3 / 4 ] [1/4,3/4] [ 1/4 , 3/4 ] . For the auxiliary update, A ρ A^{\rho} A ρ is a constant multiple of W W W in Theorem 5.10, so
A u a ρ Z u ρ = ρ t + 1 , u a ∈ [ e − 1 , e ] . \frac{A^{\rho}_{ua}}{Z_u^{\rho}}=\rho_{t+1,ua}\in[e^{-1},e]. Z u ρ A u a ρ = ρ t + 1 , u a ∈ [ e − 1 , e ] .
Here Z u ρ ≥ κ Z_u^{\rho}\ge\kappa Z u ρ ≥ κ , and the bias of P t + 1 P_{t+1} P t + 1 lies in [ 1 / ( 2 e 2 ) , 1 / 2 ] [1/(2e^2),1/2] [ 1/ ( 2 e 2 ) , 1/2 ] . The elementary-formula factory therefore supplies both state coins with their exact biases.
Query cost and arithmetic work
Each output procedure supplied by Boxλ _\lambda λ or Tilt, and each remaining formula coin, uses an expected constant number of input calls and expected constant additional work. These costs compound over T T T rounds to a bound exponential in T T T , with an absolute base. This also bounds the number of graph queries. Theorem B.2 gives the finite-arithmetic implementation and establishes the corresponding computational-work bound in the model of § 2.1 .
Lemma 6.7 (Adaptive composition). Suppose a procedure makes an expected at most k k k calls to earlier procedures, at adaptively chosen arguments. If each call has conditional expected cost at most c c c , given the history before it, and the procedure’s own expected cost is at most b b b , then its expected cost is at most b + k c b+kc b + k c .
Proof. Let I j I_j I j indicate that the j j j -th call is made and let C j C_j C j be its cost, zero if the call is not made. Conditional on the history when the call is decided, E C j ≤ c I j \mathbb{E}C_j \le cI_j E C j ≤ c I j . The tower property and Tonelli’s theorem give E ∑ j C j ≤ c E ∑ j I j ≤ c k \mathbb{E}\sum_j C_j \le c\mathbb{E}\sum_j I_j \le ck E ∑ j C j ≤ c E ∑ j I j ≤ c k . □ \square □
Proposition 6.8 (Cost of the recursive procedures). There is an absolute constant A 0 ≥ 2 A_0 \ge2 A 0 ≥ 2 such that every round-t t t procedure, and every intermediate procedure in that round, terminates almost surely and has total work W W W satisfying
E W ≤ A 0 t + 1 . \mathbb{E}W \le A_0^{t+1}. E W ≤ A 0 t + 1 . The expectation is uniform over the argument and over the history before a fresh invocation. In particular, the same bound holds for the expected number of graph queries.
Proof. By Theorems 6.1, 6.3 and 6.4, each new procedure makes an expected constant number of input calls and performs expected constant additional work. The dependency order in Algorithm 5 has constant depth within one round. Applying Theorem 6.7 through these dependencies bounds each round’s expected cost by a fixed constant times one plus the preceding round’s maximum expected cost. Initialization has constant cost, giving the displayed bound after choosing A 0 A_0 A 0 sufficiently large. Fresh independent randomness gives the same bounds conditional on the history before an invocation. Finite expected total work implies almost sure termination. □ \square □
Theorem 6.9 (Local proposal sampler). For every graph G G G and 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , Algorithm 4 returns an exact sample from q u ( δ ) q_u^{(\delta)} q u ( δ ) , where
( 2 − δ ) ν f ( G ) ≤ P ( q u ( δ ) ) ≤ 2 ν f ( G ) . (2-\delta)\nu_f(G) \le P(q_u^{(\delta)}) \le2\nu_f(G). ( 2 − δ ) ν f ( G ) ≤ P ( q u ( δ ) ) ≤ 2 ν f ( G ) . It terminates almost surely and has expected total work at most
C ( δ , Δ ) : = A 0 T δ + 1 = ( 2 Δ ) O ( 1 / δ ) . C(\delta,\Delta) := A_0^{T_\delta+1} = (2\Delta)^{O(1/\delta)}. C ( δ , Δ ) := A 0 T δ + 1 = ( 2Δ ) O ( 1/ δ ) . The same bound holds for the expected number of graph queries. Independent invocations use independent randomness.
Proof. Choosing a uniform round samples the average distribution exactly by Theorem 6.6. Its accepted-mass bound is Theorem 5.1 ; its cost follows from Theorem 6.8, absorbing the constant overhead of choosing a round into A 0 A_0 A 0 . Finally, T δ = O ( δ − 1 log ( 2 Δ ) ) T_\delta= O(\delta^{-1}\log(2\Delta)) T δ = O ( δ − 1 log ( 2Δ )) . □ \square □
From samples to a fractional matching
We use the sampler of § 6 to construct an LCA for a fractional matching, with a worst-case work bound per query. Each invocation of the sampler has a fixed work budget, that is exceeded, the dummy is returned. Each vertex makes K K K such proposals (invocations) and keeps at most K K K incoming ones. Giving weight 1 / ( 2 K ) 1/(2K) 1/ ( 2 K ) to every kept proposal is feasible in every graph. We bound the loss from these two steps and give consistent local access to the kept proposals. Estimation and rounding use these guarantees separately.
Capping the work of a proposal
In the sequel we use the exact finite-arithmetic sampler of Theorem B.2. Increasing the absolute constant A 0 A_0 A 0 in C ( δ , Δ ) C(\delta,\Delta) C ( δ , Δ ) if necessary, this quantity also bounds its expected computational work in the model of § 2.1 . All work budgets below count this computational work.
The expected total-work bound of Theorem 6.9 gives a worst-case work budget directly. For 0 < δ , τ < 1 0 < \delta,\tau< 1 0 < δ , τ < 1 , set
B = ⌈ C ( δ , Δ ) τ ⌉ . (30) B=\left\lceil\frac{C(\delta,\Delta)}{\tau}\right\rceil. \tag*{(30)} B = ⌈ τ C ( δ , Δ ) ⌉ . (30)
The capped sampler runs Out ( δ ) ( u ) \operatorname{Out}^{(\delta)}(u) Out ( δ ) ( u ) for at most B B B units of work. If the sampler has returned by then, we use its output; otherwise we abort and return ⊥ u \bot_u ⊥ u . All recursive calls share this one budget, including the work inside Bernoulli factories. Maintaining the work counter adds only constant overhead per operation, so the total work is O ( B ) O(B) O ( B ) . Write q ~ u \widetilde q_u q u for the capped output law.
Lemma 7.1 (Capping). The capped sampler has a deterministic O ( B ) O(B) O ( B ) total-work bound and satisfies
( 2 − δ − 2 Δ τ ) ν f ( G ) ≤ P ( q ~ ) ≤ 2 ν f ( G ) . (2-\delta-2\Delta\tau)\nu_f(G)\le P(\widetilde q)\le2\nu_f(G). ( 2 − δ − 2Δ τ ) ν f ( G ) ≤ P ( q ) ≤ 2 ν f ( G ) .
Proof. Couple the capped and uncapped runs using the same randomness. If W W W is the uncapped run’s total work, then Theorem 6.9 and Markov’s inequality give
P { a b o r t } = P { W > B } ≤ E W B ≤ τ . \mathbb{P}\{\mathrm{abort}\}=\mathbb{P}\{W>B\}\le\frac{\mathbb{E}W}{B}\le\tau. P { abort } = P { W > B } ≤ B E W ≤ τ .
Capping only replaces outcomes by the dummy. Thus, for every u u u , the real-coordinate probabilities can only decrease, and their total decrease is at most τ \tau τ :
q ~ u v ≤ q u v ( δ ) ( v ∈ N ( u ) ) , ∑ v ∈ N ( u ) ( q u v ( δ ) − q ~ u v ) ≤ τ . \widetilde q_{uv}\le q_{uv}^{(\delta)}\quad(v\in N(u)),\qquad\sum_{v\in N(u)}\left(q_{uv}^{(\delta)}-\widetilde q_{uv}\right)\le\tau. q uv ≤ q uv ( δ ) ( v ∈ N ( u )) , v ∈ N ( u ) ∑ ( q uv ( δ ) − q uv ) ≤ τ .
Since ℓ ↦ min { 1 , ℓ } \ell\mapsto\min\{1,\ell\} ℓ ↦ min { 1 , ℓ } is monotone and 1-Lipschitz,
0 ≤ P ( q ( δ ) ) − P ( q ~ ) ≤ ∑ v ( ℓ v ( q ( δ ) ) − ℓ v ( q ~ ) ) ≤ τ n 0 ≤ 2 Δ τ ν f ( G ) . 0\le P(q^{(\delta)})-P(\widetilde q)\le\sum_v\left(\ell_v(q^{(\delta)})-\ell_v(\widetilde q)\right)\le\tau n_0\le2\Delta\tau\nu_f(G). 0 ≤ P ( q ( δ ) ) − P ( q ) ≤ v ∑ ( ℓ v ( q ( δ ) ) − ℓ v ( q ) ) ≤ τ n 0 ≤ 2Δ τ ν f ( G ) .
Here isolated vertices send no real mass, and the last inequality is Theorem 2.4. The lower bound follows from Theorem 6.9 ; the upper bound follows from Theorem 3.1(a).
For the rest of the construction, choose
δ = ε 32 , τ = ε 64 Δ , K = 2 ⌈ log 2 ( 4096 / ε 2 ) ⌉ . (31) \delta=\frac{\varepsilon}{32},\qquad\tau=\frac{\varepsilon}{64\Delta},\qquad K=2^{\lceil\log_2(4096/\varepsilon^2)\rceil}. \tag*{(31)} δ = 32 ε , τ = 64Δ ε , K = 2 ⌈ l o g 2 ( 4096/ ε 2 )⌉ . (31)
Then K = Θ ( ε − 2 ) K=\Theta(\varepsilon^{-2}) K = Θ ( ε − 2 ) is a power of two, as needed by the later degree-halving procedure. The choice of τ \tau τ bounds the loss in accepted mass from aborted draws by 2 Δ τ ν f ( G ) = ε ν f ( G ) / 32 2\Delta\tau\nu_f(G)=\varepsilon\nu_f(G)/32 2Δ τ ν f ( G ) = ε ν f ( G ) /32 , and the work budget satisfies B = ( 2 Δ ) O ( 1 / ε ) B=(2\Delta)^{O(1/\varepsilon)} B = ( 2Δ ) O ( 1/ ε ) .
Keeping proposals
Each vertex u u u makes K K K independent capped proposals, identified by ( u , j ) (u,j) ( u , j ) for j = 1 , … , K j=1,\ldots,K j = 1 , … , K . A real proposal to v v v is a copy of the edge u v uv uv with this ID. Let N v N_v N v count the proposals received by v v v . The receiver keeps the min { K , N v } \min\{K,N_v\} min { K , N v } proposals with smallest IDs, in lexicographic order. All kept copies form a multigraph H H H on V V V , with
S : = ∣ E ( H ) ∣ = ∑ v min { K , N v } . S := |E(H)| = \sum_v \min\{K,N_v\}. S := ∣ E ( H ) ∣ = v ∑ min { K , N v } .
Parallel copies, including proposals in opposite directions, remain distinct. A vertex has at most K K K kept outgoing and K K K kept incoming copies, so H H H has maximum degree at most 2 K 2K 2 K . Thus the weights
f { u , v } H = # { kept copies of u v } 2 K (32) f^H_{\{u,v\}} = \frac{\#\{\text{kept copies of }uv\}}{2K} \tag*{(32)} f { u , v } H = 2 K # { kept copies of uv } (32)
form a fractional matching of G G G , of value S / ( 2 K ) S/(2K) S / ( 2 K ) . The multigraph H H H is bipartite whenever G G G is bipartite.
Clipping the incoming count at K K K loses little in expectation. The following estimate isolates that loss.
Lemma 7.2 (Relative clipping). If N N N is a sum of independent Bernoulli variables with mean K ℓ K\ell K ℓ , for an integer K ≥ 1 K \ge1 K ≥ 1 , then
( 1 − 2 K ) min { 1 , ℓ } ≤ E min { K , N } K ≤ min { 1 , ℓ } . \left(1-\frac{2}{\sqrt{K}}\right)\min\{1,\ell\}
\le\frac{\mathbb{E}\min\{K,N\}}{K}
\le\min\{1,\ell\}. ( 1 − K 2 ) min { 1 , ℓ } ≤ K E min { K , N } ≤ min { 1 , ℓ } . Proof. The upper bound is Jensen’s inequality. Suppose first that μ : = E N ≤ K \mu:= \mathbb{E}N \le K μ := E N ≤ K . Write N = ∑ i X i N=\sum_i X_i N = ∑ i X i , p i = E X i p_i=\mathbb{E}X_i p i = E X i , and N i = N − X i N_i=N-X_i N i = N − X i . Since ( N − K ) + (N-K)_+ ( N − K ) + vanishes unless N > K N>K N > K ,
E ( N − K ) + ≤ 1 K E [ N ( N − K ) + ] \mathbb{E}(N-K)_+ \le\frac{1}{K}\mathbb{E}[N(N-K)_+] E ( N − K ) + ≤ K 1 E [ N ( N − K ) + ] = 1 K ∑ i p i E ( N i + 1 − K ) + = \frac{1}{K}\sum_i p_i\mathbb{E}(N_i+1-K)_+ = K 1 i ∑ p i E ( N i + 1 − K ) + ≤ μ K ( K + 1 ) ≤ 2 μ K . \le\frac{\mu}{K}(\sqrt{K}+1)\le\frac{2\mu}{\sqrt{K}}. ≤ K μ ( K + 1 ) ≤ K 2 μ . For the penultimate step, E N i ≤ K \mathbb{E}N_i\le K E N i ≤ K and Var N i ≤ K \operatorname{Var}N_i\le K Var N i ≤ K imply E ( N i + 1 − K ) + ≤ E ∣ N i − E N i ∣ + 1 ≤ K + 1 \mathbb{E}(N_i+1-K)_+\le\mathbb{E}|N_i-\mathbb{E}N_i|+1\le\sqrt{K}+1 E ( N i + 1 − K ) + ≤ E ∣ N i − E N i ∣ + 1 ≤ K + 1 . Subtracting the loss from μ \mu μ proves this case. If μ > K \mu>K μ > K , independently retain each success with probability K / μ K/\mu K / μ . The thinned count has mean K K K and is at most N N N , so the first case gives the required bound.
Corollary 7.3 (Expected value). The fractional matching of kept proposals satisfies
( 1 − ε / 16 ) ν f ( G ) ≤ E S 2 K ≤ ν f ( G ) . \left(1-\varepsilon/16\right)\nu_f(G)\le\frac{\mathbb{E}S}{2K}\le\nu_f(G). ( 1 − ε /16 ) ν f ( G ) ≤ 2 K E S ≤ ν f ( G ) . Proof. Each N v N_v N v is a sum of K deg ( v ) K\deg(v) K deg ( v ) independent indicators with mean K ℓ v ( q ~ ) K\ell_v(\widetilde q) K ℓ v ( q ) . Summing Theorem 7.2 and applying Theorem 7.1 gives
E S 2 K ≥ ( 1 − 2 K ) P ( q ~ ) 2 ≥ ( 1 − 2 K ) ( 1 − δ 2 − Δ τ ) ν f ( G ) . \frac{\mathbb{E}S}{2K}\ge\left(1-\frac{2}{\sqrt{K}}\right)\frac{P(\widetilde q)}{2}
\ge\left(1-\frac{2}{\sqrt{K}}\right)\left(1-\frac{\delta}{2}-\Delta_\tau\right)\nu_f(G). 2 K E S ≥ ( 1 − K 2 ) 2 P ( q ) ≥ ( 1 − K 2 ) ( 1 − 2 δ − Δ τ ) ν f ( G ) . By (31) , 2 / K ≤ ε / 32 2/\sqrt{K}\le\varepsilon/32 2/ K ≤ ε /32 and δ / 2 + Δ τ = ε / 32 \delta/2+\Delta_\tau=\varepsilon/32 δ /2 + Δ τ = ε /32 , giving the lower bound. The upper bound follows from feasibility for every realization.
Consistent local access
Independent seeds fix the proposals, so any query can reconstruct the same kept copies. Give each proposal ( u , j ) (u,j) ( u , j ) its own seed ω u , j \omega_{u,j} ω u , j as in § 2.1 . Re-evaluating it with the same seed and work budget reproduces the same outcome. These seeds therefore fix one multigraph H H H , regardless of the query order.
Algorithm 6 gives the local routines. Incoming ( v ) \operatorname{Incoming}(v) Incoming ( v ) lists the copies kept by v v v ; List ( v ) \operatorname{List}(v) List ( v ) also checks which proposals made by v v v were kept by their receivers. Each list stores the IDs and endpoints of its copies. The routines recompute the entries they need and use no persistent memory.
Algorithm 6: Local access to the proposal multigraph
Input: Fixed parameters δ, B, K and independent proposal seeds ωu,j.
Procedure Propose(u, j):
Run Out(δ)(u) with seed ωu,j for at most B units of total sampler work
if the sampler has returned an output a then return a
return ⊥u
Procedure Incoming(v):
L ← empty list
foreach u ∈ N(v) do
for j = 1, . . . , K do
if Propose(u, j) = v then
Append the copy of uv with ID (u, j) to L
Sort L by ID and return its first min{K, |L|} copies
Procedure List(v):
L ← Incoming(v)
for j = 1, . . . , K do
w ← Propose(v, j)
if w ≠ ⊥v then
if the copy with ID (v, j) belongs to Incoming(w) then
Append that copy to L
Sort L by ID and return L
Lemma 7.4 (The proposal multigraph). For every graph G G G , H H H has S S S edges and maximum degree at most 2 K 2K 2 K . Giving each copy weight 1 / ( 2 K ) 1/(2K) 1/ ( 2 K ) yields a feasible fractional matching with the expected value in Theorem 7.3 . The list of copies incident to a specified vertex, sorted by ID, can be computed consistently using at most
A = O ( Δ K 2 ( B + log ( 2 Δ K ) ) ) = ( 2 Δ ) O ( 1 / ε ) A = O\left(\Delta K^2(B+\log(2\Delta K))\right) = (2\Delta)^{O(1/\varepsilon)} A = O ( Δ K 2 ( B + log ( 2Δ K )) ) = ( 2Δ ) O ( 1/ ε ) total work, and hence at most that many graph queries.
Proof. The size, degree, and feasibility claims follow from the construction, and Theorem 7.3 gives the expected value.
A call to Incoming \operatorname{Incoming} Incoming evaluates at most Δ K \Delta K Δ K proposals and sorts at most that many copies. Its total work is O ( Δ K ( B + log ( 2 Δ K ) ) ) O(\Delta K(B+\log(2\Delta K))) O ( Δ K ( B + log ( 2Δ K ))) . A call to List \operatorname{List} List makes at most K + 1 K+1 K + 1 such calls, evaluates another K K K proposals, and sorts at most 2 K 2K 2 K kept copies. This gives the stated bound. Every decision uses the same IDs and proposal seeds, so all evaluations agree. Since G G G has no loops, an incoming copy and an outgoing copy at a vertex are distinct, and List \operatorname{List} List returns exactly its incident copies in H H H .
The size estimator
The estimator samples the incoming contribution of a uniformly random vertex. Recall that the fractional matching of § 7 has value
S 2 K = 1 2 ∑ v min { K , N v } K . \frac{S}{2K}=\frac{1}{2}\sum_v\frac{\min\{K,N_v\}}{K}. 2 K S = 2 1 v ∑ K min { K , N v } .
One estimation trial chooses a uniform vertex v v v , generates its incoming proposals, and returns the normalized count min { K , N v } / K \min\{K,N_v\}/K min { K , N v } / K . Averaging independent trials and multiplying by n / 2 n/2 n /2 estimates the expected value of this fractional matching, which is close to ν f ( G ) \nu_f(G) ν f ( G ) by Theorem 7.3 .
Write CappedOut δ , B ( u ) \operatorname{CappedOut}_{\delta,B}(u) CappedOut δ , B ( u ) for the capped sampler of § 7.1 . Each invocation uses fresh independent randomness, even when a source or receiver is sampled again. The estimator only counts incoming proposals; it needs no proposal IDs, sorting, shared seeds, or rounding.
Algorithm 7: Estimating the fractional matching number
Input: Graph access, n n n , degree bound Δ \Delta Δ , and 0 < ε , ζ < 1 / 2 0<\varepsilon,\zeta<1/2 0 < ε , ζ < 1/2 .
Output: An estimate ν ^ f \widehat{\nu}_f ν f of ν f ( G ) \nu_f(G) ν f ( G ) .
Set δ , τ , K \delta,\tau,K δ , τ , K as in (7.2)
B ← ⌈ C ( δ , Δ ) / τ ⌉ B\leftarrow\lceil C(\delta,\Delta)/\tau\rceil B ← ⌈ C ( δ , Δ ) / τ ⌉
s ← ⌈ 2 ε − 2 log ( 2 / ζ ) ⌉ s\leftarrow\lceil2\varepsilon^{-2}\log(2/\zeta)\rceil s ← ⌈ 2 ε − 2 log ( 2/ ζ )⌉
for i = 1 , … , s i=1,\ldots,s i = 1 , … , s do
Choose v v v uniformly from V V V
N ← 0 N\leftarrow0 N ← 0
foreach u ∈ N ( v ) u\in N(v) u ∈ N ( v ) do
for j = 1 , … , K j=1,\ldots,K j = 1 , … , K do
a ← CappedOut ( u ; δ , B ) a\leftarrow\operatorname{CappedOut}(u;\delta,B) a ← CappedOut ( u ; δ , B ) // fresh randomness
if a = v a=v a = v then N ← N + 1 N\leftarrow N+1 N ← N + 1
Z i ← min { K , N } / K Z_i\leftarrow\min\{K,N\}/K Z i ← min { K , N } / K
return ν ^ f = n 2 s ∑ i = 1 s Z i \widehat{\nu}_f=\dfrac{n}{2s}\sum_{i=1}^{s}Z_i ν f = 2 s n ∑ i = 1 s Z i
On bipartite graphs, the same output estimates ν ( G ) \nu(G) ν ( G ) .
Proof of Theorem 1.1 (b). For a fixed v v v , the trial has exactly the incoming-count law used in § 7 . Thus Theorem 7.3 gives
n 2 E Z ∈ [ ( 1 − ε / 16 ) ν f ( G ) , ν f ( G ) ] ⊆ [ ν f ( G ) − ε n / 32 , ν f ( G ) ] . \frac{n}{2}\mathbb{E}Z\in\left[(1-\varepsilon/16)\nu_f(G),\nu_f(G)\right]\subseteq\left[\nu_f(G)-\varepsilon n/32,\nu_f(G)\right]. 2 n E Z ∈ [ ( 1 − ε /16 ) ν f ( G ) , ν f ( G ) ] ⊆ [ ν f ( G ) − ε n /32 , ν f ( G ) ] .
The inclusion uses ν f ( G ) ≤ n / 2 \nu_f(G)\le n/2 ν f ( G ) ≤ n /2 . Because the trials are independent and lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , Theorem 2.5 yields
P { ∣ 1 s ∑ i Z i − E Z ∣ > ε / 2 } ≤ 2 e − s ε 2 / 2 ≤ ζ . \mathbb{P}\left\{\left|\frac{1}{s}\sum_i Z_i-\mathbb{E}Z\right|>\varepsilon/2\right\}\le2e^{-s\varepsilon^2/2}\le\zeta. P { s 1 i ∑ Z i − E Z > ε /2 } ≤ 2 e − s ε 2 /2 ≤ ζ .
Otherwise the sampling error is at most ε n / 4 \varepsilon n/4 ε n /4 , and the total error is at most 9 ε n / 32 9\varepsilon n/32 9 ε n /32 , in particular at most ε n \varepsilon n ε n . Each trial uses O ( Δ K ( B + 1 ) ) O(\Delta K(B+1)) O ( Δ K ( B + 1 )) total work. The resulting worst-case bound on both graph queries and arithmetic work is
O ( Δ K ( B + 1 ) ε − 2 log ( 2 / ζ ) ) = ( 2 Δ ) O ( 1 / ε ) log ( 2 / ζ ) . O\left(\Delta K(B+1)\varepsilon^{-2}\log(2/\zeta)\right)=(2\Delta)^{O(1/\varepsilon)}\log(2/\zeta). O ( Δ K ( B + 1 ) ε − 2 log ( 2/ ζ ) ) = ( 2Δ ) O ( 1/ ε ) log ( 2/ ζ ) .
Remark 8.1 (Estimation from the deterministic oracle). The estimation claim in Theorem 1.2 follows by the same vertex-sampling argument. Use Theorem 5.3 with relative error ε / 2 \varepsilon/2 ε /2 , and for a uniform vertex v v v compute its incident weight Y v = ∑ e ∋ v f e ∈ [ 0 , 1 ] Y_v = \sum_{e \ni v} f_e \in[0,1] Y v = ∑ e ∋ v f e ∈ [ 0 , 1 ] . Then ( n / 2 ) E Y v = ∑ e f e (n/2)\mathbb{E}Y_v = \sum_e f_e ( n /2 ) E Y v = ∑ e f e , whose deficit from ν f ( G ) \nu_f(G) ν f ( G ) is at most ε ν f ( G ) / 2 ≤ ε n / 4 \varepsilon\nu_f(G)/2 \le\varepsilon n/4 ε ν f ( G ) /2 ≤ ε n /4 . Averaging O ( ε − 1 log ( 2 / ζ ) ) O(\varepsilon^{-1}\log(2/\zeta)) O ( ε − 1 log ( 2/ ζ )) independent vertex samples estimates this value within ε n / 2 \varepsilon n/2 ε n /2 with probability at least 1 − ζ 1-\zeta 1 − ζ . Evaluating Y v Y_v Y v makes at most Δ \Delta Δ edge-weight queries; these polynomial factors are absorbed into the stated bound. Only vertex sampling is randomized.
Rounding to a consistent local oracle
The proposal multigraph H H H has S S S copies, degree at most D = 2 K D=2K D = 2 K , and represents the fractional matching f H f^H f H of § 7 . We round its bipartite double cover B ( H ) B(H) B ( H ) to a matching and project back to G G G . The resulting output is half-integral on every graph and integral whenever G G G is bipartite. The algorithm requires neither a bipartition nor knowledge of whether G G G is bipartite.
The key is to use the same random marks for the two lifts of each proposal copy. On bipartite inputs, this makes the rounding decisions agree in the two copies of each connected component. The optimization, sampling, and proposal construction all run directly on G G G ; only the rounding uses the double cover.
Local degree halving
The rounding repeatedly halves a degree bound, doubling the weight represented by each remaining edge. Pairing incident copies reduces each step to choosing alternating edges along paths and even cycles. Random marks cut these components into pieces that can be explored with bounded work.
Set H 0 = B ( H ) H_0=B(H) H 0 = B ( H ) , so H 0 H_0 H 0 has 2 S 2S 2 S copies and maximum degree at most D = 2 K = 2 J D=2K=2^J D = 2 K = 2 J . Each lifted copy has an ID consisting of its original proposal ID followed by a side index; IDs are ordered lexicographically and retained throughout the rounding. Write D i = D / 2 i D_i=D/2^i D i = D / 2 i and m i = ∣ E ( H i ) ∣ m_i=|E(H_i)| m i = ∣ E ( H i ) ∣ . Fix a loss allowance 0 < ξ < 1 / 2 0<\xi<1/2 0 < ξ < 1/2 and set
s = ⌈ log 2 2 J ξ ⌉ , p = 2 − s , R = 2 s p . (33) s=\left\lceil\log_2 \frac{2J}{\xi}\right\rceil,\qquad p=2^{-s},\qquad R=\frac{2s}{p}. \tag*{(33)} s = ⌈ log 2 ξ 2 J ⌉ , p = 2 − s , R = p 2 s . (33)
This choice gives ξ / ( 4 J ) < p ≤ ξ / ( 2 J ) \xi/(4J)<p\le\xi/(2J) ξ / ( 4 J ) < p ≤ ξ / ( 2 J ) and R ≥ 2 log ( 1 / p ) / p R\ge2\log(1/p)/p R ≥ 2 log ( 1/ p ) / p . Each mark is generated from exactly s s s independent random bits: it is one precisely when all these bits are zero.
One halving step. At each vertex of H i H_i H i , sort incident copies by ID and pair consecutive ones, leaving one unpaired if the degree is odd. The link multigraph P i P_i P i has the copies of H i H_i H i as vertices and these pairs as edges. A copy has at most one link at each endpoint, so P i P_i P i has maximum degree two. Along a cycle, links alternate between the two sides of H 0 H_0 H 0 ; every cycle is therefore even.
At level i i i , give each original proposal copy an independent Bern ( p ) \operatorname{Bern}(p) Bern ( p ) mark, shared by its surviving lifts. Marks are independent across levels and independent of the proposal seeds. Write B R ( e ) B_R(e) B R ( e ) for the vertices of P i P_i P i within distance R R R of a lifted copy e e e . Delete e e e if it is marked, or if ∣ B R ( e ) ∣ ≥ R |B_R(e)|\ge R ∣ B R ( e ) ∣ ≥ R and B R ( e ) B_R(e) B R ( e ) contains no mark. On each surviving component, keep the larger class of its proper 2-coloring; on a tie, keep the class containing the smallest ID. These kept copies form H i + 1 H_{i+1} H i + 1 .
Lemma 9.1 (One halving step; cf. [1 , 25 ] ). Every surviving component of P i P_i P i has at most 2 R 2R 2 R vertices, and H i + 1 H_{i+1} H i + 1 has maximum degree at most D i + 1 D_{i+1} D i + 1 . If Z i Z_i Z i copies are deleted, then m i + 1 ≥ ( m i − Z i ) / 2 m_{i+1}\ge(m_i-Z_i)/2 m i + 1 ≥ ( m i − Z i ) /2 .
Proof. A surviving path or cycle with more than 2 R 2R 2 R vertices has a vertex whose radius-R R R ball lies within that component. The ball has at least R R R vertices and no mark, so the deletion rule would have removed this vertex.
The two copies of a pair cannot both be kept: if both survive, they are adjacent in P i P_i P i and have opposite colors. Hence each vertex retains at most ⌈ deg H i ( v ) / 2 ⌉ ≤ D i / 2 = D i + 1 \lceil\deg_{H_i}(v)/2\rceil\le D_i/2 = D_{i+1} ⌈ deg H i ( v ) /2 ⌉ ≤ D i /2 = D i + 1 copies, since D i D_i D i is even for i < J i < J i < J . Choosing the larger color class keeps at least half of all surviving copies, which proves the edge-count bound. □ \square □
Sharing marks preserves the expected-loss bound: any set of R R R lifted copies contains at least R / 2 R/2 R /2 distinct original IDs, and hence at least R / 2 R/2 R /2 independent marks.
Lemma 9.2 (Deletion loss). Conditional on H i H_i H i , E [ Z i ∣ H i ] ≤ 2 p m i \mathbb{E}[Z_i \mid H_i] \le2pm_i E [ Z i ∣ H i ] ≤ 2 p m i .
Proof. A copy is marked with probability p p p . If its radius-R R R ball has at least R R R vertices, that ball has no mark with probability at most
( 1 − p ) R / 2 ≤ e − p R / 2 ≤ p . (1-p)^{R/2} \le e^{-pR/2} \le p. ( 1 − p ) R /2 ≤ e − pR /2 ≤ p .
Thus each copy is deleted with probability at most 2 p 2p 2 p ; summing proves the claim. □ \square □
Proposition 9.3 (Local degree halving; cf. [1 , 25 ] ). After J J J steps, H J H_J H J is a matching and
E [ ∣ E ( H J ) ∣ ∣ H 0 ] ≥ ( 1 − ξ ) E [ ∣ E ( H 0 ) ∣ ] D . \mathbb{E}[|E(H_J)| \mid H_0] \ge(1-\xi)\frac{\mathbb{E}[|E(H_0)|]}{D}. E [ ∣ E ( H J ) ∣ ∣ H 0 ] ≥ ( 1 − ξ ) D E [ ∣ E ( H 0 ) ∣ ] . If a sorted list of copies at a vertex of H 0 H_0 H 0 costs at most A A A total work, a mate query to H J H_J H J costs at most A ( C D R 2 ) J A(CDR^2)^J A ( C D R 2 ) J total work, for an absolute constant C C C . The same bound therefore holds for graph queries and arithmetic operations. Fixed IDs and marks indexed by original proposal ID and level give consistent answers in every query order.
Proof. The final degree bound is D J = 1 D_J=1 D J = 1 , so H J H_J H J is a matching. By Theorems 9.1 and 9.2,
E [ m i + 1 D i + 1 | H i ] ≥ m i − E [ Z i ∣ H i ] D i ≥ ( 1 − 2 p ) m i D i . \mathbb{E}\left[\frac{m_{i+1}}{D_{i+1}}\middle|H_i\right] \ge\frac{m_i-\mathbb{E}[Z_i\mid H_i]}{D_i} \ge(1-2p)\frac{m_i}{D_i}. E [ D i + 1 m i + 1 H i ] ≥ D i m i − E [ Z i ∣ H i ] ≥ ( 1 − 2 p ) D i m i .
Iterating expectations gives E [ m J ∣ H 0 ] ≥ ( 1 − 2 p ) J m 0 / D ≥ ( 1 − 2 p J ) m 0 / D \mathbb{E}[m_J\mid H_0]\ge(1-2p)^Jm_0/D\ge(1-2pJ)m_0/D E [ m J ∣ H 0 ] ≥ ( 1 − 2 p ) J m 0 / D ≥ ( 1 − 2 p J ) m 0 / D . Since 2 p J ≤ ξ 2pJ\le\xi 2 p J ≤ ξ , this is the value bound.
For local evaluation, let List i ( v ) \operatorname{List}_i(v) List i ( v ) return the incident copies in H i H_i H i in ID order, at worst-case cost A i A_i A i . The two possible neighbors of a copy in P i P_i P i are obtained from the lists at its endpoints. Testing deletion uses O ( R ) O(R) O ( R ) such list calls. Determining whether a surviving copy is kept explores its component of at most 2 R 2R 2 R copies and tests their boundary, using O ( R 2 ) O(R^2) O ( R 2 ) list calls in total. This reveals both color classes and their smallest IDs. Generate each encountered copy’s mark once and reuse it during this exploration. The tested balls together contain O ( R ) O(R) O ( R ) copies, so generating their marks costs O ( R s ) ≤ O ( R 2 ) O(Rs)\le O(R^2) O ( R s ) ≤ O ( R 2 ) additional work. Filtering List i ( v ) \operatorname{List}_i(v) List i ( v ) through these tests preserves ID order and gives
A i + 1 ≤ C D R 2 A i . A_{i+1}\le CDR^2A_i. A i + 1 ≤ C D R 2 A i .
This bound includes comparisons and all other local work. Finally, the fixed seeds define one global sequence H 0 , … , H J H_0,\ldots,H_J H 0 , … , H J ; every evaluation reconstructs its relevant part using the same choices. □ \square □
Integral and half-integral outputs
Apply Theorem 9.3 with ξ = ε / 32 \xi= \varepsilon/32 ξ = ε /32 , and let M = E ( H J ) M = E(H_J) M = E ( H J ) . The incident lists of H 0 = B ( H ) H_0 = B(H) H 0 = B ( H ) are obtained from those of H H H in Theorem 7.4 with constant-factor overhead. We now project M M M to one fractional matching of G G G and show that it is integral on bipartite inputs.
Projection and value. As in Theorem 2.3(b), each matched lift contributes weight 1 / 2 1/2 1/2 to its original edge of G G G , with contributions from parallel copies added. At each vertex, its two lifts contribute at most 1 / 2 1/2 1/2 each. Thus the resulting weights f e f_e f e are feasible, belong to { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } , and satisfy ∑ e f e = ∣ M ∣ / 2 \sum_e f_e = |M|/2 ∑ e f e = ∣ M ∣/2 . Conditional on H H H ,
E [ ∑ e f e ∣ H ] ≥ ( 1 − ε / 32 ) S 2 K . \mathbb{E}\left[\left.\sum_e f_e\right|H\right] \ge(1-\varepsilon/32)\frac{S}{2K}. E [ e ∑ f e H ] ≥ ( 1 − ε /32 ) 2 K S .
Together with Theorem 7.3, this gives
E ∑ e f e ≥ ( 1 − ε / 32 ) ( 1 − ε / 16 ) ν f ( G ) ≥ ( 1 − 3 ε / 32 ) ν f ( G ) . \mathbb{E}\sum_e f_e \ge(1-\varepsilon/32)(1-\varepsilon/16)\nu_f(G) \ge(1-3\varepsilon/32)\nu_f(G). E e ∑ f e ≥ ( 1 − ε /32 ) ( 1 − ε /16 ) ν f ( G ) ≥ ( 1 − 3 ε /32 ) ν f ( G ) .
Integrality on bipartite inputs. If G G G is bipartite, so is H H H , and the double cover of each connected component of H H H consists of two isomorphic copies. Swapping the lifts gives an isomorphism between these copies that preserves original proposal IDs. Within either copy, these IDs are distinct, so the secondary side indices never affect their relative order.
The two copies therefore undergo identical rounding decisions. Indeed, this holds initially and is preserved at every level: incident pairings correspond, shared marks give corresponding deletions, and the larger-class rule and its smallest-ID tie-break choose corresponding color classes. Consequently, M M M contains both lifts of each proposal copy or neither. Its projection is integral and hence is a matching of G G G . This conclusion follows from the input being bipartite; the algorithm never needs to test it.
Local queries. An edge query for u v uv uv uses two mate queries to M M M , at ( u , 1 ) (u,1) ( u , 1 ) and ( v , 1 ) (v,1) ( v , 1 ) , and returns half the number of these that are matched to ( v , 2 ) (v,2) ( v , 2 ) and ( u , 2 ) (u,2) ( u , 2 ) , respectively. On bipartite inputs, a mate query at v v v uses just the mate of ( v , 1 ) (v,1) ( v , 1 ) , returning its original vertex or reporting that v v v is unmatched. Both query interfaces access the same projected output.
Completing the LCA guarantee
We finish Theorem 1.1(a) using the expected-value bound above and then check total work. Write Y = ∑ e f e Y=\sum_e f_e Y = ∑ e f e and ν = ν f ( G ) \nu=\nu_f(G) ν = ν f ( G ) . Feasibility gives 0 ≤ Y ≤ ν 0\le Y\le\nu 0 ≤ Y ≤ ν , and
E ( ν − Y ) ≤ 3 ε 32 ν . \mathbb{E}(\nu-Y)\le\frac{3\varepsilon}{32}\nu. E ( ν − Y ) ≤ 32 3 ε ν .
If ν = 0 \nu=0 ν = 0 , the output is already optimal. Otherwise, Markov’s inequality applied to the nonnegative deficit gives
P { Y < ( 1 − ε ) ν } ≤ E ( ν − Y ) ε ν ≤ 3 32 < 0.1. \mathbb{P}\{Y<(1-\varepsilon)\nu\}\le\frac{\mathbb{E}(\nu-Y)}{\varepsilon\nu}\le\frac{3}{32}<0.1. P { Y < ( 1 − ε ) ν } ≤ ε ν E ( ν − Y ) ≤ 32 3 < 0.1.
Thus the output has the required multiplicative guarantee with probability at least 0.9. On bipartite inputs it is a matching and ν f ( G ) = ν ( G ) \nu_f(G)=\nu(G) ν f ( G ) = ν ( G ) . Any other fixed success probability below one is obtained by a constant rescaling of the accuracy parameters.
Work per query. Theorems 7.4 and 9.3 bound total work by a constant multiple of
Δ K 2 ( B + log ( 2 Δ K ) ) ( C D R 2 ) J \Delta K^2\left(B+\log(2\Delta K)\right)\left(CDR^2\right)^J Δ K 2 ( B + log ( 2Δ K ) ) ( C D R 2 ) J
Here K K K , D D D , R R R are polynomial in 1 / ε 1/\varepsilon 1/ ε , J = O ( log ( 2 / ε ) ) J=O(\log(2/\varepsilon)) J = O ( log ( 2/ ε )) , and ( C D R 2 ) J = e O ( log 2 ( 2 / ε ) ) \left(CDR^2\right)^J=e^{O(\log^2(2/\varepsilon))} ( C D R 2 ) J = e O ( l o g 2 ( 2/ ε )) . Together with B = ( 2 Δ ) O ( 1 / ε ) B=(2\Delta)^{O(1/\varepsilon)} B = ( 2Δ ) O ( 1/ ε ) , this gives ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) total work per output query. The two mate queries for an edge weight add only a constant factor. The bound is independent of n n n .
Validity and consistency. Proposal seeds fix H H H , and the marks indexed by original proposal ID and level fix every rounding decision. Each query therefore reconstructs part of the same projected fractional matching, in every query order, including adaptive ones. The proposal work cap and the bounded rounding explorations ensure that every query terminates within the stated budget. Feasibility and consistency hold for every realization of the seeds; only the approximation guarantee is probabilistic. This proves Theorem 1.1 (a).
Remark 9.4 (Constants). The absolute constants in the exponent are large and are not optimized. The cap multiplies the expected sampler cost by 1 / τ = O ( Δ / ε ) 1/\tau=O(\Delta/\varepsilon) 1/ τ = O ( Δ/ ε ) , and the degree-halving overhead is exp ( O ( log 2 ( 2 / ε ) ) ) \exp(O(\log^2(2/\varepsilon))) exp ( O ( log 2 ( 2/ ε ))) ; both are absorbed into ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) . The result concerns the dependence of the exponent on 1 / ε 1/\varepsilon 1/ ε .
Conclusion and open questions
Our approach combines a rapidly converging local optimizer with exact recursive sampling of its iterates. The optimizer gives deterministic local access to a fractional matching; the sampler reduces the dependence on the degree by replacing neighborhood expansion with constant expected branching. This combination suggests several directions for further work.
Integral matchings in general graphs. Can a randomized mate-query LCA find a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) -approximate matching in a general graph using ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) queries and arithmetic operations per query, with constant success probability? Our fractional relaxation leaves an obstruction from odd cycles, since ν f ( G ) \nu_f(G) ν f ( G ) can exceed ν ( G ) \nu(G) ν ( G ) . The recent preprint of OpenAI [49 ] on almost-linear-time exact matching combines representations of odd components with continuous optimization and flow-based repairs. Whether its treatment of these components can be adapted to an efficiently locally simulatable method is an interesting question.
Graphs of unbounded degree. When the bounded-degree assumption is dropped, Bhattacharya, Kiss, and Saranurak [13 ] estimate ν ( G ) \nu(G) ν ( G ) within ± ε n \pm\varepsilon n ± ε n in n 2 − Ω ε ( 1 ) n^{2-\Omega_\varepsilon(1)} n 2 − Ω ε ( 1 ) queries, and Behnezhad, Roghani, and Rubinstein [11 ] prove an Ω ( n 2 − δ ( ε ) ) \Omega(n^{2-\delta(\varepsilon)}) Ω ( n 2 − δ ( ε ) ) lower bound. However, the dependence on ε \varepsilon ε in the exponent remains wide open. Because [13 ] simulates McGregor’s augmenting-path streaming algorithm [42 ] , its exponent savings Ω ε ( 1 ) \Omega_\varepsilon(1) Ω ε ( 1 ) is doubly exponentially small in 1 / ε 1/\varepsilon 1/ ε , whereas the lower bound of [11 ] only forces δ ( ε ) \delta(\varepsilon) δ ( ε ) to vanish roughly as 1 / log ( 1 / ε ) 1/\sqrt{\log(1/\varepsilon)} 1/ log ( 1/ ε ) . Can continuous optimization methods avoid this compounding of augmenting-path phases in the unbounded-degree regime as well, and achieve n 2 − poly ( ε ) n^{2-\operatorname{poly}(\varepsilon)} n 2 − poly ( ε ) queries?
Other local optimization problems. It would be useful to identify a broader class of optimization methods whose iterates admit exact recursive sampling with constant expected branching. Capacitated allocation, fractional packing, and entropy-regularized transport are natural candidates. The challenge is to obtain both fast convergence and a representation by samplers and coins that is preserved by the updates, with uniformly bounded simulation cost. Our construction shows how these requirements can guide the choice of formulation, regularizer, and update rules.
Acknowledgments
Edith Cohen was partially supported by the Israel Science Foundation (grant No. 1156/23).
AI methodology. We acknowledge substantive contributions from Astra (OpenAI), Claude (Anthropic), and Gemini (Google). Starting from an earlier unpublished writeup by the second author, these systems contributed the first proof of an additive approximation guarantee. Through many subsequent iterations with the authors, they helped strengthen the guarantees, refine the statements and presentation, and identify connections to related work. This assistance materially influenced the proofs, result statements, exposition, and related-work discussion. The authors take full responsibility for the correctness, originality, and integrity of all content, including the proofs and references.
Bernoulli-factory proofs
This appendix proves the two primitives stated together in § 6.1 , including their arithmetic-work bounds. The extensions used for the price readouts are specified in § 6.5 ; they are part of the sampler’s preparation, not an additional assumption of these proofs.
Elementary formulas
We represent each intermediate value by a bounded unbiased random variable, and convert the final representation into a coin. Every sample and every repeated trial below uses fresh independent randomness.
Proof of Theorem 6.1. Linear amplification. For fixed C > 1 C > 1 C > 1 and η > 0 \eta> 0 η > 0 , the linear factory of Huber [29 ] converts a p p p -coin into a C p Cp C p -coin whenever C p ≤ 1 − η Cp \le1 - \eta C p ≤ 1 − η , using O ( C / η ) O(C/\eta) O ( C / η ) expected input flips. Its additional work is O ( N + 1 ) O(N + 1) O ( N + 1 ) on an execution using N N N input flips in our model: each inner step uses one input flip, one known-parameter geometric draw, and constant arithmetic; each outer step contains an inner step and adds constant work. A geometric draw uses a uniform draw, logarithms, and integer rounding. Thus fixed C C C , η \eta η give constant expected additional work. For 0 ≤ C ≤ 1 0 \le C \le1 0 ≤ C ≤ 1 , thinning suffices.
Bounded unbiased representations. A procedure represents a a a if it returns independent samples X X X with E X = a \operatorname{E}X = a E X = a and ∣ X ∣ ≤ B \lvert X\rvert\le B ∣ X ∣ ≤ B for a known constant B > 0 B > 0 B > 0 . If a ≥ m > 0 a \ge m > 0 a ≥ m > 0 , draw X X X and then a known-bias coin with conditional bias ( B − X ) / ( 2 B ) (B - X)/(2B) ( B − X ) / ( 2 B ) . This is a coin of bias
q = B − a 2 B . q = \frac{B-a}{2B}. q = 2 B B − a .
Linear amplification with multiplier 2 applies because 2 q = 1 − a / B ≤ 1 − m / B 2q = 1 - a/B \le1 - m/B 2 q = 1 − a / B ≤ 1 − m / B . Complementing its output gives an a / B a/B a / B -coin. One may use slack min { 1 / 2 , m / B } \min\{1/2, m/B\} min { 1/2 , m / B } . This conversion uses constant expected calls and additional work for fixed B B B , m m m .
Arithmetic. An input bit represents its bias. Constants, sums, differences, and scalar multiples preserve bounded unbiased representations. If X X X , Y Y Y independently represent a a a , b b b , their product represents a b ab ab and is bounded by B X B Y B_XB_Y B X B Y . Every repeated occurrence in a formula uses an independent representation; in particular, a square uses two independent copies. The formula is fixed, so these operations preserve constant expected cost.
Reciprocals. Suppose X X X represents a ≥ m > 0 a \ge m > 0 a ≥ m > 0 , with ∣ X ∣ ≤ B \lvert X\rvert\le B ∣ X ∣ ≤ B . Set c = m / 2 c = m/2 c = m /2 and D = B + c D = B + c D = B + c . The variable X − c X - c X − c has mean a − c ≥ c a - c \ge c a − c ≥ c and absolute value at most D D D , so the conversion above supplies an ( a − c ) / D (a - c)/D ( a − c ) / D -coin. In each trial, choose one of two branches uniformly. On the first branch, flip a known c / D c/D c / D -coin and return 1 on heads. On the second, flip an ( a − c ) / D (a - c)/D ( a − c ) / D -coin and return 0 on heads. On tails, repeat. A trial accepts with probability a / ( 2 D ) ≥ m / ( 2 D ) a/(2D) \ge m/(2D) a / ( 2 D ) ≥ m / ( 2 D ) , and the returned bit J J J satisfies
P { J = 1 } = c / ( 2 D ) a / ( 2 D ) = c a . \mathbb{P}\{J = 1\} = \frac{c/(2D)}{a/(2D)} = \frac{c}{a}. P { J = 1 } = a / ( 2 D ) c / ( 2 D ) = a c .
Thus J / c J/c J / c represents 1 / a 1/a 1/ a , is bounded by 1 / c 1/c 1/ c , and has constant expected cost. A quotient is the product of independent numerator and reciprocal representations.
Roots. For 0 < α < 1 0 < \alpha< 1 0 < α < 1 , Mendo [43 ] gives the following p α p^\alpha p α -coin. At iteration i = 1 , 2 , … i = 1, 2, \ldots i = 1 , 2 , … , flip a p p p -coin and return 1 on heads; otherwise return 0 with probability α / i \alpha/i α / i , and continue if neither event occurs. The expected number of input flips is p α − 1 p^{\alpha-1} p α − 1 , and each iteration has constant additional work. If X X X represents a ≥ m > 0 a \ge m > 0 a ≥ m > 0 with ∣ X ∣ ≤ B \lvert X\rvert\le B ∣ X ∣ ≤ B , convert it to an a / B a/B a / B -coin, apply this procedure, and multiply the returned bit by B α B^{\alpha} B α . The result represents a α a^{\alpha} a α , is bounded by B α B^{\alpha} B α , and has constant expected cost since a / B ≥ m / B a/B \ge m/B a / B ≥ m / B . We use α = 1 / 2 \alpha= 1/2 α = 1/2 and 1 / 4 1/4 1/4 .
Exponentials. If X X X represents a a a with ∣ X ∣ ≤ B \lvert X\rvert\le B ∣ X ∣ ≤ B , drawing X X X and then a known-bias coin with conditional bias ( X + B ) / ( 2 B ) (X+B)/(2B) ( X + B ) / ( 2 B ) gives a coin of bias p = ( a + B ) / ( 2 B ) p=(a+B)/(2B) p = ( a + B ) / ( 2 B ) . Draw N ∼ Poisson ( 2 B ) N \sim\operatorname{Poisson}(2B) N ∼ Poisson ( 2 B ) and let J = 1 J=1 J = 1 if all N N N independent p p p -coins are heads, including when N = 0 N=0 N = 0 . Then
E J = E [ p N ] = e 2 B ( p − 1 ) = e a − B . \mathbb{E}J=\mathbb{E}[p^N]=e^{2B(p-1)}=e^{a-B}. E J = E [ p N ] = e 2 B ( p − 1 ) = e a − B .
Hence e B J e^B J e B J represents e a e^a e a and is bounded by e B e^B e B . It uses at most 2 B 2B 2 B expected calls to the X X X -procedure. The Poisson count can be sampled using exponential interarrival times in expected O ( B + 1 ) O(B+1) O ( B + 1 ) work, which is constant for fixed B B B .
The final coin. Apply these constructions along the fixed formula Φ \Phi Φ . Every intermediate has a known finite support bound. The promised positive lower bounds permit all reciprocal and root steps, and Theorem 6.7 gives constant expected input calls and additional work for each representation. Write f = Φ ( p ) f=\Phi(p) f = Φ ( p ) and choose a support bound B ≥ 2 B\ge2 B ≥ 2 for its representation. Since f ≥ γ f\ge\gamma f ≥ γ , positive-mean conversion gives an f / B f/B f / B -coin. A final linear amplification with multiplier B B B and slack γ \gamma γ produces an exact f f f -coin, because f ≤ 1 − γ f\le1-\gamma f ≤ 1 − γ . All constants depend only on the formula and its promised bounds. Finite expected work implies almost sure termination.
Smooth one-variable functions
The proof uses a mixture of Bernstein polynomials. Choosing the polynomial first makes both the input-flip count and the coefficient-evaluation work easy to bound.
Proof of Theorem 6.2. Put g ( z ) = z ( 1 − z ) f ′ ′ ( z ) g(z)=z(1-z)f^{\prime\prime}(z) g ( z ) = z ( 1 − z ) f ′′ ( z ) and b n ( z ) = f ( z ) − g ( z ) / ( 2 n ) b_n(z)=f(z)-g(z)/(2n) b n ( z ) = f ( z ) − g ( z ) / ( 2 n ) . Define the degree-n n n Bernstein polynomial
P n ( p ) = ∑ j = 0 n b n ( j / n ) ( n j ) p j ( 1 − p ) n − j . P_n(p)=\sum_{j=0}^{n} b_n(j/n)\binom{n}{j}p^j(1-p)^{n-j}. P n ( p ) = j = 0 ∑ n b n ( j / n ) ( j n ) p j ( 1 − p ) n − j .
It converges uniformly to f f f . We first bound the change between degrees n n n and 2 n 2n 2 n at the coefficient level.
When P n P_n P n is expressed in degree 2 n 2n 2 n , its coefficient at index j j j is E b n ( Z ) \mathbb{E}b_n(Z) E b n ( Z ) , where Z = H / n Z=H/n Z = H / n and H H H is hypergeometric: sample n n n positions from 2 n 2n 2 n positions, of which j j j are marked. Writing z = j / ( 2 n ) z=j/(2n) z = j / ( 2 n ) , we have
E ( Z − z ) = E ( Z − z ) 3 = 0 , E ( Z − z ) 2 = z ( 1 − z ) 2 n − 1 , E ( Z − z ) 4 = O ( n − 2 ) . \mathbb{E}(Z-z)=\mathbb{E}(Z-z)^3=0,\qquad\mathbb{E}(Z-z)^2=\frac{z(1-z)}{2n-1},\qquad\mathbb{E}(Z-z)^4=O(n^{-2}). E ( Z − z ) = E ( Z − z ) 3 = 0 , E ( Z − z ) 2 = 2 n − 1 z ( 1 − z ) , E ( Z − z ) 4 = O ( n − 2 ) .
The odd moments vanish because a sample and its complement have the same law. The fourth-moment bound is uniform in j j j , as follows from the fourth central moment of a hypergeometric count. Taylor expansion through order three for f f f and through order one for g g g therefore gives
E b n ( Z ) = b 2 n ( z ) + O ( n − 2 ) , \mathbb{E}b_n(Z)=b_{2n}(z)+O(n^{-2}), E b n ( Z ) = b 2 n ( z ) + O ( n − 2 ) ,
uniformly in j j j . The constant is controlled by the bounds on the first four derivatives of f f f . Choose a fixed known L > 0 L>0 L > 0 such that every degree-2 n 2n 2 n coefficient of P 2 n − P n P_{2n}-P_n P 2 n − P n has absolute value at most L / n 2 L/n^2 L / n 2 .
Choose a sufficiently large fixed integer n 0 n_0 n 0 , and put
n j = 2 j n 0 , w j = 2 L / n j 2 , W = ∑ j ≥ 0 w j . n_j=2^j n_0,\qquad w_j=2L/n_j^2,\qquad W=\sum_{j\ge0}w_j. n j = 2 j n 0 , w j = 2 L / n j 2 , W = j ≥ 0 ∑ w j .
We can ensure W ≤ γ / 2 W \le\gamma/2 W ≤ γ /2 and that all coefficients of P n 0 P_{n_0} P n 0 lie in [ 3 γ / 4 , 1 − 3 γ / 4 ] [3\gamma/4,1-3\gamma/4] [ 3 γ /4 , 1 − 3 γ /4 ] . Consequently,
Q 0 = P n 0 − W / 2 1 − W , Q j + 1 = 1 2 + P 2 n j − P n j w j Q_0 = \frac{P_{n_0}-W/2}{1-W}, \qquad Q_{j+1} = \frac{1}{2}+\frac{P_{2n_j}-P_{n_j}}{w_j} Q 0 = 1 − W P n 0 − W /2 , Q j + 1 = 2 1 + w j P 2 n j − P n j
have Bernstein coefficients in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and telescoping gives
( 1 − W ) Q 0 + ∑ j ≥ 0 w j Q j + 1 = f . (1-W)Q_0+\sum_{j\ge0}w_jQ_{j+1}=f. ( 1 − W ) Q 0 + j ≥ 0 ∑ w j Q j + 1 = f .
Sample this mixture. To simulate the selected polynomial of degree m m m , flip the input coin m m m times and let h h h be the number of heads. Return a known-bias coin whose bias is the polynomial’s h h h -th Bernstein coefficient. Its unconditional bias is the selected polynomial evaluated at p p p , so the mixture is an exact f ( p ) f(p) f ( p ) -coin.
The expected number of input flips is at most
n 0 + ∑ j ≥ 0 2 n j w j < ∞ . n_0+\sum_{j\ge0}2n_jw_j<\infty. n 0 + j ≥ 0 ∑ 2 n j w j < ∞.
Only one Bernstein coefficient is needed on any invocation. For a degree-2 n 2n 2 n branch, compute the single hypergeometric expectation above using at most n + 1 n+1 n + 1 terms. Binomial-coefficient recurrences generate its probabilities in O ( n ) O(n) O ( n ) operations, and each term requires a constant-work evaluation of b n b_n b n . Thus the additional work on that branch is O ( n ) O(n) O ( n ) and has constant expectation as well. Mixture selection has constant expected work because the non-base weights are proportional to 4 − j 4^{-j} 4 − j . All constants depend only on f f f and γ \gamma γ , and the construction is uniform over p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] .
Finite precision
Finite precision suffices for both the deterministic optimizer and the randomized construction. The optimizer tolerates small errors in its updates; for the sampler, we instead implement its exact coin decisions by successively refining numerical bounds. The work cap then gives a finite computation on every invocation.
We count numerical bit operations, while treating graph access, vertex identifiers, and the known graph size n n n in the usual oracle or word model. Charging also for these O ( log n ) O(\log n) O ( log n ) -bit words introduces an additional polynomial factor in log n \log n log n . Independent random bits and uniform vertex samples are supplied by an oracle; we do not charge for storing or addressing random seeds. We may replace the requested accuracy by a dyadic number within a factor of two, so its description has O ( log ( 2 / ε ) ) O(\log(2/\varepsilon)) O ( log ( 2/ ε )) bits.
The optimizer and bounded messages
Proposition B.1. The deterministic construction can be implemented with finite arithmetic, retaining its ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) fractional-matching guarantee, its radius O ( ε − 1 log ( 2 Δ ) ) O(\varepsilon^{-1}\log(2\Delta)) O ( ε − 1 log ( 2Δ )) , and its bound ( 2 Δ ) O ( ε − 1 log ( 2 Δ ) ) (2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} ( 2Δ ) O ( ε − 1 l o g ( 2Δ )) on graph queries and numerical bit operations per edge query. There is also a distributed implementation using T = O ( ε − 1 log ( 2 Δ ) ) T=O(\varepsilon^{-1}\log(2\Delta)) T = O ( ε − 1 log ( 2Δ )) rounds and O ( log ( 2 Δ / ε ) ) O(\log(2\Delta/\varepsilon)) O ( log ( 2Δ/ ε )) bits per edge per round. The total computational work at each vertex v v v is at most
( deg ( v ) + 1 ) poly ( log ( 2 Δ ) ε ) . (\deg(v)+1)\operatorname{poly}\left(\frac{\log(2\Delta)}{\varepsilon}\right). ( deg ( v ) + 1 ) poly ( ε log ( 2Δ ) ) . In particular, this is an O ( ε − 1 log ( 2 Δ ) ) O(\varepsilon^{-1}\log(2\Delta)) O ( ε − 1 log ( 2Δ )) -round CONGEST algorithm when ε ≥ n − O ( 1 ) \varepsilon\ge n^{-O(1)} ε ≥ n − O ( 1 ) and Δ ≤ n \Delta\le n Δ ≤ n .
The useful error bound is a perturbation of the potential proof, not a comparison between the rounded and exact trajectories. Write n 0 n_0 n 0 for the number of nonisolated vertices and fix a numerical tolerance 0 < ω < 1 0 < \omega< 1 0 < ω < 1 . Store the transformed price τ \tau τ as a rational number, with the mathematical state price defined by x = tanh τ x = \tanh\tau x = tanh τ . Thus the state remains interior even when its price is very close to an endpoint. Numerical evaluations of x x x need not be exact. All rounding and evaluation rules are fixed and deterministic.
Errors in the update inequalities. Use the notation a ( h ) a(h) a ( h ) and MD from § 5.2 for the exact score and mirror-descent map at the current state. Require each implemented distribution update to have the form
p ~ + = M D p β ( a ( p ) + e ) , ∥ e ∥ ∞ ≤ ω . (34) \widetilde{p}^{+} = \mathrm{MD}_{p}^{\beta}(a(p) + e), \qquad\lVert e \rVert_{\infty} \le\omega. \tag*{(34)} p + = MD p β ( a ( p ) + e ) , ∥ e ∥ ∞ ≤ ω . (34)
For the second distribution update of the extragradient stage, the base is q ˉ \bar{q} q ˉ and the score is a ( q + ) a(q^{+}) a ( q + ) , as in Theorem 5.6. Require each implemented price response y ~ = tanh τ ~ \widetilde{y} = \tanh\widetilde{\tau} y = tanh τ to satisfy
∥ v x + 2 ( 1 + L h ) τ ~ − 2 ( 1 + L q ) τ ∥ ∞ ≤ ω . (35) \left\lVert v^{x} + 2(1 + Lh)\widetilde{\tau} - 2(1 + Lq)\tau\right\rVert_{\infty} \le\omega. \tag*{(35)} ∥ v x + 2 ( 1 + L h ) τ − 2 ( 1 + L q ) τ ∥ ∞ ≤ ω . (35)
Here v v v is the gradient vector prescribed by the algorithm at its current, possibly rounded, state. Errors in evaluating this vector are included in these residuals.
These conditions add at most 6 ω n 0 6\omega n_0 6 ω n 0 to the right-hand side of Theorem 5.5, and at most 8 ω n 0 8\omega n_0 8 ω n 0 to that of Theorem 5.6. Indeed, a score error contributes at most 2 ω n 0 2\omega n_0 2 ω n 0 in each use of the mirror-descent identity, since two distributions have ℓ 1 \ell_1 ℓ 1 distance at most two per block. Also,
∣ tanh ′ ( t ) ∣ ≤ 1 , ∣ d d t ψ ( tanh t ) ∣ = ∣ t ∣ sech 2 t ≤ 1. \lvert\tanh'(t) \rvert\le1, \qquad\left\lvert\frac{d}{dt}\psi(\tanh t) \right\rvert= \lvert t\rvert\operatorname{sech}^{2} t \le1. ∣ tanh ′ ( t )∣ ≤ 1 , d t d ψ ( tanh t ) = ∣ t ∣ sech 2 t ≤ 1.
By (B.2), the transformed output differs from the exact box response by at most ω / 2 \omega/2 ω /2 per coordinate. Consequently, replacing the exact response by this output contributes at most 2 ω n 0 2\omega n_0 2 ω n 0 through the proposal gradient and 2 ω n 0 2\omega n_0 2 ω n 0 through price stationarity. There is one mirror-descent error in the gradient stage and two in the extragradient stage, giving the asserted constants.
The proof of Theorem 5.7 therefore gives
η ⟨ g ( z t ′ ) , z t ′ − w ⟩ ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) + 22 ω n 0 . (36) \eta\langle g(z'_t), z'_t - w \rangle\le2\Phi_t(w) - 2\Phi_{t+1}(w) + 22\omega n_0. \tag*{(36)} η ⟨ g ( z t ′ ) , z t ′ − w ⟩ ≤ 2 Φ t ( w ) − 2 Φ t + 1 ( w ) + 22 ω n 0 . (36)
Keep the initial proposal distributions exact, and initialize τ 0 \tau_0 τ 0 within ω \omega ω of atanh ( − 1 + 1 / Δ ) \operatorname{atanh}(-1 + 1/\Delta) atanh ( − 1 + 1/Δ ) . For the comparison points in Theorem 5.8, this changes Φ 0 \Phi_0 Φ 0 by at most 7 ω n 0 7\omega n_0 7 ω n 0 . To see this, differentiate its price-dependent part with respect to one initial transformed price: the derivative is
− 2 ( 1 + ℓ v ( q 0 ) ) ( w v x − tanh τ v ) + 2 ( ℓ v ( q 0 ) − ℓ v ( q ∗ ) ) τ v sech 2 τ v , -2(1 + \ell_v(q_0))(w^x_v - \tanh\tau_v) + 2(\ell_v(q_0) - \ell_v(q^*))\tau_v \operatorname{sech}^{2}\tau_v, − 2 ( 1 + ℓ v ( q 0 )) ( w v x − tanh τ v ) + 2 ( ℓ v ( q 0 ) − ℓ v ( q ∗ )) τ v sech 2 τ v ,
whose absolute value is at most seven because ℓ v ( q 0 ) ≤ 1 / 4 \ell_v(q_0) \le1/4 ℓ v ( q 0 ) ≤ 1/4 and ℓ v ( q ∗ ) ∈ { 0 , 1 } \ell_v(q^*) \in\{0, 1\} ℓ v ( q ∗ ) ∈ { 0 , 1 } . Summing (B.3) exactly as in § 5.3 now yields
2 ν f ( G ) − P ( q ^ ) ≤ 3 B Δ ν f ( G ) + 21 ω n 0 T + 33 ω n 0 . (37) 2\nu_f(G) - P(\widehat{q}) \le\frac{3B\Delta\nu_f(G) + 21\omega n_0}{T} + 33\omega n_0. \tag*{(37)} 2 ν f ( G ) − P ( q ) ≤ T 3 B Δ ν f ( G ) + 21 ω n 0 + 33 ω n 0 . (37)
Thus ω = c ε / Δ \omega= c\varepsilon/\Delta ω = c ε /Δ for a sufficiently small absolute c > 0 c > 0 c > 0 , and T = C ε − 1 log ( 2 Δ ) T = C\varepsilon^{-1}\log(2\Delta) T = C ε − 1 log ( 2Δ ) for a sufficiently large C C C , leave a constant fraction of the error allowance for the final output rounding. We use n 0 ≤ 2 Δ ν f ( G ) n_0 \le2\Delta\nu_f(G) n 0 ≤ 2Δ ν f ( G ) from Theorem 2.4.
Implementing the residual bounds. Only modest absolute accuracy is needed in messages, even though locally stored probabilities may be very small. Let Π t = ( 1 + L q t ) τ t \Pi_t=(1+Lq_t)\tau_t Π t = ( 1 + L q t ) τ t . The main price update and (B.2) give
Π t + 1 = Π t + L q t ′ − 1 12 + r t 2 , ∥ r t ∥ ∞ ≤ ω . \Pi_{t+1}=\Pi_t+\frac{Lq'_t-1}{12}+\frac{r_t}{2}, \qquad\lVert r_t\rVert_\infty\le\omega. Π t + 1 = Π t + 12 L q t ′ − 1 + 2 r t , ∥ r t ∥ ∞ ≤ ω .
Since every load is at most Δ \Delta Δ , all transformed prices, including provisional responses, have magnitude O ( log ( 2 Δ ) + T Δ ) O(\log(2\Delta)+T\Delta) O ( log ( 2Δ ) + T Δ ) . The logarithmic-ratio recurrence in Theorem 5.9 still contracts by 1 / 4 1/4 1/4 , with an additional O ( ω ) O(\omega) O ( ω ) perturbation. It follows that all update ratios remain between fixed positive constants and every proposal probability is at least e − O ( T ) / ( 2 Δ 2 ) e^{-O(T)}/(2\Delta^2) e − O ( T ) / ( 2 Δ 2 ) .
Evaluate each unnormalized proposal weight to relative error O ( ω / β ) O(\omega/\beta) O ( ω / β ) , round it to a positive dyadic number, and normalize the resulting weights exactly. If a weight is changed by a factor e d e^d e d , this is precisely a score perturbation − β d -\beta d − β d ; allocating the error allowance between score evaluation and weight rounding gives (B.1). The normalized rational probabilities have numerators and denominators of O ( T + log ( Δ / ω ) ) O(T+\log(\Delta/\omega)) O ( T + log ( Δ/ ω )) bits. Elementary functions on these inputs can be evaluated by convergent series and range reduction in polynomial bit work. In particular, ψ ( tanh τ ) \psi(\tanh\tau) ψ ( tanh τ ) can be evaluated stably as τ tanh τ − log cosh τ \tau\tanh\tau-\log\cosh\tau τ tanh τ − log cosh τ , using log cosh τ = ∣ τ ∣ + log ( 1 + e − 2 ∣ τ ∣ ) − log 2 \log\cosh\tau=|\tau|+\log(1+e^{-2|\tau|})-\log2 log cosh τ = ∣ τ ∣ + log ( 1 + e − 2∣ τ ∣ ) − log 2 .
For communication, round each required scalar q u v q_{uv} q uv , x v x_v x v , or ψ ( x v ) \psi(x_v) ψ ( x v ) to absolute error at most h = 2 − b h=2^{-b} h = 2 − b , where
h ≤ ω C 1 ( T + 1 ) ( Δ + 1 ) 4 (38) h\le\frac{\omega}{C_1(T+1)(\Delta+1)^4} \tag*{(38)} h ≤ C 1 ( T + 1 ) ( Δ + 1 ) 4 ω (38)
for a sufficiently large absolute C 1 C_1 C 1 . Incoming load errors are at most Δ h \Delta h Δ h . The price formula divides by 1 + ℓ ≥ 1 1+\ell\ge1 1 + ℓ ≥ 1 and its numerator uses a transformed price of magnitude O ( T Δ + log Δ ) O(T\Delta+\log\Delta) O ( T Δ + log Δ ) . Consequently these message errors, and local rounding on the same mesh, contribute O ( ( T + 1 ) ( Δ + 1 ) 3 h ) O((T+1)(\Delta+1)^3h) O (( T + 1 ) ( Δ + 1 ) 3 h ) to the residual in (B.2). The preceding Lipschitz bounds give O ( ω ) O(\omega) O ( ω ) errors in the scores; choosing smaller constant fractions of the tolerances gives (B.1) as well. Each round has only a constant number of neighbor exchanges. Equation (B.5) requires b = O ( log ( T Δ / ε ) ) = O ( log ( 2 Δ / ε ) ) b=O(\log(T\Delta/\varepsilon))=O(\log(2\Delta/\varepsilon)) b = O ( log ( T Δ/ ε )) = O ( log ( 2Δ/ ε )) bits. All larger representations and normalizations remain local.
Each round processes O ( deg ( v ) + 1 ) O(\deg(v)+1) O ( deg ( v ) + 1 ) scalar entries at vertex v v v , with representations of O ( T + log ( Δ / ε ) ) O(T+\log(\Delta/\varepsilon)) O ( T + log ( Δ/ ε )) bits. Each scalar update requires polynomial bit work in this length. Summing over T T T rounds, and including initialization and final output rounding, gives the claimed total computational-work bound per vertex.
A feasible finite output. For the output average, round each transmitted tentative probability downward to the h h h -grid and put the missing mass on the dummy. The resulting average q b q^b q b satisfies q u v b ≤ q ^ u v q^b_{uv}\le\widehat q_{uv} q uv b ≤ q uv on real coordinates and
P ( q b ) ≥ P ( q ^ ) − n 0 Δ h . P(q^b)\ge P(\widehat q)-n_0\Delta h. P ( q b ) ≥ P ( q ) − n 0 Δ h .
Its entries have denominator T 2 b T2^b T 2 b , so its loads and accepted directed assignments can be computed exactly with O ( b + log ( T Δ ) ) O(b+\log(T\Delta)) O ( b + log ( T Δ )) -bit rational numbers. Round each accepted directed assignment downward to a common dyadic grid of spacing at most ε / Δ \varepsilon/\Delta ε /Δ , exchange the two directed values, and average them as in (16) . This gives exact endpoint agreement and preserves feasibility. The final decrease in fractional value is at most ∣ E ∣ ε / Δ ≤ 2 ε ν f ( G ) \lvert E\rvert\varepsilon/\Delta\le2\varepsilon\nu_f(G) ∣ E ∣ ε /Δ ≤ 2 ε ν f ( G ) . Together with (B.4), this proves the value guarantee in Theorem B.1. The local polynomial bit work is absorbed by the stated LCA bound. For arbitrary smaller ε \varepsilon ε , splitting a scalar message across CONGEST rounds gives the bound
O ( log ( 2 Δ ) ε ⌈ log ( 2 Δ / ε ) log n ⌉ ) . O\left(\frac{\log(2\Delta)}{\varepsilon}\left\lceil\frac{\log(2\Delta/\varepsilon)}{\log n}\right\rceil\right). O ( ε log ( 2Δ ) ⌈ log n log ( 2Δ/ ε ) ⌉ ) .
Exact sampling with finite arithmetic
For the randomized construction, we keep the original exact iterates as the target distributions.
Proposition B.2. With the randomness oracle described above, the uncapped sampler has an exact implementation with expected numerical bit work ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) . Capping this work, rather than the number of exact-real operations, retains all the guarantees and asymptotic bounds of Theorem 1.1 . Every capped invocation uses finite precision and terminates within its deterministic work budget.
Known numerical biases. A coin with a computable bias a a a does not require computing a a a exactly. Compute certified intervals containing a a a and reveal bits of an independent uniform random number until the two intervals are disjoint. With interval widths O ( 2 − r ) O(2^{-r}) O ( 2 − r ) , the probability of remaining undecided is O ( 2 − r ) O(2^{-r}) O ( 2 − r ) , uniformly in a a a . Thus a bias evaluable to error 2 − r 2^{-r} 2 − r in poly ( s + r ) \operatorname{poly}(s+r) poly ( s + r ) bit operations has an exact coin implementation with poly ( s + 1 ) \operatorname{poly}(s+1) poly ( s + 1 ) expected bit work. This observation concerns known numerical coefficients inside a factory; unknown input biases are still accessed only through independent input flips.
The smooth factory. The proof of Theorem 6.2 selects a polynomial of degree Θ ( 2 j ) \Theta(2^j) Θ ( 2 j ) with probability O ( 4 − j ) O(4^{-j}) O ( 4 − j ) . For a degree-2 n 2n 2 n branch, its only nontrivial coefficient is a scaled difference involving a hypergeometric expectation of b n ( H / n ) b_n(H/n) b n ( H / n ) . It is enough to approximate this coefficient to error 2 − r 2^{-r} 2 − r in
n poly ( log ( n + 1 ) + r ) (39) n\operatorname{poly}(\log(n+1)+r) \tag*{(39)} n poly ( log ( n + 1 ) + r ) (39)
bit operations. This avoids the unnecessary cost of forming exact large binomial coefficients. Here is such an evaluation. For H ∼ Hypergeom ( 2 n , j , n ) H \sim\operatorname{Hypergeom}(2n,j,n) H ∼ Hypergeom ( 2 n , j , n ) , start at a mode with unnormalized weight one. Generate the other weights outward using adjacent probability ratios, which are at most one in this direction; for example,
P { H = k + 1 } P { H = k } = ( j − k ) ( n − k ) ( k + 1 ) ( n − j + k + 1 ) . \frac{\mathbb{P}\{H=k+1\}}{\mathbb{P}\{H=k\}}=\frac{(j-k)(n-k)}{(k+1)(n-j+k+1)}. P { H = k } P { H = k + 1 } = ( k + 1 ) ( n − j + k + 1 ) ( j − k ) ( n − k ) .
There are O ( n ) O(n) O ( n ) terms, and the sum of the unnormalized weights is at least one. With s s s fractional bits, rounding these products and sums introduces O ( n 2 2 − s ) O(n^2 2^{-s}) O ( n 2 2 − s ) error. The mixture coefficient scales the difference by O ( n 2 ) O(n^2) O ( n 2 ) , so s = r + O ( log ( n + 1 ) ) s=r+O(\log(n+1)) s = r + O ( log ( n + 1 )) suffices. Evaluating f f f and f ′ ′ f'' f ′′ at this precision therefore gives (B.6) whenever their evaluation cost is polynomial in the argument length and precision. The known-bias comparison above makes the expected work of this branch n poly ( log ( n + 1 ) ) n\operatorname{poly}(\log(n+1)) n poly ( log ( n + 1 )) . Summing over branches gives a constant, since ∑ j ≥ 0 4 − j 2 j poly ( j + 1 ) < ∞ \sum_{j\ge0}4^{-j}2^j\operatorname{poly}(j+1)<\infty ∑ j ≥ 0 4 − j 2 j poly ( j + 1 ) < ∞ .
The conversion functions used in § 6.5 satisfy this evaluation condition. They are fixed affine rescalings of
F ( ξ ) = tanh ξ 1 − ξ 2 , G ( ξ ) = ψ ( F ( ξ ) ) , F(\xi)=\tanh\frac{\xi}{\sqrt{1-\xi^2}}, \qquad G(\xi)=\psi(F(\xi)), F ( ξ ) = tanh 1 − ξ 2 ξ , G ( ξ ) = ψ ( F ( ξ )) ,
extended constantly past ξ = ± 1 \xi=\pm1 ξ = ± 1 . For t = ξ / 1 − ξ 2 t=\xi/\sqrt{1-\xi^2} t = ξ / 1 − ξ 2 , their deviations from the endpoint values, and their second derivatives, are bounded by C 2 ( 1 + ∣ t ∣ ) 7 e − 2 ∣ t ∣ C_2(1+|t|)^7e^{-2|t|} C 2 ( 1 + ∣ t ∣ ) 7 e − 2∣ t ∣ . Thus when ∣ t ∣ ≥ C 3 ( r + 1 ) |t|\ge C_3(r+1) ∣ t ∣ ≥ C 3 ( r + 1 ) one uses the endpoint values and zero derivatives to precision 2 − r 2^{-r} 2 − r . Otherwise all elementary evaluations have arguments of polynomial size in r r r and the input length.
Elementary formulas. For a finite-arithmetic implementation of Theorem 6.1, one may use the preceding smooth factory in place of its individual nonlinear constructions. Retain its bounded unbiased representations: E X = a \mathbb{E}X=a E X = a and ∣ X ∣ ≤ B |X|\le B ∣ X ∣ ≤ B for a fixed known bound B B B . A draw of X X X , followed by a coin of bias ( X + B ) / ( 2 B ) (X+B)/(2B) ( X + B ) / ( 2 B ) , supplies a coin of bias ( a + B ) / ( 2 B ) (a+B)/(2B) ( a + B ) / ( 2 B ) . For each reciprocal, root, or exponential operation, extend the desired scalar function smoothly outside its promised interval and encode its output inside a fixed subinterval of ( 0 , 1 ) (0,1) ( 0 , 1 ) . Such an extension can be chosen using fixed polynomial transition functions, with f f f and f ′ ′ f^{\prime\prime} f ′′ evaluable in polynomial bit work. The smooth factory gives its encoded output coin, which decodes to another bounded unbiased representation. Addition and multiplication of independent representations work as before. Finally, use a smooth extension of the affine decoding map that agrees with the requested output bias on [ γ , 1 − γ ] [\gamma,1-\gamma] [ γ , 1 − γ ] . The formula and all interval bounds are fixed, so this implementation has constant expected input calls and additional numerical bit work. It changes no output law. This assertion concerns the computable constants and fixed functions in our sampler, not arbitrary real constants in a general factory specification.
Composition and the work cap. The initialization coins have expected poly ( log ( 2 Δ ) ) \operatorname{poly}(\log(2\Delta)) poly ( log ( 2Δ )) numerical bit cost. Applying Theorem 6.7 through the same constant-depth dependencies as in Theorem 6.8 bounds a round-t t t invocation by A t + 1 poly ( t + log ( 2 Δ ) ) A^{t+1}\operatorname{poly}(t+\log(2\Delta)) A t + 1 poly ( t + log ( 2Δ )) expected bit work, for an absolute A A A . Consequently the exact sampler still has expected work ( 2 Δ ) O ( 1 / ε ) (2\Delta)^{O(1/\varepsilon)} ( 2Δ ) O ( 1/ ε ) . Use this bound in (30) , with the same abort probability τ = Θ ( ε / Δ ) \tau=\Theta(\varepsilon/\Delta) τ = Θ ( ε /Δ ) , counting all numerical work and recursive calls against the budget. The coupling proof of Theorem 7.1 is unchanged: an unfinished proposal becomes the dummy, so real-coordinate probabilities only decrease. Fixed random streams reproduce the same capped outputs on every reevaluation.
The marking probability in (33) is a power of two, so each rounding mark uses exactly s = O ( log ( 2 / ε ) ) s=O(\log(2/\varepsilon)) s = O ( log ( 2/ ε )) random bits. This deterministic cost is included in the rounding bound of Theorem 9.3 . The estimator uses fresh uniform vertex samples and the same capped proposals. Its integer counts can be accumulated by binary counters, with amortized constant bit work per increment; there are at most Δ K \Delta K Δ K increments per trial. Hence both the LCA and estimator retain their stated worst-case numerical work bounds. The uncapped exact sampler can require arbitrarily fine precision on rare executions; no fixed precision bound for that uncapped procedure is claimed or needed.