Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case
Authors: Taihei Oki
Shinsaku Sakaue
Venue: NeurIPS 2023 poster (2023)
Keywords: algorithms with predictions
beyond the worst-case analysis of algorithms
time complexity
combinatorial optimization
discrete convex analysis
submodular functions
TL;DR: We present a framework for accelerating M-convex function minimization with predictions, thus complementing previous research and extending the range of optimization algorithms that can benefit from predictions.

Abstract: Recent years have seen a growing interest in accelerating optimization algorithms with machine-learned predictions. Sakaue and Oki (NeurIPS 2022) have developed a general framework that warm-starts the *L-convex function minimization* method with predictions, revealing the idea's usefulness for various discrete optimization problems. In this paper, we present a framework for using predictions to accelerate *M-convex function minimization*, thus complementing previous research and extending the range of discrete optimization algorithms that can benefit from predictions. Our framework is particularly effective for an important subclass called *laminar convex minimization*, which appears in many operations research applications. Our methods can improve time complexity bounds upon the best worst-case results by using predictions and even have potential to go beyond a lower-bound result.

Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case
Taihei Oki The University of Tokyo
Shinsaku Sakaue The University of Tokyo
Tokyo, Japan
Tokyo, Japan
oki @mist..........m....mmm..mmm.mmt w.w.i.uutoo. w...t..uoooocc...o
sakaue@mist. -.ttaeeeiitt..uu.tooo.o..... ac jp
Abstract
Recent years have seen a growing interest in accelerating optimization algorithms with machine-learne' predictions. Sakaue and Oki (NeurIPS 2022) have developed a general framework that warm-starts the L-convex function minimization method with predictions, revealing the idea's 's usefulness for various discrete optimization problems. In this paper, we present a framework for using predictions to accelerate M-convex function minimization, thus complementing previous research and extend- ing the range of discrete optimization algorithms that can benefit from predictions. Our framework is particularly effective for an important subelass called laminar convex minimization, which appears in many operations research applications. Our methods can improve time complexity bounds upon the best worst-case results by using predictions and even have potential to go beyond a lower-bound result.
Introduction
Recent research on algorithms with predictions [29] has demonstrated that we can improve algorithms' performance beyond the limitations of the worst-case analysis using predictions learned from past data. In particular, surge of interest has been given to research on using predictions to improve the time complexity of algorithms, which we refer to as Since Dinitz et al. [11]'s seminal work speeding up the Hungarian method for weighted bipartite matching with predictions, researchers have extended this idea to algorithms for various problems [7, 35, 10]. Sakaue and Oki [39] have found similarities between the idea and standard warm-starts in continuous convex optimization and extended to L-convex function minimization, a broad class of discrete optimization problems studied in discrete convex analysis [31]. They thus have shown that warm-starts with predictions can improve the time complexity of algorithms for various discrete optimization problems, including weighted bipartite matching and weighted matroid intersection.
with predictions for convenience.
In this paper, we extend the idea of warm-start starts with predictions to new direction called M-convex function minimization, another important problem class studied in discrete convex analysis. The M- convexity known be conjugate relation the L-convexity. Hence, exploring the applicability of warm-starts with predictions to M-convex function minimization is crucial to broaden further the range of algorithms that can benefit from predictions, as is also mentioned in [39]. This paper mainly discusses an important subclass of M-convex function minimization called laminar convex minimization (Laminar), a large problem class widely studied in operations research (see references in Section 1.2). To make it easy imagine, we describe the most basic form (Box) of Laminar,
(Box)
minimize ZE2
Σ f((xs)
subject to
Σ x = R 4 S 2 S uu I,...,n), (I)
where fi...., fn R are univariate convex functions, R E Z, e,,..., lu E Z and WI,..., Un UUUU (+oo). Note that the variable x E nn is an integer vector, which is needed when,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table Our results and the best worst-case bounds for General, Laminar, Nested, and Box, where
General refers to general M-convex function minimization discussed in Section 3.1. n is the number
of variables, R specifies the equality constraint as in (1), and m = |[ E E : |Y] 2 2 = O(n) is the number of additional constraints needed to convert Box into Nested and Laminar (see Section 4).
PROBLEM
OUR RESULTS
WORST-CASE TIME COMPLEXITY
General
O(nSFM + n =0 || =||1)
O(n² log(L/n) L/n) min(n, (L/o)) }EO,) [43]
O (n log n. log mit logn
Laminar
O(n|<>' - =111)
[18, 34)'
Nested
O(n|a** =1l1))
(n log m log R) [46]
Box
O + log n || # $111)
(n log #) [14, 191
for example, considering allocating R indivisible resources to entities. As detailed later, adding some constraints and objectives to Box yields more general classes, Nested and Laminar, where the level of generality increases in this order. Streamlining repetitive solving of such problems by using predictions can provide substantial benefits of saving computation costs, as we often encounter those problems in, e.g., resource allocation [22], equilibrium analysis [16], and portfolio management [8].
1.1 Our contribution
We give framework for accelerating M-convex minimization with predictions building on previous research [11, 39] (Section 3). We show that, given a vector E RR that predicts an optimal solution x" E Z". the greedy algorithm (Algorithm 1) for M-convex function minimization finds an optimal solution in (Timi + Toc | ælI1) time, where Tinit and Tho represent the time for converting into initial fcasible solution and for finding a locally steepest descent direction, respectively. Since we can minimize ||.- - @ll provably and approximately given optimal solutions to past instances [11, 23), this framework can provide better time complexity bounds benefiting from predictions. We also discuss how to apply our framework to general M-convex function minimization in Section 3.1.
Section 4 presents our main technical results. We apply our framework to Laminar, Nested, and Box and obtain time complexity bounds shown in Table Our time complexity bounds can improve the existing worst-case bounds given accurate predictions. In particular, our O(n||=* - @|| )-time bound for Laminar improves the existing Onn² log n log mil ) bound even if prediction error ||x" .||| is as large as (n). Our result for Nested is corollary of that for Laminar and improves the existing worst-case bound if || - - = O(1). In the case of Box, we can further reduce the time complexity to On + log n |x- 2 by modifying the algorithm for Laminar. Notably, our algorithm for Box runs in O(n) time if ||x- +||| O(n/ log even though there exists an On log log( R/ (ttnn"))-time lower bound for Box [19]. As far as we know, this is the first result that can go beyond the lower bound the time complexity in the context of warm-starts with predictions. Experiments in Section 5 confirm that using predictions can improve empirical computation costs.
Few studies in the literature have made explicit improvements upon the theoretically fastest algorithms, even if predictions are accurate enough. The only exception is [7], whose shortest-pan path algorithm with predictions can improve the best worst-case time complexity by couple of log factors. By contrast, our methods with accurate predictions can improve the best worst-case bounds by O(n) (up to log factors) in the Laminar case and potentially go beyond the lower-bound result in the Box case. Thus, our work not only extends the class of problems that we can efficiently solve using predictions but also represents a crucial step toward revealing the full potential of warm-starts with predictions. In this paper, we do not discuss the worst-case time complexity of our algorithms since we can upper bound it by executing standard algorithms with worst-case guarantees in parallel, as discussed in [39].
1.2 Related work
Algorithms with predictions [29], improving algorithms' performance by using predictions learned from past data, a promising subfield in beyond the worst-case analysis of algorithms [38]. While this idea initially gained attention to improve competitive ratios of online algorithms [36, 2, 28, 1].
'Whie the worst-case analysis in [18, 34] focuses on separable objective functions, we can extend it to more general Laminar in (2) by introducing additional variables at the slight cost of setting = O()).

---

recent years have seen a surge of interest in improving algorithms' running time [11, 7, 39, 35, 10]. A comprehensive list of papers on algorithms with predictions is available [27]. The most relevant to our work is [39], in which predictions are used to accelerate L-/L L-/L -cconvex function minimization, a large problem class including weighted bipartite matching and weighted matroid intersection. On the other hand, warm-starts with predictions remain to be studied for M-convex function minimization," another essential class that is in conjugate relation to L-convex function minimization in discrete convex analysis [31]. Although our basic idea for utilizing predictions is analogous the previous approach [1 1, 39], our algorithmic techniques to obtain the time complexity bounds in Table for the specific M-convex function minimization problems are entirely different (see Section 4).
M-convex function minimization includes many important nonlinear integer programming problems, including Laminar, Nested, and Box, which have been extensively studied in the context of resource allocation [22]. A survey of recent results is given in [41]. Table I summarizes the worst-case time complexity bounds relevant to ours. Besides, faster algorithms for those problems under additional assumptions have been studied. For example, Schoot Uiterkamp et al. [41] showed that, if an objective function is a sum of f(z;+ b,) (i 1..... n) for some identical convex function f and bj E Z, we can solve Box, Nested, and Laminar with existing algorithms that run in (n) [4, 211, O(n log m) [46], and (n²2) [30] time, respectively. Hochbaum [19] gave an O log n log n J-time algorithm for Laminar with separable objective functions and no lower bound constraints." Even in those special cases, our results in Table are comparable or better given that prediction errors ||0* - =I|| are small enough. There also exist empirically fast algorithms [42, 47], whose time complexity bounds are generally worse than the best results. Other problem classes with network and submodular constraints have also been studied [20, 30J. Extending framework to those classes is left for future work.
R
Resource allocation with continuous variables has also been well-studied. One may think we can immediately obtain faster algorithms for discrete problems by accelerating continuous optimization algorithms for relaxed problems with predictions and using obtained solutions as warm-starts. How- ever, this is not true since there generally exists an ((n) gap in the & no-morm between real and integer optimal solutions [30, Example 2.9]. implying that we cannot always obtain faster algorithms for solving discrete problem even if an optimal solution to its continuous relaxation is available for free.
2 Preliminaries
Let N = [1.....,n] n be finite ground set of size For i E N, let e; be the ith standard vector, ie., all zero but the ith entry set to one. For any x E RN and X _ N, let x(X) = Eiex Ft. Let 1-1 denote (clement-wise) rounding to closest integer. For a function f zN + + U [+o0] on the integer lattice ZN. its effective domain defined as dom = {x E zN f(()) < +00 J. A
function f is called proper if dom f + O. For Q C R.V, its indicator function εQ RR - {0, +00 defined by (x) == if x E Q and 400 otherwise.
2.1 M-convexity and greedy algorithm for M-convex function minimization
We briefly explain M-convex functions and sets; see [31, Sections 4 and 6] for details. We say a proper
function f N RU (oo is M-convex if for every x, y E dom and i ( E N xy > we }. there exists j E { e : my < Yy such that f(x) + f(v) 2 f(x - e, + t,,) + fly + 6 - ee). A non-empty set Q C N is said to be M-convex its indicator function dG NN + {0, +00} is M-convex. Conversely, if f is an M-convex function, dom f is an M-convex set. An M-convex set always lies in a hyperplane defined by { x E R x(N)= = R for some R E Z. It is worth mentioning that the M-convexity is built upon the well-known basis exchange property of matroids, and the base polytope of matroid is the convex hull of an M-convex set.
The main subject of this paper is M-convex function minimization, mingezN f(x),, where f ZNN - IR U [+00] is an M-convex function. Note that dom f C Z represents the feasible region of the problem. For convenience of analysis, we assume the following basic condition.
Assumption 2.1. An M-convex function f Z R (+20) always has a unique minimizer x".
"Similar the L-/L L-/LL --onvex case, can deal with M -cnvex finctions by considering corresponding M-convex functions with one additional variable. See [31, Section 6.1] 1J for details.
1 "An O(n log rime algorithm for Laminar (and Nested) with quadratic objective functions was also proposed in [20]. but later it turned out incorrect, as pointed out in [30].
3

---

This uniqueness assumption is common in previous research [39, 10] (and is also needed in [11, 7, 35], although not stated explicitly). In the case of Laminar, is satisfied for generic, strictly convex objective functions. Even if not, there are natural tie-breaking rules, e.g., choosing the minimizer that attains the lexicographic minimum among all minimizers closest to the origin; we can implement this by adding < <|<=:12 + Σ> [ for sufficiently small (0, 1) to f, preserving its M- M-convexity. This is in contrast to the L-convex case, where arbitrarily many minimizers always exist (see [40]).
We can solve M-convex function minimiza- tion by simple greedy algorithm shown in Algorithm 1, which iteratively finds a locally steepest direction, -c; + ej. and proceeds along it. If this update does not improve the objective value, the current so- lution is ensured to be the minimizer x" arg min f due the M-convexity [31, The- orem 6.26]. The number of iterations de- pends on the & distance to x² as follows.
Algorithm Greedy algorithm
1:
f- x²
2:
while not converged:
3:
Find i.j E N that minimize f(x - e, + ez)
4:
if (xr) S f1x es + e,):
5:
return T
6:
- x e ee
Proposition 2.2 ([44, Corollary 4.2]). Algorithm terminates exactly ||2* x /2 iterations.
A similar iterative method is used in the L-convex case [39], whose number of iterations depends on the -distttte and steepest direction is found by some combinatorial optimization algorithm (e.g.. the Hopcroft-Karp algorithm in the bipartite-mathiing case). On the other hand, in the M-convex case, computing a steepest direction is typically cheap (as we only need to find two elements i.j E N), while the number of iterations depends on the E1 disiistac which can occupy larger fraction of the total time complexity than the &o -distance. Hence, reducing the number of iterations with predictions can be more effective in the M-convex case. Section 3 presents a framework for this purpose.
Similar methods to Algorithm are also studied in submodular function maximization [25]. Indeed, M-convex function minimization captures non-trivial subclass of submodular function maximization that the greedy algorithm can solve (see [31, Note 6.21I), while it NP-hard in general [32, 13]
3 Warm--ttart.witt-preeiiiio framework M-convex function minimization
We present a framework for warm-starting the greedy algorithm for M-convex function minimization with predictions. Although it resembles those of previous studies [11, 39], it is worth stating explicitly how the time complexity depends on prediction errors for M-convex function minimization.
We consider the following three phases as in previous studies: (i) obtaining an initial feasible solution x E N from a prediction & E RN,, (ii) solving a new instance by warm-startin sutm-strrtigg an algorithm with x., and (iii) learning predictions é. The following theorem gives a time complexity bound for (i) and (ii), implying that we can quickly solve new instance if a given prediction & is accurate.
Theorem 3.1. Les f NN + RU (+02} be an M-convex function that has unique minimizer x² = arg min f and & E RN be possibly infeasible prediction. Suppose that Algorithum! starts from an initial feasible solution satisfying x" E arg min I [1]||
dom }. Then, Algorithum I terminates in O(1 x= - -0(11) iterations. Thus, if we can compute x in Tiuit time and find i, E N that minimize f( 6 + ej) in Step 3 in The time, the total time complexity is O + Toocll - =11.).
Thus, it suffices to prove ||.= - 11|| 0 O(I - .l By using the triangle inequality, we obtain ||. - x²
Proof. Due to Proposition 2.2, the number of iterations is bounded by
The second term is bounded as [2 [ S || - x²I1 I| since x E N As for the third term, we have ||
- + | [+]]| + [
xx 1. We below show that the right-hand side is O(I|=*
||| - x 1 since x E dom f is feasible point closest to [ and x= E dom f. and
the right-hand side, ||[ - x" II,, is further bounded as [| - x= 11 < [|[@ -ll1 + || x1111
2| 1 ||1 due to the previous bound on the second term. Thus, ||0- x 1 S 4 x² holds. 0
Note that we round å to a closest integer point [ before projecting it onto dom f, while rounding comes after projection in the L-/I. L-/L.--convex case [39]. This subtle difference is critical since rounding after projection may result in an infeasible integer point that far from the minimizer x" by O(n) in the & norm. To avoid this, swap the order of the operations and modify the analysis accordingly.

---

Let us turn to phase (iii), learning predictions. This phase can be done in the same way as previous studies [11, 23]. In particular, we can learn predictions in an online fashion with the standard online subgradient descent method (OSD) as in [23]. which works as follows in our case. Let V C R.N be convex set that we expect to contain an optimal prediction. For any sequence of M-convex functions fi....,Jr, we regard L (ā) == ||=; El|1 for t 1, ....: T as loss functions, where x; is the minimizer of ft. Fixing Φ1 E V arbitrarily, for = I,..., T, OSD iteratively computes a subgradient 2, (f, and set Āe+1 arg mingev || T) -112. where 1 0 is the step size. OSD returns predictions f1,..., .t that enjoy a regret bound (see, e.g., [33]], and a sample complexity bound follows from online-to- bo-batch conversion [5, 9]. Formally, the following proposition guarantees that we can provably learn predictions to decrease the time complexity bound in Theorem 3.1.
1....,T T be sequence of M-convex functions, each of which has unique minimizer xt = arg min St. and V C IR be a closed convex set whose lz diammeet is D. Then, OSD with 17 = D/v D/Vn//TTTT /nT returns .I...., Er E V that satisfy
Proposition 3.2 ([23)). Let fe NN + R U [+o) for
T E - -elli I
T
min V'EV
|| - +1
Furthermore, for any distribution D over M-convex functions f: + R {+00]. each of which has a unique minimizer s'ÿ- = arg min f, 8 E (0, 1], and E > 0, given T = 2 ( n log } i.i.d. from D, we can compute 2 V that satisfies
draws, : fI.
|2 +||ة S f~D
E
min E |ay a= +
EV
with a probability of at least 1- 8 via online miine-to-bbtee bbtchh conversion (i.e., we apply OSD to ||>;, -Il for t = =1, I,...,T T and average the outputs).
The convex set V should be designed based on prior knowledge of upcoming instances. For example, previous studies [11, 39] set V = =[-c, +C}* for some C >> 0, which is expected to contain optimal solutions of all possible instances; then D = 2C holds. In our case, we sometimes know that the total amount of resources is fixed, i.e., <<NN(vV (N = R, and that every x; is always non-negative. Then,
we may set V = { E RR : x(N) = R }. whose lz-diameter is D = R/2.
3.1 Time complexity bound for general M-convex function minimization
We here discuss how to apply the above framework to general M-convex function minimization. The reader interested in the main results in Table 1 can skip this section and go to Section 4.
For an M-convex function f N + R U (+00), given access to f's value and dom f. we can implement the greedy algorithm with warm- starts so that both Tim and The are polynomially bounded. Suppose that evaluating (x) for any 2 E 2 takes EO, time. Then, we can find a steepest descent direction at any x E dom f in Tic = O(n²EO,) time by computing fxx-e,+e,) ) for all j E N. As for the computation of x we need additional information to identify dom f (otherwise. finding any feasible solution may require exponential time in the worst case). Since dom f is an M-convex set, we build on a fundamental fact that any M-convex set can be written as the set of integer points in the base pegeepooin
polyhedron of an integer-valued valued submodular function [15, 31]. A set function p 2 - IR U {+oo} called submodular if p(X) )+ + p(Y) 2 p(X n Y) + p(X UY) holds for X, Y C N, and its base X,Y
polyhedron is defined as B(p)= == fI E IR N xxX) < p(X) (X N), x(N) = p(N) }. where
p(0) = and p(N)= < +oo are assumed. Thus, dom f is expressed as dom f = B(p) n Z with an integer-valued submodular function p: 2%V + Z U [+o0]. We assume that, for any E Z.N. we can minimize the submodular function p + x, defined by (p + + (X) = p(X) + xxX) for X C N, in SFM time. Then, we can obtain x dom f from [&] EN in Tinit = O(nSFM) time, as detailed in Appendix A.I. Therefore, Theorem 3.1 implics the following bound on the total time complexity.
Theorem 3.3, Given a prediction & E N we can minimize I in O(nSFM+
=$ll1) time.
The current fastest M-convex function minimization algorithms run in O log 4 EO,) and O n² log 4) (log /,/ log n) EO,) time [43], where L max ||. ylloo x. E dom ff }. Thus, our algorithm runs faster if || +1|1 = =(n) and SFM = onn²EO,) We discuss concrete situations where our approach is particularly effective in Appendix A.2.
5

---

4 Laminar convex minimization
This section presents how to obtain the time complexity bounds in Table by applying our framework to laminar convex minimization (Laminar) and its subclasses, which are special cases of M-convex function minimization (see [31, Section 6.3)). We first introduce the problem setting of Laminar.
A laminar F S 2 is set family such that for any X, Y E F, either X CY.X Y,, Xny = holds. For convenience, we suppose that F satisfies the following basic properties without loss of generality: 0 E E N E F, and (i] E F for every E N. Then, Laminar is formulated as follows:
minimize rEEN
Σ (x(r) YET
subject to x(N)= = R. ly xxY) uy (Y e F (0, (2)
where each fy: : IR- + +RRRY E is univariate convex function that can be evaluated in O1)) time,
R E Z, and by E EZUR (-((-x)) and by E ZZ (+x)) } for Y E F. We denote the objective function by fsum = Erez fr (x()))). We let :
[+ be function such that f(x) = fsum (1) if x satisfies the constraints in (2) and f(x) = +oo otherwise; then, is M-convex and dom f C Z represents the feasible region of (2). Nested is special case where feum is written as EiEN fc and {Y E M 2] = (Yi, .,.....y Ym) consists of nested subsets, i.e., Y1 C 1/2 c... C Ym. and Box is a special case of Nested without nested-subset constraints. Note that our framework in Section only requires the ground set N to be identical over instances. Therefore, we can use it even when both objective functions and constraints change over instances.
is well known that we can represent a laminar F S 2 by a tree Ty = -V, E). The vertex set is V = FV (O). For Y E V/, (NV, we call X E V parent of Y if X is the unique minimal set that properly contains Y; let pYY) E V denote the parent of Y. We call Y E V (N) a child of X if pYY) = X. This parent-child relation defines the set of edges as E = {X, that each { E V corresponds to a leaf and that N E V is the root. For simplicity, we below suppose the tree Ty = (V, F.) to be binary without loss of generality. If parent has more than two children, we can recursively divide them into one and the others, which only doubles the number of vertices. Figure illustrates a tree T'= of laminar F (0, (1); (2), (3). (1, (13,.33}
X,Y E V. p(Y) X }. Note
Applications of Laminar include resource allocation [30], equilibrium analysis of network congestion
games [16], and inventory and portfolio management [8]. We below describe simple example that the reader can better grasp the image of Laminar; we will also use it in the experiments in Section 5.
Example: staff assignment. We consider assigning R staff mem- bers to tasks, which form the ground set N. Each task is associated with higher-level task. For example, if staff members have com- pleted tasks 1,2 E N, they are assigned to new task Y = {1,2), 2). which may involve integrating the outputs of the individual tasks. The dependencies among all tasks, including higher-level ones, can be expressed by a laminar F C 2 Each task Y E F is supposed to be done by at least ey (2 1) and at most uy (5 R) members. An employer aims to assign staff members in attempt to minimize the total perceived workload. For instance, if task E N requires c, > O amount of work and x; staff members are assigned to it, each of them may perceive a workload of f((2;) = es ca/2,. Similarly, the perceived workload of task Y {1,2) is fr (x)Y) = cy /Y() The problem of assigning R staff members to n tasks to minimize the total perceived workload, summed over all tasks in F, is formulated as in (2). Figure 1 illustrates two example assignments, I and II. Here, people assigned to {1} and {2} must do more tasks than those assigned to (3), and hence assignment I naturally leads smaller total perceived workload than II. We can also use any convex function fy on [Ly, uy] to model other objective functions. Making it faster to solve such problems with predictions enables us to manage massive allocations daily or more frequently.
(12233
(1.2)
(1)
(2)
[3]
X1
X2
X3
tt1
Figure 1: Image of tree Ty. Each leaf (i) has variable xt. The lower part shows example assignments.
Our main technical contribution is to obtain the following time complexity bound for Laminar via Theorem 3.1, which also applies to Nested since it is a special case of Laminar.
Theorem 4.1. For Laminar, given prediction & E R,N, we can obtain an initial feusible solution
x E arg min |x - [ : x E dom f in Tini = O(n) time and find a steepest descent direction in Step 3 of Algorithm in Tioc = O(n) time. Thus, we can solve Laminar in O(zl|z² - =bl1) time.

---

We prove Theorem 4.1 by describing how to obtain an initial feasible solution and find steepest descent direction in Sections 4.1 and 4.2. respectively. Section 4.3, we further reduce the time complexity bound for Box. The algorithmic techniques we use below are not so complicated and can be implemented efficiently, suggesting the practicality of our warn-start--vitt-prrdicooo framework.
4.1
Obtaining initial feasible solution via fast convex min-sum convolution
We show how to compute x" E dom f in Timit (n)) time. Given prediction E E RX we first compute [+t E Z~ in O(n) time and then solve the following special case of Laminar to obtain x":
minimize 2E2N
Σ
Ir - 1G:11
subject to x(N) = R, by S x(()) uy (Y E (J, (O,
(3)
EN
Note that it suffices to find an integer optimal solution to the continuous relaxation of (3) since all the input parameters are integers. Thus, we below discuss how to solve the continuous relaxation of (3).
Solving (3) naively may be as costly as solving the original Laminar instance. Fortunately, however, we can solve it much faster using the special structure of the -norm objective function. The method we describe below is based on the fast convex min-sum convolution [45], which immediately provides an (n log ni)-time algorithm for solving (3). We simplify it and eliminate the logarithmic factors by using the fact that the objective function has only two kinds of slopes, +1.
+1
24
Conjugate
g"
We suppose that each non-leaf vertex Y V in T>= = (V, E)) has variable Ty E R. in addition to the original variables r; for leaves {i} E V. We consider assigning a univariate function g R- + RRU++c of the following form to each vertex in V:
Conjugate (4) relation of g and g"
Figure 2:
((z) -| (),,)(())
where E, E [+o)) and é < <b< u. Note that if g is given by (4) up to an additive constant, its convex conjugate 9" (p) = supl (p. x) =g(x)= x E R } is a piecewise-
function whose slope u can occur). Figure illustrates this conjugate relation. We below construct such functions in a bottom-up manner on T'.
is l if S 11, b 11 p S +1,an0 and u if 2 +1 (where f f= and/or
First, assign function (x,) = [z, [ + (z,) to each leaf {t} E V, which represents the ith term of the objective function and the constraint on in (3). Next, given two functions Jx (ax) = x - bxl + [xxxxx((xx and gy (xy) )- = |xy - by + ayy ) of X,Y Y E V with an identical parent KUY& E V. we construct the parent's function as gxur (gx gy + (f where (yx D gy (xxur)
min gx (xxx + gr (xr) : xx + zy xxur is the infimal convolution. We can confirm that gxuy also takes the form of (4) as follows. Since 9x and gy are of the form (4), gx and gy have the same breakpoints, =1 (see Figure 2). Furthermore, since gx Lg
+ g holds (e.g., [37, Theorem 16.4)), gx Dgy takes the form of (4) with E = fx + Ey. b = bx + by, and = ux + uy. Finally, adding 8igxoy
preserves the form of (4). We can compute resulting e, b, and u values of gxuy in O(1) time, and hence we obtain gy for all Y V in bottom-up manner in O(n) time. By construction, for each Y E V. gy (xv) indicates the minimum objective value corresponding the subtree, (Vy, Ey). rooted at Y when xy is given. That is, we have
gy (xy) min Exey [ x<Y) xY, ey x(Y)) uy (Y' E Vy \ {YH)
up to constants ignored when constructing gy, where gy (zY) = +oo if the feasible region is empty. Thus, gN (R) corresponds to the minimum value of (3), and our goal is to find integer values xy for Y E V that attain the minimum value when NN R E Z is fixed.
Given gy constructed as above, we can compute desired zy values in top-down manner follows.
Let X KUYE E V be a len- vertex with two children X and Y. Once EXuY E dom gx Jy is fixed, we can regard minf gx (æx) + gy (zy) xx + Zy = xxur } (= gXuy (xxux)) as univariate convex dieceisse-linea minimization with variable xx E R (since Zy = EXUY 2x). which we can solve (1) time. Moreover, since TXuY and all the parameters of gx and gy are integers, we can find an integral minimizer xx E Z (and dy = zXuY xx E Z). Starting from xN R E Z, we thus compute By values for E V in a top-down manner, which takes O(n) time. The resulting I, value for each leaf [i] E V gives the ith element of a desired initial feasible solution d dom f.
7

---

4.2 Finding steepest descent direction via dynamic programming
We present dynamic programming (DP) algorithm to find a steepest descent direction in Tloc = (m) time. Our algorithm is an extension of that used in [30]. The original algorithm finds that minimizes f( - e; + ee) for a fixed (n) time. We below extend
find a pair of (i.j) in (nz) time.
Let æ E dom f be current solution before executing Step 3 in Algorithm 1. We define a directed edge set, Ax, on the vertex set V as follows:
A₂ = ()(Y). YEV (N), x(Y) < uvy ) JU((Y,P(Y)) YEV x(Y) > 6r
Note that x - Ga + e, is feasible if and only if (V, A²) has a directed path from {i} E V to (i} EV. We then assign an edge weight WX,Y to each (X, Ar defined as
WXY [r((a(M) + (x()(()) if -P)) if - p(X).
By the convexity of fr, we have Wp(Y) 2 Wy,p(Y), i... there is no negative cycle. If c, + e is feasible, fsum (x - 6; + e;) (z) is equal to the length of shortest path from {i} to {j} with respect to the edge weights y (see [30, Section 3.3]). Therefore, finding a steepest descent direction, E4 + ej, reduces to the problem of finding shortest leaf-to-leaf path in this (bidirectional) tree Tn == (V, A.). Constructing this tree takes (nn) time.
We present DP algorithm for finding shortest leaf-to-lead path. For Y E V. we denote by TY the subtree of Te rooted at Y. Let L. be the length of a shortest path from a leaf Y in Tg (Y). L the length of a shortest path from Y to a leaf in TY).,, and LĀ the length of a shortest path between any leaves in (Y). Clearly, L = L. = L 0 holds if Y is a leaf in Tz. For non-leaf vertex Y E V, let C(Y) denote the set of children of Y in T3 We have the following recursive formulas:
LX min { + ] LY XEC(Y): (X,
min { + wy,x), LX min(1 LY min L XEC(Y): (Y.X)EA,
where we regard the minimum on an empty set as toc. Note that, if shortest leaf-to-Y and Y-to-leaf paths in (Y) are not edge-disjoint, there must be a leaf-to-leaf simple path in (Y' whose length is no more than L + Ly since no negative cycle exists. According to these recursive formulas, we compute Lİ L. and L for all Y V in O(n) time by the bottom-up DP T₃- Then, L is the length of desired shortest leaf-to-leaf path, and its leaves (i), [o} V can be obtained by backtracking the DP table in O(n) time. Thus, we can find a desired direction -e; + ej in O(n) time.
4.3 Faster steepest descent direction finding for box-constrained case
We focus Box (1) and present a faster method to find a steepest descent direction, which takes only Toc = Olog n) time after an O(n)-time prepprocessing. Note that we can obtain an initial feasible solution with the same method as in Section 4.1; hence Tima O(r) also holds in the Box case.
Theorem 4.2. For Box, given a prediction â E TR,N, after an O(n) be included in Tinit = (n)), we can find a steepest descent direction in Step 3 of Algorithm I in Toc = O(log n)) time. Thus, can solve Box in O(n + log || 1a" =(l:) time.
pre-processing (that can
f, (I,) holds if and te are feasible. Furthermore, only need to care about the box constraints, & < H2 S u, for i = 1,... , n (since x(N)= = R is always satisfied due to the update rule). Therefore, by keeping AF = [a 1 11- (xx( + + (xx) and A = f& (xt + -1
Proof. In the Box case, f(x -x--4- -,
f(x, fx;)) +
+ + for l = 11...,, n with two min-heaps, respectively, we can efficiently find i E arg min ( Yi and j E arg min( } then, -e; + e, is a steepest descent direction. More precisely, at the beginning of Algorithm 1, we construct the two heaps that maintain A and A values, respectively. and two arrays that keep track of the location of each element in the heaps; this pre-processing takes Onn) time. Then, in each iteration of Algorithm 1, we can find steepest descent direction -e; + ej. update A, At. AJ. and A values (by the so-called the heaps and arrays in Tioe nl time. Thus, Theorem 3.1 implics the time complexity. D
values
operations), and update
8

---

20
2000
Lears
Learn
Learn
Berratons
Relax
ledex
Relax
Relax
1000
Cod
Cold
Cold
Cold
50
100
50
100
100
50
100
t
Figure 3: The number of iterations of the greedy algorithm initialized with Learn, Relax, and Cold. The curve and error band show the mean and standard deviation of 10 independent runs, respectively.
5 Experiments
We complement our theoretical results with experiments. We used MacBook Air with Apple M2 chip, 24 GB of memory, and macOS Ventura 13.2.1. We implemented algorithms in Python 3.9.12 with libraries such as NumPy 1.23.2. We used Gurobi 10.0.1 [17] for a baseline method explained later. The source code is available at https: //gi thub. ctt.uu..co/sssaaaaeeeaaeee cow.ssakaue/////eeeeaeaaaaaaaaaa /alps-msm wwm.mm-coo----e-mmoo-m code.
5.1 Staff assignment
We consider Laminar instances of the staff-assignment setting described in Section Suppose that we have R = 12800 staff members and n 128 tasks. Let T> (V. E) be a complete binary tree with n leaves. Define an objective function and inequality constraints as fsum (1) = Evev ey /x) and by I x (Y) S R for Y E EF (0. N). respectively, with cy and ly values defined as follows. We set cy controls the noise strength. We let by min + ub R/2"-h3, where h {0, 1.... log. n } is the height of Y in Ty (a leaf Y has = 0) and Ug is drawn uniformly at random from {0, 1,...... 50]; the minimum with R/2n-/ is taken to ensure that the feasible region is non-empty. We thus create dataset of T = 100 random instances for each E (1,5, 10, 20J. We generate 10 such random datasets independently to calculate the mean and standard deviation of the results. The instances arrive one by one and we learn predictions from optimal solutions to past instances online. By design of cy, the ith entry of an optimal solution tends to be larger as increases, which is unknown in advance and should be reflected on predictions ft by learning from optimal solutions to past instances.
max iEY + dua 1). where ua follows the standard normal distribution and o
We learn predictions é, E N for t. ., T by using OSD on V = {xx E [0, RJ x(N) = R} with step size of 0.01 v R/n, where the projection onto V is implemented with a technique in [3]. We use the all-one vector multiplied by R/n as an initial prediction, in E V. and set the (th prediction, ft, to the average of past t outputs, based on online-to- saline-to-batchh conversion. We denote this method by "Learn." " We also two baseline methods, "Cold" and "Relax", which obtain initial feasible solutions of the greedy algorithm as follows. Cold always uses &o as an initial feasible solution. Relax is variant of the continuous relaxation approach [30], the fastest method for Laminar with quadratic objectives. Given a new instance, Relax first solves its continuous relaxation (using Gurobi), where the objective function is replaced with its quadratic approximation at st. and then converts the obtained solution into an initial feasible solution, as with our method. Note that Relax requires information on newly arrived instances, unlike Learn and Cold. Thus, Relax naturally produces good initial feasible solutions while incurring the overhead of solving new relaxed problems. We compare those initialization methods in terms of the number of iterations of the greedy algorithm.
Figure 3
compares Learn, Relax, and Cold for each noise strength a. Learn always outperforms Cold, and it does even Relax if o < 10, suggesting that under moderate noise levels, learning predictions from past optimal solutions can accelerate the greedy algorithm more effectively than solving the relaxed problem of new instance. The advantage of Learn decreases increases, as expected.
5.2 Resource allocation
We also present experiments using Nested instances of [47, Section 6.3], which include three types of problems, denoted by F, CRASH, and FUEL. The objective functions of F, CRASH, and FUEL are written as Σi_ fe(xx)) where fx())) = /4 + PiTri fa()))) = h; + p1/aa, and fa(a;)) = Pe ca(c///a 3,, respectively, with some input parameters ps. ki, C.. F is synthetic problem of optimizing the

---

0.1
10
Loarn
Loam
Learn
Rolex
Relax
Rellx
2000
Cold
Cold
50
100
100
50
(a)
10
800
Lear
Leam
Rolex
Relex
Relex
Cold
Cold
Cold
200
100
(h) CRASH
0.1
Iterations
10
Learn
LesIn
LEAATE
Hellox
Relax
Relax
35
Gold
Coll
Culd
30
(c) FUEL
Figure 4: The number of iterations of the greedy algorithm initialized with Learn, Relax, and Cold. The curve and error band show the mean and standard deviation of 10 independent runs, respectively.
fourth-order polynomial, while CRASH and FUEL come from real-world project crashing and ship speed optimization, as noted in [46]. We create Nested instances with n = 100 for F, CRASH, and FUEL based on the procedure of [47]. We then generate T 100 instances by perturbing parameters defining constraints and objectives with Gaussian noises multiplied by controls the noise strength. As with the previous experiments, we measure the number of iterations of the greedy algorithm initialized by Cold, Relax, and Learn over the 100 instances. Regarding Learn, we set OSD's step size in the same manner as the previous experiments, and each element of an initial prediction do is set to [R/n]] or [R/n] + 1 at random so that (NV A holds.
0.1, 1.0, 10.0, which
Figure shows the results. Similar to the previous synthetic setting, Learn attains fewer iterations than Relax and Cold for CRASH and FUEL with moderate noise strengths (a = 0.1, 1.0). As for F, Relax performs extremely well and surpasses Learn, probably because the synthetic fourth- order polynomial objective is easy to handle with the certinuuuu-rllxattion method used in Relax. Nevertheless, it significant that Learn can surpass Relax for CRASH and FUEL, which come from real-world applications, under moderate noises.
Conclusion and limitations
We have extended the idea of warm-start, with predictions to M-convex function minimization. By combining framework with algorithmic techniques, we have obtained specific time complexity bounds for Laminar, Nested, and Box. Those bounds can be better than the current best worst-case bounds given accurate predictions, which we can provably learn from past data. Experiments have confirmed that using predictions reduces the number of iterations the greedy algorithm.
Since our focus is improving theoretical guarantees with predictions, further study of practical aspects is left for future work. While we have used the standard OSD for learning predictions, we expect that more sophisticated learning methods can further improve the empirical performance. Also, extending the framework to other problem classes is an exciting future direction. technical open problem is eliminating Assumption 2.1, although it hardly matters in practice. We expect the idea of [40] for the L-/L'-convee -coovvx case is helpful, but it seems more complicated in the M-convex case.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Satoru Iwata for telling us about the integrality of the dual problem of submodular function minimization. The authors also thank the anonymous reviewers for their helpful comments. This work was supported by JST ERATO Grant Number JPMJERI 1903 and JSPS KAKENHI Grant Number J722K17853.
References
[1] Azar, D. Panigrahi, and N. Touitou. Online graph algorithms with predictions. Pro- ceedings of the 2022 Anmual ACM-SIAM Symposium Discrete Algorithms (SODA 2022), pages 35-66. 66. SIAM, 2022 (cited on page 2).
[2] 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 (cited on page 2).
[3] C. Bauckhage. NumPy/SciPy recipes for data science: projections onto the standard simplex. Technical report, 2020 (cited on page 9).
[4] P. Brucker. An O (1) algorithm for quadratic knapsack problems. Operations Research Letters, 3(3):133-166, 1984 (cited on page 3).
[5] Cesa-Bianchi, A. Conconi, and Gentile. On the generalization ability of on-line learning algorithms. JEEE Transactions on Information Theory, 50(9):2050-2055 2004 (cited on
page 5).
[6] D. Chakrabarty, P. Jain, and Kothari. Provable submodular minimization using Wolfe's algorithm. In Advances in Neural Information Processing Systems (NuerIPS 2014), volume 27, pages 802-809. Curran Associates, Inc., 2014 (cited on page 15).
[7] 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 (ICML 2022), volume 162, pages 3583-3602. PMLR, 2022 (cited on pages 1-4).
[8] Chen and M. Li. Mc-conexxity and its applications in operations. Operations Research, 19)6:1396-1440 2021 (cited on pages 2, 6).
[9] A. Cutkosky. Anytime amline-to-bated optimism and acceleration. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), volume 97, pages 1446-1454.
PMLR, 2019 (cited page 5).
[10] S. Davies, B. Moseley, S. Vassilvitskii, and Y. Wang. Predictive flows for faster Ford Ford-Fulkerson In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), volume 202, pages 7231-7248. PMLR. 2023 (cited on pages 1,3, 4).
[11] M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, pages 10496.00406... Curran Associates, Inc., 2021 (cited on pages 1-5).
[12] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Struc- tures and Their Applications, pages 69-87. Gordon and Breach, New York, 1970 (cited on page 14).
[13] U. Feige. A threshold of In for approximating set cover. Journal the ACM, 45(4))6344655 1998 (cited on page 4).
[14] G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking in X + and matrices with sorted columns. Journal of Computer and System Sciences, 24(2):19--208, 1982 (cited on page 2).
[15] S. Fujishige. Submodular Functions and Optimization, volume 58 of Annals of Discrete
Mathematics. Elsevier, Amsterdam, second edition, 2005 (cited on pages 5, 14).
[16] S. Fujishige, M. Goemans, T. Harks, B. Peis, and R. Zenklusen. Congestion games viewed from M-convexity. Operations Research Letters, 13(3):329-333) 2015 (cited on pages 2, 6).
[17] Gurobi Optimization, LLC. Gurobi optimizer reference manual. https: //www//www///// gurobi com, 2023 (cited on page 9).
[18] D. S. Hochbaum and G. Shanthikumar. Convex separable optimization is not much harder than linear optimization, Journal of the ACM, 37(4):843-862, 1990 (cited on page 2).

---

[19] D. S. Hochbaum. Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Mathematics of Operations Research, 19(2):390-400) 409, 1994 (cited on pages 2, 3).
[20] D. Hochbaum and S.-P. Hong. About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Mathematical Programmingg 69(1-3):269330 1995 (cited pages 15).
[21] T. Ibaraki and N. Katoh. Resource Allocation Problems: Algorithmic Approaches. MIT Press, first edition, 1988 (cited on page 3).
[22] N. Katoh, A. Shioura, and T. Ibaraki. Resource allocation problems. In Handbook of Combi- natorial Optimization, pages 2897-2988. Springer, New York, NY, 2013 (cited on pages 2,
3).
[23] M. Khodak, M.-F. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning predictions for algo- rithms with predictions. In Advances in Neural Information Processing Systems (NeurIPS 2022), volume 35, pages 3542-3555. Curran Associates, Inc., 2022 (cited on pages 2, 5).
[24] S. Lacoste-Julien and Jaggi. On the global linear convergence of Frank variants. In Advances in Neural Information Processing Systems (NeurIPS 2015), volume 28, pages 496-504, Curran Associates, Inc., 2015 (cited on page 15).
Frank-Wolfe Wolfe optimization
[25] Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko. Maximizing nonmonotone submodular functions under matroid knapsack constraints. SIAM Journal on Discrete Mathematics, 23(4):2033-2078, 2010 (cited on page 4).
[26] Y. T. Lee. A. Sidford, and S. C.-W. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 1049-1065, 2015 (cited on page 15).
[27] A. Lindermayr and N. Megow. https: allalllgll aorroorrooiooooooo thms with predictions github io/ (cited on page 3).
[28] T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM. 68(4):1-25, 2021 (cited on page 2).
[29] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, Cambridge, 2021 (cited on pages 2).
[30] S. Moriguchi, A. Shioura, and N. Tsuchimura. M-convex function minimization by continu- relaxation approach: proximity theorem and algorithm. SIAM Journal Optimization, 21 (33)66333666, 2011 (cited on pages 3, 6, 8, 9, 15).
[31] K. Murota. Discrete Conver Analysis, volume 10 of Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2003 (cited on pages 1, 3,3-6, 14).
[32] G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978 (cited on
page 4).
[33] F. Orabona. A Modern Introduction to Online Learning. OpenBU, 2020 (cited on page 5),
[34] J. B. Orlin and B. Vaidyanathan. Fast algorithms for convex cost flow problems on circles, lines, and trees. Networks, 62(4):288-29) 2013 (cited on page 2).
[35] A. Polak and M. Zub. hhamiin--augmentee maximum flow. 2rXiv:2207.12911, 2022 (cited on pages 1, 3, 4).
[36] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems (NeurIPS 2018), volume 31, pages 9684- 9693. Curran Associates, Inc., 2018 (cited on page 2).
[37] R. T. Rockafellar. Convex Analysis, volume 13 of Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton, 1970 (cited on page 7).
[38] T. Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge, 2021 (cited on page 2).
[39] S. Sakaue and T. Oki. with predictions. Advances in Neural Information Processing Systems (NeurIPS 2022), volume 35, pages 20988-21000 Curran Associates, Inc., 2022 (cited on pages 1-5).
wwwvex-anallsii--eeeeeooooa framework for warm-starting algorithms
12

---

[40] S. Sakaue and T. Oki. Rethinking warm- starts with predictions: learning predictions close to sets of optimal solutions for faster L-/L" L-/L- -convex function minimization. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), volume 202, pages 29760- 29776. PMLR, 2023 (cited on pages 4, 10).
[41] M. H. H. Schoot Uiterkamp, M. E. T. Gerards, and J. L. Hurink. On a reduction for class resource allocation problems. INFORMS Journal on Computing, 340):1387-1402, 2022
(cited pages 3, 15).
[42] M. H. H. Schoot Uiterkamp. J. L. Hurink, and M. E. T. Gerards. A fast algorithm for quadratic resource allocation problems with nested constraints. Computers & Operations Research, 135:105451, 2021 (cited on page 3).
[43] Shioura. Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discrete Applied Mathematics, 134(1):303-316, 2004 (cited
on pages 2, 14).
[44] A. Shioura. M-convex function minimization under LI-distance constraint and its application dock reallocation in bike-sharing system. Mathematics of Operations Research, 47(2): 156661566
1611, 2022 (cited on page 4).
[45] P. Tseng and Z. Luo. On computing the nested sums and infimal convolutions of convex piecewise- linear functions. Journal of Algorithms Computational Technology, 21(2):240-
266, 1996 (cited on page 7).
[46] T. Vidal, D. Gribel, and P. Jaillet. Separable convex optimization with nested lower and upper constraints. INFORMS Journal on Optimization, 1(1):71-90, 2019 (cited on pages 2, 3, 10).
[47] Z. Wu, K. Nip, and Q. He. A new combinatorial algorithm for separable convex resource allocation with nested bound constraints. INFORMS Journal on Computing. 33(3):1197-122 2021 (cited on pages 3, 9, 10).
13


Reviews:
[{"review_id": "BpSA9YYtSV", "reviewer": "Reviewer_xgTQ", "summary": "The paper discusses the growing interest in accelerating optimization algorithms using machine-learned predictions. It highlights the work of Sakaue and Oki, who introduced a general framework for employing predictions to warm-start the L-convex function minimization method, demonstrating its effectiveness for various discrete optimization problems. Building on this, the paper presents a new framework that leverages predictions to accelerate M-convex function minimization with improved time complexity bounds, thereby extending the applicability of predictive techniques to a wider range of discrete optimization algorithms.", "questions": "Could the authors present concrete evidence illustrating how the theoretical bounds offer valuable insights capable of significantly accelerating the practical applications using the proposed algorithm?", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper is well-written, presenting intuitive results. It exhibits technical solidity, providing clear explanations of how the proposed algorithm enhances the existing worst-case time complexity.", "weaknesses": "1. The main theoretical results appear to be straightforward. The computational time complexity relies on the distance between the initialization and the optimal solution, assuming a good initialization is provided. However, one limitation of this paper is the absence of an analysis regarding the methodology for obtaining such a good initialization.\n2. The difficulty in deriving the corresponding theoretical results is not well elucidated in the paper. For instance, proving Theorem 3.1 hinges on Proposition 2.2, which is simply a direct application from existing works [44]. It would be more beneficial if the paper provided a clearer explanation of the technical challenges involved in obtaining the theoretical results.\n3. This paper lacks numerical justifications for the proposed theoretical time complexity bound. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing valuable feedback. We present our response to each comment below. \n\n> **Weakness 1.** The main theoretical results appear to be straightforward. The computational time complexity relies on the distance between the initialization and the optimal solution, assuming a good initialization is provided. However, one limitation of this paper is the absence of an analysis regarding the methodology for obtaining such a good initialization.\n\nWe would like to clarify that our contribution is not merely deriving the general distance-dependent bound (Theorem 3.1). More important results are specific time complexity bounds for the Laminar, Nested, and Box problems (Table 1), which are significant in the literature [11, 7, 39, 35, 10] as they demonstrate the possibility of surpassing the best worst-case bounds and even a lower bound [19] using predictions, as discussed in Section 1.1. To achieve those bounds, we have developed fast projection and direction-finding methods and combined them with Theorem 3.1, as discussed in Section 4. Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for further details of our technical novelty for developing those algorithms. \n\nWe also point out that the procedure for obtaining a good initialization (or learning a prediction) is covered in lines 169--187. As we have discussed there, we can use the same online subgradient descent method as [23] for our purpose, which enjoys the regret and sample-complexity bounds as stated in Proposition 3.2. \n\n> **Weakness 2.** The difficulty in deriving the corresponding theoretical results is not well elucidated in the paper. For instance, proving Theorem 3.1 hinges on Proposition 2.2, which is simply a direct application from existing works [44]. It would be more beneficial if the paper provided a clearer explanation of the technical challenges involved in obtaining the theoretical results.\n\nWe would like to re-emphasize that Theorem 3.1 is not our primary result. Our main results are the time complexity bounds for the Laminar, Nested, and Box problems, summarized in Table 1, and the core technical challenges reside in devising efficient algorithms for those problems, as described in Section 4.\n\n> **Weakness 3.** This paper lacks numerical justifications for the proposed theoretical time complexity bound.\n\nWe conducted additional experiments using Nested instances from [47]. Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for details. Results from the additional experiments, along with the original ones in Section 5, indicate that by learning predictions $\\hat x$ from more past instances to approximate optimal solutions $x^*$ better in expectation, we can reduce the number of iterations of the greedy algorithm, thus justifying our theoretical $\\\\|x^* - \\hat x\\\\|_1$-dependent time complexity bounds. \n\n> **Question.** Could the authors present concrete evidence illustrating how the theoretical bounds offer valuable insights capable of significantly accelerating the practical applications using the proposed algorithm?\n\nThe experiments in Section 5 and the additional ones in the [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) offer concrete evidence that the computational cost decreases in practice as predictions become more accurate, aligning directly with our $\\\\|x^* - \\hat x\\\\|_1$-dependent time complexity bounds. More precisely, the number of iterations of the greedy algorithm (y-axis) decreases as the number of past instances observed (x-axis) increases, where the increasing number of observed instances enables learning of predictions $\\hat x$ closer to optimal solutions $x^*$ in expectation. In essence, our theoretical bounds offer a practical implication that learning better predictions on larger datasets accelerates the greedy algorithm, which the experiments validate empirically.\n\nAs previously mentioned, Proposition 3.2 ensures that we can learn predictions $\\hat x$ that are close to the best-performing prediction $\\hat x^*$ given enough past instances. Specifically, we can use the online subgradient descent method to learn such predictions; please also refer to lines 369--372 for the learning procedure used in our experiments. "}, {"review_id": "2mlaXbCFul", "reviewer": "Reviewer_pZm4", "summary": "This paper studies some classes of $M$-convex minimization problems, to which the recent framework of \"warm-starts with predictions\" is applied. The paper provides provable time complexity bounds on the standard greedy algorithm for $M$-convex minimization where the bounds are dependent on the $\\ell_1$-distance between the optimal solution and the predicted initial solution. The theoretical performance guarantees are promising and improve upon the existing methods that are not using predictions. At the same time, however, one would argue that the technical contributions of this paper are limited in that the results rely on and are deduced by applications of the existing results in the literature. Furthermore, one would be interested to see the numerical impact of the framework on more concrete problem settings, e.g., portfolio management and resource allocation, which were not tested in this paper.", "questions": "* When testing the performance of this paper's framework against the methods without predictions, would it be fair to consider the time to compute a good prediction? Proposition 3.2 provides the regret bound by the standard online learning method, but what would be the required number of iterations to deduce the desired proximity bound on $\\|x^*-\\hat x\\|_1$? Can you compare the total time required by the framework of this paper, adding up the time for learning a good prediction and the time to solve the problem with the warm start, against the methods without predictions?\n\n* You mention that the required framework for $M^\\natural$-convex minimization is similar to that for $M$-convex minimization. Can you provide more details?", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The time complexity bounds provided in this paper are the first results that analyze the performance of the framework of warm-starts with predictions applied to $M$-convex function minimization.\n\n* The time complexity bounds improve upon the existing bounds for some classes of $M$-convex minimization problems when we may obtain an accurate prediction where the accuracy is measured by the $\\ell_1$-distance to the (unique) optimal solution.", "weaknesses": "* ​The technical contributions of this paper are limited. The greedy algorithm and main results of this paper are built upon and follow from [(Shioura (2022), Corollary 4.2)](https://pubsonline.informs.org/doi/abs/10.1287/moor.2021.1180) which gives an upper bound on the number of required iterations for the greedy algorithm in terms of the proximity term. The rest of the results are basically about bounding $T_{\\text{init}}$, the time required to convert a prediction to a feasible solution, and $T_{\\text{loc}}$, the time bound for computing a locally steepest direction. Even these results follow from standard techniques in the literature.\n\n* This paper lacks computational demonstration. $M$-convex minimization has applications in resource allocation, equilibrium analysis, and portfolio management, but none of these problems were tested. In particular, one would be interested in how well the framework of this paper performs for the operations management models studied in [(Chen and Li, (2021))](https://pubsonline.informs.org/doi/abs/10.1287/opre.2020.2070). Furthermore, the numerical results reported in Section 6 do not consider the methods against which the theoretical complexity bounds are compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments. We are delighted that the reviewer has found our improvements using predictions upon existing methods promising. We respond to each comment below.\n\n### On weaknesses\n> ​The technical contributions of this paper are limited. The greedy algorithm and main results of this paper are built upon and follow from (Shioura (2022), Corollary 4.2) which gives an upper bound on the number of required iterations for the greedy algorithm in terms of the proximity term. The rest of the results are basically about bounding $T_{\\text{init}}$, the time required to convert a prediction to a feasible solution, and $T_{\\text{loc}}$, the time bound for computing a locally steepest direction. Even these results follow from standard techniques in the literature.\n\nWhile deriving the general bound (Theorem 3.1) from (Shioura (2022), Corollary 4.2) is not difficult, our techniques used in Section 4 for bounding $T_{\\text{init}}$ and $T_{\\text{loc}}$ are not straightforward, as detailed in [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD). Specifically, we have modified the $\\mathrm{O}(n\\log^2 n)$-time convolution (Teng and Luo, 1996) to achieve $T_{\\text{init}} = \\mathrm{O}(n)$-time projection, as in Section 4.1. Furthermore, we have improved the direction-finding method of (Moriguchi et al. 2011) to achieve $T_{\\text{loc}} = \\mathrm{O}(n)$-time direction finding (where the direct use of the original one results in $T_{\\text{loc}} = \\mathrm{O}(n^2)$, as discussed in lines 311--313). Moreover, our polynomial-time projection and direction-finding methods for the general $\\text{M}$-convex case require non-trivial techniques on the base polyhedron of submodular functions, as discussed in Section 3.1 and Appendix A.1.\n\n> This paper lacks computational demonstration. \n$\\text{M}$-convex minimization has applications in resource allocation, equilibrium analysis, and portfolio management, but none of these problems were tested. In particular, one would be interested in how well the framework of this paper performs for the operations management models studied in (Chen and Li, (2021)). Furthermore, the numerical results reported in Section 6 do not consider the methods against which the theoretical complexity bounds are compared.\n\nWe conducted additional experiments using Nested instances from [47], which involve two real-world settings, project crashing (CRASH) and ship speed optimization (FUEL), and one synthetic setting (F). Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for details. Under the CRASH and FUEL settings with moderate noises, our method, Learn, outperformed the continuous-relaxation-based method, Relax, as with the results in Section 5. We believe these additional experimental results strengthen the practical side of our work and hope the reviewer will appreciate them.\n\nUnfortunately, we could not find public datasets for operation management models in (Chen and Li, 2021). Also, we employed the continuous-relaxation method (Relax) rather than the theoretically fast methods for the convenience of fair comparisons based on the number of iterations of the greedy algorithm, as detailed in [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD). \n\n### On questions\n> When testing the performance of this paper's framework against the methods without predictions, would it be fair to consider the time to compute a good prediction? Proposition 3.2 provides the regret bound by the standard online learning method, but what would be the required number of iterations to deduce the desired proximity bound on? Can you compare the total time required by the framework of this paper, adding up the time for learning a good prediction and the time to solve the problem with the warm start, against the methods without predictions?\n\nIn the literature [11, 7, 39, 35, 10], it is customary and regarded as fair to consider only the time to solve new instances when comparing against the methods without predictions; i.e., we assume predictions are given. This is because data of past instances is already provided, and learning a prediction $\\hat x$ from it is usually allowed to take much longer than the time for solving an upcoming instance. That is, only $T_\\text{init} + T_\\text{loc}\\\\| x^* - \\hat x\\\\|_1$ matters when we focus on solving upcoming instances quickly, and we learn $\\hat x$ beforehand to make $\\\\| x^* - \\hat x\\\\|_1$ small.\n\nFurthermore, in our case, predictions are learned via online subgradient descent whose *single* iteration constitutes the time for learning a prediction at each $t$ (see lines 369--371). This increase in the total computation time is negligible compared to the hundreds of iterations of the greedy algorithm (Algorithm 1) on each $t$th instance. \n\n> You mention that the required framework for $\\text{M}$-convex minimization is similar to that for $\\text{M}^\\natural$-convex minimization. Can you provide more details?\n\nThere is a one-to-one correspondence between $\\text{M}^\\natural$-convex functions of $n$ variables and $\\text{M}$-convex functions of $n+1$ variables, as described in Section 6.1 in [31]. Indeed, for an $\\text{M}^\\natural$-convex function $f: \\mathbb{Z}^N \\to \\mathbb{R} \\cup \\{+\\infty\\}$, we can construct an $\\text{M}$-convex function $\\tilde{f}: \\mathbb{Z} \\times \\mathbb{Z}^N \\to \\mathbb{R} \\cup \\{+\\infty\\}$ by setting $\\tilde{f}(x_0, x) = f(x)$ if $x_0 = -x(N)$ and $\\tilde{f}(x_0, x) = +\\infty$ otherwise for $x_0 \\in \\mathbb{Z}$ and $x \\in \\mathbb{Z}^N$. Clearly, $x \\in \\mathbb{Z}^N$ minimizes $f$ if and only if $(-x(N), x)$ minimizes $\\tilde{f}$.\nThus, we can apply our warm-start framework to $\\text{M}$-convex $\\tilde{f}$ to solve the original $\\text{M}^\\natural$-convex minimization of $f$. Alternatively, we can slightly modify our framework to deal with $\\text{M}^\\natural$-convex minimization directly without using $\\tilde{f}$. "}, {"review_id": "Ae4ha8dz3k", "reviewer": "Reviewer_NNSF", "summary": "Extending the warm-starting techniques in L-convex function minimization by Sakaue and Oki (2022), the authors study the problem of acclerating M-convex function minimization with predictions. The idea is to start from a (possibly infeasible) predicted solution, project the rounded solution to the feasible region and then apply the standard M-convex function minimization greedy algorithm. In particular, the authors show that when applied to Laminar convex minimization, a special case of M-convex function minimization, their framework can achieve better time complexity than current worst-case time complexity provided that the prediction is accurate enough. Experiments on the staff-assignment problem confirm that the proposed framework can help reduce the number of iterations of the greedy algorithm.", "questions": "The staff assignment problem does not seem to be a very realistic test problem to me (with 12800 staff members and 128 tasks). Are there more standard test problems? How does the proposed framework perform on them?", "limitations": "The limitations have been addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies an interesting problem, and is written well in terms of structure, clarity in explanation and technical presentation. Theoretical results are justified by empirical experiments.", "weaknesses": "1. The framework proposed in this paper for M-convex optimization is somewhat similar to the one in Sakaue and Oki (2022) for L-convex optimization. So novelty in the general framework is limited.\n2. The authors provide comparision between their results and worst-case time complexity for laminar convex minimization. However, it seems like their complexity outperforms the worst-case only under the assumption of highly accurate predictions (small enough $\\ell_1$ norm prediction error), which does not necessarily hold in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for providing valuable comments. Below we respond to each comment. \n\n> **Weaknesses 1.** The framework proposed in this paper for M-convex optimization is somewhat similar to the one in Sakaue and Oki (2022) for L-convex optimization. So novelty in the general framework is limited.\n\nWhile our framework for M-convex minimization, at a high level, resembles that for L-convex minimization in (Sakaue and Oki, 2022), these two classes are entirely different, as detailed in our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD). In particular, the definitions of convexity and corresponding steepest descent directions completely differ between L- and M-convex cases. Thus, new efficient methods for projection and computation of steepest directions are required, as discussed in Section 4. We hope the reviewer understands that our paper has sufficient novelty, despite the apparent similarity of the general frameworks.\n\n> **Weaknesses 2.** The authors provide comparision between their results and worst-case time complexity for laminar convex minimization. However, it seems like their complexity outperforms the worst-case only under the assumption of highly accurate predictions (small enough $\\ell_1$ norm prediction error), which does not necessarily hold in practice.\n\nAssuming accurate predictions in order to surpass the worst-case limitations is standard in the literature [11, 7, 39, 35, 10]; similar ideas are also common in the *beyond-the-worst-case* paradigm [38]. Researchers in these fields have theoretical interests in doing better than the worst-case limitations on algorithm performance by leveraging past data. Therefore, even if accurate predictions are demanded, our theoretical time complexity bounds, which potentially surpass the best worst-case results [14, 18, 19, 34, 46] and a lower-bound result [19], are of great significance. It should also be noted that our $\\mathrm{O}(n\\\\| x^* - \\hat x\\\\|_1)$-time bound for the Laminar problem outperforms the best known bound of $\\mathrm{O}(n^2\\log n \\log (mR/n))$ [18, 34] if $\\\\| x^* - \\hat x\\\\|_1 = \\mathrm{O}(n)$, i.e., every element is allowed to have a constant error on average. Surpassing the best worst-case results with such a mild assumption on prediction accuracy is rare in this context. \n\nWe also remark that if accurate predictions do not exist, surpassing the worst-case limitations is inevitably difficult. That is, if past instances exhibit no tendency, we cannot utilize them to improve algorithm performance. Considering this, as in Proposition 3.2, we aim to learn predictions that perform best on the underlying distribution of instances, hoping that such best predictions incur small errors in practice. This idea is customary in general *agnostic PAC learning*, as also mentioned by Reviewer [SFP3](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=ci542rY7dc). We will clearly state this point in our revision.\n\n> **Question.** The staff assignment problem does not seem to be a very realistic test problem to me (with 12800 staff members and 128 tasks). Are there more standard test problems? How does the proposed framework perform on them?\n\nIn response to the reviewer's question, we conducted additional experiments using Nested instances from [47]. Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for details. As with the results in Section 5, under realistic settings (referred to as \"CRASH\" and \"FUEL\"), our method, Learn, outperformed the continuous-relaxation-based method, Relax, in scenarios with moderate noises. We believe that the additional experiments adequately validate the performance of our method in practice and hope the reviewer will appreciate them.\n\n> **Limitation.** The authors admit that solving real-world instances requires tailored methods for learning predictions. Therefore, it is not clear when one can benefit from the framework the authors propose.\n\nWe would like to clarify that tailored learning methods are not always necessary. Predictions learned via standard online subgradient descent, as in our experiments, are helpful enough to reduce the computation cost of solving real-world instances, which the additional experiments also validate. We intended to express that such tailored learning methods could further enhance performance. We apologize for the misleading description."}, {"review_id": "qezLgxevq3", "reviewer": "Reviewer_KCcb", "summary": "The goal of the work is to minimize M-convex functions with prediction. The work mainly focuses on a subclass of M-convex functions that use Laminar, Nested or Box constraints.", "questions": "I have two major concerns with the work\n\n1. In section 4.2, it is clear that finding the node $j$ for a fixed node $i$ can be done in $O(n)$ time. However, I think it is not  $O(n)$ as the Dynamic programming algorithm iterates over $\\mathcal{C}(Y)$ and this is not a constant which depends on the type of laminar function. On the other hand, such a tree is much simpler for a nested case or box case.\n\n2. For the sake of clarity, I request the authors to also explain the learning predictions part even though it is the same as used in other seminal works at least in the appendix. The paper is not self contained otherwise.", "limitations": "This work would have been more complete if more efficient algorithms could be proposed for submodular constraints. This is the only reason for me to not give strong accept. Although laminar, nested and box are interesting, I believe, they have limited application scope.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Minimizing M-convex functions is an important class of discrete optimization problems that has wide variety of applications. Using algorithms with prediction is an important area of research that can typically solve many problems in discrete convex analysis. Especially due to wide variety of application.\n\nSoundness. The work is technically sound that uses relevant algorithms produced in literature to solve a very important problem.\n\nPresentation. The paper is very well written that flows flawlessly with very minor concerns.\n\nContribution. The contribution is first of its kind to the class of problems that it is applied it. However, it must be noted that most of the major algorithms used in the paper are proposed in literature. The main contribution is modification of these classical algorithms to solve the bigger problem of minimizing M-convex functions with predictions.", "weaknesses": "I dont find many weaknesses in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful reading and constructive feedback. We are pleased that the reviewer understood our main contribution and appreciated the importance of our results. Below are our responses to the comments.\n\n> **Question 1.** In section 4.2, it is clear that finding the node for a fixed node can be done in $O(n)$ time. However, I think it is not $O(n)$ as the Dynamic programming algorithm iterates over $\\mathcal{C}(Y)$ and this is not a constant which depends on the type of laminar function. On the other hand, such a tree is much simpler for a nested case or box case.\n\nWe assume, for simplicity, that the tree $T_\\mathcal{F}$ is binary, i.e., $|\\mathcal{C}(Y)| \\le 2$, as stated in lines 231--233. Thus, the dynamic programming algorithm terminates in $\\mathrm{O}(n)$ time. It should be noted that we can always preprocess $T_\\mathcal{F}$ to make it binary by adding at most $n$ dummy nodes without worsening the asymptotic time complexity. This treatment is indeed only for simplifying the analysis. Even if $T_\\mathcal{F}= (\\mathcal{V}, E)$ is non-binary, the sum of $|\\mathcal{C}(Y)|$ over all nodes $Y \\in \\mathcal{V}$ is $n - 1$ since every non-root node has exactly one parent. Thus, the total time complexity of the dynamic programming algorithm is $\\mathrm{O}(\\sum_{Y \\in \\mathcal{V}} |\\mathcal{C}(Y)|) = \\mathrm{O}(n)$ anyway.\n\n> **Question 2.** For the sake of clarity, I request the authors to also explain the learning predictions part even though it is the same as used in other seminal works at least in the appendix. The paper is not self contained otherwise.\n\nWe appreciate the reviewer's helpful suggestion. We agree with the need to elaborate further on the learning of predictions for completeness, although the procedure is the same as (Khodak et al., 2022). We will include a more detailed explanation in our revision.\n\n> **Limitation.** This work would have been more complete if more efficient algorithms could be proposed for submodular constraints. This is the only reason for me to not give strong accept. Although laminar, nested and box are interesting, I believe, they have limited application scope.\n\nWe appreciate this comment. Certainly, developing more efficient algorithms for general submodular constraints is of great significance; this is an avenue for future work. Below is our perspective on this challenge. In the general M-convex case, we obtain an initial feasible solution by projecting a prediction onto the base polyhedron of a submodular function. This process contains the membership testing for the base polyhedron as a special case, which is considered to be as hard as submodular minimization due to the equivalence of minimization and separation. Therefore,  designing a projection algorithm that is much faster than submodular minimization (or $\\mathrm{O}(\\textsf{SFM})$-time) for general M-convex minimization would be challenging.\n\nOn the other hand, our $\\mathrm{O}(n\\textsf{SFM})$-time projection described in Section 3.1 and Appendix A.1 is helpful in that it ensures the existence of a polynomial-time projection algorithm for general M-convex minimization. That is, when we consider applying our warm-start-with-prediction framework to new M-convex minimization subclasses, we know from our general $\\mathrm{O}(n\\textsf{SFM})$-time bound that the projection can be done in polynomial time. This information effectively focuses our attention on designing more efficient projection algorithms using problem-specific structures."}, {"review_id": "ci542rY7dc", "reviewer": "Reviewer_SFP3", "summary": "This paper applies the learning-augmented algorithms framework to a class of discrete optimization problems called M-convex. A function defined on an integer grid is M-convex if for every x, y it holds that f(x)+f(y) >= f(x-ei+ej)+f(y+ei-ej) for some base vectors ei, ej. The paper complements the line of research on improving running time of static algorithms using predictions, started by Dinitz et al. (NeurIPS’21), and is a natural followup to the Sakaue&Oki’s paper (NeurIPS’22) on another class, called L-convex.\n\nThe authors propose a general framework for solving M-convex optimization problems given a predicted optimal solution that is supposed to be close to the true one. Then, they give algorithms for specific subclasses of these problems, called Laminar, Nested, and Box (after the form of constraints allowed in each class). The running times they obtain are O(n*eta) for Laminar and Nested and O(n+log(n)*eta) for Box, where eta = ||x_opt - x_pred||_1 is the L1-error of the prediction.", "questions": "Could you find some real-world applications of laminar convex optimization that have existing benchmarks/datasets, and run experiments on them? (Even with some synthetic method for generating predictions.)\n\nStatement in lines 59–60 seems not accurate. For instance, the negative-weight SSSP algorithm of [7] runs in O(m) time for very good predictions, beating the best known worst-case bound by a couple of log factors.\n\nI do not agree with the statement in line 390 that you can beat best known algorithms “(...) given accurate predictions, which we can provably learn from past data.” The learnability proofs tell you that you can efficiently generate predictions as good as possible in a given context, but not that there exist predictions with small enough error. (This is a common limitation of PAC-learning framework, so I’m not complaining about your result, just about the way in which you describe it.)\n\nMinor comments:\n\nLine 26: At first it was totally unclear to me what “conjugate” was supposed to mean in this context.\n\nLine 28: “Specifically, we focus on an important subclass (...)” – this sentence is misleading as it suggests that you only focus on the subclass, which is not the case, because you address the general problem as well.\n\nLine 30: “(...) is widely studied (...)” – could you please provide some references?\n\nLine 42: Please mention that the greedy algorithm is given later as Algorithm 1.\n\nLine 101: “closet” -> “closest”\n\nLine 223: For readability, I’d consider using a colon instead of \\mid because \\mid blends with the set cardinality symbol.", "limitations": "Treating it as a theory paper, it does not have any important limitations (apart from the possibly limited impact itself). The title might be slightly misleading, since the most interesting results are only for a relatively narrow special case (laminar) and not the general case mentioned in the title (L-convex).", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "There are nice algorithms in Sections 4.1 and 4.2 (for rounding to the nearest feasible solution and for finding the steepest descent in the laminar case).\n\nWith (very) accurate predictions, the algorithm for the special case of box constraints can go (a tiny bit) below a known lower bound for classic (prediction-less) algorithms, and it seems to be the first such example in the literature about learning-augmented static algorithms.\n\nThe paper is written with care and not hard to follow.", "weaknesses": "The algorithm/framework for general M-convex optimization is technically trivial. The algorithms for the laminar subclass are much more interesting, but I’m not convinced that this subclass is interesting enough on its own for the results to have substantial implications.\n\nInteresting technical ideas seem very much tailored to the specific setup, so it might be difficult for this paper to have a larger impact or inspire further research.\n\nThe experiments are very simplistic – on a toy problem with synthetic data and predictions. (Still it was somewhat surprising to learn that, for a concentrated enough distribution of instances, an integral solution learned from previous instances can be a better initialization than an optimal solution to the fractional relaxation.) If I consider this paper to be a pure theory paper (which for now I do), then such experiments are not an issue, but in that case the theoretical contributions of the paper might not be strong enough to pass the ICML bar.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's detailed and constructive comments. We are pleased that the reviewer recognizes the technical strengths of the algorithms in Sections 4.1 and 4.2 and the significance of our result for Box, a first demonstration of the potential to surpass the lower-bound result using predictions. Below are our responses to the review comments.\n\n### On weaknesses\n> I'm not convinced that this subclass is interesting enough on its own for the results to have substantial implications.\n\nAlthough the subclasses (the Laminar, Nested, and Box problems) might not be as widely recognized in the machine learning (ML) community as the ones addressed in the literature (Dinitz et al. [11]; Chen et al. [7]; Davis et al. [10]; Polak and Zub [35]), those problems are extensively studied in operations research (OR) [18, 19, 20, 22, 30, 41, 42, 43, 46, 47] for their importance in the industrial domain. We believe our work can deliver a substantial impact by catalyzing cross-disciplinary future research between ML and OR.\n\n> Interesting technical ideas seem very much tailored to the specific setup, so it might be difficult for this paper to have a larger impact or inspire further research.\n\nAlthough the individual algorithms in Section 4 may appear specific, they stem from our general framework M-convex minimization in Section 3. This general framework tells us that efficient $\\ell_1$-projection and computation of a steepest descent direction of the form $-e_i + e_j$ are crucial for using predictions to accelerate algorithms for the broad class of M-convex minimization. This general implication could benefit future research by providing a clear direction for enhancing M-convex minimization algorithms with predictions.\n\n### On questions\n> Could you find some real-world applications of laminar convex optimization that have existing benchmarks/datasets, and run experiments on them? (Even with some synthetic method for generating predictions.)\n\nIn response to the question, we conducted additional experiments using Nested instances from [47]. Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for details. (Unfortunately, we could not find datasets for Laminar instances due to the scarcity of public datasets in this domain.) Under realistic settings (referred to as \"CRASH\" and \"FUEL\") with moderate noises, our method, Learn, outperformed the continuous-relaxation-based method, Relax, as with the results in Section 5. We believe these additional experiments strengthen the practical side of our work and hope the reviewer will appreciate them.\n\n> Statement in lines 59–60 seems not accurate. For instance, the negative-weight SSSP algorithm of [7] runs in O(m) time for very good predictions, beating the best known worst-case bound by a couple of log factors.\n\nWe thank the reviewer for pointing this out. We will revise lines 59--60 to clarify that Chen et al. [7] 's SSSP algorithm with predictions can surpass the best worst-case bound.\n\nWe would like to make two remarks to ensure that all reviewers have a correct understanding. (i) We are still the first to demonstrate the potential to surpass the *lower-bound* result [19] using predictions. (ii) Given accurate predictions, our algorithm for Laminar can achieve an $\\mathrm{O}(n)$-factor improvement over the best-known algorithm [18, 34], in contrast to Chen et al. [7] 's logarithmic improvement upon the best algorithm.  \n\n> I do not agree with the statement in line 390 that you can beat best known algorithms \"(...) given accurate predictions, which we can provably learn from past data.\" The learnability proofs tell you that you can efficiently generate predictions as good as possible in a given context, but not that there exist predictions with small enough error. (This is a common limitation of PAC-learning framework, so I'm not complaining about your result, just about the way in which you describe it.)\n\nWe appreciate this comment. As the reviewer mentioned, there is an inevitable limitation of agnostic PAC learning, i.e., even optimal predictions may not achieve small errors depending on the situation. We will clearly state this general limitation of the agnostic PAC learning framework in our revision.\n\nWe also appreciate the minor comments and will revise our title to better reflect our primary findings, as suggested."}, {"review_id": "CzMG1jdMzT", "reviewer": "Reviewer_xsf6", "summary": "In the vein of the seminal work by Sakaue and Oki for L-convex functions, this paper proposes a new method to accelerate M-convex function minimization using past predictions, a technique known as warm-start. \n\nThe contributions are as follows:\n1) Present a framework to accelerate M-convex function minimization with past predictions\n2) Applying this framework to the Laminar, Box and Nested classes of problems and improving time bounds using warm start for each of these problems", "questions": "- In figure 3, the y-axis label is set to \"Iterations\". What is the meaning of these iterations? Shouldn't this be the suboptimality gap?", "limitations": "The limitations are addressed.\nNo negative societal impact.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The results in the experiments section seems promising. Although I'm not an expert in discrete optimization, the problems tackled seemed of great importance.", "weaknesses": "1) This paper is very theoretically dense and tries to tackle a lot of problems at once, the contributions are not clear. I think this paper would gain at focusing solely on the Laminar problem and possibly present the extension of your work in appendix. The demonstration would be clearer, and your paper more straight to the point.\n\n2) Although rigorously written, it feels like this paper is a re-adaptation of the work from Sakaue and Oki to the class of M-convex functions and is thus not particularly original. \n\n3) The results section is rather light compared to the extent of the theoretical claims on the Laminar, Box and Nested subproblems. I'd have preferred for each of the 3 classes of problems you mention, a first experiment on synthetic data with comparison between warm start and no warm-start. Then, a second experiment on real-world data to prove the superiority of your method. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's valuable comments. We are glad that the reviewer found our experimental results promising. Below, we respond to each comment. \n\n> **Weakness 1.** This paper is very theoretically dense and tries to tackle a lot of problems at once, the contributions are not clear. I think this paper would gain at focusing solely on the Laminar problem and possibly present the extension of your work in appendix. The demonstration would be clearer, and your paper more straight to the point.\n\nFirstly, we would like to clarify that our contribution is two-fold.\n\n1. We present a general warm-start-with-prediction framework for M-convex minimization (as described in Theorem 3.1), and\n2. based on Theorem 3.1, we obtain specific time complexity bounds shown in Table 1 for M-convex-minimization subclasses: Laminar, Nested, and Box.\n\nIt should be noted that all our results can be interpreted in a unified manner as warm-starts with predictions for M-convex minimization. To demonstrate the versatility of this unified perspective, we have described how we can deal with those problems.\n\nAs the reviewer noted, the result for Laminar is technically the most significant (with the result for Nested following as a special case of Laminar). However, as outlined in Section 1.1, our result for Box is also crucial as it is the first demonstration in the literature [11, 7, 39, 35, 10] that the theoretical worst-case lower bound [19] can be surpassed using predictions. \n\nWe would appreciate it if the reviewer could understand the unified perspective and the significance of each result. \n\n> **Weakness 2.** Although rigorously written, it feels like this paper is a re-adaptation of the work from Sakaue and Oki to the class of M-convex functions and is thus not particularly original.\n\nOur work is not a re-adaptation of (Sakaue and Oki, 2022). Although L-convex minimization, addressed by Sakaue and Oki (2022), and M-convex minimization are nominally similar, they represent completely different classes of problems (L-convex encompasses bipartite matching, min-cost flow, etc., while M-convex includes Laminar, Nested, Box, etc.), hence named and studied separately in discrete convex analysis [31]. Consequently, our algorithms and theoretical analyses differ significantly from (Sakaue and Oki, 2022). Please refer to our [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for further details. \n \n> **Weakness 3.** The results section is rather light compared to the extent of the theoretical claims on the Laminar, Box and Nested subproblems. I'd have preferred for each of the 3 classes of problems you mention, a first experiment on synthetic data with comparison between warm start and no warm-start. Then, a second experiment on real-world data to prove the superiority of your method.\n\nWe appreciate your suggestion. We have conducted additional experiments on realistic settings provided in [47]. Please refer to the [global response](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=3iQVwbCgqD) for details. As with the experimental results in Section 5, under realistic settings (referred to as \"CRASH\" and \"FUEL\") with moderate noises, our method, Learn, outperformed the continuous-relaxation-based method, Relax. We hope the additional experimental results effectively address the reviewer's concern about the shortage of experiments. \n\nTo clarify, as explained in lines 222--224, the Nested and Box problems are special cases of the Laminar problem. Thus, our experimental results for the Laminar problem could imply similar results for Nested and Box. (Indeed, the additional experimental results with Nested instances were similar to the original ones with Laminar instances.)\n\n> **Question.** In figure 3, the y-axis label is set to \"Iterations\". What is the meaning of these iterations? Shouldn't this be the suboptimality gap?\n\nBy \"Iterations,\" we refer to the number of iterations of the greedy algorithm (Algorithm 1) taken to solve each $t$th instance, as noted in the figure caption. Thus, the experimental result should read as follows: as the x-axis increases (indicating an increase in the number of observed past instances), the prediction tends to become more accurate (as implied in Proposition 3.2), reducing the number of iterations of the greedy algorithm required to solve a new instance (i.e., the y-axis). This experimental result validates our $\\\\|x^* - \\hat x\\\\|_1$-dependent time complexity bounds, i.e., the time complexity decreases as we learn a prediction $\\hat x$ from more past instances in order to approximate an optimal solution $x^*$ more accurately in expectation."}]

Author rebuttal:
# Global response on experiments and technical novelty
We sincerely thank all reviewers for providing valuable feedback. Given the mixed reviews, we deem it necessary to begin by addressing key comments. Below, we address comments on experiments and technical novelty. 

## Experiments
First, we recap our experimental results. In Figure 3, the x- and y-axes indicate the numbers of past instances observed and of iterations taken by the greedy algorithm (Algorithm 1) to solve the new $t$th instance, respectively. Increasing x-axis values imply that predictions $\hat x$ better approximate optimal solutions $x^*$ in expectation (cf. Proposition 3.2). Our proposed method, denoted by "Learn," effectively reduces the number of iterations as the number of observed instances grows, supporting our $\\|x^* - \hat x\\|_1$-dependent time complexity bounds. 

We also emphasize that the "Relax" benchmark method is a strong competitor, which follows the same continuous-relaxation idea as the fastest method for Laminar with quadratic objectives [30]. As Reviewer [SFP3](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=ci542rY7dc) mentioned, it is noteworthy that our experiments have shown the potential to outperform Relax by using predictions. We could also implement and test other existing methods. However, while we are interested in how predictions affect the number of iterations of the greedy algorithm, other methods do not necessarily take the form of a similar iterative method, making a fair comparison difficult. Even if we were to compare based on running time, the results would be influenced by implementation and could not yield informative outcomes. 

We conducted additional experiments to address the concern about the lack of experiments with standard datasets. While public datasets are scarce in this domain, we have found that Wu et al. [47] have made their code for the Nested problem available. As in [47, Section 6.3], there are three types of objective functions: "F," "CRASH," and "FUEL." F is a synthetic fourth-order polynomial, while CRASH and FUEL come from real-world project crashing and ship speed optimization, respectively. Following [47], we obtained Nested instances with those objectives and generated $T=100$ instances by perturbing parameters defining constraints and objectives with Gaussian noises multiplied by $\sigma = 0.1, 1.0, 10.0$, which controls the noise strength. As with Section 5, we measured the number of iterations of the greedy algorithm initialized by Cold (the cold-start baseline), Relax, and Learn over the $100$ instances. 

The results are shown in the attached PDF file. For CRASH and FUEL with $\sigma = 0.1, 1.0$, Learn outperformed Relax, as with the results in Section 5. As for F, Relax performed extremely well and beat Learn, probably because the synthetic fourth-order objective is easy to handle for the continuous-relaxation method. Still, it is significant that Learn can surpass Relax for CRASH and FUEL, which come from real-world applications, under moderate noises. We believe these results effectively address reviewers' concerns about the performance of our method in practice.

## Technical novelty
Reviewers [NNSF](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=Ae4ha8dz3k) and [xsf6](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=CzMG1jdMzT) have expressed concerns about the perceived overlap with (Sakaue and Oki, 2022). Sakaue and Oki (2022) have studied warm-starts with predictions for L-convex minimization, and the high-level idea of using predictions for discrete convex minimization is similar to ours. However, M-convex minimization (which includes the Box, Nested, and Laminar problems addressed in our paper) is fundamentally different from L-convex minimization (which includes bipartite matching, min-cost flow, etc.). This is why they are named and studied separately in discrete convex analysis [31]. In particular, the definitions of feasible regions (or convex sets) and locally steepest directions entirely differ between M- and L-convex cases. Consequently, new methods for projection and finding directions for M-convex minimization are required, which we have developed for Laminar, Nested, and Box in Section 4. 

Reviewers [xgTQ](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=BpSA9YYtSV) and [pZm4](https://openreview.net/forum?id=xtQ9IGRzIW&noteId=2mlaXbCFul) have suggested that our technical contribution is limited since Theorem 3.1 is straightforward given Proposition 2.2 presented in [44, Corollary 4.2]. We emphasize that our technical contribution is not only Theorem 3.1 but, more importantly, developing fast algorithms with predictions for Laminar, Nested, and Box in Section 4 using Theorem 3.1. 
Specifically, to obtain our $\mathrm{O}(n \\|x^* - \hat x\\|_1)$-time algorithm for Laminar, we have developed

- an $\mathrm{O}(n)$-time projection method by carefully modifying the $\mathrm{O}(n\log^2 n)$-time convex min-sum convolution [45] (see Section 4.1) and  
- an $\mathrm{O}(n)$-time dynamic programming method for computing the steepest descent direction by refining the method in [30] (see Section 4.2). (The direct application of [30] costs $\mathrm{O}(n^2)$ time.)

As for Box, we achieved faster $\mathrm{O}(\log n)$-time direction finding in Section 4.3 by using the min-heap technique. While the technique is standard, this improvement is crucial for our method for Box to enjoy the potential to go beyond the lower-bound result [19] with moderately accurate predictions, as discussed in Section 1.1. Our polynomial-time projection and direction finding for general M-convex minimization in Section 3.1 and Appendix A.1 also involve substantial technical sophistication.

All in all, despite the existence of (Sakaue and Oki, 2022) and other existing studies [30, 44, 45], our work has significant technical novelty, which is crucial for the potential of our time complexity bounds in Table 1 to surpass the best worst-case and lower-bound results.

Meta-review: Summary and contributions:
======================
This paper studies an acceleration for M-convex function minimization extending recent findings from Sakaue and Oki 2022 and warm starting L-convex function minimization with predictions. 

The proposed methodology enhances pre-existing worst case time complexity and where the time-complexity bound are a function of the L1 distance between the predicted initial solution and the unique optimal solution. The authors introduced faster algorithms for laminar, nested, and box settings.

Review Summary:
=============
Two of the initial reviewers gave low confidence reviews. Alternative emergency recruiters with sufficient experience were recruited awarding the paper an accept score (7) with high confidence (4). The remaining initial reviewers awarded the paper 5/6 (borderline/weak accept) with confidence of 3. 

There is a reasonable consensus among the reviewers with common strengths being observed where the contributions (above) were identified. 

Common weaknesses included:

* CW1: A suggestion that the technical contribution is limited (i.e. an adaptation of S+O 2022)
* CW2: Lacking sufficient empirical results. Including testing on standard test sets.
* CW3: An observation that the worst case complexity depends on the accuracy of the initial predictions as the time is bounded by the L1 distance of initial and optimal solutions. 

Responses from the authors addressed these concerns resulting in the reviewers increasing their scores. 

* CW1: The authors rebuttal stated that their technical contributions is not only limited to the solution distance complexity (Thm3.1), but also algorithm speedups for O(n) time projection method for convex min-sum convolution (S4.1) and O(n) DP method for computing steepest descent direction (S4.2).

* CW2: Authors provided additional experimental results for the nested problem from Wu et al.[47] with F, FUEL and CRASH objective functions during the rebuttal phase.

* CW3: I believe this observation to be a non-issue. The corollary of this is that with very accurate predictions, the performance may exceed lower bound of classical optimization algorithms.


Reason for decision:
=================
Consistent reviews 5,6,7,7 with confidence 3,3,4,4. Most weaknesses addressed resulted in reviewers increasing scores.
Decision: Accept (poster)