# Faster Matchings via Learned Duals

Michael Dinitz Department of Computer Science, Johns Hopkins University,
Baltimore, MD<EMAIL_ADDRESS>Supported in part by NSF grant CCF-1909111.
Sungjin Im Electrical Engineering and Computer Science, University of
California, 5200 N. Lake Road, Merced CA 95344<EMAIL_ADDRESS>Supported
in part by NSF grants CCF-1617653 and CCF-1844939. Thomas Lavastida Tepper
School of Business, Carnegie Mellon University, Pittsburgh, PA.
<EMAIL_ADDRESS>Supported in part by NSF grants CCF-1824303,
CCF-1845146, CCF-1733873 and CMMI-1938909. Benjamin Moseley Tepper School of
Business, Carnegie Mellon University, Pittsburgh, PA<EMAIL_ADDRESS>Supported in part by a Google Research Award, an Infor Research Award, a
Carnegie Bosch Junior Faculty Chair and NSF grants CCF-1824303, CCF-1845146,
CCF-1733873 and CMMI-1938909. Sergei Vassilvitskii Google Research New York,
NY<EMAIL_ADDRESS>
###### Abstract

A recent line of research investigates how algorithms can be augmented with
machine-learned predictions to overcome worst case lower bounds. This area has
revealed interesting algorithmic insights into problems, with particular
success in the design of competitive online algorithms. However, the question
of improving algorithm running times with predictions has largely been
unexplored.

We take a first step in this direction by combining the idea of machine-
learned predictions with the idea of “warm-starting" primal-dual algorithms.
We consider one of the most important primitives in combinatorial
optimization: weighted bipartite matching and its generalization to
$b$-matching. We identify three key challenges when using learned dual
variables in a primal-dual algorithm. First, predicted duals may be
infeasible, so we give an algorithm that efficiently maps predicted infeasible
duals to nearby feasible solutions. Second, once the duals are feasible, they
may not be optimal, so we show that they can be used to quickly find an
optimal solution. Finally, such predictions are useful only if they can be
learned, so we show that the problem of learning duals for matching has low
sample complexity. We validate our theoretical findings through experiments on
both real and synthetic data. As a result we give a rigorous, practical, and
empirically effective method to compute bipartite matchings.

##  1 Introduction

Classical algorithm analysis considers worst case performance of algorithms,
capturing running times, approximation and competitive ratios, space
complexities, and other notions of performance. Recently there has been a
renewed interest in finding formal ways to go beyond worst case analysis [48],
to better understand performance of algorithms observed in practice, and
develop new methods tailored to typical inputs observed.

An emerging line of research dovetails this with progress in machine learning,
and asks how algorithms can be augmented with machine-learned predictors to
circumvent worst case lower bounds when the predictions are good, and
approximately match them otherwise (see Mitzenmacher and Vassilvitskii [39]
for a survey). Naturally, a rich area of applications of this paradigm has
been in online algorithms, where the additional information revealed by the
predictions reduces the uncertainty about the future and can lead to better
choices, and thus better competitive ratios. For instance, see the work by
Lykouris and Vassilvitskii [36], Rohatgi [47], Jiang et al. [31] on caching;
Antoniadis et al. [4], Dütting et al. [22] on the classic secretary problem;
Purohit et al. [46], Lattanzi et al. [34] on scheduling; Purohit et al. [46],
Anand et al. [2] on ski rental; and Bamas et al. [9] on set cover.

However, the power of predictions is not limited to improving online
algorithms. Indeed, the aim of the empirical paper that jump-started this area
by Kraska et al. [33] was to improve running times for basic indexing
problems. The main goal and contribution of this work is to show that at least
in one important setting (weighted bipartite matching), we can give formal
justification for using machine learned predictions to improve running times:
there are predictions which can provably be learned, and if these predictions
are “good” then we have running times that outperform standard methods both in
theory and empirically.

How can predictions help with running time? One intuitive approach, which has
been used extensively in practice, is through the use of “warm-start"
heuristics [54, 26, 25, 41], where instead of starting with a blank slate, the
algorithm begins with some starting state (which we call a warm-start
“solution" or “seed") which hopefully allows for faster completion. While it
is a common technique, there is a dearth of analysis understanding what
constitutes a good warm-start, when such initializations are helpful, and how
they can best be leveraged.

Thus we have a natural goal: put warm-start heuristics on firm theoretical
footing by interpreting the warm-start solution as learned predictions. In
this set up we are given a number of instances of the problem (the training
set), and we can use them to compute a warm-start solution that will
(hopefully) allow us to more quickly compute the optimal solution on future,
test-time, instances. There are three challenges that we must address:

  1. (i)

Feasibility. The learned prediction (warm-start solution) might not even be
_feasible_ for the specific instance we care about! For example, the learned
solution may be matching an edge that does not exist in the graph at testing
time.

  2. (ii)

Optimization. If the warm-start solution is feasible and near-optimal then we
want the algorithm to take advantage of it. In other words, we would like our
running time to be a function of the quality of the learned solution.

  3. (iii)

Learnability. It is easy to design predictions that are enormously helpful but
which cannot actually be learned (e.g., the “prediction" is the optimal
solution). We need to ensure that a typical solution learned from a few
instances of the problem generalizes well to new examples, and thus offers
potential speedups.

If we can overcome these three challenges, we will have an _end-to-end_
framework for speeding up algorithms via learned predictions: use the solution
to challenge (iii) to learn the predictions from historical data, use the
solution to challenge (i) to quickly turn the prediction into something
feasible for the particular problem instance while preserving near-optimality,
and then use this as a warm-start seed in the solution to challenge (ii).

###  1.1 Our Contributions

We focus on one of the fundamental primitives of combinatorial optimization:
computing bipartite matchings. For the bipartite minimum-weight perfect
matching (MWPM) problem, as well as its extension to $b$-matching, we show
that the above three challenges can be solved.

Instead, following the work of [17, 53], we look at the _dual_ problem; that
is, the dual to the natural linear program. We quantify the “quality” of a
prediction $\hat{y}$ by its $\ell_{1}$-distance from the true optimal dual
$y^{*}$, i.e., by $\|\hat{y}-y^{*}\|_{1}$. The smaller quantities correspond
to better predictions. Since the dual is a packing problem we must contend
with feasibility: we give a simple linear time algorithm that converts the
prediction $\hat{y}$ into a feasible dual while increasing the $\ell_{1}$
distance by a factor of at most 3.

Next, we run the Hungarian method starting with the resulting feasible dual.
Here, we show that the running time is in proportional to the $\ell_{1}$
distance of the feasible dual to the optimal dual (Theorem 13). Finally, we
show via a pseudo-dimension argument that not many samples are needed before
the empirically optimal seed is a good approximation of the true optimum
(Theorem 14), and that this empirical optimum can be computed efficiently
(Theorem 23). For the learning argument, we assume that matching instances are
drawn from a fixed but unknown distribution ${\cal D}$.

Putting it all together gives us our main result.

######  Theorem 1 (Informal).

There are three algorithms (learning, feasibility, optimization) with the
following guarantees.

  * •

Given a (possibly infeasible) dual $\hat{y}$ from the learning algorithm,
there exists an $O(m+n)$ time algorithm that takes a problem instance $c$, and
outputs a feasible dual $\hat{y}^{\prime}(c)$ such that
$\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1}\leq 3\|\hat{y}-y^{*}(c)\|_{1}$.

  * •

The optimization algorithm takes as input feasible dual $\hat{y}^{\prime}(c)$
and outputs a minimum weight perfect matching, and runs in time
$\tilde{O}(m\sqrt{n}\
\cdot\min\\{\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1},\sqrt{n}\\})$.

  * •

After $\tilde{O}(C^{2}n^{3})$ samples from an unknown distribution ${\cal D}$
over problem instances, the learning algorithm produces duals $\hat{y}$ so
that $\mathbb{E}_{c\sim{\cal D}}\ [\|\hat{y}-y^{*}(c)\|_{1}]$ is approximately
minimum among all possible choices of $\hat{y}$, where $C$ is the maximum edge
cost and $y^{*}(c)$ is an optimal dual for instance $c$.

Combining these gives a single algorithm that, with access to
$\tilde{O}(C^{2}n^{3})$ problem instance samples from ${\cal D}$, has expected
running time on future instances from ${\cal D}$ of only
$\tilde{O}(m\sqrt{n}\min\\{\alpha,\sqrt{n}\\})$, where
$\alpha=\min_{y}\mathbb{E}_{c\sim{\cal D}}\ [\|y-y^{*}(c)\|_{1}]$.

We emphasize that the Hungarian method with $\tilde{O}(mn)$ running time is
the standard algorithm in practice. Although there are other theoretically
faster exact algorithms for bipartite minimum-weight perfect matching [44, 24,
23, 21], including [21] that runs in $O(m\sqrt{n}\log(nC))$, they are
relatively complex (using various scaling techniques). In fact, we could not
find any implementation of them, while multiple implementations of the
Hungarian method are readily available.

Note that our result shows that we can speed up the Hungarian method as long
as the $\ell_{1}$-norm error of the learned dual, i.e.,
$\|\hat{y}-y^{*}(c)\|_{1}$ is $o(\sqrt{n})$. Further, as the projection step
that converts the learned dual into a feasible dual takes only linear time,
the overhead of our method is essentially negligible. Therefore, even if the
prediction is of poor quality, our method has worst-case running time that is
_never_ worse than that of the Hungarian algorithm. Even our learning
algorithm is simple, consisting of a straightforward empirical risk
minimization algorithm (the analysis is more complex and involves bounding the
“pseudo-dimension” of the loss functions).

We validate our theoretical results via experiments. For each dataset we first
feed a small number of samples (fewer than our theoretical bounds) to our
learning algorithm. We then compare the running time of our algorithm to that
of the classical Hungarian algorithm on new instances.

Details of these experiments can be found in Section 4. At a high level they
show that our algorithm is _significantly_ faster in practice. Further, our
experiment shows only very few samples are needed to achieve a notable speed-
up. This confirms the power of our approach, giving a theoretically rigorous
yet also practical method for warm-start primal-dual algorithms.

###  1.2 Related Work

Matchings and $b$-Matchings: Bipartite matchings are one of the most well
studied problems in combinatorial optimization, with a long history of
algorithmic improvements. We refer the interested reader to Duan and Pettie
[20] for an overview. We highlight some particular results here. We are
interested in the weighted versions of these problems and when all edge
weights are integral. Let $C$ be the maximum edge weight, $n$ be the number of
vertices, and $m$ the number of edges. For finding exact solutions to the
minimum weight perfect matching problem, the scaling technique leads to a
running time of $O(m\sqrt{n}\log(nC))$ [44, 24, 23, 21]. For dense graphs
there is a slightly better algorithm running in time
$O(n^{5/2}\log(nC)(\frac{\log\log(n)}{\log(n)})^{1/4})$ [14]. Finally,
algebraic techniques can be used to get a run time of $O(Cn^{\omega})$ [49],
where $\omega$ is the exponent for fast matrix multiplication.

The minimum cost $b$-matching problem and its generalization, the minimum cost
flow problem, have also been extensively studied. See [42] for a summary of
classical results. More recently there has been improvements by applying
interior point methods. The algorithm of [16] has running time
$\tilde{O}(m^{3/2}\log^{2}(C)$) and it is improved by the algorithm of [35]
which runs in time $\tilde{O}(m\sqrt{n}\log^{O(1)}(C))$.

Large scale bipartite matchings have been studied extensively in the online
setting, as they represent the basic problem in ad allocations [37]. While the
ad allocation is inherently online, most of the methods precompute a dual
based solution based on a sample of the input [17, 53], and then argue that
this solution is approximately optimal on the full instance. In contrast, we
strive to compute the exactly optimal solution, but use previous instances to
improve the running time of the approach.

Algorithms with Predictions: Kraska et al. [33] showed how to use machine
learned predictions to improve heavily optimized indexing algorithms. The
original paper was purely empirical and came with no rigorous guarantees;
recently there has been a flurry of work putting such approaches on a strong
theoretical foundation, evaluating the benefit of augmenting classical
algorithms with machine learned predictions, see [39] for a survey. Online and
streaming algorithms in particular have seen significant successes, as
predictions reveal information about the future and can help guide the
algorithms’ choices. This has led to the design of new methods for caching
[36, 47, 31], scheduling [46, 34], frequency counting [15, 30, 1], and
membership testing [38, 51] that can break through worst-case lower bounds
when the predictions are of sufficiently high quality.

Most of the above work abstracts the predictions as access to an error-prone
oracle and asks how to best use predictions: getting performance gains when
the predictions are good, but limiting the losses when they are not. A related
emergent area is that of data driven algorithm design [28, 8, 6, 5, 7, 13].
Here, the objective is to “learn” a good algorithm for a particular family of
inputs. The goal is not typically to tie the performance of the algorithm to
the quality of the prediction, but rather to show that the prediction makes
sense; that is only a small number of problem samples are needed in order to
ensure the learned algorithm generalizes to new data points.

Comparison to Dynamic Algorithms: A natural counterpoint to our approach is
the area of _dynamic algorithms_. In dynamic algorithms, we attempt to design
algorithms that allow us to very quickly recompute the optimal solution when
there is a single (or a very small number) of changes in the input. In other
words, the input is changing over time, and we need to always maintain an
optimal solution as it changes. There has been an active line of work on
dynamic matching algorithms, see [11, 50].

This is in some sense very similar to what we are trying to do, since we are
also trying to quickly compute an optimal solution when we have a history and
previous optimal solutions. But these two approaches, of dynamic algorithms
and of machine-learned predictions for warm-start, are quite different and are
actually highly complementary. Dynamic algorithms work extremely well in the
setting where the input changes slowly but where the output can change
quickly, since they are optimized to handle _single_ changes in the input
(e.g., a single edge being added or removed from the graph). Our approach, on
the other hand, works extremely well when the input can change dramatically
but the optimal solution is relatively stable, since then our learned dual
values will be quite close to optimal.

###  1.3 Roadmap

We begin with preliminaries and background in Section 2. We then present our
main theoretical results on min-cost perfect bipartite matching in Section 3.
The experiments are presented in Section 4. Finally, the extension to
$b$-matching is presented in Section 5.

##  2 Preliminaries

##### Notation:

Let $G=(V,E)$ be an undirected graph. We will use $N(i):=\\{e\in E\mid i\in
e\\}$ to be the set of edges adjacent to vertex $i$. Similarly if $G$ is
directed, then we use $N^{+}(i)$ and $N^{-}(i)$ to be the set of edges leaving
$i$ and the set of edges entering $i$, respectively. For a set $S\subseteq V$,
let $\Gamma(S)$ be the vertex neighborhood of $S$. For a vector
$y\in\mathbb{R}^{n}$, we let $\|y\|_{1}=\sum_{i}|y_{i}|$ be its
$\ell_{1}$-norm. Let $\langle x,y\rangle$ be the standard inner product on
$\mathbb{R}^{n}$.

Linear Programming and Complementary Slackness: Here we recall optimality
conditions for linear programming that are used to ensure the correctness of
some algorithms we present. Consider the primal-dual pair of linear programs
below.

$\begin{array}[]{cc}\min&c^{\top}x\\\ &Ax=b\\\ &x\geq 0\end{array}$ ($P$)
$\begin{array}[]{cc}\max&b^{\top}y\\\ &A^{\top}y\leq c\end{array}$ ($D$)

A pair of solutions $x,y$ for $(P)$ and $(D)$, respectively, satisfy
complementary slackness if $x^{\top}(c-A^{\top}y)=0$. The following lemma is
well-known.

######  Lemma 2.

Let $x$ be a feasible solution for $(P)$ and $y$ be a feasible solution for
$(D)$. If the pair $x,y$ satisfies complementary slackness, then $x$ and $y$
are optimal solutions for their respective problems.

Maximum Cardinality Matching: Let $G=(V,E)$ be a bipartite graph on $n$
vertices and $m$ edges. A matching $M\subseteq E$ is a collection of non-
intersecting edges. The Hopcroft-Karp algorithm for finding a matching
maximizing $|M|$ runs in time $O(\sqrt{n}\cdot m)$ [29], which is still state-
of-the-art for general bipartite graphs. For moderately dense graphs, a recent
result by van den Brand et al. [52] gives a better running time of
$\tilde{O}(m+n^{1.5})$ (where $\tilde{O}$ hides polylogarithmic factors).

Minimum Weight Perfect Matching (MWPM): Again, let $G=(V,E)$ be a bipartite
graph on $n$ vertices and $m$ with costs $c\in\mathbb{Z}_{+}^{E}$ on the
edges, and let $C$ be the maximum cost. A matching $M$ is _perfect_ if every
vertex is matched by $M$. The objective of this problem is to find a perfect
matching $M$ minimizing the cost $c(M):=\sum_{e\in M}c_{e}$.

When looking for optimal solutions we can assume that $G$ is a complete graph
by adding all possible edges not in $E$ with weight $Cn^{2}$. It is easy to
see that any $o(n)$ approximate solution would not use any of these edges.

Maximum Flow: Now let $G=(V,E)$ be a directed graph on $n$ vertices and $m$
edges with a capacity vector $u\in\mathbb{R}_{+}^{E}$. Let $s$ and $t$ be
distinct vertices of $G$. An $st$-flow is a vector $f\in\mathbb{R}_{+}^{E}$
satisfying $\sum_{e\in N^{+}(i)}f_{e}-\sum_{e\in N^{-}(i)}f_{e}=0$ for all
vertices $i\neq s,t$. An $st$-flow $f$ is maximum if it maximizes $\sum_{e\in
N^{+}(s)}f_{e}=\sum_{e\in N^{-}(t)}f_{e}$. The algorithm due to Orlin [43] and
King, Rao, and Tarjan [32] runs in time $O(nm)$.

##  3 Faster Min-Weight Perfect Matching

In this section we describe how predictions can be used to speed up the
bipartite Minimum Weight Perfect Matching (MWPM) problem.

The MWPM problem can be modeled by the following linear program and its dual –
the primal-dual view will be very useful for our algorithm and analysis. We
will sometimes refer to a set of dual variables $y$ as dual _prices_. Both LPs
are well-known to be integral, implying that there always exist integral
optimal solutions.

$\begin{array}[]{ccc}\min&\displaystyle\sum_{e\in E}c_{e}x_{e}&\\\
&\displaystyle\sum_{e\in N(i)}x_{e}=1&\forall i\in V\\\ &x_{e}\geq 0&\forall
e\in E\end{array}$ (MWPM-P) $\begin{array}[]{ccc}\max&\displaystyle\sum_{i\in
V}y_{i}&\\\ &\displaystyle y_{i}+y_{j}\leq c_{e}&\forall e=ij\in E\\\
\end{array}$ (MWPM-D)

Suppose we are given a prediction $\hat{y}$ of a dual solution. If $\hat{y}$
is feasible, then by complementary slackness we can check if $\hat{y}$
represents an optimal dual solution by running a maximum cardinality matching
algorithm on the graph $G^{\prime}=(V,E^{\prime})$, where
$E^{\prime}=\\{e=ij\in E\mid\hat{y}_{i}+\hat{y}_{j}=c_{ij}\\}$ is the set of
tight edges. If this matching is perfect, then its incidence vector $x$
satisfies complementary slackness with $\hat{y}$ and thus represents an
optimal solution by Lemma 2.

We now consider the problem from another angle, factoring in learning aspects.
Suppose the graph $G=(V,E)$ is fixed but the edge cost vector
$c\in\mathbb{Z}^{E}_{+}$ varies (is drawn from some distribution ${\cal D}$).
If we are given an optimal dual $y^{*}$ as a prediction, then we can solve the
problem by solving the max cardinality matching problem only once. However,
the optimal dual can significantly change depending on edge cost $c$.
Nevertheless, we will show how to learn “good” dual values and use them later
to solve new MWPM instances faster. Specifically, we seek to design an end-to-
end algorithm addressing all the aforementioned challenges:

  1. 1.

Feasiblity (Section 3.1). The learned dual $\hat{y}$ may not be feasible for
MWPM-D with some specific cost vector $c$. We show how to quickly convert it
to a feasible dual $\hat{y}^{\prime}(c)$ by appropriately decreasing the dual
values (the more we decrease them, the further we move away from the optimum).
Finding the feasible dual minimizing $\|\hat{y}-\hat{y}^{\prime}(c)\|_{1}$
turns out to be a variant of the vertex cover problem, for which we give a
simple $2$-approximation running in $O(m+n)$ time. As a result, we have
$\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1}\leq 3\|\hat{y}-y^{*}(c)\|_{1}$. See
Theorem 7.

  2. 2.

Optimization (Section 3.2). Now that we have a feasible solution
$\hat{y}^{\prime}(c)$, we want to find an optimal solution starting with
$\hat{y}^{\prime}(c)$ in time that depends on the quality of
$\hat{y}^{\prime}(c)$. Fortunately, the Hungarian algorithm can be seeded with
any feasible dual, so we can “warm-start" it with $\hat{y}^{\prime}(c)$. We
show that its running time will be proportional to
$|\|\hat{y}^{\prime}(c)\|_{1}-\|y^{*}(c)\|_{1}|\leq\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1}$.
See Theorem 13. Our analysis does not depend on the details of the Hungarian
algorithm, and so applies to a broader class of primal-dual algorithms.

  3. 3.

Learnability (Section 3.3). The target dual we seek to learn is
$\arg\min_{y}\mathbb{E}_{c\sim{\cal D}}\|y-y^{*}(c)\|$; here $y^{*}(c)$ is the
optimal dual for MWPM-D with cost vector $c$. We show we can efficiently learn
$\hat{y}$ that is arbitrarily close to the target vector after
$\tilde{O}(C^{2}n^{3})$ samples from ${\cal D}$. See Theorem 14.

Combining all of these gives the following, which is a more formal version of
Theorem 1. Let ${\cal D}$ be an arbitrary distribution over edge costs where
every vector in the support of ${\cal D}$ has maximum cost $C$. For any edge
cost vector $c$, let $y^{*}(c)$ denote the optimal dual solution.

######  Theorem 3.

For any $p,\epsilon>0$, there is an algorithm which:

  * •

After $O\left(\left(\frac{nC}{\epsilon}\right)^{2}(n\log n+\log(1/p))\right)$
samples from ${\cal D}$, returns dual values $\hat{y}$ such that
$\displaystyle\mathbb{E}_{c\sim{\cal
D}}[\|\hat{y}-y^{*}(c)\|_{1}]\leq\min_{y}\mathbb{E}_{c\sim{\cal
D}}[\|y-y^{*}(c)\|_{1}]+\epsilon$ with probability at least $1-p$.

  * •

Using the learned dual $\hat{y}$, given edge costs $c$, computes a min-cost
perfect matching in time
$O\left(m\sqrt{n}\cdot\min\\{\|\hat{y}-y^{*}(c)\|_{1},\sqrt{n}\\}\right)$.

In the rest of this section we detail our proof of this Theorem.

###  3.1 Recovering a Feasible Dual Solution (Feasibility)

Let $\hat{y}$ be an infeasible set of (integral) dual prices – this should be
thought of as the “good" dual obtained by our learning algorithm. Our goal in
this section is to find a new _feasible_ dual solution $\hat{y}^{\prime}(c)$
that is close to $\hat{y}$, for a given MWPM-D instance with cost $c$. In
particular we seek to find the closest feasible dual under $\ell_{1}$ norm,
i.e. one minimizing $\|\hat{y}^{\prime}(c)-\hat{y}\|_{1}$.

Looking at (MWPM-D), it is clear that we need to decrease the given dual
values $\hat{y}$ in order to make it feasible. More formally, we are looking
for a vector of non-negative perturbations $\delta$ such that
$\hat{y}^{\prime}:=\hat{y}-\delta$ is feasible. We model finding the best set
of perturbations, in terms of preserving $\hat{y}$’s dual objective value, as
a linear program. Let $F:=\\{e=ij\in E\mid\hat{y}_{i}+\hat{y}_{j}>c_{ij}\\}$
be the set of dual infeasible edges under $\hat{y}$. Define
$r_{e}:=\hat{y}_{i}+\hat{y}_{j}-c_{e}$ for each edge $e=ij\in F$. Asserting
that $\hat{y}-\delta$ is feasible for (MWPM-D) while minimizing the amount
lost in the dual objective leads to the following linear program:

$\begin{array}[]{ccc}\min&\displaystyle\sum_{i\in V}\delta_{i}&\\\
&\displaystyle\delta_{i}+\delta_{j}\geq r_{ij}&\forall ij\in F\\\
&\delta_{i}\geq 0&\forall i\in V\end{array}$ (1)

Note that this is a variant of the vertex cover problem—the problem becomes
exactly the vertex cover problem if $r_{ij}=1$ for all edges $ij$. We could
directly solve this linear program, but we are interested in making this step
efficient. To find a fast approximation for (1), we take a simple greedy
approach.

Algorithm 1 Fast Approx. for Distance to Feasibility

1:procedure FastApprox($G=(V,E),r$)

2: $\forall i\in V$, $\delta_{i}\leftarrow 0$

3: while $E\neq\emptyset$ do

4: Let $i$ be an arbitrary vertex of $G$

5: while $i$ has a neighbor do

6: $j\leftarrow\arg\max_{j^{\prime}\in N(i)}r_{ij^{\prime}}$

7: $\delta_{i}\leftarrow r_{ij}$

8: $\gamma_{ij}=1/2$ $\triangleright$ $\gamma_{ij}$ is only used for analysis

9: Delete $i$ and all its edges from $G$

10: $i\leftarrow j$

11: Return $\delta$

Algorithm 1 is a modification of the algorithm of Drake and Hougardy [18]
which walks through the graph setting $\delta_{i}$ appropriately at each step
to satisfy the covering constraints in (1). The analysis is based on
interpreting the algorithm through the lens of primal-dual—the dual of (1)
turns out to be a maximum weight matching problem with new edge weights
$r_{ij}$. The dual is the following:

$\begin{array}[]{ccc}\max&\displaystyle\sum_{e}r_{e}\gamma_{e}&\\\
&\displaystyle\sum_{e\in N(i)\cap F}\gamma_{e}\leq 1&\forall i\in V\\\
&\gamma_{e}\geq 0&\forall e\in F\end{array}$ (2)

First we show the algorithm is fast.

######  Lemma 4.

Algorithm 1 runs in time $O(n+m)$.

###### Proof.

This follows from the trivial observation that each vertex/edge is considered
$O(1)$ times. ∎

Next, by construction the algorithm constructs a feasible dual solution.

######  Lemma 5.

The perturbations $\delta$ returned by Algorithm 1 is feasible for (1).

###### Proof.

We want to show that $\delta_{i}+\delta_{j}\geq r_{e}$ for all edges $e=ij\in
E$. We claim that this condition holds whenever the edge is deleted from $G$.
Suppose that the algorithm is currently at $i$ and let $ij^{\prime}$ be the
edge selected by the algorithm in this step. By definition of the algorithm we
have $\delta_{i}=r_{ij^{\prime}}\geq r_{ij}$ so $\delta_{i}+\delta_{j}\geq
r_{ij}$. ∎

Finally, we address the objective.

######  Lemma 6.

The perturbations $\delta$ returned by Algorithm 1 are a 2-approximation for
(1).

###### Proof.

In each iteration, the increase of the primal objective ($\delta_{i}=r_{ij}$
in Line 7) is exactly twice the increase of the dual objective
($r_{ij}\gamma_{ij}=r_{ij}/2$ in Line 8). Thus, due to weak duality, it
suffices to show that the dual is feasible. This follows from the observation
that $\\{ij\;|\;\gamma_{ij}=1/2\\}$ forms a collection of vertex disjoint
paths and cycles. Thus, for every $i\in V$, there are at most two edges $e$
adjacent to $i$ such that $\gamma_{e}>0$, and for those edges $e$,
$\gamma_{e}=1/2$. Therefore, the dual is feasible. ∎

This shows we can project the predicted dual prices $\hat{y}$ onto the set of
feasible dual prices at approximately the minimum cost. The prior lemmas give
the following theorem by noticing that $y^{*}(c)$ is a possible feasible
solution. Note that integrality is immediate from the algorithm.

######  Theorem 7.

There is a $O(m+n)$ time algorithm that takes an infeasible integer dual
$\hat{y}$ and constructs a feasible integer dual $\hat{y}^{\prime}(c)$ for
MWPM-D with cost vector $c$ such that $\|\hat{y}^{\prime}(c)-\hat{y}\|_{1}\leq
2\|\hat{y}-y^{*}(c)\|_{1}$ where $y^{*}(c)$ is the optimal dual solution for
MWPM-D with cost vector $c$. Thus by triangle inequality we have
$\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1}\leq 3\|\hat{y}-y^{*}(c)\|_{1}$.

###  3.2 Seeding Hungarian with a Feasible Dual (Optimization)

In this section we assume that we are given a feasible integral dual
$\hat{y}^{\prime}(c)$ for an input with cost vector $c$ and the goal is to
find an optimal solution. We want to analyze the running time in terms of
$\|\hat{y}^{\prime}(c)-y^{*}(c)\|_{1}$, the distance to optimality. We use a
simple primal-dual schema to achieve this, which is given formally in
Algorithm 2.

Algorithm 2 Simple Primal-Dual Scheme for MWPM

1:procedure MWPM-PD($G=(V,E),c,y$)

2: $E^{\prime}\leftarrow\\{e\in E\mid y_{i}+y_{j}=c_{ij}$ } $\triangleright$
Set of tight edges in the dual

3: $G^{\prime}\leftarrow(V,E^{\prime})$ $\triangleright$ $G$ containing only
tight edges

4: $M\leftarrow$ Maximum cardinality matching in $G^{\prime}$

5: while $M$ is not a perfect matching do

6: Find $S\subseteq L$ such that $|S|>|\Gamma(S)|$ in $G^{\prime}$
$\triangleright$ Exists by Hall’s Theorem

7:$\triangleright$ Can be found in $O(m+n)$ time

8: $\epsilon\leftarrow\min_{i\in S,j\in
R\setminus\Gamma(S)}\\{c_{ij}-y_{i}-y_{j}\\}$

9: $\forall i\in S$, $y_{i}\leftarrow y_{i}+\epsilon$

10: $\forall j\in\Gamma(S)$, $y_{j}\leftarrow y_{j}-\epsilon$

11: Update $E^{\prime},G^{\prime}$

12: $M\leftarrow$ Maximum cardinality matching in $G^{\prime}$

13: Return $M$

To satisfy complementary slackness, we must only choose edges with
$y_{i}+y_{j}=c_{ij}$. Let $E^{\prime}$ be the set of such edges. We find a
maximum cardinality matching in the graph $G^{\prime}=(V,E^{\prime})$. If the
resulting matching $M$ is perfect then we are done by complementary slackness
(Lemma 2) Otherwise, in steps 7-9 we modify the dual in a way that guarantees
a strict increase in the dual objective. Since all parameters of the problem
are integral, this strict increase then implies our desired bound on the
number of iterations.

We now analyze Algorithm 2. Recall that $L$ and $R$ give the bipartition of
$V$. First we show that the algorithm is correct. The main claim we need to
establish is that if $y$ is initially dual feasible, then it remains dual
feasible throughout the algorithm. First we check that the update defined in
lines 6-10 is well defined, i.e. in line 6 such a set $S$ always exists and
$\epsilon$ defined in line 7 is always strictly positive.

######  Proposition 8.

If $M$ is not a perfect matching in $G^{\prime}$, then there exists a set
$S\subseteq L$ such that $|S|>|\Gamma(S)|$ in $G^{\prime}$. Further, such $S$
can be found in $O(m+n)$ time.

###### Proof.

The first claim follows directly from Hall’s Theorem applied to $G^{\prime}$.
It is well-known that the maximum matching size is equal to the minimum vertex
cover size when the underlying graph is bipartite. Further, a minimum vertex
cover $C$ can be derived from a maximum matching $M$ in time $O(m+n)$. We set
$S=L\setminus C$. Then, we have $\Gamma(S)\subseteq C\cup R$ due to $C$ being
a vertex cover, and $|C\cap L|+|C\cap R|=|C|<n$ as the minimum cover size is
less than $n$; recall $M$ is not perfect. Thus, we have $|S|=n-|C\cap
L|>|C\cap R|\geq|\Gamma(S)|$, as desired. ∎

######  Proposition 9.

Let $y$ be dual feasible and suppose that $S\subseteq L$ with
$|S|>|\Gamma(S)|$ in $G^{\prime}$. Let $\epsilon=\min_{i\in S,j\in
R\setminus\Gamma(S)}c_{ij}-y_{i}-y_{j}$. Then as long as $c$ and $y$ are
integer we have $\epsilon\geq 1$.

###### Proof.

Every edge $ij$ considered in the definition of $\epsilon$ is not in
$E^{\prime}$ and thus must have $c_{ij}>y_{i}+y_{j}$. Thus for all such edges
we have $c_{ij}-y_{i}-y_{j}\geq 1$ since $c$ and $y$ are integer, and so
$\epsilon\geq 1$.

If no such edge exists, then we have a set $S\subseteq L$ such that $|S|$ is
strictly larger than its neighborhood in $G$ (rather than $G^{\prime}$) which
shows that the problem is infeasible. This contradicts our assumption that the
original problem is feasible. ∎

We now show the main claims we described above.

######  Lemma 10.

If Algorithm 2 is given an initial dual feasible $y$, then $y$ remains dual
feasible throughout its execution.

###### Proof.

Inductively, it suffices to show that if $y$ is dual feasible then it remains
so after the update steps defined in lines 6-10. To make the notation clear,
let $y^{\prime}$ be the result of applying the update rule to $y$. Consider an
edge $ij\in E$. We want to show that $y^{\prime}_{i}+y^{\prime}_{j}\leq
c_{ij}$ after the update step. There are 4 cases to check: (1) $i\in
L\setminus S,j\in R\setminus\Gamma(S)$, (2) $i\in L\setminus S,j\in\Gamma(S)$,
(3) $i\in S,j\in R\setminus\Gamma(S)$, and (4) $i\in S,j\in\Gamma(S)$.

In the first case, neither $y_{i}$ nor $y_{j}$ are modified, so we get
$y^{\prime}_{i}+y^{\prime}_{j}=y_{i}+y_{j}\leq c_{ij}$ since $y$ was initially
dual feasible. In the second case we have
$y^{\prime}_{i}+y^{\prime}_{j}=y_{i}+y_{j}-\epsilon\leq c_{ij}$ since
$\epsilon>0$. In the third case we have $y^{\prime}_{i}=y_{i}+\epsilon$ and so
$y^{\prime}_{i}+y^{\prime}_{j}=y_{i}+\epsilon+y_{j}\leq c_{ij}$ since there
was slack on these edges and $\epsilon$ was chosen to be the smallest such
slack. Finally, in the last case we have
$y^{\prime}_{i}+y^{\prime}_{j}=y_{i}+\epsilon+y_{j}-\epsilon\leq c_{ij}$. Thus
we conclude that $y$ remains feasible throughout the execution of Algorithm 2.
∎

######  Lemma 11.

Each iteration strictly increases the value of the dual solution.

###### Proof.

Note that in each iteration $y_{i}$ increases by $\epsilon$ for all $i\in S$
and $y_{j}$ decreases by $\epsilon$ for all $j\in\Gamma(S)$; and all other
dual variables remain unchanged. Thus, the dual objective increases by
$\epsilon(|S|-|\Gamma(S)|)\geq\epsilon$. ∎

The above lemma allows us to analyze the running time of our algorithm in
terms of the distance to optimality.

######  Lemma 12.

Consider an arbitrary cost vector $c$. Suppose that $\hat{y}^{\prime}(c)$ is
an integer dual feasible solution and $y^{*}(c)$ is an integer optimal dual
solution. If Algorithm 2 is initialized with $\hat{y}^{\prime}(c)$, then the
number of iterations is bounded by $\|\hat{y}(c)-y^{*}(c)\|_{1}$.

###### Proof.

By Lemma 11, we have that the value of the dual solution increases by at least
1 in each iteration. Thus the number of iterations is at most
$\sum_{i}y^{*}_{i}(c)-\sum_{i}\hat{y}_{i}(c)\leq\sum_{i}|y^{*}_{i}(c)-\hat{y}_{i}(c)|=\|y^{*}(c)-\hat{y}(c)\|_{1}$.
∎

Finally, we get the following theorem as a corollary of the lemmas above and
the $O(m\sqrt{n})$ runtime of the Hopcroft-Karp algorithm for maximum
cardinality matching [29]. More precisely, the above lemmas show that the
algorithm performs at most
$O\left(\|y^{*}(c)-\hat{y}^{\prime}(c)\|_{1}\right)$ iterations, each running
in $O(m\sqrt{n})$ time. We can further improve this by ensuring the algorithm
runs no longer than the standard Hungarian algorithm in the case that we have
large error in the prediction, i.e., $\|y^{*}(c)-\hat{y}^{\prime}(c)\|_{1}$ is
large. In particular, steps 6 and 11 do not precisely specify the choice of
the set $S$ and the matching $M$. If we instantiate these steps appropriately
(let $S=L\setminus C$ for step 6, where $C$ is a minimum vertex cover, and
update $M$ along shortest-augmenting-paths for step 11) then we recover the
Hungarian Algorithm and its $\tilde{O}(mn)$ running time.

######  Theorem 13.

Consider an arbitrary cost vector $c$. There exists an algorithm which takes
as input a feasible integer dual solution $\hat{y}^{\prime}(c)$ and finds a
minimum weight perfect matching in
$\tilde{O}\left(\min\left\\{m\sqrt{n}\|y^{*}(c)-\hat{y}^{\prime}(c)\|_{1},mn\right\\}\right)$
time, where $y^{*}(c)$ is an optimal dual solution.

###  3.3 Learning Optimal Advice (Learning)

Now we want to formally instantiate the “learning" part of our framework: if
there is a good starting dual solution for a given input distribution, we want
to find it without seeing too many samples. The formal model we will use is
derived from data driven algorithm design and PAC learning.

We imagine solving many problem instances drawn from the same distribution. To
formally model this, we let ${\cal D}$ be an unknown distribution over
instances. For simplicity, we consider the graph $G=(V,E)$ to be fixed with
varying costs. Thus ${\cal D}$ is a distribution over cost vectors
$c\in\mathbb{R}^{E}$. We assume that the costs in this distribution are
bounded. Let $C:=\max_{c\sim{\cal D}}\max_{e\in E}c_{e}$ be finite and known
to the algorithm. Our goal is to find the (not necessarily feasible) dual
assignment that performs “best” in expectation over the distribution. Based on
Theorems 7 and 13 , we know that the “cost” of using dual values $y$ when the
optimal dual is $y^{*}$ is bounded by $O(m\sqrt{n}\|y^{*}-y\|_{1})$, and hence
it is natural to define the “cost" of $y$ as $\|y^{*}-y\|_{1}$.

For every $c\in\mathbb{R}^{E}$ we will let $y^{*}(c)$ be a fixed optimal dual
solution for $c$:

$y^{*}(c):=\arg\max_{y}\Big{\\{}\sum_{i}y_{i}\ |\ \forall ij\in
E,y_{i}+y_{j}\leq c_{ij}\Big{\\}}.$

Here we assume without loss of generality that $y^{*}(c)$ is integral as the
underlying polytope is known to be integral. We will let the loss of a dual
assignment $y$ be its $\ell_{1}$-distance from the optimal solution:

$L(y,c)=\|y-y^{*}(c)\|_{1}.$

Our goal is to learn dual values $\hat{y}$ which minimizes
$\mathbb{E}_{c\sim{\cal D}}[L(y,c)]$. Let $y^{*}$ denote the vector minimizing
this objective, $y^{*}=\arg\min_{y}\mathbb{E}_{c\sim{\cal D}}[L(y,c)]$.

We will give PAC-style bounds, showing that we only need a small number of
samples in order to have a good probability of learning an approximately-
optimal solution $\hat{y}$. Our algorithm is conceptually quite simple: we
minimize the empirical loss after an appropriate number of samples. We have
the following theorem.

######  Theorem 14.

There is an algorithm that after
$s=O\left(\left(\frac{nC}{\epsilon}\right)^{2}(n\log n+\log(1/p))\right)$
samples returns dual values $\hat{y}$ such that $\mathbb{E}_{c\sim{\cal
D}}[L(\hat{y},c)]\leq\mathbb{E}_{c\sim{\cal D}}[L(y^{*},c)]+\epsilon$ with
probability at least $1-p$. The algorithm runs in time polynomial in $n,m$ and
$s$.

This theorem, together with Theorems 7 and 13, immediately implies Theorem 3.

####  3.3.1 Proof of Theorem 14

We now discuss the main tools we require from statistical learning theory in
order to prove Theorem 14. For every dual assignment $y\in\mathbb{R}^{V}$, we
define a function $g_{y}:\mathbb{R}^{E}\to\mathbb{R}$ by
$g_{y}(c)=L(y,c)=\|y^{*}(c)-y\|_{1}$. Let ${\cal H}=\\{g_{y}\mid
y\in\mathbb{R}^{V}\\}$ be the collection of all such functions. It turns out
that in order to prove Theorem 14, we just need to bound the _pseudo-
dimension_ of this collection. Note that the notion of shattering and pseudo-
dimension in the following is a generalization to real-valued functions of the
classical notion of VC-dimension for boolean-valued functions (classifiers).

######  Definition 15.

[45, 3, 40] Let $\mathcal{F}$ be a class of functions $f:X\to\mathbb{R}$. Let
$S=\\{x_{1},x_{2},\ldots,x_{s}\\}\subset X$. We say that that $S$ is
_shattered_ by $\mathcal{F}$ if there exist real numbers $r_{1},\ldots,r_{s}$
so that for all $S^{\prime}\subseteq S$, there is a function $f\in\mathcal{F}$
such that $f(x_{i})\leq r_{i}\iff x_{i}\in S^{\prime}$ for all $i\in[s]$. The
_pseudo-dimension_ of $\mathcal{F}$ is the largest $s$ such that there exists
an $S\subseteq X$ with $|S|=s$ that is shattered by $\mathcal{F}$.

The connection between pseudo-dimension and learning is given by the following
uniform convergence result.

######  Theorem 16.

[45, 3, 40] Let ${\cal D}$ be a distribution over a domain $X$ and ${\cal F}$
be a class of functions $f:X\to[0,H]$ with pseudo-dimension $d_{{\cal F}}$.
Consider $s$ independent samples $x_{1},x_{2},\ldots,x_{s}$ from ${\cal D}$.
There is a universal constant $c_{0}$, such that for any $\epsilon>0$ and
$p\in(0,1)$, if $s\geq c_{0}\left(\frac{H}{\epsilon}\right)^{2}(d_{{\cal
F}}+\ln(1/p))$ then we have

$\left|\frac{1}{s}\sum_{i=1}^{s}f(x_{i})-\mathbb{E}_{x\sim{\cal
D}}[f(x)]\right|\leq\epsilon$

for all $f\in{\cal F}$ with probability at least $1-p$.

Intuitively, this theorem says that the sample average
$\frac{1}{s}\sum_{i=1}^{s}f(x_{i})$ is close to its expected value for every
function $f\in{\cal F}$ simultaneously with high probability so long as the
sample size $s$ is large enough. This theorem can be utilized to give a
learning algorithm for our problem by considering an algorithm which minimizes
the empirical loss. In general, the “best” function is the one which minimizes
the expected value over ${\cal D}$, i.e. $f^{*}=\arg\min_{f\in{\cal
F}}\mathbb{E}_{x\sim{\cal D}}[f(x)]$. We have the following simple corollary
for learning and approximately best function $\hat{h}$.

######  Corollary 17.

Consider a set of $s$ independent samples $x_{1},x_{2},\ldots,x_{s}$ from
${\cal D}$ and let $\hat{f}$ be a function in ${\cal F}$ which minimizes
$\frac{1}{s}\sum_{i=1}^{s}\hat{f}(x_{i})$. If $s$ is chosen as in Theorem 16,
then with probability $1-p$ we have $\mathbb{E}_{x\sim{\cal
D}}[\hat{f}(x)]\leq\mathbb{E}_{x\sim{\cal D}}[f^{*}(x)]+2\epsilon$

Thus based on the above Theorem and Corollary, to prove Theorem 14 we must
accomplish the following tasks. First and foremost, we must bound the pseudo-
dimension of our class of functions ${\cal H}$. Next, we need to check that
the functions are bounded on the domain we consider, and finally we need to
give an algorithm minimizing the empirical risk. The latter two tasks are
simple. By assumption the edge costs are bounded by $C$. If we restrict ${\cal
H}$ to be within a suitable bounding box, then one can verify that we can take
$H=O(nC)$ to satisfy the conditions for Theorem 16. Additionally, the task of
finding a function to minimize the loss on the sample can be done via linear
programming. We formally verify these details in Sections 3.3.2 and 3.3.3.
This leaves bounding the pseudo-dimension of the class ${\cal H}$, which we
focus on now.

To bound the pseudo-dimension of ${\cal H}$, we will actually consider a
different class of functions ${\cal H}_{n}$: for every $y\in\mathbb{R}^{n}$ we
define a function $f_{y}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ by
$f_{y}(x)=\|y-x\|_{1}$, and we let ${\cal H}_{n}=\\{f_{y}\mid
y\in\mathbb{R}^{n}\\}$. It is not hard to argue that it is sufficient to bound
the pseudo-dimension of this class.

######  Lemma 18.

If the pseudo-dimension of ${\cal H}_{n}$ is at most $k$, then the pseudo-
dimension of ${\cal H}$ is at most $k$.

###### Proof.

We prove the contrapositive: we start with a set of size $s$ which is
shattered by ${\cal H}$, and use it to find a set of size $s$ which is
shattered by ${\cal H}_{n}$. Let $S=\\{c_{1},c_{2},\dots,c_{s}\\}$ with each
$c_{i}\in\mathbb{R}^{E}$ be a set which is shattered by $\mathcal{H}$. Then
there are real numbers $r_{1},r_{2},\dots,r_{s}$ so that for all
$S^{\prime}\subseteq[s]$, there is a function $g\in{\cal H}$ where
$g(c_{i})\leq r_{i}\iff i\in S^{\prime}$. By definition of ${\cal H}$, this
$g$ is $g_{y_{S^{\prime}}}$ for some $y_{S^{\prime}}\in\mathbb{R}^{n}$, and so
$\|y_{S^{\prime}}-y^{*}(c_{i})\|_{1}\leq r_{i}\iff i\in S^{\prime}$.

Let $\hat{S}=\\{y^{*}(c_{1}),y^{*}(c_{2}),\dots,y^{*}(c_{s})\\}$. We claim
that $\hat{S}$ is shattered by ${\cal H}_{n}$. To see this, consider the same
real numbers $r_{1},\dots,r_{s}$ and some $S^{\prime}\subseteq[s]$. Then
$f_{y_{S^{\prime}}}(y^{*}(c_{i}))=\|y_{S^{\prime}}-y^{*}(c_{i})\|_{1}=g_{y_{S^{\prime}}}(c_{i})$
and hence $f_{y_{S^{\prime}}}(y^{*}(c_{i}))\leq r_{i}\iff
g_{y_{S^{\prime}}}(c_{i})\leq r_{i}\iff i\in S^{\prime}$. Thus $\hat{S}$ is
shattered by ${\cal H}_{n}$. ∎

So now our goal is to prove the following bound, which (with Lemma 18 and
Theorem 16) implies Theorem 14.

######  Theorem 19.

The pseudo-dimension of ${\cal H}_{n}$ is at most $O(n\log n)$.

Let $k$ be the pseudo-dimension of ${\cal H}_{n}$. Then by the definition of
pseudo-dimension there is a set $P=\\{x^{1},x^{2},\dots,x^{k}\\}$ which is
shattered by ${\cal H}_{n}$, so there are values
$r_{1},r_{2},\ldots,r_{k}\in\mathbb{R}_{\geq 0}$ so that for all $S\subseteq
P$ there is an $f\in{\cal H}_{n}$ such that $f(x^{i})\leq r_{i}\iff x^{i}\in
S$. By our definition of ${\cal H}_{d}$, this means that there is a
$y_{S}\in\mathbb{R}^{n}$ so that $\|y_{S}-x^{i}\|_{1}\leq r_{i}\iff x^{i}\in
S$.

For each $S\subseteq P$, define the _region_ of $S$ (denoted by $r(S)$) to be

$r(S)=\\{y\in\mathbb{R}^{n}:\|y-x^{i}\|_{1}\leq r_{i}\iff x^{i}\in S\\},$

i.e., the set of points that are at $\ell_{1}$-distance at most $r_{i}$ from
$x^{i}$ for precisely the $x^{i}$’s that are in $S$. Clearly each $r(S)$ is
nonempty for every $S\subseteq P$ due to the existence of $y_{S}$. Let
$m=2^{k}$ be the number of nonempty regions.

To upper bound the pseudo-dimension $k$ we will prove that there cannot be too
many nonempty regions (i.e., $m$ is small). This is somewhat complex since the
$\ell_{1}$-balls have complex structure (in particular, have $2^{d}$ facets),
so we will do this by partitioning $\mathbb{R}^{n}$ into _cells_ in which the
$\ell_{1}$ balls are simpler. For each $x^{i}\in P$ and $j\in[n]$, let
$Q^{i}_{j}$ be the hyperplane in $\mathbb{R}^{n}$ that passes through $y_{i}$
and is perpendicular to the axis $e_{j}$ (i.e.,
$Q^{i}_{j}=\\{y\in\mathbb{R}^{n}:\langle y-x^{i},e_{j}\rangle=0\\}$). Clearly
there are $kn$ of these hyperplanes. Define a _cell_ to be a maximal set of
points in $\mathbb{R}^{n}$ which are the same side of every hyperplane. Note
that there are $(k+1)^{n}$ of these cells, they partition $\mathbb{R}^{n}$,
and every cell which is bounded is a hypercube.

######  Lemma 20.

Let $C$ be a cell and $x^{i}\in P$. There is a halfspace $H$ such that
$B_{1}(x^{i},r_{i})\cap C=H\cap C$.

###### Proof.

If $B_{1}(x^{i},r_{i})\cap C=\emptyset$ then we are done. So suppose that
$B_{1}(x^{i},r_{i})\cap C\neq\emptyset$. By definition, $B_{1}(x^{i},r_{i})$
is the set of points $y\in\mathbb{R}^{n}$ such that
$\sum_{j=1}^{n}|x^{i}_{j}-y_{j}|\leq r_{i}$. Hence $B_{1}(x^{i},r_{i})$ is
defined by the intersection of $2^{n}$ halfspaces:

$\displaystyle B_{1}(x^{i},r_{i})=\left\\{y\in\mathbb{R}^{n}\ \mid\
\sum_{j=1}^{n}a_{j}(x^{i}_{j}-y_{j})\leq r_{i}\ \forall
a\in\\{-1,+1\\}^{n}\right\\}$

If the intersection of the boundary of $B_{1}(x^{i},r_{i})$ with $C$ is one of
these hyperplanes, then we are finished. Otherwise, there are at least two of
these hyperplanes $H_{1}=(a_{1},\dots a_{n})$ and
$H_{2}=(a^{\prime}_{1},\dots,a^{\prime}_{n})$ such that
$B_{1}(x^{i},r_{i})\cap C$ contains a point $y\in H_{1}\setminus H_{2}$ and a
point $y^{\prime}\in H_{2}\setminus H_{1}$, both of which are also on the
boundary of $B_{1}(x^{i},r_{i})$. Let $j\in[n]$ such that
$a_{j}=-a^{\prime}_{j}$. Then $y_{j}-x^{i}_{j}$ has a different sign than
$y^{\prime}_{j}-x^{i}_{j}$, since the fact that $y$ and $y^{\prime}$ are on
the boundary of $B_{1}(x^{i},r_{i})$ but on different facets implies that
$x^{i}_{j}-y_{j}$ has sign $a_{j}$ while $x^{i}_{j}-y^{\prime}_{j}$ has sign
$a^{\prime}_{j}$. But this contradicts the definition of $C$, since it means
that $y$ and $y^{\prime}$ are on different sides of $Q^{i}_{j}$ and hence not
in the same cell. ∎

This lemma allows us to analyze the number of regions that intersect any cell.

######  Lemma 21.

Let $C$ be a cell. The number of regions that intersect $C$ is at most
$2^{O(n)}k^{n}$.

###### Proof.

For every $S\subseteq P$, the region $r(S)$ is the set of points that are in
$B_{1}(x^{i},r_{i})$ for all $x_{i}\in S$ and are not in $B_{1}(x^{i},r_{i})$
for all $x_{i}\not\in S$. By Lemma 20, $r(S)\cap C$ is the intersection of $C$
with $k$ halfspaces (one for each $x^{i}\in P$). It is well-known that $k$
halfspaces can divide $\mathbb{R}^{n}$ into at most
$\sum_{i=0}^{n}\binom{k}{i}=O(n)k^{n}$ regions, and hence the same bound holds
for $C$. ∎

Now some standard calculations imply Theorem 19, and hence Theorem 14.

###### Proof of Theorem 19.

Lemma 21, together with the fact that there are at most $(k+1)^{n}$ cells,
implies that the number of nonempty regions $m$ is at most
$O(n)k^{n}\cdot(k+1)^{n}\leq O(n)(k+1)^{2n}$. Since $m=2^{k}$, this implies
that $2^{k}\leq O(n)(k+1)^{2n}$. Taking logarithms of both sides yields that

$k\leq\log(k+1)\cdot O(n),$ (3)

and then taking another logarithm and rearranging yields that $\log
n\geq\Omega(\log k-\log\log k)=\Omega(\log k)$ and hence $\log(k+1)\leq O(\log
n)$. Plugging this into (3) implies Theorem 19. ∎

####  3.3.2 Bounding the Range

In this section we verify the condition for Theorem 16 that every function in
${\cal H}$ has its range in $[0,H]$ for $H=O(nC)$. This is actually not quite
true as defined, but it is easy enough to ensure: we just consider a
restricted class of functions ${\cal H}^{\prime}=\\{g_{y}\mid g_{y}\in{\cal
H},y\in[-C,C]^{V}\\}$. Note that for any fixed set of costs $c$ the class
${\cal H}^{\prime}$ contains $y^{*}(c)$, so without loss of generality we can
just use ${\cal H}^{\prime}$ instead of ${\cal H}$. From the definition of
pseudo-dimension and ${\cal H}^{\prime}\subseteq{\cal H}$, it immediately
follows that the pseudo-dimension of ${\cal H}^{\prime}$ is at most that of
${\cal H}$. Thus, we just need to ensure that the range of the restricted
functions are bounded.

######  Lemma 22.

Each function $g_{y}\in{\cal H}^{\prime}$ has its range in $[0,H]$ for
$H=O(nC)$.

###### Proof.

Let’s bound the range by considering the maximum value $g_{y}$ can take on a
set of costs $c$. Recall that $g_{y}(c)=\|y-y^{*}(c)\|_{1}$. Each coordinate
can contribute at most $O(C)$ to the sum since $y^{*}_{i}(c)\in[-C,C]$ and
$y_{i}\in[-C,C]$. Summing over the $n$ coordinates gives $H=O(nC)$. ∎

####  3.3.3 Minimizing the Empirical Loss

Now we give an algorithm to minimize the empirical loss on a collection of
sample instances. Let $c_{1},c_{2},\ldots,c_{s}$ be a collection of samples
from ${\cal D}$. Our goal is to find dual prices $y$ minimizing
$\frac{1}{s}\sum_{i=1}^{s}g_{y}(c_{i})=\frac{1}{s}\sum_{i=1}^{s}\|y-y^{*}(c_{i})\|_{1}$.
Let $x^{i}=y^{*}(c_{i})$. Then the problem amounts to minimizing
$\frac{1}{s}\sum_{i=1}^{s}\|y-x^{i}\|_{1}$ over $y\in[-C,C]^{V}$. Then, for
each coordinate $j$ it suffices to find $y_{j}$ minimizing
$\sum_{i=1}^{s}\|y_{j}-x^{i}_{j}\|_{1}$, where $y_{j}$ and $x^{i}_{j}$ denote
the $j$-th coordinate of $y$ and $x_{i}$, respectively. Further, it is easy to
see that $\sum_{i=1}^{s}\|y_{j}-x^{i}_{j}\|_{1}$ is a continuous piece-wise
linear function in $y_{j}$ where the slope can change only at
$\\{x^{i}_{j}\\}_{i\in[s]}$. Recalling that we can assume wlog that
$x^{i}=y^{*}(c_{i})$ is an integer vector, we only need to consider setting
$y_{j}$ to each value in $\\{x^{i}_{j}\\}_{i\in[s]}$, which is a set of
integers. This leads to the following result.

######  Theorem 23.

Given $s$ samples $c_{1},c_{2},\ldots,c_{s}$, there exists a polynomial time
algorithm which finds integer dual prices $y$ minimizing
$\frac{1}{s}\sum_{i=1}^{s}\|y-y^{*}(c_{i})\|_{1}$.

We remark that minimizing this empirical loss can be efficiently implemented
by taking the coordinate-wise median of each optimal dual, i.e. taking
$y_{j}=\operatorname{median}(x^{1}_{j},x^{2}_{j},\ldots,x^{s}_{j})$ for each
$j\in V$.

##  4 Experiments

In this section we present experimental results on both synthetic and real
data sets. Our goal is to validate the two main hypotheses in this work. First
we show that warm-starting the Hungarian algorithm with learned duals provides
an empirical speedup. Next, we show that the sample complexity of learning
good duals is small, ensuring that our approach is viable in practice. We
present some representative experimental results here; additional results are
in the Appendix A.

Experiment Setup: All of our experiments were run on Google Cloud Platform
[27] e2-standard-2 virtual machines with 2 virtual CPU’s and 8 GB of memory.

We consider two different setups for learning dual variables and evaluating
our algorithms.

  * •

Batch: In this setup, we receive $s$ samples $c_{1},c_{2},\ldots,c_{s}$ from
the distribution of problem instances, learn the appropriate dual variables,
and then test on new instances drawn from the distribution.

  * •

Online: A natural use case for our approach is an _online_ setting, where
instance graphs $G_{1},G_{2},\ldots$ arrive one at a time. When deciding on
the best warm start solution for $G_{t}$ we can use all of the data from
$G_{1},\ldots,G_{t-1}$. This is a standard scenario in industrial applications
like ad matching, where a new ad allocation plan may need to be computed daily
or hourly.

Datasets: To study the effect of the different algorithm parameters, we first
run a study on synthetic data. Let $n$ be the number of nodes on one side of
the bipartition and let $\ell,v$ be two parameters we set later. First, we
divide the $n$ nodes on each side of the graph into $\ell$ groups of equal
size. The weight of all edges going from the $i$’th group on the left side and
the $j$’th group on the right side is initialized to some value $W_{i,j}$
drawn from a geometric distribution with mean $250$. Then to generate a
particular graph instance, we perturb each edge weight with independent random
noise according to a binomial distribution, shifted and scaled so that it has
mean 0 and variance $v$. We refer to this as the _type_ model (each type
consists of a group of nodes). We use $n=500$, $\ell\in\\{50,100\\}$ and vary
$v$ from $0$ to $2^{20}$.

We use the following model of generating instances from real data. Let $X$ be
a set of $n$ points in $\mathbb{R}^{d}$, and fix a parameter $k$. We first
divide $X$ randomly into two sets, $X_{L}$ and $X_{R}$ and compute a $k$-means
clustering on each partition. To generate an instance $G=(L\cup R,E)$, we
sample one point from each cluster on each side, generating $2k$ points in
total. The points sampled from $X_{L}$ (resp. $X_{R}$) form the vertices in
$L$ (resp. $R$). The weight of an $(i,j)$ edge is the Euclidean distance
between these two points. Changing $k$ allows us to control the size of the
instance.

Dataset | Blog Feedback [12] | Covertype | KDD | Skin [10] | Shuttle
---|---|---|---|---|---
# of Points ($n$) | 52,397 | 581,012 | 98,942 | 100,000 | 43500
# of Features ($d$) | 281 | 54 | 38 | 4 | 10
Table 1: Datasets used in experiments based on Euclidean data

We use several datasets from the UCI Machine Learning repository [19]. See
Table 1 for a summary. For the KDD and Skin datasets we used a sub-sample of
the original data (sizes given in Table 1).

Implemented Algorithms and Metrics: We implemented the Hungarian Algorithm (a
particular instantiation of Algorithm 2, as discussed in Section 3.2) allowing
for arbitrary seeding of a feasible integral dual. We experimented with having
initial dual of $0$ (giving the standard Hungarian Algorithm) as the baseline
and having the initial duals come from our learning algorithm followed by
Algorithm 1 to ensure feasibility (which we refer to as “Learned Duals”). We
also added the following “tightening” heuristic, which is used in all standard
implementations of the Hungarian algorithm: given any feasible dual solution
$y$, set $y_{i}\leftarrow y_{i}+\min_{j\in N(i)}\\{c_{ij}-y_{i}-y_{j}\\}$ for
all nodes $i$ on one side of the bipartition. This can be quickly carried out
in $O(n+m)$ time, and guarantees that each node on that side has at least one
edge in $E^{\prime}$. We compare the runtime and number of primal-dual
iterations, reporting mean values and error bars denoting 95% confidence
intervals. The runtime results can be found in Appendix A, and exhibit similar
behavior (i.e., the extra running time caused by using Algorithm 1 in Learned
Duals is negligible).

To learn initial duals we use a small number of independent samples of each
instance type. We compute an optimal dual solution for each instance in the
sample. To combine these together into a single dual solution, we compute the
median value for each node’s set of dual values. This is an efficient
implementation of the empirical risk minimization algorithm from Section 3.3.

Results: First, we examine the performance of Learned Duals in the batch
setting described above. For these experiments, we used 20 training instances
to learn the initial duals and then tested those on 10 new instances. For the
type model, we used $\ell=50$ and considered varying the variance parameter
$v$. The left plot in Figure 1 shows the results as we increase $v$ from $0$
to $300$. We see a moderate improvement in this case, even when the noise
variance is larger than the mean value of an edge weight. Going further, in
the middle plot of Figure 1 we consider increasing the noise variance in
powers of two geometrically. For both of these plots, we mark the x-axis
according to $v/250$ which is the ratio of the noise variance to the mean
value of the original weights. Note that even when the noise significantly
dominates the original signal from the mean weights (and hence the training
instances should not help on the test instances), our method is comparable to
the Hungarian method.

Continuing with the Batch setting, the right plot in Figure 1 summarizes our
results for the clustering derived instances on all datasets with $k=500$
(similar results hold for other values of $k$; see Figure 4). We see an
improvement across all datasets, and a greater than 2x improvement on all but
the Covertype dataset.

Figures 2 and 3 display our results in the online setting. We aim to show that
not too many samples are needed to learn effective duals. From left to right,
the plots in Figure 2 show the performance averaged over 20 repetitions of the
experiment with 20 time points on the type model with $\ell=100,v=200$, and
the clustering derived instances on the KDD and Covertype datasets with
$k=500$, respectively. We see that only a few iterations are needed to see a
significant separation between the run time of our method with learned duals
and the standard Hungarian method, with further steady improvement as we see
more instances.

We see similar trends in both the real and synthetic data sets. We conclude
the following.

  * •

The theory is predictive of practice. Empirically, learning dual variables can
lead to significant speed-up. This speed-up is achieved in both the batch and
online settings.

  * •

As the distribution is more concentrated, the learning algorithm performs
better (as one would suspect).

  * •

When the distribution is not concentrated and there is little to learn, then
the algorithm has performance similar to the widely used Hungarian algorithm.

All together, these results demonstrate the strong potential for improvements
in algorithm run time using machine-learned predictions for the weighted
matching problem.

Figure 1: Iteration count results for the Batch setting. The left figure gives
the iteration count for the type model (synthetic data) versus linearly
increasing $v$, while the middle geometrically increases $v$. The right figure
summarizes the results for clustering based instances (real data) in the batch
setting.

Figure 2:  Iteration count results for the Online setting. The left figure is
for the type model (synthetic data), while the middle and right are for the
clustering based instances (real data) with $k=500$ on KDD and Covertype,
respectively.

Figure 3:  More iteration count results for the Online setting. From left to
right, we have the results for the clustering based instances on Blog
Feedback, Shuttle, and Skin, all with $k=500$.

Figure 4:  Iteration count results for clustering derived instances in the
Batch setting on other values of $k$. Here we give the results for each $k$ in
$\\{100\cdot i\mid 1\leq i\leq 10\\}\setminus\\{500\\}$.

##  5 Extending to $b$-Matching

We now extend the results from Section 3 to the minimum weight perfect
$b$-matching problem on bipartite graphs. In the extension we are given a
bipartite graph $G=(V,E)$, where $V=L\cup R$, a weight vector
$c\in\mathbb{Z}_{+}^{E}$ and a demand vector $b\in\mathbb{Z}_{+}^{V}$. As
before, we assume that the primal is feasible for the remainder of this
section. Note that the feasibility of the primal can be checked with a single
call to a maximum flow algorithm.

The problem is modeled by the following linear program and its dual linear
program.

$\begin{array}[]{ccc}\min&\displaystyle\sum_{e\in E}c_{e}x_{e}&\\\
&\displaystyle\sum_{e\in\delta(i)}x_{e}=b_{i}&\forall i\in V\\\ &x_{e}\geq
0&\forall e\in E\end{array}$ (MWBM-P)
$\begin{array}[]{ccc}\max&\displaystyle\sum_{i\in V}b_{i}y_{i}&\\\
&\displaystyle y_{i}+y_{j}\leq c_{ij}&\forall ij\in E\\\ \end{array}$ (MWBM-D)

First we show how to project an infeasible dual onto the set of feasible
solutions, then we give a simple primal dual scheme for moving to an optimal
solution. The end goal of this section is proving the following theorem.

######  Theorem 24.

There exists an algorithm which takes as input a (not necessarily feasible)
dual assignment $y$ and finds a minimum weight perfect $b$-matching in
$O(mn\|y^{*}-y\|_{1})$ time, where $y^{*}$ is an optimal dual solution and
$\|y^{*}-y\|_{b,1}:=\sum_{i}b_{i}|y^{*}_{i}-y_{i}|$.

###  5.1 Recovering a Feasible Dual Solution for $b$-Matching

As in Section 3, our goal now is to find non-negative perturbations $\delta$
such that $\hat{y}^{\prime}:=\hat{y}-\delta$ is feasible for (MWPM-D). We
would like these perturbations to preserve as much of the dual objective value
as possible. Again we define $r_{e}:=\hat{y}_{i}+\hat{y}_{j}-c_{e}$ for each
edge $e=ij\in E$. Following the same steps as before, this leads to the
following linear program and it’s dual.

$\begin{array}[]{ccc}\min&\displaystyle\sum_{i\in V}b_{i}\delta_{i}&\\\
&\displaystyle\delta_{i}+\delta_{j}\geq r_{e}&\forall e=ij\in E\\\
&\delta_{i}\geq 0&\forall i\in V\end{array}$ (4)
$\begin{array}[]{ccc}\max&\displaystyle\sum_{e\in E}r_{e}\gamma_{e}&\\\
&\displaystyle\sum_{e\in N(i)}\gamma_{e}\leq b_{i}&\forall i\in V\\\
&\gamma_{e}\geq 0&\forall e\in E\end{array}$ (5)

Again we are interested in finding a fast approximate solution to this
problem. We develop a new algorithm different than that used in the prior
section and show it is a $2$ approximation to (4). To do so, consider the dual
LP above. This is an instance of the weighted $b$-matching problem where edges
can be selected any number of times. We will first develop a $2$ approximation
to this LP in $O(m\log m+n)$ time. The analysis will be done via a dual
fitting analysis. This analysis will give us the corresponding $2$-approximate
fractional primal solution that will be used to construct $\hat{y}^{\prime}$.

Consider the following algorithm for the dual problem. Sort the edges $e$ in
decreasing order of $r_{e}$. When considering an edge
$e^{\prime}=i^{\prime}j^{\prime}$ in this order set $\gamma_{e^{\prime}}$ as
large as possible such that $\sum_{e\in N(i^{\prime})}\gamma_{e}\leq
b_{i^{\prime}}$ and $\sum_{e\in N(j^{\prime})}\gamma_{e}\leq b_{j^{\prime}}$.
Notice the running time of the algorithm is bounded by $O(m\log m+n)$.

When the algorithm terminates we construct a corresponding primal solutions.
For each $i\in V$, set $\delta_{i}=\frac{\sum_{e\in
N(i)}\gamma_{e}r_{e}}{b_{i}}$. That is, $\delta_{i}$ is the summation of the
weights $r$ of the adjacent edges divided by the $b$-matching constraint value
$b_{i}$. We will show that $\delta$ is a feasible primal solution. Moreover
that the primal and dual objectives are within a factor two of each other.

######  Lemma 25.

The solution $\delta$ is feasible for LP (4) and $\gamma$ is feasible for the
dual LP (5).

###### Proof.

The feasibility for the dual is by construction, so consider the primal.
Consider any edge $e^{\prime}=i^{\prime}j^{\prime}$. Our goal is to show that
$\delta_{i^{\prime}}+\delta_{j^{\prime}}\geq r_{e^{\prime}}$. Let
$A_{e^{\prime}}$ be the set of edges considered by the algorithm up to edge
$e^{\prime}$ including the edge itself. These edges have weight at least as
large $e^{\prime}$. We claim that either $\sum_{e\in N(i^{\prime})\cap
A_{e^{\prime}}}\gamma_{e}=b_{i^{\prime}}$ or $\sum_{e\in N(j^{\prime})\cap
A_{e^{\prime}}}\gamma_{e}=b_{j^{\prime}}$. Indeed, otherwise we would increase
$\gamma_{e^{\prime}}$ until this is true. Without loss of generality say that
$\sum_{e\in N(i^{\prime})\cap A_{e^{\prime}}}\gamma_{e}=b_{i^{\prime}}$. We
will argue that $\delta_{i^{\prime}}\geq r_{e^{\prime}}$. Knowing that
$\delta_{j^{\prime}}$ is non-negative, this will complete the proof.

Consider the value of $\delta_{i^{\prime}}$. This is $\frac{\sum_{e\in
N(i^{\prime})}\gamma_{e}r_{e}}{b_{i^{\prime}}}=\frac{\sum_{e\in
N(i^{\prime})\cap A_{e^{\prime}}}\gamma_{e}r_{e}}{b_{i^{\prime}}}$. We know
from the above that $\sum_{e\in N(i^{\prime})\cap
A_{e^{\prime}}}\gamma_{e}=b_{i^{\prime}}$ and every edge in $A_{e^{\prime}}$
has weight greater than $e^{\prime}$. Thus, $\frac{\sum_{e\in
N(i^{\prime})\cap A_{e^{\prime}}}\gamma_{e}r_{e}}{b_{i^{\prime}}}\geq
r_{e^{\prime}}\frac{\sum_{e\in N(i^{\prime})\cap
A_{e^{\prime}}}\gamma_{e}}{b_{i^{\prime}}}=r_{e^{\prime}}$ ∎

Next we bound the objective of the primal as a function of the dual.

######  Lemma 26.

The primal objective is exactly twice the dual objective.

###### Proof.

It suffices to show each edge $e=ij$ contributes twice as much to the primal
objective as it does to the dual objective. First, $e$’s contribution to the
dual objective is clearly $r_{e}\gamma_{e}$. For the dual, edge $e$
contributes to the summation for both end points. That is, $e$ contributes to
$\delta_{i}$ by $\gamma_{e}r_{e}/b_{i}$ and to $\delta_{j}$ by
$\gamma_{e}r_{e}/b_{j}$. Thus, edge $e$’s contribution to the primal objective
is
$b_{i}\frac{\gamma_{e}r_{e}}{b_{i}}+b_{j}\frac{\gamma_{e}r_{e}}{b_{j}}=2\gamma_{e}r_{e}$,
as desired. ∎

Thus, we have found a 2-approximate solution to the primal LP (4). However,
the solution is not necessarily integral. Thus, to make it integral, we do the
following simple rounding:

$\delta_{i}\leftarrow\begin{cases}\lfloor 2\delta_{i}\rfloor&\mbox{if
}\delta_{i}\geq 0.5\\\ 0&\mbox{if }\delta_{i}\in[0,0.5)\end{cases}$

Clearly this update can double the cost in the worst case. Hence we only need
to check that every constraint remains satisfied. To see this consider an edge
$e=ij$ and let $\delta_{i}$ and $\delta_{j}$ be the dual values before the
update. Note that $r_{e}$ is an integer assuming that we are given integer
dual values $\hat{y}$. Assume $r_{e}\geq 1$ since otherwise the constraint
trivially holds true. It is an easy exercise to see that $\lfloor
2x\rfloor\geq x$ for all $x\geq 0.5$. Thus, if $\delta_{i},\delta_{j}\geq
0.5$, then the update only increases the value of $\delta_{i}$ and
$\delta_{j}$, keeping the constraint satisfied. Further, as $r_{e}\geq 1$, it
must be the case that $\delta_{i}\geq 0.5$ or $\delta_{j}\geq 0.5$. So, we
only need to consider the case either $\delta_{i}\geq 0.5$ and
$\delta_{j}<0.5$; or $\delta_{i}<0.5$ and $\delta_{j}\geq 0.5$. Assume wlog
that the latter is the case. Since $\delta_{i}\leq\delta_{j}$, if
$\delta_{i}+\delta_{j}\geq r_{e}$, we have $2\delta_{j}\geq r_{e}$. Then, we
have $\lfloor 2\delta_{j}\rfloor\geq r_{e}$ as $r_{e}$ is an integer. Again,
the constraint is satisfied.

Thus, we obtain the following which is analogous to Theorem 7.

######  Theorem 27.

There is a $O(m\log m+n)$ time algorithm that takes an infeasible integer dual
$\hat{y}$ and constructs a feasible integer dual $\hat{y}^{\prime}$ such that
$\|\hat{y}-\hat{y}^{\prime}\|_{b,1}\leq 4\|y^{*}-\hat{y}\|_{b,1}$ where
$y^{*}$ is the optimal dual solution. Thus, we have
$\|\hat{y}^{\prime}-y^{*}\|_{b,1}\leq 5\|\hat{y}-y^{*}\|_{b,1}$.

###  5.2 Converting a Feasible Dual Solution to an Optimal Primal Solution

Now we consider taking a feasible dual $y$ and moving to an optimal solution
for the $b$-matching problem. The algorithm we use is a simple primal-dual
scheme that generalizes Algorithm 2. See Algorithm 3 for details. Below we
give a brief analysis of this algorithm. The objective is to establish a
running time in terms of the following distance
$\|y^{*}-y\|_{b,1}:=\sum_{i}b_{i}|y^{*}_{i}-y_{i}|$. One can view this
distance as the $\ell_{1}$ norm distance where each coordinate axis is given a
different level of importance by the $b_{i}$ values.

Algorithm 3 Simple Primal-Dual Scheme for MWBM

1:procedure MWBM-PrimalDual($G=(V,E),c,y$)

2: $E^{\prime}\leftarrow\\{ij\in E\mid y_{i}+y_{j}=c_{ij}$ } $\triangleright$
Set of tight edges in the dual

3: $G^{\prime}\leftarrow(L\cup R\cup\\{s,t\\},E^{\prime}\cup\\{si\mid i\in
L\\}\cup\\{jt\mid j\in R\\})$ $\triangleright$ Network of tight edges

4: $\forall e\in E(G^{\prime})$ s.t. $e=si$ or $e=it$, $u_{e}\leftarrow b_{i}$

5: $u_{e}\leftarrow\infty$ for all other edges of $G^{\prime}$

6: $f\leftarrow$ Maximum $s-t$ flow in $G^{\prime}$ with capacities $u$

7: while Value of $f$ is $<\sum_{i\in L}b_{i}$ do

8: Find a set $S\subseteq L$ such that $\sum_{i\in
S}b_{i}>\sum_{j\in\Gamma(S)}b_{j}$ $\triangleright$ Exists by Lemma 28

9:$\triangleright$ Can be found in $O(m+n)$ time

10: $\epsilon\leftarrow\min_{i\in S,j\in
R\setminus\Gamma(S)}\\{c_{ij}-y_{i}-y_{j}\\}$

11: $\forall i\in S$, $y_{i}\leftarrow y_{i}+\epsilon$

12: $\forall j\in\Gamma(S)$, $y_{j}\leftarrow y_{j}-\epsilon$

13: Update $E^{\prime},G^{\prime},u$

14: $f\leftarrow$ Maximum $s-t$ flow in $G^{\prime}$ with capacities $u$

15: $x\leftarrow f$ restricted to edges of $G$

16: Return $x$

First we consider the correctness of the algorithm. As before, we need to show
that the update rule is well defined. The following is a well known
generalization of Hall’s theorem, showing that line 8 is well defined.
Further, the step can be implemented efficiently given $f$. The proof closely
follows that of Proposition 8 – the only difference is factoring $b$ in the
matching size and vertex cover size.

######  Proposition 28.

Let $G^{\prime}$ be the flow network defined in Algorithm 3 with capacities
$\rho$ and let $f$ be the maximum $s-t$ flow in $G^{\prime}$ if the value of
$f$ is less than $\sum_{i\in L}b_{i}$ then there exists $S\subseteq L$ such
that $\sum_{i\in S}b_{i}>\sum_{j\in\Gamma(S)}b_{j}$. Further, such $S$ can be
found in $O(m+n)$ time.

The following is analogous to Proposition 9 in Section 3.

######  Proposition 29.

Let $y$ be dual feasible and suppose that $S\subseteq L$ with $\sum_{i\in
S}b_{i}>\sum_{j\in\Gamma(S)}b_{j}$ in $G^{\prime}$. Let $\epsilon=\min_{i\in
S,j\in R\setminus\Gamma(S)}\\{c_{ij}-y_{i}-y_{j}\\}$. Then as long as $c$ and
$y$ are integers we have $\epsilon\geq 1$.

Additionally, we need to establish that $y$ remains feasible throughout the
execution of the algorithm. This is nearly identical to the corresponding
lemma in Section 3 so we state it as the following lemma without proof.

######  Lemma 30.

If Algorithm 3 is given an initial dual feasible $y$, then $y$ remains dual
feasible throughout its execution.

The above statements can be combined to give the following theorem.

######  Theorem 31.

There exists an algorithm for minimum weight perfect $b$-matching in bipartite
graphs which runs in time $O(nm\|y^{*}-y\|_{b,1})$, where $y^{*}$ is an
optimal dual solution and $y$ is the initial dual feasible solution passed to
the algorithm.

###### Proof.

The correctness of the algorithm is implied by Lemma 30 and the fact that the
flow network $G^{\prime}$ ensures that the resulting solution $x$ that it
finds satisfies complementary slackness with $y$. Thus we just need to
establish the running time.

Note that it suffices to bound the number of iterations in terms of
$O(\|y^{*}-y\|_{b,1})$ since the most costly step of each iteration is finding
the maximum flow in the network $G^{\prime}$, which can be done in time
$O(nm)$. The two propositions above state that the net increase in the dual
objective is always at least $1$, and so the number of iterations is at most
$\sum_{i}b_{i}y^{*}_{i}-\sum_{i}b_{i}y_{i}\leq\sum_{i}b_{i}\|y^{*}_{i}-y_{i}\|=\|y^{*}-y\|_{b,1}$.
∎

This theorem, combined with Theorem 27, gives Theorem 24, as desired.

###  5.3 Learning the Dual Prices

In this section we extend the results from Section 3.3 to the case of
$b$-matching. As before, we consider a graph with fixed demands $b$ and an
unknown distribution ${\cal D}$ over the edge costs $c$. We are interested in
learning a fixed set of prices $y$ which is in some sense best for this
distribution. Since the running time of the algorithms we consider depends on
$\|y^{*}-y\|_{b,1}$ it is natural to choose this as our loss function with
respect to the learning task. Thus we define
$L_{b}(y,c)=\|y-y^{*}(c)\|_{b,1}$, where again $y^{*}(c)$ is a fixed optimal
dual vector for costs $c$. Our goal is to perform well against the best choice
for the distribution. Formally, let $y^{*}:=\arg\min_{y}\mathbb{E}_{c\sim{\cal
D}}[L_{b}(y,c)]$. Additionally, let $C$ be a bound on the edge costs and
$B=\max_{i\in V}b_{i}$ be a bound on the demands. We have the following result
which is analogous to Theorem 14.

######  Theorem 32.

There is an algorithm that after
$s=O\left(\left(\frac{nCB}{\epsilon}\right)^{2}(n\log n+\log(1/\rho)\right)$
samples returns integer dual values $\hat{y}$ such that
$\mathbb{E}_{c\sim{\cal D}}[L_{b}(\hat{y},c)]\leq\mathbb{E}_{c\sim{\cal
D}}[L(y^{*},c]+\epsilon$ with probability at least $1-\rho$. The algorithm
runs in time polynomial in $n,m$ and $s$.

At a high level, we can prove this theorem by again applying Theorem 16 and
Corollary 17. To do this we define the following family of functions ${\cal
H}_{b}=\\{g_{y}\mid y\in\mathbb{R}^{V}\\}$ where $g_{y}=\|y-y^{*}(c)\|_{b,1}$.
We need to verify the following: (1) the range of these functions are bounded
in $[0,H]$ for some $H=O(nCB)$, (2) minimizing the empirical loss can be done
efficiently, and (3) the pseudo-dimension of ${\cal H}_{b}$ is bounded by
$O(n\log n)$. Applying similar arguments as in Sections 3.3.2 and 3.3.3 give
us the first two points. Here we focus on the last point, bounding the pseudo-
dimension.

Note that for $b\in\mathbb{R}_{+}^{n}$, $\|\cdot\|_{b,1}$ is a norm.
Intuitively, the geometry induced by $\|\cdot\|_{b,1}$ is the same as the
geometry induced by $\|\cdot\|_{1}$ except some axes are stretched by an
appropriate amount. This should imply that the functions in ${\cal H}_{b}$
should not be more complicated than the functions in ${\cal H}$. We make this
intuition more formal by arguing that we can map from one setting to the other
while preserving membership in the respective balls induced by these norms.
The following key lemma will imply that the pseudo-dimension of ${\cal H}_{b}$
is no larger than the pseudo-dimension of ${\cal H}$.

######  Lemma 33.

Let $B_{b,1}(x,r)=\\{y\mid\|x-y\|_{b,1}\leq r\\}$ and
$B_{1}(x,r)=\\{y\mid\|x-y\|_{1}\leq r\\}$ be the balls of radius $r$ under
each norm, respectively. There is a mapping
$\phi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ such that $y\in B_{b,1}(x,r)$ if and
only if $\phi(y)\in B_{1}(\phi(x),r)$.

###### Proof.

Define $\phi(y)_{i}=b_{i}y_{i}$ for $i=1,2,\ldots,n$. Now we have the
following which implies the lemma.

$\begin{split}\|x-y\|_{b,1}&=\sum_{i}b_{i}|x_{i}-y_{i}|=\sum_{i}|b_{i}x_{i}-b_{i}y_{i}|\\\
&=\|\phi(x)-\phi(y)\|_{1}\end{split}$

Thus one of these is at most $r$ if and only if the other is. ∎

Now define the family of functions ${\cal
H}_{b,n}=\\{f_{y}:\mathbb{R}^{n}\to\mathbb{R}\mid
y\in\mathbb{R}^{n},f_{y}(x)=\|y-x\|_{b,1}\\}$, we have the following which is
analogous to Lemma 18.

######  Lemma 34.

The pseudo-dimension of ${\cal H}_{b}$ is at most the pseudo-dimension of
${\cal H}_{b,n}$

###### Proof.

Nearly identical to that of Lemma 18 but with $\|\cdot\|_{1}$ replaced with
$\|\cdot\|_{b,1}$. ∎

We can now prove that the pseudo-dimension of ${\cal H}_{b}$ is bounded by
$O(n\log n)$.

######  Lemma 35.

The pseudo-dimension of ${\cal H}_{b}$ is at most $O(n\log n)$.

###### Proof.

By Lemma 34 we have that the pseudo-dimension of ${\cal H}_{b}$ is at most
${\cal H}_{b,n}$. We now show that the pseudo-dimension of ${\cal H}_{b,n}$ is
at most the pseudo-dimension of ${\cal H}_{n}$ using Lemma 33. Let
$x^{1},\ldots,x^{k}\in\mathbb{R}^{n}$ be given. Now consider
$y^{j}=\phi(x^{j})$ for $j=1,\ldots,k$. By Lemma 33 we can see that
$x^{1},\ldots,x^{k}$ are shattered by ${\cal H}_{b,n}$ if and only if
$y^{1},\ldots,y^{k}$ are shattered by ${\cal H}_{n}$. Thus the pseudo-
dimension of ${\cal H}_{b,n}$ is at most ${\cal H}_{n}$ and then the lemma
follows by Theorem 19. ∎

##  6 Conclusion and Future Work

In this work we showed how to use learned predictions to warm-start primal-
dual algorithms for weighted matching problems to improve their running times.
We identified three key challenges of feasibility, learnability and
optimization, for any such scheme, and showed that by working in the dual
space we could give rigorous performance guarantees for each. Finally, we
showed that our proposed methods are not only simpler, but also more efficient
in practice.

An immediate avenue for future work is to extend these results to other
combinatorial optimization problems. The key ingredient is identifying an
appropriate intermediate representation: it must be simple enough to be
learnable with small sample complexity, yet sophisticated enough to capture
the underlying structure of the problem at hand.

## References

  * Aamand et al. [2019] Anders Aamand, Piotr Indyk, and Ali Vakilian.  (learned) frequency estimation algorithms under zipfian distribution.  _arXiv preprint arXiv:1908.05198_ , 2019.
  * Anand et al. [2020] Keerti Anand, Rong Ge, and Debmalya Panigrahi.  Customizing ML predictions for online algorithms.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 303–313. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/anand20a.html.
  * Anthony and Bartlett [2009] Martin Anthony and Peter L Bartlett.  _Neural network learning: Theoretical foundations_.  cambridge university press, 2009.
  * Antoniadis et al. [2020] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 345–355. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/antoniadis20a.html.
  * Balcan et al. [2018a] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik.  Learning to branch.  In Jennifer G. Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 353–362. PMLR, 2018a.  URL http://proceedings.mlr.press/v80/balcan18a.html.
  * Balcan et al. [2018b] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik.  Dispersion for data-driven algorithm design, online learning, and private optimization.  In Mikkel Thorup, editor, _59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018_ , pages 603–614. IEEE Computer Society, 2018b.  doi: 10.1109/FOCS.2018.00064.  URL https://doi.org/10.1109/FOCS.2018.00064.
  * Balcan et al. [2018c] Maria-Florina Balcan, Travis Dick, and Colin White.  Data-driven clustering via parameterized lloyd’s families.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_ , pages 10664–10674, 2018c.
  * Balcan et al. [2019] Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik.  How much data is sufficient to learn high-performing algorithms?  _CoRR_ , abs/1908.02894, 2019.  URL http://arxiv.org/abs/1908.02894.
  * Bamas et al. [2020] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.  URL https://proceedings.neurips.cc/paper/2020/hash/e834cb114d33f729dbc9c7fb0c6bb607-Abstract.html.
  * Bhatt and Dhall [2012] Rajen Bhatt and Abhinav Dhall.  Skin segmentation dataset, uci machine learning repository, 2012.
  * Bhattacharya et al. [2016] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  _New Deterministic Approximation Algorithms for Fully Dynamic Matching_ , page 398–411.  Association for Computing Machinery, New York, NY, USA, 2016.  ISBN 9781450341325.  URL https://doi.org/10.1145/2897518.2897568.
  * Buza [2014] Krisztian Buza.  Feedback prediction for blogs.  In Myra Spiliopoulou, Lars Schmidt-Thieme, and Ruth Janning, editors, _Data Analysis, Machine Learning and Knowledge Discovery_ , pages 145–152, Cham, 2014. Springer International Publishing.  ISBN 978-3-319-01595-8.
  * Chawla et al. [2019] Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang.  Learning optimal search algorithms from data.  _CoRR_ , abs/1911.01632, 2019.  URL http://arxiv.org/abs/1911.01632.
  * Cheriyan and Mehlhorn [1996] Joseph Cheriyan and Kurt Mehlhorn.  Algorithms for dense graphs and networks on the random access computer.  _Algorithmica_ , 15(6):521–549, 1996.  doi: 10.1007/BF01940880.  URL https://doi.org/10.1007/BF01940880.
  * Cohen et al. [2020] Edith Cohen, Ofir Geri, and Rasmus Pagh.  Composable sketches for functions of frequencies: Beyond the worst case.  _CoRR_ , abs/2004.04772, 2020.  URL https://arxiv.org/abs/2004.04772.
  * Daitch and Spielman [2008] Samuel I. Daitch and Daniel A. Spielman.  Faster approximate lossy generalized flow via interior point algorithms.  In Cynthia Dwork, editor, _Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008_ , pages 451–460. ACM, 2008.  doi: 10.1145/1374376.1374441.  URL https://doi.org/10.1145/1374376.1374441.
  * Devanur and Hayes [2009] Nikhil R. Devanur and Thomas P. Hayes.  The adwords problem: online keyword matching with budgeted bidders under random permutations.  In _Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6–10, 2009_ , pages 71–78, 2009.
  * Drake and Hougardy [2003] Doratha E. Drake and Stefan Hougardy.  A simple approximation algorithm for the weighted matching problem.  _Inf. Process. Lett._ , 85(4):211–213, 2003.  doi: 10.1016/S0020-0190(02)00393-9.  URL https://doi.org/10.1016/S0020-0190(02)00393-9.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Duan and Pettie [2014] Ran Duan and Seth Pettie.  Linear-time approximation for maximum weight matching.  _J. ACM_ , 61(1):1: 1–1: 23, 2014.  doi: 10.1145/2529989.  URL https://doi.org/10.1145/2529989.
  * Duan and Su [2012] Ran Duan and Hsin - Hao Su.  A scaling algorithm for maximum weight matching in bipartite graphs.  In Yuval Rabani, editor, _Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012_ , pages 1413–1424. SIAM, 2012.  doi: 10.1137/1.9781611973099.111.  URL https://doi.org/10.1137/1.9781611973099.111.
  * Dütting et al. [2020] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii.  Secretaries with advice.  _CoRR_ , abs/2011.06726, 2020.  URL https://arxiv.org/abs/2011.06726.
  * Gabow [1985] Harold N. Gabow.  A scaling algorithm for weighted matching on general graphs.  In _26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985_ , pages 90–100. IEEE Computer Society, 1985.  doi: 10.1109/SFCS.1985.3.  URL https://doi.org/10.1109/SFCS.1985.3.
  * Goldberg and Kennedy [1997] Andrew V. Goldberg and Robert Kennedy.  Global price updates help.  _SIAM J. Discret. Math._ , 10(4):551–572, 1997\.  doi: 10.1137/S0895480194281185.  URL https://doi.org/10.1137/S0895480194281185.
  * Gondzio [1998] Jacek Gondzio.  Warm start of the primal-dual method applied in the cutting-plane scheme.  _Math. Program._ , 83:125–143, 1998.  doi: 10.1007/BF02680554.  URL https://doi.org/10.1007/BF02680554.
  * Gondzio and González-Brevis [2015] Jacek Gondzio and Pablo González-Brevis.  A new warmstarting strategy for the primal-dual column generation method.  _Math. Program._ , 152(1-2):113–146, 2015.  doi: 10.1007/s10107-014-0779-8.  URL https://doi.org/10.1007/s10107-014-0779-8.
  * [27] Google Cloud Platform.  https://cloud.google.com/.
  * Gupta and Roughgarden [2017] Rishi Gupta and Tim Roughgarden.  A PAC approach to application-specific algorithm selection.  _SIAM J. Comput._ , 46(3):992–1017, 2017.  doi: 10.1137/15M1050276.  URL https://doi.org/10.1137/15M1050276.
  * Hopcroft and Karp [1973] John E. Hopcroft and Richard M. Karp.  An $n^{5/2}$-algorithm for maximum matchings in bipartite graphs.  _SIAM Journal on Computing_ , 2(4):225–231, 1973\.  doi: 10.1137/0202019.  URL https://doi.org/10.1137/0202019.
  * Hsu et al. [2019] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian.  Learning-based frequency estimation algorithms.  In _7th International Conference on Learning Representations_ , 2019\.
  * Jiang et al. [2020] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun.  Online algorithms for weighted paging with predictions.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, _47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)_ , volume 168 of _LIPIcs_ , pages 69:1–69:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi: 10.4230/LIPIcs.ICALP.2020.69.  URL https://doi.org/10.4230/LIPIcs.ICALP.2020.69.
  * King et al. [1994] V. King, S. Rao, and R. Tarjan.  A faster deterministic maximum flow algorithm.  _Journal of Algorithms_ , 17(3):447 – 474, 1994\.  ISSN 0196-6774.  doi: https://doi.org/10.1006/jagm.1994.1044.  URL http://www.sciencedirect.com/science/article/pii/S0196677484710443.
  * Kraska et al. [2018] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In _Proceedings of the 2018 International Conference on Management of Data_ , pages 489–504. ACM, 2018.
  * Lattanzi et al. [2020] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Shuchi Chawla, editor, _Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020_ , pages 1859–1877. SIAM, 2020.  doi: 10.1137/1.9781611975994.114.  URL https://doi.org/10.1137/1.9781611975994.114.
  * Lee and Sidford [2014] Yin Tat Lee and Aaron Sidford.  Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow.  In _55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014_ , pages 424–433. IEEE Computer Society, 2014.  doi: 10.1109/FOCS.2014.52.  URL https://doi.org/10.1109/FOCS.2014.52.
  * Lykouris and Vassilvitskii [2018] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 3302–3311, 2018.
  * Mehta et al. [2007] Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani.  Adwords and generalized online matching.  _J. ACM_ , 54(5):22, 2007.  doi: 10.1145/1284320.1284321.  URL https://doi.org/10.1145/1284320.1284321.
  * Mitzenmacher [2018] Michael Mitzenmacher.  A model for learned bloom filters and optimizing by sandwiching.  In _Advances in Neural Information Processing Systems_ , pages 464–473, 2018.
  * Mitzenmacher and Vassilvitskii [2020] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  _CoRR_ , abs/2006.09123, 2020.  URL https://arxiv.org/abs/2006.09123.
  * Morgenstern and Roughgarden [2015] Jamie H Morgenstern and Tim Roughgarden.  On the pseudo-dimension of nearly optimal auctions.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 136–144. Curran Associates, Inc., 2015.  URL http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions.pdf.
  * Nair et al. [2018] Vinod Nair, Dj Dvijotham, Iain Dunning, and Oriol Vinyals.  Learning fast optimizers for contextual stochastic integer programs.  In Amir Globerson and Ricardo Silva, editors, _Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018_ , pages 591–600. AUAI Press, 2018.  URL http://auai.org/uai2018/proceedings/papers/217.pdf.
  * Orlin [1993] James B. Orlin.  A faster strongly polynomial minimum cost flow algorithm.  _opera. Res._ , 41(2):338–350, 1993.  doi: 10.1287/opre.41.2.338.  URL https://doi.org/10.1287/opre.41.2.338.
  * Orlin [2013] James B. Orlin.  Max flows in o(nm) time, or better.  In _Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing_ , STOC ’13, page 765–774, New York, NY, USA, 2013. Association for Computing Machinery.  ISBN 9781450320290.  doi: 10.1145/2488608.2488705.  URL https://doi.org/10.1145/2488608.2488705.
  * Orlin and Ahuja [1992] James B. Orlin and Ravindra K. Ahuja.  New scaling algorithms for the assignment and minimum mean cycle problems.  _math. Program._ , 54:41–56, 1992.  doi: 10.1007/BF01586040.  URL https://doi.org/10.1007/BF01586040.
  * Pollard [2012] David Pollard.  _Convergence of stochastic processes_.  Springer Science & Business Media, 2012.
  * Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  In _Advances in Neural Information Processing Systems_ , pages 9661–9670, 2018.
  * Rohatgi [2020] Dhruv Rohatgi.  Near-optimal bounds for online caching with machine learned advice.  In _Symposium on Discrete Algorithms (SODA)_ , 2020.
  * Roughgarden [2020] Tim Roughgarden.  _Beyond the Worst-Case Analysis of Algorithms_.  Cambridge University Press, 2020.
  * Sankowski [2006] Piotr Sankowski.  Weighted bipartite matching in matrix multiplication time.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, _Automata, Languages, and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I_ , volume 4051 of _Lecture Notes in Computer Science_ , pages 274–285. Springer, 2006.  doi: 10.1007/11786986\␣_25.  URL https://doi.org/10.1007/11786986_25.
  * Sankowski [2007] Piotr Sankowski.  Faster dynamic matchings and vertex connectivity.  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’07, page 118–126, USA, 2007. Society for Industrial and Applied Mathematics.  ISBN 9780898716245.
  * Vaidya et al. [2020] Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher.  Partitioned learned bloom filter.  _CoRR_ , abs/2006.03176, 2020.  URL https://arxiv.org/abs/2006.03176.
  * van den Brand et al. [2020] Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Bipartite matching in nearly-linear time on moderately dense graphs.  In _61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020_ , pages 919–930. IEEE, 2020.  doi: 10.1109/FOCS46700.2020.00090.  URL https://doi.org/10.1109/FOCS46700.2020.00090.
  * Vee et al. [2010] Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram.  Optimal online assignment with forecasts.  In _Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010_ , pages 109–118, 2010\.
  * Yamashita and Tanabe [2010] Hiroshi Yamashita and Takahito Tanabe.  A primal-dual exterior point method for nonlinear optimization.  _SIAM Journal on Optimization_ , 20(6):3335–3363, 2010.  doi: 10.1137/060676970.  URL https://doi.org/10.1137/060676970.

##  Appendix A Additional Experimental Results

Here we present additional experimental results that were omitted from Section
4. First we present our results while looking at the running time as opposed
to the number of primal dual iterations.

###  A.1 Running Time

Figure 5 gives running time results for the batch setting, while Figure 6 give
the results for the online setting. Finally, Figure 7 looks at the clustering
derived instances for other values of $k$. We see similar performance
improvements for Learned Duals against the standard Hungarian algorithm,
showing that the impact of running Algorithm 1 to make the predicted duals
feasible is minimal.

Figure 5: Running time results (in seconds) for the Batch setting. The left
figure gives the iteration count for the type model (synthetic data) versus
linearly increasing $v$, while the middle geometrically increases $v$. The
right figure summarizes the results for clustering based instances (real data)
in the batch setting.

Figure 6:  Running time results for the Online setting. The top left figure is
for the type model (synthetic data). The rest, in order, are KDD and
Covertype, Blog Feedback, Shuttle, and Skin. All use $k=500$.

Figure 7:  Running time results (in seconds) for clustering derived instances
in the Batch setting on other values of $k$. Here we give the results for each
$k$ in $\\{100\cdot i\mid 1\leq i\leq 10\\}\setminus\\{500\\}$.