Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
Authors: Shinsaku Sakaue
Taihei Oki
Venue: NeurIPS 2022 Accept (2022)
Keywords: combinatorial optimization
discrete convex analysis
algorithms with predictions
time complexity

Abstract: Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and Vassilvitskii~(2021) have demonstrated that warm-starts with learned dual solutions can improve the time complexity of the Hungarian method for weighted perfect bipartite matching. We extend and improve their framework in a principled manner via \textit{discrete convex analysis} (DCA), a discrete analog of convex analysis. We show the usefulness of our DCA-based framework by applying it to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization for computer vision. Our DCA-based framework yields time complexity bounds that depend on the $\ell_\infty$-distance from a predicted solution to an optimal solution, which has two advantages relative to the previous $\ell_1$-distance-dependent bounds: time complexity bounds are smaller, and learning of predictions is more sample efficient. We also discuss whether to learn primal or dual solutions from the DCA perspective.

Discrete-Convex--nalyii---eae Framework for Warm-Starting Algorithms with Predictions
Shinsaku Sakaue The University of Tokyo
Taihei Oki The University of Tokyo Tokyo, Japan
Tokyo, Japan sakaue@mist. w.w.tokyo...cc....
oki @mist...........mm.. i. .uutooyo....
Abstract
Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and Vassilvitskii (2021) have demonstrated that warm-starts with learned dual solutions can improve the time complexity of the Hungarian method for weighted perfect bipartite matching. We extend and improve their framework in principled manner via discrete conver analysis (DCA), discrete analog of convex analysis. We show the usefulness of our DCA-based framework by applying it to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization for computer vision. Our DCA-based framework yields time complexity bounds that depend on the foc -distance from predicted solution to an optimal solution, which has two advantages relative to the previous é (--distancedependeer bounds: time complexity bounds are smaller, and learning of predictions is more sample efficient. We also discuss whether to learn primal dual solutions from the DCA perspective.
Introduction
Discrete optimization algorithms applied to many real-world instances that take place repetitively. For example, recommendation systems repeat to solve bipartite matching instances to match users with services, and solve series of pixel-labeling instances to process images of movie. Since such instances arising in the same domain often have some tendencies, using predictions made from past instances improve algorithms' performance is natural and promising idea. A recent line of work [36, 41, 4, 34, 43, 2, 5] successfully combined online algorithms with predictions and showed that those algorithms perform provably better than known worst-case bounds if predictions good while enjoying worst-case guarantees even if predictions are poor. See [37] for a survey.
Dinitz et al. [17] recently initiated the study of improving the time complexity of algorithms with pre- dictions. They focused on carm-starting the well-known Hungarian method for the weighted perfect bipartite matching problem with predictions mn)) }), where n and m are the number of vertices and edges, respectively, optimal dual solution p" R". That is, while the Hungarian method
dual solutions, and obtained the time complexity of
O fmin/mm//lp and I is prediction takes (mm) time in the worst case, it can run faster given good prediction. Dinitz et al. [17] also presented an algorithm for converting infeasible learned dual solutions into initial feasible solutions, and proved an (z log n) sample complexity bound for learning á that approximately minimizes the expected & -eroor Elip- ||,, assuming optimal prediction is contained in [-C, +CJ". They thus established an end-to-end framework for warm-starting the Hungarian method with predictions.
While Dinitz et al. [17] has shown that their inddicttionbbaeld warm-start framework is effective for bipartite matching and b-matching, its application to other problems remains to be studied. Since their idea has the potential to yield strong beyond-the howanddd-h-wwoo-casss time complexity bounds, the next question theoretical interest is: when and how can we warm-start algorithms with predictions?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table Our results for weighted perfect bipartite matching (BM) on bipartite graphs with n vertices and at most m edges, weighted matroid intersection (MI) on pairs of rank-r matroids on an identical ground set of size n (r the running time of independence oracles), and discrete energy minimization on graphs with vertices and at most m edges.
Problem
Local optimization problem
Time complexity
Prediction
Weighted perfect BM Weighted MI
Maximum cardinality BM
Om po100)
Dual
Maximum cardinality MI
O Ornrl131/p -0100)
Dual
Discrete energy min.
Minimum cut
O(mn?lpp" oo1
Primal
Our contribution is to extend and improve the framework of [17] in principled manner. Our idea comes from an intuition that the time com- plexity bound of [17] seems to be originating from some geometric property of the Hungar- ian method. In continuous optimization, warm- starting the gradient descent method reduces its by simple geo-
aramin
arganin
Warm stalt
Warm
running time, which metric reasoning (see Figure la). We formalize this idea for discrete optimization via discrete convex analysis (DCA) by Murota [38], which a discrete analog of convex analysis [42] and offers a gradient-descent-in various discrete optimization algorithms, Figure 1b. Based on DCA, we show that warm- starting with predictions is effective for a large class of problems called I/L -cnvvex minimization.
(a) Continuous
(b) Discrete
Figure I: Images of warm-starts in (a) continuous and (b) discrete optimization, where darker colors indicate smaller objective values.
interpretation of in
As with the framework of [17], given a prediction P an optimal solution p", we convert ý into an initial feasible solution pº. Then, starting from p², we iteratively solve a local optimization problem to find a direction, along which we proceed. We will see that the number of iterations is O(Ilp* - -0))>>)) so) (see Figure 1b for an image). Thus, a local optimization solver runs in Toc time, the total time complexity is OTTocllp" Toc. Table summarizes the results obtained by applying our DCA-based framework to specific problems, where Tioe is replaced with the running time of standard local optimization solvers. As for bipartite matching, our bound is up to n times smaller than the Omm///ll p² l| bound of [17].'
oo) plus the time of converting P into pº, which is often shorter than
We then provide an O sample complexity bound for learning predictions that approximately minimize the expected foc -rror, Bllp" - olloo assuming an optimal prediction to be in I-C.+ Our bound is better than the previous O log n) bound of [17] for approximately minimizing the expected -error. Our method for learning predictions is based on a recent online-learning framework by Khodak al. [31], and we also obtain an OCCvnT) regret bound for the online setting.
We finally discuss whether to learn primal or dual solutions, which depends on problems as in Table I and has been decided in a somewhat ad-hoc manner literature. We provide guideline for choosing primal or dual from the DCA perspective by considering path connectivity of feasible regions.
1.1 Related work
Theoretically fast algorithms. We overview existing theoretically fast algorithms. We emphasize that, as with [17], our motivation accelerate simple algorithms, not to develop theoretically fast algorithms, which are often difficult to implement and empirically slow due to hidden large constants. For maximum cardinality bipartite matching, the standard Hoperoft-Kary algorithm [26] runs in (mmyn) time, and recent fast algorithm [47] takes 0(m + n 1-5) time (up to logarithmic factors). For weighted bipartite matching with nog-negative integer weights bounded by W, a scaling-ty type algorithm [18] runs in O(m// log(1) W)) time. Morcover, a recent almost-lineaa lincar-tinmee max/min-cost
Unlike [17]. our framework cannot yield worst-case bounds in general, which is a limitation of our work. This, however, does not matter in practice if can standard algorithms in parallel, discussed in Section 6.

---

flow algorithm [14] implies an O(m O(m²+(())
1+((1) log" W) W algorithm for weighted bipartite matching. For maximum cardinality matroid intersection, standard algorithm is Cunningham's ((Turl-5-timm) algorithm [15], and a recent faster algorithm [12] runs in O(rnr logr) time. For weighted matroid intersection, there an O ( algorithm [9]. Moreover, the maximum weight bounded by W, there are O(Tn² log (n W) )-ime [35] and O(rnr1
[27] algorithms. For discrete energy minimization, there is an (mn log(n"/ /m) (ng(n))))tim)) algorithm [l], where W is the number of possible vertex labels. For a particular case where smoothness of vertex labels is measured by linear deviation functions, there is an algorithm that takes almost the same time to solve a min-cut instance [25]; combined with the algorithm of [14), runs in O(m ++((2) log W) time.
Algorithms with predictions. Many recent studies [36, 41, 4. 34, 43, 2, 5] improved competitive ratios of online algorithms with predictions. Dinitz et al. [17] proposed to warm- start algorithms with predictions. Khodak al. [31] developed an online-learning framework for learning predictions, and applied it to the feeerrrr minimization setting of [17] to obtain O(CnVT) regret and O(C?n²) sample complexity bounds. By contrast, we learn predictions to minimize the 2 yielding better guarantees. Data-driver algorithm design [3] closely related to algorithms with predictions. As discussed in [31], one distinction is that the former aims to tune algorithm parameters to optimize the expected performance, while the latter focuses on prediction-dependee
bounds to quantify the improvement gained by using predictions. A very recent study [13] also extended and improved [17], which should be considered as independent of each other and employs different approach from ours.
2 Preliminaries
Let 1-1 denote the rounding to the nearest integer (0.5 is rounded down). We apply I:J. [-], and [-1 to vectors in an element wise manner. We use V= = ...,,....u n) to denote a finite ground set of size n E N. For any X C V. 1x E {0, 13 denotes an indicator vector whose entries corresponding to X are one and the others are zero; let 1 lv. Let and A denote the element-wise maximum and minimum operators, respectively. For any S C ZV, let conv(S) C RVV denote the convex hull of S.
Given any function g : ZV + RU {+oo}, let dom g = {p E ZV g(p) < +00 } be its effective domain, which indicates the feasible region of a minimization problem of form minpezyv g(p). We say is proper if dom + 0. In this paper, we assume the following basic conditions to hold.
Assumption 1. We assume that any objective function Z - R U (+x} is proper and has at least one minimizer. Moreover, given any 9, we uniquely associate p" (g) E argmin g(p) with g by breaking ties with an arbitrary predefined rule (to deal with the case of multiple minimizers).
2.1 Background on discrete convex analysis
We overview the basics of discrete convex analysis. We refer the reader to [38] for more information.
Considering functions on zV, how to define convexity is already nontrivial. A well-known property
of continuous convex function f is midpoint convexity, i.e., f(x)+(()) S (t22 ), and its natural
2 discrete analog for a function g : zV + IR U {+oc} would be g(p) + g(4) 2 g 2 ) + a( 2
for all p. 9 E zV. This condition is indeed equivalent to the following L convexityy of Definition 1. A proper function g: Z + R U { + is L-comvex if it has the following properties.
Submodularity: g(p) + g(g) 2 g(p v q) + g(p A q) for all p,q E ZV.
Linearity in the direction of 1: there exists r E R such that g(p + 1) = =g(g) + for all E ZY.
A proper function g ZV - R [0o} is Li-convex if function g: Z x ZV + RRUUU {+0 defined by ((po.P) p) = -(p Po1) for all Pa E Z and p E ZV is I--conve.
While L c--coovex functions form a wider class than L-convex functions, the two classes are essentially equivalent due to the one-to-one correspondence between L'- co-coveex functions on ZV and L-convex functions on E ZV. Thus, we can choose whichever is more convenient for modeling problems. Note that the sum of two coovvxx functions, 91 and g2, is L/L -convex if it is proper.
3

---

Algorithm| Steepest descent method for L--covvx (l---covex) function minimization D pe is an initial feasible solution.
1: p < p" E dom 9
2: while not converged:
3: d + argminn d') EN+}
> Replace N with W if g is L'-convex.
4:
if g( + d) = g(p):
5:
return p
6:
A - sup X' E E g(p + Xd) g(p) X(g( -g(p)) Alteraaively, A 1.
7:
+ p Xd
We say a non-emply set S _ ZV is LLLLLLcoovver its indicator function 63 is LLo'vxx where (p( = Of p E S and +00 otherwise. If g z - R U (+x) is L/I.'-covvex, then domg g E ZV is an Loovec set. The next proposition provides useful representations of L/L''convex sets. Proposition 1. A non-empty set S C 3 ZU ( and Jij E Z U (+o0) (i.j E Vi /i j) such that
z is L'-convex if and only if there exist a; E E (-
= fp ZV a, S p. S Br, Pj - P: S "ha for forijje serijeVV; V; and is L-convex if and only S is written as above without the box constraints O; S ps S B: E
Therefore, the colored area in Figure 1b illustrates an example of L--convex sets in Z2, We can also represent cSnv(5) S RV above by replacing ZV with IR V (see [38, Section 5.5]). L/o_vxoovex sets also have the following useful property, which we prove in Appendix A.
Lemma 1. Let S C zV be an L/Li-convex set and p E conv(S). Then, it holds [p] S.
2.2 Steepest descent method for L/L' -convex function minimization
An essential property of continuous convex functions is that the local optimality implies the global optimality, which enables the gradient descent method to reach a global optimum. L- and I. l---conexitty inherits this property with respect to neighborhood N4+ {00, +1} and N {0, -1 uuo, +1)" respectively. i.c., for any L-convex (L' (L'-convex) function g Z +
R U [+oo} and p E z it holds g(p) S g + d) for every d E N_ (d E N1).
p argmin ( ((g) e }
=
This fact underpins the convergence of a steepest descent method (Algorithm 1) to a global minimum of any -coovex function g z - IR U {+oo], as stated in Proposition presented below.
Algorithm 1 is very simple: starting from an initial point pd E dom g. it finds a steepest direction by solving a local optimization problem (Step 3), sets the step length X, and updates the solution (Algorithm 1 is long-step version [24, 46), and we can also let X = 1 in Step 6). The algorithm terminates if Step 3 does not improve the objective value. The local optimization problem in Step can be written as m f(X)= = g(p+ 1x) (or g(p+1x) if g is I.--convex). From L/Ix--covvxxty of g, one can confirm that 2 - IR U {+x) a submodular function, which can be minimized in polynomial time in general, and more efficient local optimization solvers are available for many specific problems. Algorithm thus provides an efficient way to minimize L/L_2-covvex functions.
The number of iterations of Algorithm 1 is known to be bounded by the distance between initial point and a global optimal solution. To describe this claim precisely, for any p E RV we define || I
||p| where || max max +p,} and ||p| max max(0, -px)- iev
Note that ||p| S I1 < 2||pl holds, i.e.,
||p| = @(pllls)). Moreover, || satisfies the axioms of norms, and hence sometimes refer to it the E -norm.
Proposition 2 ([39, Theorem 1.2] and [24, Theorem 6.2]). Algorithm returns a global optimal solution to millpay (()) in at most (lp"(a) 1 + 1 O(IIp" -1ll)-pp1l loc)) iterations.
Note that Proposition 2 holds regardless of L/L and the choice of X in Step 6. The original results shown in [39, 24) provide stronger bounds on the number of iterations by using global optimal solution p" with the smallest ||p" (g) y" l value, and we obtain Proposition 2 by replacing p" with an optimal solution p" (g) that is uniquely associated with g by Assumption I; we do this get simple convex loss functions with which we can learn predictions (see Section 4).

---

3 DCA-based framework and its applications
We present our general DCA-based framework for L/L L/L'-co minimization. Our basic idea is to warm-start Algorithm 1 with predictions and bound the number of iterations by using Proposition 2. Algorithm has two parts that take considerable time: obtaining an initial feasible solution in Step 1 and solving local optimization problem in Step For now, we suppose that oracles for the two steps are available and present our main theorem, which, together with learning guarantees in Section 4, formalizes our DCA-based framework.
Theorem 1. Let : ZV R U {+oo} be an L/L'-convex function. If. for any 9 RY, we can compute an t projection P(g) E argmin |pp qllaz p E conv(dom g) } in Pxi time and we can solve local optimization problem in Step 3 in Too time, the following guarantees hold.
1. Given a possibly infeasible prediction P E RR, we can obtain an initial feasible solution pe [P()]] E domg g in O[Tp) + [V]) time.
2. Given the initial feasible solution p² = [P()]], Algorithm I computes an optimal solution to minpezy g(p) in ( (Ip" )o))o) time.
Proof. Regarding the first claim, the time complexity follows from the Tpy--tmme projection and the O(IVi)-time rounding, and [P()]] E dom g follows from P(p) E conv(dom g) and Lemma 1. We below prove the second claim. Proposition 2 implies that we can compute an optimal solution in
(ll"" (g) - pd I1 + 1) time. We further bound IIp" pp -1 as follows. Since the rounding p S Ipp (g)
changes each entry up to +1/2. ||p"
P(p) + 1 holds. Furthermore, g) 1lp - pl and p (g) E ccnv g)
the triangle inequality of |1-11 P(p) E argmin
imply [|p" (g) p < [g) - - + IP()) D I 2||p" (g) ~ S 41) - pllx..
Thus, the time complexity is ( Ilp - plloo), as desired.
That is, given a prediction ş E RRV, we can solve minpezy g(p) in + (p) ( time. We below discuss how large Trj and Tio can be for bipartite matching, matroid intersection, and discrete energy minimization; we also mention general L L'-convex function minimization. In all the cases, it turns out Tprj + IV| < Thoc implying the total time complexity of O(Tice (Ipl(() xol Thus, replacing Toc with those of standard local optimization solvers, we obtain the results in Table 1.
3.1 Weighted perfect bipartite matching
We consider the weighted perfect bipartite matching problem studied in [17]. Let G (V. E) be a bipartite graph with bipartition V L R. [T.] RR] n2/2 (where n is even), and E S m. Let w E _ be edge weights. We assume that V is fixed and G' has at least one perfect matching (which we can check by solving the maximum cardinality bipartite matching problem once). Under this condition, we allow both and E to change over instances generated randomly or adversarially, as described in Section 4; this slightly extends the setting of [17], which fixes E.2 The dual problem of the maximum weight perfect bipartite matching problem on G is given as follows:?
minimize DERL,EEEE
Σ s: VEL.
Σt, ty JER
subject to s - t, 2 Wiy
v(i.j) E E.
(1)
We below use p (s, E こ x =z==z²_ to denote the dual variables. The objective function is linear (L-convex), and the inequalities defining the feasible region can be written as in Proposition 1, whose indicator function is L-convex. Thus, if we let zV + R U {+o0] be the sum of these two functions, we can write (1) as an L-convex function minimization problem of form minpezy g(p).
Projection. Given a prediction ş = (8, E R x IR R we compute & = max - 8 fz). If e < 0. f is already in conv (dom g): otherwise, (8 + 5 - 51) gives an E -rojjjectionn P(p), as in the following Lemma 2. The total computation time of this projection step is TTp O(m).
Whiil the minimum weight setting is studied in [17]. we consider the maximum weight setting for conve- nience. Note that we can deal with the minimum- weight setting since w allowed to have negative entries. "Since edge weights are integer and the constraint is given by a totally unimodular matrix, there is at least integral optimal solution. Hence, we restrict the domain to 2 x "t
5

---

Lemma 2. For any p = (8) E B R such that = > 0, (3 + 51, 1 gives an E projection of onto conv(domg) g). the convex hull of the feasible region of (1).
Proof. For any As E R and At E R., we have (&+ As, + At) E conv(dom g) if and only
As; At, 2 Wij - 8 + i, for (i,3) E E; in particular, ( At,) 2 s must hold.
Thus, the f distance from (s, E) to any point in conv(dom g) is lower bounded by as follows:
[[As, A max max {0, + + + max max {0, - - 2 (As; Alj) 2 e.
iEL
jER
(KJ)EE
This lower bound is attained by setting As 5 and At = 1 as in the lemma statement.
Local optimization. As in [17], local optimization reduces to the minimum vertex cover problem (the dual of the maximum cardinality matching problem). We below briefly describe this reduction. Given a current solution p (s, t) E dom g, Step asks find an optimal direction over X S L and Y _ R. Letting S = X and T = R \ Y, we can formulate this problem as
(1x, ly)
minimize |S| [T] + const. subject to Liss + JeT 2 wij - s; + t +1 v(i,)) E E, (2) SCL,TER
where 1 14: = 1 (0) the argument is true (false). The constraint for each (i,j) E E matters only when (i.j) tight, i.e., S; - t, wij- Thus, letting E be the set of tight edges, we can write (2) as minimize |S| IT] const. subject to i jr E T SEA,TER
v(i.j) E",
which is the minimum vertex cover problem (V. E*), the dual of maximum cardinality matching. If we solve with the Hoperoft-Karp algorithm [26], we have Tic = O(m/n).
theorem [44, Theorem 16.2], there exists a vertex cover (S, with |S| - [T'] < n/2 if and only if (V, E*) has no perfect matching. Once a minimum vertex cover (8, T) with |S| + [T] < n/2 2 is found, we update ts to (s + Alg,t + RY,), where the step length 1 wig If we find a vertex cover (S,T) such that ) is a maximum- weight matching on G by complementary slackness [44, Section 18.5b), thus solving the original problem.
By the
A in Step 6 is given by minggt,s.JeRyy
[S] + [T] = n/2 on (V,E*,, any maximum-cardinnlliy matching on EV)
3.2 Weighted matroid intersection
We next consider the weighted matroid intersection problem, generalization of various problems such as bipartite matchings, packing spanning trees, and arborescences in directed graph. Due to this broad coverage, the discussion here would serve as role model for applying our DCA-based framework to various problems, even though the general result by itself may not immediately provide practical algorithms for specific problems.
A matroid M consists of a finite set V and a non-empty set family B C 2 satisfying the following exchange axiom: for any B1, B2 E B and E B, B2, there exists j E Bg B, such that Bi \ {i) U {i} E B and B2 ( E B. Elements in B are called bases, and an independent set subset of a base. The rank function p: 2 + Z of M is defined as p(X)= = maxBEs XX n BJ. The rank of M is defined by p(V), which coincides with the cardinality of any base B E B.
Let M1 (V, B2) and M2 (V, be rank-r matroids on an identical fixed ground set V of size n, equipped with a weight vector w E ZV. We assume that the matroids are given as independence oracles, which test whether an input set is independent or not in time. We also assume B₁ (1 # 0 (which we can check by solving the maximum cardinality matroid intersection problem once). The weighted matroid intersection problem where ((X) = Diex U, for any U E ZV and X C V. Its dual structure can be captured via the weight-splitting theorem [22, Theorem 13.2.4] and the dual problem is written as
(M, 1, M2) asks to find B E B, nB2 that maximizes ur wBB),
minimize PEgv
g(p)
max p(B) + max (B). BEB;
BEB,
The objective function g in (3) is known to be L-convex.* Since (3) an unconstrained problem, nothing is needed for the projection. We below focus on the local optimization step (Step 3).
'For &s = 1, 2. g1 (p) = maxsEB, P(B) is an L-convex function obtained as the discrete Legendre- Fenchel conjugate of the indicator function db, of Ba (regarded as the collection of la for B E Bu), which is M-comeex. As gı and 92 are L-convex, so is g(p) = gi (p) g2(w (w- p). See [38] for details.

---

Local optimization. We see that the local optimization reduces to the maximum cardinality matroid intersection problem, which asks to find a matroids. Letting p E zd be current feasible solution to (3) and w p. the problem of finding an optimal direction d = 1x over X S V is written as
common independent set of two
minimize XCV
max (p + Lx)( + max (q - (B). BEB:
BEB;
For matroid M = (V, B) and E ZV, let 8 arginax vB) and M" (V, B.). Then, M forms matroid [20], and its rank function is given as follows (see Appendix B. 1 for the proof),
Lemma 3. The rank function of M is given by (X) maxBEs(U 1B) maxBEB BBB.
From Lemma 3, by using rank functions pi and p9 of My and M2, respectively, we can rewrite (4) as (x) + p3 (V X) + const.,
minimize XCV
(5)
where const. = BaX pBB) +max (B)-r. The problem (5) (without the constant term) is the dual of the maximum cardinality matroid intersection problem on (MP, MX) (Edmonds" matroid intersection theorem [19], thus completing the reduction. The standard augmenting path algorithm by Cunningham [15] makes ((n calls to independence oracles of My and M2, and every independence testing on MR and ME, queried by the algorithm can be implemented with a single call to independence oracles of M, and M2, respectively, which takes time (see Appendix B.2).
Lemma 4. There is an algorithm that solves the maximum cardinality matroid intersection problem on (MP, Mž) by making ((1r1.5) calls to independence oracles of M, and M
Once a maximum common independent set of (M,. ME) is found, we can obtain optimal solution
X C V to (5) by traversing the auxiliary graph constructed in the augmenting- Theorem 41.3]). Thus, the total time complexity of local optimization is Tio = O If [ < т, update p to p A1x, where the step length À is determined by binary search [46] (or let À 1). If [ = r, current p is optimal to (3) and is a maximum weight common base of (M1, M2) [21].
algorithm (see [44,
3.3 Discrete energy minimization
We consider discrete energy minimization problems on fixed vertex set V. Let G = (V, E) be an
undirected graph with V = n and [E| S m. Given univariate convex functions Φ; : -- RU (oo) and Økyz Z + R
U { [ } for j E with i + j. the energy minimization problem is written as
minimize PE2v
g(p)
Σ o.(::)+ + Σ REV
ViglP; -P:).
(6)
(L,))E
This problem appears in many computer-vision (CV) applications [8, 25, 28] and belongs to L'-convex minimization [32]. In CV settings, Φi measures how well label ps fits pixel and 4/y quantifies smoothness of labels of adjacent pixels i and
Projection. In CV applications, we usually have box constraint representing the range of pixel values. Also, we may have an acceptable range of non-smoothness of adjacent pixels. To deal with such constraints, we suppose o; and tij to return +oo if input variables are out of the ranges. The resulting feasible region can be represented as in Proposition 1. If we only have box constraints, we can easily obtain Et -proeection of f E RV by computing max max(ax (o;, min (p:, }{} for each i V. which takes Prjj = (n) time. When imposing the smoothness constraints, we need to compute an t projection onto general L co-vex set. This is reduced to the shortest path problem, and we can compute the projection in Tрe) ((m)) time with the Bellman-Fort algorithm (see Appendix D).
Local optimization. Since the steepest descent method for problem (6) is already studied in [32], we here briefly describe key points. Let p E dom g be current solution and consider finding steepest
direction d e N = (0, +1} (0, -13 is analogous. Letting of (d,) = (p( + d,) for i E V and wiy) (dz, dz) = Wis (p; + d2 - pt- d:)
". We focus on exploring (0, 11) the case of {0. 1) V
for (1.j) E E, the local optimization problem on {0, +13 is written as
minimize dE(
g (P) = Σ (p) (d)) + Σ
w ( (d,,
vVV
(K))E
7

---

Since convexity of the implies vij (1,0) 1 (0.1) (1,1+ +/ (0, gld) is sub-
modular function that can be written as a sum of secudo-booleay functions with at most two variables. Minimization of such submodular function is reduced to min-cut problem vertices and 3m + nt edges [29, 6]. If we solve the min-cut problem with the Dinic algorithm [16].
graph with n + 2
takes The (mm?) time. We can also use empirically fast min-cut algorithms for CV settings [7]. Once a direction d is found, the step length À can be determined by binary search [46] (or let À = 1).
3.4 General L -cnvvex function minimization
We consider general L L'-convex function minimization min g()), assuming dom g to be rep- resented as in Proposition 1. Given prediction á E RV, we can compute an e -rojectiion P(ý) onto conv (domm g) with the Bellman-Ford algorithm in prj = O(n²) time (since
S n²),, as
mentioned in Section 3.3. As for the local optimization, given current solution p E dom g. we can find steepest direction by solving minxgv f(X), where f(X) = g(p 1x) or g(p 1x) is submodular function, as mentioned in Section 2.2. An empirically fast algorithm for submodular function minimization is the Fujishige-Wolfe algorithm [23], which solves the local optimization problem in Too = O((n + n²) time [11, 33J, where EO is the time of evaluating fXX) for any X C V and F = max;ev max(If((()). (f()) - f(V {d)ii (and theoretically faster strongly polynomial-time algorithm runs in ( log" n EO + n log (())
n) time [35]). In total, we can minimize general L -o-ccx function O( + 1 Ilp' (g) pol time.
4 Learning predictions
We detail how to learn predictions ý E TRY We consider online and batch learning settings where instances of form pez De (p) for t = ...., T are given adversarially and randomly, respectively. We make the following assumption, which is common with the previous studies [17, 31].
Assumption 2. Functions -1,.--: FT are defined on the same ground set V and satisfy Assumption I.
Furthermore, as in Theorem 2, we assume that a benchmark (optimal) prediction ji is included in [-C,+0]* for some C > 0, which is also common with [17, 31]. As for bipartite matching, there always exists an optimal dual solution included in [-C, +C1" if C 2 nl]wilse [30. Lemma 4.5], and the same condition holds for matroid intersection with C 2 r||ww|| (see Appendix B.3). This condition is also natural in discrete energy minimization since the range of pixel values is bounded. Also, we choose any suboptimal solution in +CI a benchmark prediction at the cost of increasing the bounds in Theorem 2.
We use the online-learning framework by Khodak et al. [31], and thus the learning method itself is not novel. Nevertheless, the improvement in the bounds is considerable. As with [31], the regret bound obtained from that of the online gradient descent method (OGD) [45], and the sample complexity bound follows from ouline-to-bateld conversion [10]. The key to the improvement is that we apply OGD to 1 l-Lipschitz convex loss functions (p) l|p" (gt) pll 6 while Khodak et al. [31] applicd OGD to Le(p) = I| (gt) - pll.. which is / Vn--ipschitz, following the setting of [17].
Theorem 2. Let V be finite set of size n and C' > O. For any sequence of functions g1..... 9T that map Z to U } there is an online learning algorithm that returns . PT E RV with the following regret bound for any 8- E cI-C,+C|²
T
Elln(o) Pr 1x
Elle"(9)) - 1011,0 CV2nTT
Moreover, for any distribution D over functions zV - RU ô E (0, 11. and > 0, if T (2((E) (n+ (n (n
i.i.d. samples 9r from D are given, we can compute á E RV that satisfies the following condition with a probability of least 1 8 for all 8 E [--C++ Eg || (g( -pl.c I Ey>DDlpp" (g) 1 t
'In [17], it is stated that C 2 ||w]| is sufficient, but this not true as shown in Appendix WW can also use (p) = [g:) plls.. which is convex and L--iishciitz; this may yield shaper bounds on the number of iterations, Proposition 2. We here present the foo -loss version for ease of exposition.
8

---

1 pploc for t = I..... T as loss functions of p E I and use the online gradient descent method (OGD). Note that (p) is convex since
Proof. We regard Lx(p)
(9)
L1
+ 9 2
p0 (9))
p + 2 <
p (g.)
+
1r (g)
9
L((p) + Le(9)
2
2
2
2
for any p, q E RV due to the triangle inequality. Furthermore, Lx(p) is L-Lipschitz since
(x(p) - [x(4)= 1lr"(a)) pl -Ixr"(() - ol S llp ح||xo S Ilp 1
for any p,q E RV due to the triangle inequality and || S ||0|/ for any I E IRY. Since Le is 1- 1-Lipschitz convex loss function and the 22-norm of any vector in [-C, is most CVTr, the regret of OGD is most Cv2nnT (see [45, Corollary 2.7l). thus obtaining the first claim. The second claim is obtained by using online-to-batch conversion. Specifically, since the loss function value is at most 2C, if we feed sampled 91...., . to OGI and let ý - Ei= Pt. then [10, Proposition 1] implies that the following inequality holds with a probability of at least
2n.
2
1 log
EgwD leeollp'00 1p'(p''')) (g) 2l100 S min pEI-C,+OJp
EgwDllp" (g) pllo + +CV
20
T
= 32 ( (n log 1)) is sufficient for bounding the sum of the last two terms in the right-hand side by from above.
Therefore, setting =
5 Whether to learn primal or dual solutions
We discuss whether to learn primal or dual solutions for successfully warm-starting algorithms with predictions from the DCA perspective (we refer the reader to [38] for more information). We expect that the discussion here is also useful in the context of augmenting online algorithms with predictions.
We consider minimization problem of form min (()), where g : ZV -> [+{+) is general objective function. As we have seen above, iterative algorithms look for an optimal solution by alternately exploring neighborhood to find steepest direction and proceeding along the direction. Intuitively, such an iterative algorithm can benefit from a prediction that is close to an optimum if the feasible region, dom g, is path connected with respect to the neighborhood; conversely, if the feasible region is not connected, good predictions are not always helpful. We below elaborate more on this idea for the case of L-convex minimization (the 1."-convex case is analogous).
First, we need to define a neighborhood, N so that we can efficiently solve local optimization problems on N. In the case of L-convex minimization, the local optimization on / =N {0, +1) reduces to submodular function minimization in general, which we can solve in polynomial time (and more efficient methods are available for many specific problems). Once a neighborhood / is defined, the next important requirement the path connectivity of the feasible region dom with respect to N, i.e., given any p, 4 E dom g, we can move from p q by iteratively finding an appropriate direction d E N and proceeding along d. L-convex sets are path connected with respect to Ni,, and this property necessary for ensuring that the steepest descent method converges an optimum.
Under the above conditions, a prediction close to an optimum is expected to be beneficial since provides short path to optimum. In other words, if feasible regions are not path connected, predictions close to an optimum do not always improve the performance of iterative algorithmss This observation gives guideline for judging whether to learn primal dual solutions: should choose the one such that a prediction can be converted into a solution in a path-connected feasible region.
In DCA, there are other convexity notions than L-convexity: M-, 1.2-, and Ma-comvexity (and their L' counterparts). In these classes, L-convex sets are path connected with respect to N4., and so are M-convex sets with respect to / = 1,)) - 16) i.j E VV.. By contrast, no appropriate neighborhoods are known that make L2- and M My-convex sets path connected. In the cases of bipartite matching and matroid intersection, the primal problems belong to My-concave maximization, while their dual problems are L-convex minimization. Thus, learning dual solutions for bipartite matching and matroid intersection reasonable. On the other hand, the primal problem of discrete energy minimization is L-convex. and thus we do not need to consider its dual.

---

6 Conclusion
We have developed a framework for warm-starting the steepest descent method for function minimization with predictions, thus bridging between discrete convex analysis and algorithms with predictions. We have demonstrated its effectiveness for weighted bipartite matching, weighted matroid intersection, and discrete energy minimization. We have also presented regret and sample complexity bounds for learning of predictions and discussed whether to learn primal or dual solutions. As for the practical aspect, experiments in Appendix F show that our DCA-based approach performs comparably to (or slightly better than) the method of [17].
A limitation of our work is that it does not yield prediction-indee independent worst-case bounds in general. This, however, often not a serious matter since we can run standard algorithms with worst-case guarantees in parallel and terminate both once either one returns solution. This point should be contrasted with the situation of augmenting online algorithms with predictions, where every decision made over time is irrevocable and thus attaining good prediction-depende guarantees simultaneously by a single algorithm is crucial. In Appendix E, we further discuss worst- cae guarantees of our DCA-based framework. In addition, we cannot deal with problems without L/L Loovextn,,, and extending our framework to W/M--covee function minimization, which also enjoys the path connectivity as mentioned in Section 5, will be an interesting future direction.
and worst-case
Acknowledgements
The authors thank Mikhail Khodak for sharing the latest results of [31] and anonymous reviewers for their valuable suggestions. This work was supported by JST ERATO Grant Number JPMJERI 1903 and JSPS KAKENHI Grant Number J722K17853.
References
[1] R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin. Solving the convex cost integer dual network flow problem. Manage. Sci., (10.499(955599999 2003. "I p.3
[2] Y. Azar, D. Panigrahi, and N. Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 35-66, SIAM, 2022. p
[3] M.-F. Balcan. Data-driven algorithm design. Beyond the Worst-Case Analysis of Algorithms, pages 626 645. Cambridge University Press, 2021. p.33
[4] E. Bamas, A. Maggiori, and O. Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems (NeurIPS 2020), volume 33, pages 20083-20094. Curran Associates, Inc., 2020. 4 p.1, p.3
[5] N. Bansal, C. Coester, R. Kumar, M. Purohit, and E. Vee. Leaming-augmennte weighted paging. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA 2022), pages 67-89. SIAM, 2022. '1 P.1, p.3
[6] E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Appl. Math., 123(1):
155-225, 2002. p.88
[7] Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max--iie algorithms for energy minimization in vision. IEEE Truns. Pattern Anal. Mach. Intell., 26(9): 1124-1177,
2004. pp8
[8] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell., 23(11):1222-1339, 2001. 7p.7
[9] C. Brezovec, G. Cormuéjols, and F. Glover. Two algorithms for weighted matroid intersection. Math. Program., 36(1) 1:39-33, 1986. p.3
[10] N. Cesa-Bianchi A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory, 50(9):2000-2057, 2004. 1p.8, 7 p.9
[11] D. Chakrabarty, P. Jain, and P. Kothari. Provable submodular minimization using Wolfe's 's algo- rithm. In Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014. 7 p.8
10

---

[12] D. Chakrabarty, Y. T. Lee, A. Sidford, S. Singla, and S. C.-W. Wong, Faster matroid intersection. In Proceedings of the 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1146-1166 168. IEFF, 2019. p.3
[13] J. Chen, S. Silwal, A. Vakilian, and F. Zhang. Faster fundamental graph algorithms via learned predictions. In Proceedings of the 39th International Conference on Machine Learning (ICMI.
2022), volume 162, pages 3583-3602. PMLR, 2022. p.3
[14) L.. Chen, R. Kyng, Liu, R. Peng,
Gutenberg, and S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. arXiv:2203.00667,, 2022. to appear in FOCS 2022.
p.3
[15] W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms. SIAM
J. Comput., 15(4):94--957) 1986. 7 p.3, " p.7, 71 p.15
[16] E. A. Dinic. Algorithm for solution of problem of maximum flow in networks with power estimation. Dokl. Akad. Nauk SSSR, 194(4):754-757 1970. p.88
[17] M. Dinitz, S. Im. T. Lavastida, B. Moseley, and S. Vassilvitskii. Faster matchings via learned duals. In Advances Neural Information Processing Systems (NeurIPS 2021), I), volume 34, pages 10393-10406. Curran Associates, Inc., 2021. '1p.1, p.2, p.3, p.5, p.6, "I p.8, '1 p.100, p.16, '1 p.118
[18] R. Duan and H.-H. Su. A scaling algorithm for maximum weight matching in bipartite graphs. In Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithuss (SODA 2012). pages 1413-1424. SIAM, 2012. P.2
[19] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, pages 69-87. Gordon and Breach, 1970. p.7
[20] Edmonds. Matroids and the greedy algorithm. Math. Program., 1:127-136, 1971. 1.7,
* p.14
[21] A. Frank. A weighted matroid intersection algorithm. Algorithm. Comput. Technol., 2(4):
328-336 1981. p.7
[22] A. Frank. Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, 2011. ' p.6
[23] S. Fujishige. Submodular Functions and Optimization. Elsevier Science, second edition, 2005. p.8
[24] S. Fujishige, K. Murota, and A. Shioura. Monotonicity in steepest ascent algorithms for
polyhedral L-concave functions. J. Oper. Res. Soc. Japan, 58(2): 2015. 'I p.4
[25] D. S. Hochbaum. An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM, 4844)1686-701, 2001. p.3, p.7
[26] Hoperoft and R. M. Karp. An 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.,
(09:225-2311 1973. p.2, p.6, p.
[27] C. C. Huang, N. Kakimura, and N. Kamiyama. Exact and approximation algorithms for weighted matroid intersection. Math. Program., 177(1): 1-2,, 2018. p.3,, ' 1.15
(28) H. Ishikawa. Fxact optimization for Markov random fields with convex priors. IEEE Trans. Pattern Anal. Mach. Intell., 23(10))1333-1333 1336, 2003. 7.7
[29] L. Ivănescu. Some network flow problems solved with pseudo-boolean programming. Oper.
Res., 13(3):388-399 1965. p.8
[30] S. Iwata, T. Oki, and M. Takamatsu. Index reduction for differential -algebbraa- equations with mixed matrices. J. ACM, 66(5):1-34, 2019. p.88
[31] M. Khodak, M.-F. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning predictions for algorithms with predictions. In Advances Neural Information Processing Systems (NeurIPS 2022). volume 35. Curran Associates, Inc., 2022. pp22, 'I p.3, 'I p.8, 'I p.10, 11p.8
[32] V. Kolmogorov and A. Shioura. New algorithms for convex cost tension problem with applica- tion computer vision. Discrete Optim., 6(4):378-393, 2009. p.777
[33] S. Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank-Wolfe optimization variants. In Advances in Neural Information Processing Systems (NIPS 2015), volume 28.
Curran Associates, Inc.. 2015. p.8

---

[34] S. Lattanzi. T. Lavastida, B. Moseley, and S. Vassilvitskii. Online scheduling via learned Symposium on Discrete Algorithms (SODA
weights. In Proceedings of the 2020 2020), pages 1859-1877. SIAM, 2020. '1 p.1, p.3
[35] Y. T. Lee, A. Sidford, and S. C.-W. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 1049-1065. IEEE, 2015,
p.33 p.8
[36] T. Lykouris and S. Vassilvtiskii, Competitive caching with machine learned advice. In Pro- ceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80, pages 3296-3300 3305. PMLR, 2018. p.1, p.3
[37] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2021. 7p
[38] K. Murota. Discrete Convex Analysis. Discrete Mathematics and Applications. SIAM, 2003.
p.2, p.3, '1 p.4, 'I 'p66, p.9
[39] K. Murota and A. Shioura. Exact bounds for steepest descent algorithms of L-convex function minimization. Oper. Res. Lett., 42(5):361-366, 2014. 'I p.4
[40] J. G. Oxley. Matroid Theory. Oxford Graduate Texts in Mathematics. Oxford University Press, second edition, 2011. p.14
[41] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via MI. predictions. In Advances in Neural Information Processing Systems (NeurlPS 2018), volume 31. Curran Associates, Inc., 2018. pP1,, p.3
[42] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970. p.2
[43] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Pro- ceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1834-1845, SIAM, 2020. 'I p.1,, p.3
[44] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. 9p66, p.7, p.15, p.17
[45] Shalev-Shwartz Online Learning and Online Convex Optimization, volume 4. Now Publish- ers, 2012. p.8, 7.9, P.188
[46] A. Shioura. Algorithms for L-convex function minimization: Connection between discrete convex analysis and other research fields. J. Oper. Res. Soc. Japan, 60(3):216-243, 2017. p.4, p.7, p p.17
[47] J. van den Brand, Y.-T. Lee, D. Nanongkai, R. Peng, T. Saranurak, A. Sidford, Z. Song, and D. Wang. Bipartite matching in nearly-linear time moderately dense graphs. In Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 919-930, 2020. p.2
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] See Section for details our contributions.
(b) Did you describe the limitations of your work? [Yes] See Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical paper and no negative societal impacts are expected.
(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 of all theoretical results? [Yes] See Assump- tions and 2
(b) Did you include complete proofs of all theoretical results? [Yes] Due to the space limitation, some proofs are shown in the supplementary.
12

---

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 as URL)? [No] All details described in Appendix
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(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)? [No]
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? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the suppiemental material or as a URL? [N/A]
(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 crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "oscVwJw6XQF", "reviewer": "Reviewer_zvz6", "summary": "This paper considers using predictions to improve algorithm running time via warm start as in the recent work due to Dinitz et al. 2021.  The authors propose a framework based on discrete convex analysis which applies a discrete steepest decent approach to go from an initial feasible solution to a global optimum.  Each iteration requires solving a local optimization problem to find a descent direction and the number of iterations can be bounded by $O(||p-p^*||_{\\infty})$, where $p$ is the initial solution and $p^*$ is an optimal solution.  Algorithms for projecting infeasible predicted solutions onto the feasible set (with respect to the $\\ell_\\infty$) norm and efficiently learning an initial predicted solution are also given to complete the framework.\n\nUsing this framework the authors give warm-start-with-predictions algorithms for:\n- weighted bipartite matching (improving the result of Dinitz et al. 2021)\n- weighted matroid intersection\n- Discrete energy minimization\n- The more general class of L/L♮-convex functions.\n\n", "questions": "- How does the proposed approach for weighted bipartite matching compare experimentally to Dinitz et al. 2021?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper gives a nice improvement over Dinitz et al 2021 for weighted bipartite matching and also extends the ideas to other problems.  The writing is a bit dense, but overall well explained.  An experimental evaluation may be interesting, but is probably not necessary for the current submission.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LcbZc8Qk2L", "reviewer": "Reviewer_TRn1", "summary": "This paper extends recent work by Dinitz et al. on using the learning-augmented algorithms model to speed up graph algorithms by warm-starting the dual solutions (in particular, they focused on the Hungarian algorithm for minimum-cost bipartite matching). In this paper, the authors interpret this idea of warm-starting in the context of discrete convex analysis, inspired by the idea that warm-starting is a well studied concept in convex optimization. Through this lens, they give an improvement in the min-cost matching problem, reducing the dependence on the prediction error from linear in the $\\ell_1$ error to linear in the $\\ell_\\infty$ error. Their framework is rather general and the authors apply it to get learning-augmented algorithms and bounds for weighted matroid intersection and discrete energy minimization as well. The authors also provide PAC bounds on learning predictions for these problems under the $\\ell_\\infty$ norm.", "questions": "Do you think that the DCA-based algorithms actually improve on the work of Dinitz et al in practice, or is it rather the case that you can give a tighter analysis of these algorithm than they could?", "limitations": "I found the discussion of limitations to be adequate. I do not foresee any specific negative impacts of this work as it is quite theoretical and abstracted away from applications.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The connection between warm-starting in Dinitz et al and in the framework of discrete convex analysis is interesting and general.\n- The improvements in the bounds from prior work are significant, changing the error dependence from $\\ell_1$ to $\\ell_\\infty$.\n- I thought the discussion of learning primal vs. dual solutions in Section 5 was very interesting. It is worthwhile to consider what factors make some predictions useful or not for algorithms with predictions.\n\nWeaknesses\n- For large graphs, the PAC bounds require many samples. In particular, if we set $C=n\\|w\\|_\\infty$, we need at least $\\frac{n^2 \\|w\\|_\\infty^2}{\\epsilon^2}$ sample instances which for large graphs seems extreme. The bounds are a significant improvement over the bounds given in prior work but I'm not sure how informative they actually are.\n- It seems that many of the techniques used in this paper come almost directly from prior work. Nonetheless, I think the application and combination of these ideas makes for some interesting insights and results on learning-augmented algorithms.\n- Perhaps most importantly, seeing as both this and the prior work are in some sense not comparing themselves to the best theoretical algorithms for matching (even if the predictions are near-perfect, the theoretical bounds will be worse), it would be more compelling if some experiments were done to show that the this discrete convex analysis approach is actually a better way to approach the problem than Dinitz et al.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4BjR6vUUuk6", "reviewer": "Reviewer_KW47", "summary": "This paper presents results illustrating the possible benefits of initializing learning algorithms based on predictions. By using a discrete convex analysis framework, the results indicate improved bounds for the sample and time complexity. The usefulness of the framework is shown by applications to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization. Finally, whereas the choice whether to learn primal or dual solutions has typically been made somewhat heuristically, the paper uses the proposed framework to give principled guidelines.", "questions": "What is the reason that your approach is unable to recover optimal worst-case bounds? Is this inherent to the approach, or can it be alleviated? (I understand that this is not crucial, as discussed in the end of the paper)  \nYou discuss in Section 6 that the issue above can be mitigated by running a standard algorithm in parallel. It seems as if the time complexity of such an approach would, compared to alternatives, never be worse by more than a constant factor 2. Is this a correct interpretation? What is the worst case?    \nCan similar lower bounds be shown for the time complexity?  \n\nMinor things:   \nline 28: worse->worst  \nline 113: \"the the\"", "limitations": "The authors clearly state the limitations, but an extended discussion on what classes of problems enjoy the different convexity notions could be beneficial.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written and structured, addresses a pertinent issue, and seems to provide novel improvements on prior work. The presentation is neat.  \nThe improvements over prior results are significant; for instance, the time complexity of some algorithms is improved by up to a factor $n$, where $n$ is the number of vertices.\n\nOne weakness of the results is that, unlike many previous analyses where the possible performance of learning algorithms due to the use of predictions, the analysis is unable to recover optimal worst-case bounds.  \nA more extensive discussion of the applicability of the given convexity assumptions and how these contrast with other notions of convexity could be beneficial in order to more clearly motivate the work and clarify the benefits and limitations.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept