Faster Matchings via Learned Duals
Authors: Michael Dinitz
Sungjin Im
Thomas Lavastida
Benjamin Moseley
Sergei Vassilvitskii
Venue: NeurIPS 2021 Oral (2021)
Keywords: Bipartite matching
run time
learning

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.

Faster Matchings via Learned Duals
Michael Dinitz Johns Hopkins University mdinitzecs. juu edu
Sungjin Im UC Merced sim3@u edu
Thomas Lavastida
Carnegie Mellon University tlavasti Sandrew. cmu.
Benjamin Moseley Carnegie Mellon University moseleyb@an eyseleyb@andrew cmu. edu
Sergei Vassilvitskii
Google sergeivdgoogle... com
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 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 b-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predieted duals may be infeasible, predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may be optimal, we show that they can be used 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 rigorous, practical, and empirically effective method to compute bipartite matchings.
give an algorithm that efficiently maps
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 [41]. to better understand performance 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 he augmented with machine-learned predictors to circumvent worst case lower bounds when the predictions good, and approximately match them otherwise (see Mitzenmacher and Vassilvitskii 36) 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
[33] Rohatgi 40), Jiang et al. 29 caching; Antoniadis
et al. 33. Dütting et al. [19] on the classic secretary problem; Purohit et al. [39], Lattanzi er al. [32
on scheduling: Purohit al. 39 Anand et al. on ski rental: and Bamas et al. on set cover.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

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. [3T 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 [46] 23 22 37,. where instead of starting with blank slate, the algorithm begins with some starting state (which we call a warm-stard "solution" or "seed")) which hopefully allows for faster completion. While it is a common technique, there is a dearth of analysis understanding what constitutes good warm-start, when such initializations are helpful, and how they can best be leveraged.
Thus we have 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 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:
(i) Feasibility. The learned prediction (warm-start solution) might not even be feasible for the specific instance care about! For example, the learned solution may be matching an edge that does not exist in the graph at testing time.
(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 function of the quality of the learned solution.
(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) 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 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 cellmmmm-wighht perfect matching (MWPM) problem, as well as its extension to 6-matching, we show that the above three challenges can be solved.
A key conceptual question is finding specification of the seed, and an algorithm to use it that satisfies the desiderata above. We have discussed warm-start "solutions", so it is tempting to think that good seed is a partial solution: a set of matched edges that can then be expanded to a optimal matching. After all, this is the structure solution is feasible (one can simply set non-existing edges to have very high weight), eschewing the need for the feasibility step. At the same time, has been observed previously in the context of this primal solution is brittle, and a minor modification in the instance (c.g. an addition of single edge) can completely change the set of optimal edges.
maintain in most classical matching algorithms. Moreover, any such
online matchings
[3 45
Instead, following the work of 13 (45,, we look at the dual problem; that is, the dual to the natural linear program. We quantify the "quality" of prediction ý by its & didittanc from the true optimal dual y" i.e., by | - y" |1a- The smaller quantities correspond to better predictions. Since the dual is packing problem converts the prediction ÿ into a feasible dual while increasing the E, distance by a factor of at most 3.
must contend with feasibility: we give simple linear time algorithm that
Next, we run the Hungarian method starting with the resulting feasible dual. Here, we show that the running time in proportional to the & distance of the feasible dual to the optimal dual (Theorem 55) Finally, we show via ascudo-dimensee argument that not many samples are needed before the

---

empirically optimal seed is good approximation of the true optimum (Theorem 6 and that this empirical optimum can be computed efficiently, For the learning argument, we assume that matching instances are drawn from fixed but unknown distribution 'D.
Putting it all together gives our main result.
Theorem 1 (Informal). There are three algorithms (feasibility, optimization, learning) with the following guarantees.
Given a (possibly infeasible) dual 9 from the learning algorithm, there exists an O + n) time algorithm that takes a problem instance c, and outputs feasible dual (c(c such that (g'(c) - y (c)]l1 S 3 y (c)ll-
The optimization algorithm takes as input feasible dual ÿ' (c) and outputs a minimum weight perfect matching, and runs in time (mmyn -iin (c) yy (c)]l vnt).
After O(C²n²) samples from an unknown distribution D over problem instances, the learning algorithm produces duals 9 so that EEND (c)ll) is approximately minimum among all possible choices of y. where C is the maximum edge cost and y² (c) is an optimal dual for instance
Combining these gives a single algorithm that, with access to Ô(C²n²) problem instance samples from D, has expected running time on future instances from 'D of only ((m /irmmmn min(a, vnl),, where
ming EewD |lly yy [c]]
We emphasize that the Hungarian method with (mm) running time is the standard algorithm in practice. Although there are other theoretically faster exact algorithms for bipartite minimum- weight perfect matching (38] 21 20 [8] that run in (mm O(myTlog(nn()) they are relatively com- plex (using various scaling techniques). Very recent breakthroughs give algorithms of run time Ó(m + n 1-5)
(C)) for the minimum-weiggtt perfect matching problem and several interesting However, the algorithms are highly complicated and their practical performance is yet to be demonstrated. In fact, we could not find any implementation of the above algorithms, except for the Hungarian method, of which multiple implementations are readily available.
extensions 4
Note that our result shows that we can speed up the Hungarian method as long as the f--nrrm error of the learned dual, i.e., |/ yc()) is (n) Further, 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 straightforward empirical risk minimization algorithm (the analysis is more complex and involves bounding the
of the loss functions).
We validate thcoretical results via experiments. For each dataset 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, 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
Bipartite matchings are one of the most well studied problems in combinatorial optimization, with long history of algorithmic improvements. We refer the interested reader to Duan and Pettie [I7] for an overview. We highlight some particular results here. If edges have no weights and thus the goal is to find the maximum cardinality matching (see Section 2 for a formal definition), the fastest running time had long been (mm)n) [14] 30 271 until the recent breakthrough with O(m+n running time was discovered [3 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 (mm//llog(C
Matchings and b-Matchings:
38 21 20 18).
3

---

Large scale bipartite matchings have been studied extensively in the online setting, as they represent the basic problem in ad allocations [34]. While the ad allocation inherently online, most of the methods precompute dual based solution based on a sample of the input [13 45 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. [31] 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 strong theoretical foundation, evaluating the benefit of augmenting classical algorithms with machine learned predictions, see [36] 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 [3 40 29],
scheduling (39 32). frequency counting [2 28 1. and membership testing [55] 42 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 [25] 7 S 6 IT. Here, the objective is "learn" 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.
1.3 Roadmap
We present our theoretical results on min-cost perfect bipartite matching in Section The experiments are presented Section 4 The extension to b-matching, as well as all missing proofs, can be found in the full version of this paper as supplementary materials.
2 Preliminaries
Notation: Let G = (V, E) be an undirected graph. When G is bipartite we will use L and R to refer to the two sides of the bipartition. We will let (i1) == fe E i E } be the set of edges adjacent vertex i. For set S C V. let I(S) be the vertex neighborhood of S. For vector y E RR, we let || = Σ, | be its -norm. Let (z, y) be the standard inner product on R..
Linear Programming and Complementary Slackness: Here 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.
m x; Ar
x
(P)
m y; A (D)
A pair of solutions x, y for (P) and (D), respectively, satisfy complementary slackness if T A A y) = The following lemma well-known.
Lemma 2. Let be a feasible solution for (P) and be a feasible solution for (D). the pair x. satisfies complementary slackness, then x and y are optimal solutions for their respective problems.
Maximum Cardinality Matching: Let G = E) be a bipartite graph on n vertices and m edges. A matching M C E is collection of -on-intersecting edges. The Hoperoft-Kan algorithm for finding a matching maximizing M runs in time O(vn. m.) (26). which is still ofate-of-the-art for general bipartite graphs. For moderately dense graphs, recent result by den Brand et al. (43 gives better running time of Ö(m + n 155 (where Ô hides polylogarithmic factors).
Minimum Weight Perfect Matching (MWPM): Again, let G (V, E) a bipartite graph on n vertices and m with costs E Z 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 to find a perfect matching M minimizing the cost c(M) := E.eM Ce.

---

When looking for optimal solutions we can assume that G' is complete graph by adding all possible edges not in E with weight Cn², It easy to see that any o(n) approximate solution would not use any of these edges.
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 of dual variables dual prices. Both LPs are well-known to be integral, implying that there always exist integral optimal solutions.
Suppose we are given a prediction ğ of a dual solution. If g feasible, then by complementary slackness we check if y represents an optimal dual solution by running a maximum cardinality matching algorithm on the graph G' = (V, E"), is the set of tight
min
Σ CoTe
(MWPM-P)
BEB
Σ Ie
VIEV
where E" = {e = ij E E' D + 03 Cit J edges. If this matching perfect, then its incidence vector æ satisfies complementary slackness with and thus represents an optimal solution by Lemma 2
eE (()
Te 20 0
E
max
Σ Vi
(MWPM-D)
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 E ZF varies (is drawn from some distribution D). If we are given 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:
iEV Y1 + yo S Ce
ye= ij E
1. Feasiblity (Section[.I) The learned dual ý may not be feasible for MWPM-D with some specific cost vector We show how to quickly convert it to feasible dual g' (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 | - ('())ll turns out be a variant of the vertex cover problem, for which we give simple 2-approximation running in O(m 1/m++1 n) time. As result, have (c) y" (c)ll1 S 3 ū -y" See Theorem 4
2. Optimization (Section 3.2). Now that we have feasible solution (c). we want to find an optimal solution starting with g'(c) in time that depends on the quality of (c().. Fortunately,
the Hungarian algorithm can be seeded with any feasible dual, so we can "warm-start" with 5/ (c). We show that its running time will be proportional to I|li" (c)]l lIy" (c) < (c) yd (c)ll Our analysis does not depend on the details of the Hungarian algorithm, and so applies a broader class of primal-dual algorithms.
3. Learnability (Section 3.3). The target dual we seek to learn is arg miny E - y (c)ll; here y" (c) is the optimal dual for MWPM-D with cost vector c. We show we can efficiently learn I that is arbitrarily close to the target vector after Ō(C²n)3 samples from D. See Theorem 6
Combining all of these gives the following, which a more formal version of Theorem [ Let D be an arbitrary distribution over edge costs where every vector in the support of D has maximum cost C. For any edge cost vector c, let y" (c) denote the optimal dual solution.
Theorem 3. For any P.E > O, there an algorithm which:
After O ( (mC)² (n log + log(1/p)) samples from D, returns dual values ÿ such that El-plll - y" (c)]la] S min Ec<pllly y (c)llu] + e with probability at least 1 p.
Using the learned dual g. given edge costs computes a min-cost perfect matching in time 0 (m/n- min(ll y" (c)lli, vTt).
In the rest of this section we detail our proof of this Theorem.
5

---

3.1 Recovering a Feasible Dual Solution (Feasibility)
Let ý be an infeasible set of (integral) dual prices - this should be thought of as the "good" dual obtained by our learning
Algorithm 1 Fast Approx. for Distance to Feasibility
1: procedure FASTAPPROX(G E).)
algorithm. Our goal in this section is to find new feasible dual solution (c( that is close to y. for given MWPM-D instance with cost c. In particular we seek to find the closest feasible dual under the l norm, i.e. one minimizing (c) ill1.
2:
vi E V. 6; 4-0 while E + 9 do
3:
4:
Let be an arbitrary vertex of G
5:
while has neighbor do
6:
j + arg (agg Tij'
7:
8:
Delete and all its edges from G i j
9:
Looking at (MWPM-D), it is clear that we need to decrease the given dual val- ues 1 order to make feasible. More formally, we are looking for vector of non-negative perturbations 5 such that j/ == 5 is feasible. We model finding the best set of perturbations, in terms of preserving j's dual objective value, as a linear program. Let F == {s új E ú. + úū > cij} } be the set of dual infeasible edges under ÿ. Define re := Ut + ûj - ce for each edge e = ij E F. Asserting that y - is feasible for (MWPM-D) while minimizing the amount lost in the dual objective leads to the following linear program:
10:
Return 8
min Σ d;
8, + 6j 2ng
Vij E F; 2,20 ViEV
SEV
Note that this is a variant of the vertex cover problem-the problem becomes exactly the vertex cover problem if rty 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 ( we take a simple greedy approach.
Algorithm iis modification of the algorithm of Drake and Hougardy [5] which walks through the
graph setting 5; appropriately at each step to satisfy the covering constraints in (.. The analysis is
based on interpreting the algorithm through the lens of primal-dual the dual of 1 turns out to be
maximum weight matching problem with new edge weights Tij.
A similar analysis as in Drake and Hougardy [5] implies this is 2-approximation which runs in O(m + n) time (all proofs are in the Supplementary material). This essentially immediately implies the following theorem (the 2-approximation turns into 3 due to a use of the triangle inequality).
Theorem There is a (m)+n) time algorithm that takes an infeasible integer dual and constructs feasible integer dual (c) for MWPM-D with cost vector such that Il0 - ~ll I 2 - y (c) where y" (c) is the optimal dual solution for MWPM-D with cost vector c. Thus by triangle inequality we have 11 (c) v² (c)]l S 3 - y (c)]l.
3.2 Seeding Hungarian with a Feasible Dual (Optimization)
In this section assume that we are given a feasible integral dual gc(c) for an input with cost vector e and the goal is to find an optimal solution. We want to analyze the running time in terms of (c) y" [c) 1. the distance to optimality. We use simple primal-dual schema to achieve this, which is given formally in Algorithm 2
To satisfy complementary slackness, we must only choose edges with y: + yj Cij. Let E' be the set of such edges. We find maximum cardinality matching the graph G' = (V. E'). If the resulting matching M is perfect then we are done by complementary slackness (1 (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 will show this algorithm performs at most O (Ilv" (c) iterations. 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., lly (c) - ÿ (c)]ll 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 (Iet S = L \ C' for step 6, where C is minimum vertex cover, and update M along poorest-augmenttng---e paths for step 1) then we recover the Hungarian Algorithm. Together, we can prove the following theorem.

---

Theorem 5. For an arbitrary cost vector the Hungarian method starting with feesibbe integer dual solution i/ (c) finds minimum weight perfect matching in Ô (myn- min (cly"() - 3/ (. time, where y (c) is an optimal dual solution.
3.3 Learning Optimal Advice (Learning)
Algorithm Simple Primal-Dual Scheme for MWPM
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, out seeing too many samples. The formal model we will use is derived from data driven algorithm design and PAC leamn
1:
procedure MWPM-PD(G (V, F), c, y)
2:
F" < {e E y + = Tight Edges
want to find with-
3:
G² (V,E") G containing only tight edges
4:
< Maximum cardinality matching in G' while M is not perfect matching do
5:
6:
Find S C L such that |S| [[S) in G'
ing.
7:
< min.
3/4 //}
8:
Vi S. y1 + y6 tE
We imagine solving many problem in- stances drawn from the same distribu- 9:
Vj E ((S). yj 4 - Update F², G'
10:
tion. To formally model this, we let D be an unknown distribution over in- stances. For simplicity, we consider the graph G (V, E') to be fixed with vary- ing costs. Thus D is a distribution over cost vectors E RE. We assume that the costs in this distribution are bounded. Let C' := maX m E ce 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 andd []] we know that the "cost" of using dual values y when the optimal dual is y² is bounded by Omm//nlo - ylli), and hence it is natural to define the "cost" of y as I1y 1/|1-
11:
M Maximum cardinality matching in G'
Return M
For every E R we will let y² (c) be a fixed optimal dual solution for c:
(c) == arg max y
Σ va Vij E, + S {.
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 be its -ddistance from the optimal solution:
L(y. c) ly y" (c)]l1.
Our goal is to learn dual values which minimize EE-D c)). Let y denote the vector minimizing this objective, y" arg min, Ee-p(L(y,e))
We will give PAC-style bounds, showing that we only need a small number of samples in order to have good probability of learning an approximately-optimal solution ÿ. Our algorithm is conceptually quite simple: we minimize the empirical loss after an appropriate number of samples. In the supplementary show that this can be done efficiently, giving the following theorem.
2 (nlog n + log(1/p)) samples returns dual values 9 such that E.-DD (( c)] < E.-D|L( LLv", " ,c] + e with probability at least 1 The algorithm runs in time polynomial in n, m and
Theorem 6. There is an algorithm that after = O ( (=²)²
This theorem, together with Theorems and immediately implies Theorem 3
At the heart of the proof of Theorem 6 lies the proof of the following theorem regarding pscudo- dimensions of f--ormm distance functions, which may be of independent interest.
Theorem 7. Let H. = {fy E }R"} where fy 1R - R is defined by fy(x) = lly =||1. The pseudo-dimension H., H.
most O log...
We remark that minimizing this emprical loss can be efficiently implemented by taking the coordinate- wise median of each optimal dual, i.c. taking yj median(z) (2), 23. ..., xz)) for each j e V.
7

---

Dataset
Blog Feedback 10
Covertype
KDD
Skin 9
Shuttle
# of Points (1))
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
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 algo- rithm with learned duals provides an empirical speedup. Next, we show that the sample complexity of learning good duals is small, ensuring that approach is viable in practice. We present some representative experimental results here; additional results are in the Supplementary Material.
Experiment Setup: All of our experiments were run on Google Cloud Platform 22-standard-2 virtual machines with virtual CPU's and 8 GB of memory.
24
We consider two different setups for learning dual variables and evaluating our algorithms.
Batch: In this setup, receive samples C₁ 02,..., Cs 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,, G2.... arrive one at a time. When deciding on the best warm start solution for G, we can use all of the data from Gi.... Gt-1- 1- This standard scenario in industrial applications like ad matching, where daily or hourly.
ad allocation plan may need to be computed
Datasets: To study the effect of the different algorithm parameters, first run study synthetic data. Let n be the number of nodes on one side of the bipartition and let E, y be two parameters we set later. First, we divide the nodes on each side of the graph into É 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 Wa, drawn from geometric distribution with mean 250. Then to generate particular graph instance, we perturb each edge weight with independent random noise according to a binomial distribution, shifted and scaled that it has mean 0 and variance v. We refer to this the type model (each type consists of a group of nodes). We use n = 500, l E (50, 100) and vary u from 0 to 220
We use the following model of generating instances from real data. Let X be and fix parameter k. We first divide X randomly into two sets, X and X and compute a k-means clustering on each partition. To generate an instance = (L R. E). we sample one point from each cluster on each side, generating 2k points in total. The points sampled from XL (resp. Xx) form the vertices in L. (resp. R). The weight of an (i,j) edge the Euclidean distance between these two points. Changing & allows us to control the size of the instance.
of points in Rd,
We several datasets from the UCI Machine Learning repository [16]. See Table | for a summary. For the KDD and Skin datasets we used sub-sample of the original data (sizes given in Table
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 fea- sible 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 to ensure fcasibility (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 Yi +- Y/ + minyeN(s) [Gi y/s yj } 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'. We compare the runtime and number of primal-dual iterations, reporting mean values and error bars denoting 95% confidence intervals. The runtime results are in the supplementary material, and exhibit similar behavior (i.e., the extra rumning time caused by using Algorithm D 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
8

---

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..
Results:
First, we examine the performance of Learned Duals in the batch setting described above. used 20 training instances to learn the initial duals and then tested those
For these experiments, 10 new instances, For the type model, we used & = 50 and considered varying the variance parameter v. The left plot in Figure shows the results as we increase from 300. We see 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 [ we consider increasing the noise variance in powers of two geometrically. 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 summarizes our results for the clustering derived instances on all datasets with k = 500 (similar results hold for other values of k; see the Supplementary Materials). We see an improvement across all datasets, and a greater than 2x improvement on all but the Covertype dataset.
F
Figure 2 has three plots on the online setting. We aim to show that not too many samples needed to learn effective duals. From left to right, the plots in Figure[]shov the performance averaged over 20 repetitions of the experiment with 20 time points the type model with ( = 100, 200, and the clustering derived instances on the KDD and Covertype datasets with = 500, respectively. We that only few iterations needed see significant separation between the run time of method with learned duals and the standard Hungarian method, with further steady improvement as see more instances. Additional plots for the other datasets are in the Supplementary Materials.
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 signifi- cant speed-up. This speed-up 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.
Type Madel tusiic
Type Motea Ercattc
Heticc
Neshod
Leaieed Dusk
Leamen
Tu0m0AA COUFT
02
Nove Veteebo Weight
18
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.
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.

---

Type Modd at Orbe
EDO Oshe Solteg
43.3
U0
323
499
359
2
15
2005 13 SE
Figure 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.
An immediate avenue for future work is to extend these results 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 capture the underlying structure of the problem at hand.
Acknowledgments and Disclosure of Funding
Michael Dinitz was supported in part by NSF grant CCF-1909111. Sungjin Im was supported in part by NSF grants CCF-1617653 and CCF-1844939, Thomas Lavastida and Benjamin Moseley were supported in part by NSF grants CCF-1824303, CCF-1845146 CCF-1733875 and CMMI- 199M999,,909 Benjamin Moseley was additionally supported in part by Google Research Award, an Infor Research Award, and Carnegie Bosch Junior Faculty Chair.
References
[1] Anders Aamand, Piotr Indyk, and Ali Vakilian. (learndd) frequency estimation algorithms under zipfian distribution. arXiv preprint arXiv: 198, 2019.
[2] 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: /tttp://preet http:///poooeeeig....o mlr www.ppresssveeee /vt9// anand20a html
[3] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floring Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Informa- tion Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL htttttss://ppcceeinngeeeeeeeeeee iew.eeeddinnnnuuniiinn neur ips cc/paper/20200 http://///2227784000006666611133 wtw.:e/2eeeet---atttttttt...
[4] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Jennifer G. Dy and Andreas Krause, editors, Proceedings 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, 2018. URL http::/proceediigg mlr. prwss/v80 wwt./////aaaaaa1aame html
[5] 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 20/8, Paris, France, October 7-9, 2018, pages 603 614. IEEE Computer Society, 2018. doi: F0.1009FOCSS.0088 20R.OCCS.208.000 000000 URL lattps://doo http:///oooo.o11/////o org/10. 1109/FOCS. 2018. 80004
[6] 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,
10

---

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, 2018.
[7] 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.02585 2019. URL http:/t/ttaaaat oaraiiii.g/..........oo.oo abs abs/1908. http://99.009944
[8] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal duall 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, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL httpp::///pocceediggggg/////
neurips wttppcpcpppppe/eeteeeee pp0ppe//020////////// 222000222/hh/ /
e834cb114d33f/ #5540116337/9abccc70066667 www.:obbbooo-Abttttt...oe Abstract html
[9] Rajen Bhatt and Abhinav Dhall, Skin segmentation dataset, uci machine learning repository, 2012.
[10] Krisztian Buza. Feedback prediction for blogs. In Myra Spiliopoulou, Lars Schmidt-Thiee and Ruth Janning, editors, Data Analysis, Machine Learning and Knowledge Discovery, pages 145-152 Cham, 2014. Springer International Publishing. ISBN
[11] Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang Learning optimal search algorithms from data. CoRR, abs/1911.01632, 2019. URL http
/ www.ii..rgg/abs///
01632
[12] Edith Cohen, Ofir Geri, and Rasmus Pagh. Composable sketches for functions of frequencies: Beyond the worst case. CoRR, abs/2004.04772. 2020. URL http://aaxxvv...rabbba/ 2004
04772
[13] 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.
[14] Efim A Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, volume I, pages 1277-1280, 1970.
[15] Doratha F. Drake and Stefan Hougardy. A simple approximation algorithm for the weighted matching problem. Inf. Process. Lett., (55(4):211-213 2003, doi: 10.1016/50020-019000)) 00393-9. URL BtLp/htps:///oot http://///ooo.orr1101111111.1111
org 10 101.:10..111110010 1ttp://001006/000000000000013330 (190
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://:://rr ics.uci. uut..ed/mmmmmm
[17] Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. ACM, 61(1):1: 1-1: 23, 2014. doi: 10. 10.1145/2529989, https://:// org/ 10. 2111//552920
[18] Ran Duan and Hsin - Hao Su. A scaling algorithm for maximum weight matching in bipartite graphs. In Yuval Rabani, editor, Proceedings of the Twenty-Thine Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1413-1422 1424. SIAM, 2012. doi: 10. 10. 00.1177719781111199999911111 9781611973099.111
URL https://doii org 1137/1
[19] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. CoRR. abs/201 1. L06726, 2020. URL http::://aaxiv..rggg/e/e//// wwtp////////......////////
[20] 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: 1981199/FFCS.198533 URL https
//doi org 10..0000020 1109 /SC9//FFSS... 1985.3

---

[21] Andrew V. Goldberg and Robert Kennedy. Global price updates help. SIAM J. Discret. Math., 10(4):551-572. 1997. doi: 10.1137750895488114288888888 httpe httpsss/:////iioooo htt:://oo...rgg////// 1137/ S0895480194281188
[22] Jacck 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 http:://doi..orrg///// 1007/BF02680535
[23] Jacek Gondzio and Pablo González-Brevis. A new warmstarting strategy for the primal- dual column generation method. Math. Program.. 152(1-2):113-144,, 2015. doi: 10.1007/
s10107-014-0779-3
[24] Google Cloud Platform. https:///cloud.goog// com/
[25] Rishi Gupta and Tim Roughgarden. PAC approach to application--specffcc algorithm selection. SIAM J. Comput., 46(3);992-1017, 2017.
doi: 10.1137/15M1050076. URL https://doi
org/10. 20. 11...1137/5MM1050270
[26] John E. Hoperoft and Richard M. Karp. An n -algoorgo for maximum matchings in bipartite
graphs. SIAM Journal on Computing, 2(4):225-231, 1973. doi: 10.1137/0202019. URL
https://doi /ttp::///oi.org/1.... 1137/0202019
[27] John E Hopcroft and Richard M Karp. An n55/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal computing, 2(4))225-231, 1973.
[28] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference Learning Representations, 2019.
[29]
Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th Interna- tional Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8- 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 L/Plcs, pages 69: 1-:1:19911 18. Schloss Dagstuhl Leibniz-Zentrun für Informatik, 2020. doi: 1044330LIPIs..CAAPP220000. https: //doi. org/ 10. 4230/LIPIcs. ICALP 2020.69
URL
[30] Alexander V Karzanov. On finding maximum flows in networks with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom, 5:81-94, 1973.
[31] Tim Kraska, Alex Beutel, Ed 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
[32] 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 Discrete Algorithms,, SODA 2020, Salt Lake City, UT, USA, January 5-8. 2020, pages 1859-1877. SIAM, 2020. doi: 10.1137/1 00.13377.97811111999944444 URL https://doi.. org 1111111111111 11111111977111119755590909 114
[33] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned ad- vice. In Proceedings of the 35th International Conference on Machine Learning. JCML 2018, Stockholmsmässann Stockholm, Sweden, July 10-15, 2018, pages 3302-3311, 2018
[34] Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007. doi: 10. 1 10.1145/124322.122... https://doi.orge org/10. 0114////14222 1284321
URL
[35] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching, In Advances in Neural Information Processing Systems, pages 464-473, 2018.
[36] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. CoRR, abs/2006.09123, 2020. URL htttps://aattti org/
vrg/aba abs/ 2006. 2006.09123
12

---

[37] Vinod Nair, Dj Dvijotham, lain Dunning, and Oriol Vinyals. Learning fast optimizers for contextual stochastic integer programs. In Amir Globerson and Ricardo Silva, editors, Pro- ceedings of the Fhirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 591-600 AUAI Press, 2018. URL http:// attp://auali /ww..
pttaa//ee//ooooeiigggsssssso http://edddnnnnapppsse/eeeeeeeee pdd.
[38] 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. 18000///0001 URL
https://doi.coe 10. 1007 100.11007/BF1110 /B001566400
[39] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018.
[40] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Symposium on Discrete Algorithms (SODA), 2020.
[41] Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.
[42] Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. Partitioned Iearned bloom filter. CoRR, abs/2006.03116, 2020. URL http:: wrgg/bs///////aoo/
[43] 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 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919-930. IEEE, 2020.
[44] Jan van den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and e--regessioon in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 859-869, 2021.
[45] Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaran. 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.
[46] Hiroshi Yamashita and Takahito Tanabe. A primal-dual exterior point method for nonlinear optimization. SIAM Journal on Optimization, 2335)333,,,3363, 2010. doi: 10. 11.11 17766667666777
httthttts://dde org/ 10. 1137/0606769)
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
focuses the efficiency of classic combinatorial optimization problem.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi-
ments multiple times)? [Yes]
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "oLSjnv8tWV7", "reviewer": "Reviewer_RBoF", "summary": "In this paper the authors propose a learning algorithm for accelerating solving of bipartite minimum weight perfect matching problems, which are combinatorial optimization problems that can be solved in polynomial time. These problems can be represented as linear programs, and they propose to learn the initial point to the dual problem, which, when feasible, can be fed to the Hungarian algorithm to kick-start the optimization process. Given a collection of training and testing instances, they propose to solve the training instance to obtain their optimal dual solutions and take their median as a learned initial dual point. Given a new test instance, they propose to take this training median as initial point, make it feasible for the test instance using a greedy heuristic, and solve the test instance using the Hungarian algorithm initialized with this feasible dual point. They compute (Theorem 1) the sample and time complexity of the algorithm, and show empirical improvements on two distribution of problems compared to a vanilla Hungarian algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the basic content of the paper is okay. In terms of philosophy, the paper is initially presented as being very general: their goal is to speed up primal-dual algorithms by learning initial dual values, and they present their work as being an initial step in that direction. The larger class of problems they want to help improve is not very clear, but I assume they would be convex problems that are commonly solved using interior point methods?\n\nI think the goal is fine (this is certainly a way among many others machine learning could be helpful in improving mathematical optimization), but I don't really know if there is a way to generalize so easily the results of the paper towards that goal: mostly, their solution to the first problem (feasibility) seems very specific to the problem at hand, and I wonder whether it would be possible at all to design reasonable, and fast, heuristics for arbitrary convex problems. That is, I feel their challenge 1 (Feasibility) would be quite difficult, and that it is really not clear whether it can be solved in general. (I'd be happy to hear if the authors have any ideas in this direction, however.)\n\nDisregarding the way the paper is sold, and focusing on the content, I think the paper makes a sensible contribution. The theory is the main contribution here (Theorem 3). Considering how NeurIPS is a machine learning conference, here is something a bit primitive about using the median of the dual solutions as initial point, instead of having, say a real machine learning model trained on the dual solutions, with features characterizing the weights, that would be used at test time. But I suppose this would make the theory harder, and since this is, as far as I know, the first work of this kind, this is not a strong objection.\n\nIn terms of experiments, I find the \"instance generation from real instances\" somewhat bizarre. I feel the authors tried to have graphs coming somehow from real data, but the procedure seems to be completely artificial. It would have been substantially better to have real graphs from real problems (for example, the ad allocation applications that are mentioned in Section 1.2.) Right now the problems seem to me still synthetic. I can't really say they have demonstrated empirical gains on the kinds of instances that one would actually encounter in real life. The size of the training and test sets are also seem quite small: 20 and 10 instances. But overall, I don't think these criticisms are enough to make me reject the paper.\n\nIn terms of structure, I thought the paper was clear, if perhaps a bit repetitive with the informal/formal duplication. I think the fact that they use the median of the dual points was quite buried in the text, and it should have been much more clear: as a machine learning reader, my first instinct was so ask, if you a learning to predict an initial dual point, what is the model and what are the features? This should have been in the abstract and the introduction but it was quite hidden as almost unimportant. I would like to see this improved if possible.\n\nOverall, my recommendation would be acceptance of the paper.\n\n---\nEdit after rebuttal\n\nThank you for your interesting answers to my questions. I think you made good points regarding near-optimality of the median that I had not thought about during my review. I increased my score to \"Accept\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The approach is developed for a specific problem (bipartite minimum weight perfect matching), which is used in ad allocation. The authors make this clear. The lack of experiments on very large graphs makes it difficult to know how the gains would scale up, although I would expect at least some gains on larger graphs. I am not concerned about adverse negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NMnc0MPD-e6", "reviewer": "Reviewer_pG4Y", "summary": "any combinatorial optimization problems may be solved or approximated with primal-dual algorithms built on a linear programming relaxation of the problem. These algorithms maintain an infeasible primal solution that is driven towards feasibility and a (matching) feasible dual solution that is driven towards optimality. The algorithm terminates once the primal solution becomes feasible and uses the feasible dual as a quality guarantee in the analysis.\n\nThe aim of the submission is to improve the running time of one particular primal-dual algorithm -- the Hungarian method for weighted bipartite matchings -- by using machine learning. The goal is to augment the algorithm with learned predictions that improve the (theoretical and empircal) running time if good, and that fall back to the theoretical worst-case otherwise.\n\nInstead of trying to predict a primal solution (something the literature has determined to be difficult for bipartite matchings), the authors propose to predict a dual solution that is already driven some way towards optimality and to use that solution to \"warm-start\" the algorithm. The difficulty here is that the prediction might not be a feasible dual solution (and thus useless for the Hungarian method). The authors fix this issue by providing a (linear time) procedure that turns an infeasible predicted dual into a feasible dual while increasing the distance to the optimum dual by at most a factor of 3. Finally, the authors prove that duals can be learned approximately from O~(C^2n^3) samples if the matching instances are drawn from a fixed, but unknown distribution (C being the maximum weight of any edge). \n\nTo argue that the learning provides an empirical improvement, the authors compare their warm-started method against the classical Hungarian method. The results convinced me that the warm-started method works well.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and well structured. The contribution extends an interesting line of theoretical research that works along similar lines and I would be happy to see develop a field here that systematically works through classical algorithms. This contribution would make good first steps. The research is certainly original and I find the goal of having a practical algorithm is achieved here; the implementation overhead to include learned duals seems minimal. \n\nIf we care deeply about practicability, there could be alternatives to the Hungarian method: Weighted bipartite matchings may be solved as minimum cost flow problems for which we have efficient implementations: \n- the double scaling algorithm runs in O(nm log nC) and matches the theoretical worst-case running time of the Hungarian method\n- the push relabel method is another primal-dual algorithm that is known to perform very well in practice (but is slower in theory)\n- the network simplex algorithm has no comparable guarantees but is known to perform very quickly in practice. \n\nWhile the authors discuss more efficient algorithms for bipartite matchings (and convincingly dismiss them as impractical), this alternative is not discussed.\n\nHowever, from a theoretical point of view, studying the Hungarian method makes a lot of sense to me, and it is not clear if minimum cost flows would be a faster alternative in a practical setting. I would therefore see this as a minor concern.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "If practicability is a big concern, a comparison with min-cost flow algorithms would add value to the contribution.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DMNqwA9trs", "reviewer": "Reviewer_9XRM", "summary": "The paper gives a learning-augmented algorithm to improve the running time for the minimum weight perfect matching (MWPM) problem in bipartite graphs. For a given bipartite graph, they consider the setting that the vector of (integral) edge weights is sampled from a probability distribution. For any given (unknown) distribution, they show that\n- one can efficiently learn dual variables that minimize the expected l1-distance to the optimal dual variables for a random instance sampled from the given distribution\n- these learned dual variables can be efficiently turned into a *feasible* dual solution for the given instance at the expense of increasing the aforementioned l1-distance by a factor at most 3.\n- using this feasible dual solution to warm-start the known Hungarian method algorithm to solve MWPM, the running time improves from O(mn) to O(min{mn,m\\sqrt{n}alpha}), where alpha is the aforementioned minimal expected l1-distance for the given distribution.\n\nAdditionally, they provide an extensive experimental evaluation confirming an improved running time when the input distribution is sufficiently concentrated, and a running time comparable to the classical Hungarian method algorithm when the distribution is not concentrated. On instances generated from real-world data, the observed running time improvement was of the order of roughly a factor 2.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The most interesting aspect of this paper is that in contrast to most work in the field of learning-augmented algorithms, which uses predictions to improve the competitive ratio, this paper uses predictions to improve the running time instead. A theoretical improvement over the Hungarian method is obtained provided that the input distribution is such that the minimal l1-distance alpha of the best \"average\" dual solution to the actual dual optimum is less than sqrt{n}. As pointed out in the paper, there also exist other algorithms for MWPM than the Hungarian method, and those algorithms achieve a running time of O(m\\sqrt{n}*log(nC)), where C is the maximal edge weight. A theoretical improvement over these algorithms is achieved provided that alpha is less than log(nC). The experiments do not include these latter algorithms, but the authors argue that the Hungarian method is the standard algorithm in practice and easy to implement.\n\nIn terms of techniques, the proofs seem relatively simple, but this does not diminish the value of the paper. In particular, I find it interesting and appealing that the learnt part are dual variables. There is a good chance that the methods of this paper extend to additional problems.\n\nA potential area of improvement is to complement the argument from line 77 about the primal solution being brittle (and therefore not useful for predictions) by an argument that the dual solution is less brittle. In other words, some kind of justification that the quantity alpha in Theorem 1 is small if the input distribution is sufficiently concentrated. Otherwise it is not clear in what settings the output of your learning algorithm is useful.\n\nThe paper is well-written and easy to understand. In my opinion, it is a significant contribution to the young field of learning-augmented algorithms, and I recommend acceptance.\n\nMinor comments:\n- Line 32: Antoniadis et al [3] is not about the secretary problem, but about caching and the more general MTS problem.\n- Line 234: A letter has a funny color.\n- Line 236-239: Where/What is the reference (3)?\n- Algorithm 2: I do not think you defined the notation L and R used here (I understand it is the left/right half of the bipartite graph)\n- Line 307: minimizes -> minimize\n- Line 319: by -> is defined by", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are adequately addressed. There is no discussion of potential negative societal impacts, but I also do not think that there are any relevant negative impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2bwRvt0bQaC", "reviewer": "Reviewer_gyoj", "summary": "The paper proposed a learning-augmented algorithm that receives a learned dual solution and uses it as a warm-start to improve upon the running time of the Hungarian method for weighted bipartite matching. The paper provides a neat 3-stage approach for obtaining “faster” algorithms for matching problem: 1) Learn a helpful dual solution for a given instance, 2) Convert a given predicted dual solution to a feasible dual solution, and 3) Lastly, get a near-optimal solution starting from the feasible “warm-start” solution. The paper provides an end-to-end algorithm for this problem using the described approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Putting all pieces together, the paper gives $\\tilde{O}(m \\sqrt{n} \\cdot \\min{\\alpha, \\sqrt{n}})$ where $\\alpha = \\min_y \\mathbb{E}_{c~D} [||y  – y^*(c)||_1]$ where $D$ is the distribution over the inputs of interest, $c$ is the weight vector of the edges in the underlying graph and $y^*(c)$ is the optimal dual solution of matching w.r.t. edge weights $c$. In particular, if the prediction vector (i.e., $y$) is close enough to the actual dual values, the algorithm shaves a factor of $\\sqrt{n}$ from the running time of the Hungarian method. \nWhile the algorithm provides an improvement over the Hungarian method if the predictions are good, it is not clear how it compares to the fastest known algorithm for weighted bipartite matching. Though, given the simplicity and applicability of the Hungarian method the result is still of interest. \n \nComments: \n1.\tTheorem 3 does not provide the running time for learning $\\hat{y}$\n2.\tProof of Theorem 19 (in appendix) is hard to follow. Line 452: $2^d$ or $2^n$? Line 453: y_i or x_i? Why is it clear that the number of hyperplane is $O(kn)$?\n3.\tParagraph starting at line 346 in the experiment. The description is a bit unclear. What is $(i,j)$?\n4.\tWhile the results are believable the proofs get informal throughout the paper. It would be beneficial if authors work further on the presentation of the technical part of the paper (specifically section 3.3.1).\n5.\tFix all instance of double quotation. For example, “warm-start” in the abstract and line 42, “solution” in line 42\nOverall, the paper provides an interesting approach in the design of algorithms with prediction. To best of my knowledge it is the first time these techniques have been used to improve the running time. However, it is not clear if the paper is comparable with the state of the art and its presentation is not the best possible. Overall, I recommend weak-accept.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an efficient learning-augmented algorithm for min cost matchings in bipartite graphs, by utilizing predictions of dual solutions. Both in theory and in experiments, the efficiency of the proposed algorithm (essentially the Hungarian algorithm with a "learned" warm-start) depends on the quality of predictions. When the predictions are "good", the algorithm is (significantly) more efficient than the baseline algorithm that does not use any predictions. 

The reviewers appreciated several aspects of this paper, such as (i) the wide applicability of the Hungarian algorithm (ii) the generality of the proposed framework, (iii) the elegance of the solution and (iv)  the novelty of using predictions to improve the runtime as opposed to, say, the competitive ratio .  There were some concerns whether the Hungarian algorithm is an appropriate baseline, and whether the predictors are too simple, but they were deemed minor or were resolved during the rebuttal phase. 
Decision: Accept (Oral)