We consider the question of speeding up classic graph algorithms with machinelearned predictions. In this model, algorithms are furnished with extra advice learned from past or similar instances. Given the additional information, we aim to improve upon the traditional worstcase runtime guarantees. Our contributions are the following: (i) We give a faster algorithm for minimumweight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the singlesource shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J. Comput., 1995); (iii) We provide a general reductionbased framework for learningbased graph algorithms, leading to new algorithms for degreeconstrained subgraph and minimumcost 01 flow, based on reductions to bipartite matching and the shortest path problem. Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion
Faster Matchings via Learned Duals
A recent line of research investigates how algorithms can be augmented with machinelearned 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 machinelearned predictions with the idea of "warmstarting" primaldual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to bmatching. We identify three key challenges when using learned dual variables in a primaldual 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, more »
 Award ID(s):
 1909111
 Publication Date:
 NSFPAR ID:
 10341916
 Journal Name:
 Advances in neural information processing systems
 Volume:
 34
 Issue:
 `
 Page Range or eLocationID:
 10393  10406
 ISSN:
 10495258
 Sponsoring Org:
 National Science Foundation
More Like this


We present an $\tilde O(m+n^{1.5})$time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negativeweight shortest paths, and optimal transport) on $m$edge, $n$node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$time [Dinic 1970; HopcroftKarp 1971; Karzanov 1973] and $\tilde O(n^\omega)$time algorithms [IbarraMoran 1981] (where currently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + \delta}$ for any constant $\delta>0$, our result improves upon the recent advances of [Madry 2013] and [LiuSidford 2020b, 2020a] which achieve an $\tilde O(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.BrandLeeSidfordSong 2020], providing a general primaldual IPM framework and new samplingbased techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublineartime algorithm for detecting and sampling highenergy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates ofmore »

We propose a sequential algorithm for learning sparse radial basis approximations for streaming data. The initial phase of the algorithm formulates the RBF training as a convex optimization problem with an objective function on the expansion weights while the data fitting problem imposed only as an ℓ∞norm constraint. Each new data point observed is tested for feasibility, i.e., whether the data fitting constraint is satisfied. If so, that point is discarded and no model update is required. If it is infeasible, a new basic variable is added to the linear program. The result is a primal infeasibledual feasible solution. The dual simplex algorithm is applied to determine a new optimal solution. A large fraction of the streaming data points does not require updates to the RBF model since they are similar enough to previously observed data and satisfy the data fitting constraints. The structure of the simplex algorithm makes the update to the solution particularly efficient given the inverse of the new basis matrix is easily computed from the old inverse. The second phase of the algorithm involves a nonconvex refinement of the convex problem. Given the sparse nature of the LP solution, the computational expense of the nonconvex algorithmmore »

The problem of learning to generalize on unseen classes during the training step, also known as fewshot classification, has attracted considerable attention. Initialization based methods, such as the gradientbased model agnostic metalearning (MAML) [1], tackle the fewshot learning problem by “learning to finetune”. The goal of these approaches is to learn proper model initialization so that the classifiers for new classes can be learned from a few labeled examples with a small number of gradient update steps. Few shot metalearning is wellknown with its fastadapted capability and accuracy generalization onto unseen tasks [2]. Learning fairly with unbiased outcomes is another significant hallmark of human intelligence, which is rarely touched in fewshot metalearning. In this work, we propose a novel PrimalDual Fair Metalearning framework, namely PDFM, which learns to train fair machine learning models using only a few examples based on data from related tasks. The key idea is to learn a good initialization of a fair model’s primal and dual parameters so that it can adapt to a new fair learning task via a few gradient update steps. Instead of manually tuning the dual parameters as hyperparameters via a grid search, PDFM optimizes the initialization of the primal and dualmore »

We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))time algorithm that returns a (1+epsilon)approximate estimate of the MST cost. This result immediately implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problemmore »