Parallel Submodular Function Minimization
Authors: Deeparnab Chakrabarty
Andrei Graur
Haotian Jiang
Aaron Sidford
Venue: NeurIPS 2023 spotlight (2023)
Keywords: parallel computation
convex optimization
submodular function minimization

Abstract: We consider the parallel complexity of submodular function minimization (SFM). 
    We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function defined on subsets of $n$ elements that has integer values between $-M$ and $M$. The first method has depth $2$ and query complexity $n^{O(M)}$ and the second method has depth $\widetilde{O}(n^{1/3} M^{2/3})$ and query complexity $O(\mathrm{poly}(n, M))$. Despite a line of work on improved parallel lower bounds for SFM, prior to our work the only known algorithms for parallel SFM either followed from more general methods for sequential SFM or highly-parallel minimization of convex $\ell_2$-Lipschitz functions. Interestingly, to obtain our second result we provide the first highly-parallel algorithm for minimizing $\ell_\infty$-Lipschitz function over the hypercube which obtains near-optimal depth for obtaining constant accuracy.

Parallel Submodular Function Minimization
Deeparnab Chakrabarty' Dartmouth College Hanover, USA
Andrei Graur Stanford University Stanford, USA
Haotian Jiang Microsoft Research Redmond, USA jutddavid660gaiil.oom
deeparnabllartmonhh.eem
agraur@stanford.c
Aaron Sidford Stanford University Stanford, USA sidfordestanforr ord. edu
Abstract
We consider the parallel complexity submodular function minimization (SFM). We provide a pair of methods which obtain two query versus depth trade- offs a submodular function defined on subsets of n elements that has integer values between -M and M. The first method has depth 2 and query complexity n ((1d) and the second method has depth ((nt///2/// and query complexity (poly(n, M)). Despite a line of work on improved parallel lower bounds for SFM, prior to our work the only known algorithms for parallel SFM either followed from more general methods for sequential SFM or eaghll-paaallel minimization of convex Ei-Lipschitz functions. Interestingly, to obtain our second result we provide the first highly-paralle paraalel algorithm for minimizing -Lipschhi function over the hypercube which obtains near-optimal depth for obtaining constant accuracy.
Introduction
function f n is submodular if it has the diminishing marginal return property that U - f(S) 2 ((TU()) f(")) for all elements E [n]] and subsets S C T C [n]] {i}. ie.. the function value increase of adding to set S is at least that of adding i superset that does not contain i. Submodular functions are used to model a range of problems arising machine learning [KG05, KNTB09, KC10], operations research [FG88, QS95], and economics [TTpp98). The submodular function minimization (SFM) problem consists of finding the subset S with the smallest S(S), given evaluation oracle access
submodular function f. using as few queries as possible. SFM has numerous applications. For example, in natural language processing SFM has played key role in speech analysis where [L.B 1, JB11] modeled the task of optimally selecting terse, yet diverse, training data out of large speech dataset as SFM problem; in computer vision, the task of energy minimization was reduced SFM VB01, KKTOS, KT1O, JBS13, KBJ+15)
Seminal work of [GLS8]] established that SFM can be solved with polynomial number of queries and in polynomial time. In the decades since, there has been extensive research characterizing the query and computational complexity of SFM. When f is integer valued with values between
"Supported in part by NSF grant #2041920.
'Supported in party by NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, and Stanford Management Science & Engineering Department Nakagawa Fellowship
'Supported in part by Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant (CCF-195505 PayPal research award, a Sloan Research Fellowship.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

-M and M, the state- thr query complexities are Ö(nM33t due to [CLSW17] and [ALS20], Ö(n² log M) and ((n²), both due to [LSW15] (the latter query complexity being improved by factor of log" n in [Jia2[]), and On log n) (with an exponential runtime) due to [Jia22]. The largest
query complexity lower bound is 22 log for deterministic algorithms due to [CGJS22].
The algorithms underlying the above results are highly sequential. State-of-the-art SFM algorithms use at least linear number of rounds of queries to the evaluation oracle (O()M2 rounds in [ALS20] and On log n) rounds in [Jia22]). Although there is a trivial 1-round algorithm that queries all 2 input of f in parallel, all known polynomial time SFM algorithms use (())) rounds.
With the prevalence of parallel computation in practice and applications of SFM to problems involving massive data sets, recently there has been an increasing number of works which study the parallel complexity of SFM, i.c., the smallest number of rounds a SFM algorithm must take. Starting with [BS20], significant progress has been made in proving lower bounds on the parallel complexity of SFM. It now known that any SFM algorithm making polynomially many queries needs (((1/s) rounds when M (n) [CCK21] and (()) rounds when M = ((n") [CGJS22].
In contrast to the significant progress on lower bounds, less progress has been made on designing SFM algorithms with small parallel complexity. This is due in part the established lower bounds; as noted above, if we desire range- segge-ideeeedennt parallel complexity bounds, i.e., independent of the range M. then it is impossible The central question motivating this paper is what non- iointrivial parallel speedups for SFM are possible if we allow methods with a range- dependennn parallel complexity.
obtain an O(n ((n)-))-round --rund SFM algorithm, for any constant > O.
Is it possible to obtain query-efficiett -rouud M M-dependent algorithms for SFM?
In this paper we provide positive answers to the above question. Our first result is an algorithm that runs in (22/3M2233 rounds with query complexity Ö(n To achieve this result, we first provide a generic reduction from parallel SFM to parallel convex optimization (a well studied problem discussed below). While naively this approach yields sublinear bound of (nn233 rounds, we show how to further improve these convex optimization methods in our setting.
Our second result is simple 2-round SFM algorithm (Algorithm 1) with query complexity n ((M). For constant M, the parallel complexity of 2 is optimal among the class of query-efficient algorithms that query the minimizer [CLSW17] 17]. It is instructive to contrast second result to the lower bound in [CCK21], where it is proved that when M n, any algorithm with query complexity n nM for any constant 8 > 0 must proceed in n (()) rounds.
Highly Parallel Convex Optimization. Motivated by applications to distributed and large scale optimization [BPC 11, GRI8]. the question of highly parallel convex optimization has received significant attention in the last decade. Formally, the task is to find an (approximate) minimizer of a convex function this is Lipschitz in some norm, using as few rounds of (ppoy((n)) parallel queries to a subgradient oracle as possible. Over the past few years, there has been progress on both upper [DBW12, SBB+ + 18, BJL + 19] and lower bounds [Nem94, BS18, DG19] for this problem.
This line of work is particularly relevant as SFM reduces to minimizing the Lovász extension (see Fact 2.4) [Lov83] over [0, 1]", which is convex and O --ipschhtt in lo (see Definition 2.1). In Section 2.1 we provide a straightforward reduction from this problem to unconstrained minimization of OLL)-Lipshitz function in Lo where the minimizer has Loo norm (1). Consequently, improved parallel & Lipschitz convex optimization algorithms can imply improved parallel SFM algorithms.
Many prior algorithms for highly parallel convex optimization focused on convex functions that are f-- Lipschitz and some were written only for unconstrained optimization problems. Naively using these algorithms for foo yields parallel complexities of ((n3///e) [DBW12] and 0(n2/3 /2/3) [BJL*19 19, 2 for convex functions that are lo Lipschitz.
Our first SFM result follows from an improved algorithm that we develop that finds a-pproxiimaee minimizers for convex lo -ipschitz functions in 0 rounds. Interestingly, for constant in this improved parallel complexity is optimal up to logarithmic
0, the dependence
'Throughout, use (n) to hide poly f (n), log n) factors. $1BJL+19. 19. CJJ+23] study the la setting. To obtain the corresponding 0(n2/8/22/3) result for fxc, we combine their result with Lemma 2.3 given in this paper.

---

factors; [Nem94] proved a lower bound of 22(n' 1/3 In(1/E)) on the round complexity of any algorithm
obtaining an e-approximate minimizer over [0. 1 for -Lipschtz convex functions. For constant & > 0, this lower bound also applies to unconstrained fx -pptimizziioon [DG19].
Paper
Year
Parallel Rounds
Paper Subgradient Descent
Year
Parallel Rounds
[ALS20]
2020
((nM²)
1960s
O(n/c²)
[JLSW20]
2020
Oon M)
Cutting Plane
1965
O(nlog(1/e)
[Jia22]
2021
((n)
[BJL+ 19, CJJ+
2019
0(1213
This paper
2023
O(n
This paper
2023
O(n2/3/e2))
Table I:
State-of-the-a parallel complexity for SFM and lo opptimizzzni.n. See Section 1.2 for references on cutting plane methods. *The (12 /62/3) result uses Lemma 2.3 from this paper.
Notation. We let [n] := (1....,,)) n for any n E Z We let I, denote the identity matrix in R"x*.
1.1 Problems, Results, and Approach
Here formally define the problems we consider, present results, and discuss some of the key insights of our approach. This section is organized as follows. We begin by presenting the parallel computation model. Then, which is closely tied to parallel SFM. We present our improvement for the &oo -Lipschit setting and offer brief overview of our techniques in obtaining this result. Finally, we formally introduce the SFM setup, along with the new results we obtain (Theorem 1.3 and Theorem 1.4).
introduce the parallel Ep-Lipschitz convex optimization problem,
Parallel Complexity Model. We consider the standard black-box query model for optimization, where we are given a convex function f : D - R. with domain D C RR, accessed through an oracle. Parallel algorithms for minimizing f proceed in rounds, where in each round the algorithm can submit a set of queries to the oracle in parallel. The parallel complexity of an algorithm the total number of rounds it uses and it captures how "sequential" the algorithm is. Additionally, consider the query complexity of an algorithm which is the total number of queries makes.
Parallel Ep L-ppichcttz Convex Optimization. In Section 2 we consider the problem of minimizing convex function ʃ Rh' + R given access to a subgradient oracle g : IR" + R", which when queried
with point v E Rh' returns a vector g(x) that is a subgradient, denote g(x) E ((f(x)) where (()()))
is the set of all subgradients of f at æ, i.e., u E Of(r) if and only if f(y) 2 f(x) 0 (y - 2) for all
y E RR... Furthermore, we assume that f is L--Lipschizz with respect to norm ||-11-
Definition 1.1 (L-Lipschitzness with respect to given norm). We say that f R + R L- -|x
Lipschitz with respect to ||.|| for norm ||-|| if lfxx) - -[()] & L [|]x- yll for all x. y E RD. If is O(p)-Lipsehitz with respect to norm I1- we say that f 1-Il-iipschitz When the norm is I|-Ilp
alternatively say that is L-Lipschitz in lp and that is f Ep-Lisschitz respectively.
There is a broad line of work on studying the parallel complexity of Ep-Lipschitz convex optimization in which the goal is to efficiently compute e-approximate minimizer (i.e., a point y with fly) S inf, f fx)) of a L,-Lipschitz convex function where the minimizer either has l, norom O(1) or the problem is constrained the f,-norm ball of of radius O(1). The case when p 2 is perhaps the most well studied and our new result regarding Eoo- -liscchit convex optimization builds upon a result in [CJJ+ (3), Theorem 1, which considers this setting. The statement of our result is below:
Theorem 1.2 (Parallel Convex Optimization in foc)) There is an algorithm that when given subgradient oracle for convex f : RR. - R. that is 1-Lipschitz loo and has a minimizer v., with || S 1 computes an e-approximate minimizer of f in queries.
rounds and Ö(ne-
In fact, we obtain a more general result that solves stochastic variants of parallel for opttiiiiziiionnn (see Theorem 2.2) and Theorem 1.2 is an important corollary of this more general result.
Our parallel convex optimization algorithms build on machinery developed for highly Spapallll algo- rithms for minimizing convex functions that are fg-Lipschitz. These methods consider a convolution of f with a centered Gaussian with covariance ILI, (also referred as Gaussian smoothing), and then apply optimization methods [CJJ+23, ACJ 21, BJL + 19] to this smooth function. By leveraging
3

---

the properties of this smoothing and the convergence rate of the associated optimization methods, they obtain their parallel complexities. Since functions which are 4x -iipshhtzz are also fz-Lipschitz, the above algorithms also apply to - functions but they give us a suboptimal dependence of n223 on the dimension. We improve the dependence on dimension by utilizing the L--Liipcchitzness of our function to add more Gaussian smoothing. This allows us to obtain a n 1/ dependence on the dimension, which is optimal up polylogarithmic factors for constant [Nem94, DG19]. The key observation is that convolving an l < function with a Gaussian of covariance ILIn changes the function value by more than (gyylogg ni) (see Lemma 2.6), whereas for fn-Liipshitz functions it could change the function value by O(p/n).
Submodular Function Minimization. In SFM, we assume the submodular function f 2/nl + Z is given by an evaluation oracle, which when queried with S S [v], returns the value of S(S). Throughout the paper, we assume that f(S) E [-M, M for some M E Z and (0) = 0. The assumption that f0) = 0 can be made without loss of generality by instead minimizing f(S) = f(S) - f(): this transformation can be implemented with one query and moves the range of by at most MM, turning any dependence on M in an algorithms' complexity to 2.M.
Note that this submodular function minimization setup is different from the setup of parallel convex optimization, as f only defined on the vertices of the unit hypercube. Nonetheless, it is known that there is convex function fLoy defined on [0, 1]". known as the Lovasz Extension, such that optimizing Lov suffices for optimizing f. Additionally, it is known how to compute a subgradient of (as highlighted in Fact 2.4).
fLov at any point in 1 round using at most n. evaluation queries
Now, we are ready to present our first result on parallel SFM. Later, Section 2.1, we provide a more general version of this theorem, Theorem 2.5, which gives improved parallel complexities for approximately minimizing bounded, real-valued submodular functions.
Theorem 1.3 (Sublinear Parallel SFM). There is an algorithm that, when given an evaluation oracle for submodular f 2(m) + with f(0 = O and [f()] S M for all S S [n], finds a minimizer of f in /3 rounds and 2 queries.
As discussed, Theorem 1.3, is obtained by using and enhancing tools for optimizing Lipschitz convex functions with a subgradient oracle. We in fact prove a more general result, namely that On /2/3 rounds and Ō(n²/e²) queries are sufficient to find an e e--approximate minimizer (Theorem 2.5). Since the function is integer valued, approximating the scaled Lovász extension to R 0(1/M gives the exact minimizer to the submodular function. Our proof of Theorem 2.5 follows from our new result on -covvxx optimization (Theorem 1.2). By applying it to a scaled version of the Lovász extension; it is known that if f is submodular function with range E n [-M, +M), then the Lovász extension scaled by O(1/M) is a convex function which is -Lpischhii However, is important to note that SFM is only equivalent to constrained minimization of the Lovász extension in [0. 1]", while Theorem 1.2 below is unconstrained (e.g. applies for minimizing over RT). To apply Theorem 1.2 in the context of SFM, we give a general reduction from constrained to unconstrained optimization by adding regularizer that restricts the minimizer of the regularized function to the constrainted set (see Lemma 2.3). This reduction is generic technique and might be of independent utility.
Parallel SFM in Two Rounds. Our second SFM result is a simple combinatorial 2-round algorithm which is efficient for functions of constant range.
Theorem 1.4 (Two-round Parallel SFM). There is an algorithm (Algorithm 1) that when given an evaluation oracle for submodular f 2 + Z with [(0) = and [S()) S M for all C (n] minimizer of f in 2 rounds and M11) queries.
The algorithm proving Theorem 1.4 relies on two key observations. First, if S, is the minimizer of maximum size, for every subset T C S. and i E [n] with fTT U (i)) < f(T), we have i E S.. In other words, every element with non-positive marginal at a subset T C S is also contained in S.. This leads to the idea of augmenting set T by the set T = TU {i f(T (2)) < f(T)). Secondly, every subgradient y E af(x) has at most M entries that are strictly positive. This ensures that there exists an M-sparse subset T C S. with the property that S(T U (i)) < f(T) forall E S. \7. Consequently, our algorithm proceeds by augmenting all M-sparse sets, as is guaranteed that one of these augmented sets is the maximal minimizer (see Section 3 for more details).

---

1.2 Related Work
Parallel Convex Optimization. As mentioned in Section 1.1, there are a number of works study- ing the parallel complexity of fp-Lipschitz convex optimization. Perhaps, the most well-studied case is that of p 2. In this case, the classic subgradient descent algorithm achieves a parallel complexity of O(= )(o=n)- -rounds and the standard cutting- -plane methods achieve a parallel complexity of (n loggl/gg(ggg/ (1/)))
[DBW12, BJL*19 19, C3]+ improved upon this rate, achieving parallel complexities of ((n [2] and ((n implications of these results for the p case, which is the object of study in our paper, were discussed earlier and we are unaware of works on alternative upper bounds for p 0c.
[BJI. CJJ+ respectively. The
In terms of lower bounds, the obtains 0(n In(1/=)) lower bound for minimizing fo -Lipschhitz functions over the bbll (see also [DG19I). When E is a constant, our upper bound matches this lower bound, though our dependence on is polynomial instead of logarithmic. For the p 2 case, [Nem94, BS18) proved a tight lower bound of ((1/=²) on the parallel complexity when 1/e²² - (O(n/3).i.. i.e. the parallel complexity of subgradient descent is optimal up to (mn//3) rounds of queries. This was later improved by [BJL 19]. which showed that subgradient descent is optimal up to (nn rounds. [DG19] considered the general p case (and other non- -uclidend settings) and proved a lower bound of (s lower bound on the parallel complexity for 2 S < 0o, (2s=2) for 1 < S 2, and ((=-2/3 2/3) for p = 1. This paper also has lower bounds for smooth convex functions.
case was studied in the prescient paper of [Nem94] which
Submodular Function Minimization. We now expand on the history of SFM upper and lower bounds for parallel and sequential algorithms touched upon earlier. Since the seminal work of Edmonds in 1970 [Edm70], there has been extensive work [GLS81, GLS88, Sch00, IFFO1, Iwa03, FI00, Vyg03, Or109, IO09, I.W15, CLSWI7, ALS20, DV721, Jia21, Jia22] on developing query- efficient algorithms for SFM. [GLS81, GLS88] gave the first polynomial time algorithms using the ellipsoid method. The state-of-the-an art SFM algorithms include a Onur)-query exponential time algorithm due to [Jia22], )query polynomial time algorithms due to [I.221,11.S7233,, a Ónn log M) - polynomial time algorithm due to [LSW15], and a O(n.M))-quer polynomial time algorithm due to [ALS20]] Despite these algorithmic improvements, limited progress has been made on lower bounding the query complexity of SFM and the best known lower bound has been (nn) for decades [Har08, CLSW17, GPRW20J. Very recently, [CGJS22] proved an 2(n log n) -looer bound for deterministic SFM algorithms.
All the algorithms above are highly sequential and proceed in at least rounds. The question of parallel complexity for SFM was first studied in [BS20] where an M(log n/ log log -lower bound on the number of rounds required by any query-efficient SFM algorithm was given. The range M in their construction is M = n (m), Subsequently, [CCK21] proved a 2( lower bound on the roumd-complexity and the range is M for their functions. Recently, [CGJS22] described ((2)
lower bound with functions of range M = n (n))
Cutting plane methods. Cutting plane methods are class of optimization methods that minimize convex function by iteratively refining a convex set containing the minimizer. Since the center of gravity method was developed independently in [Lev65, New65], there have been many developments of faster cutting plane methods over the last six decades [Sho77, YN76, Kha80, KTE88, NN89, Vai89, BV04, LSW15], with the state-of-the-art due [JLSW20].
2 Minimizing loo -Lipschitz Functions and Submodular Functions
In this section we provide a new, improved parallel algorithm for convex optimization in Eoo and show how to use these algorithms to obtain an improved parallel algorithm for SFM. In much of this section, we consider the following optimization problem which we term stochastic convex optimization in fxc As we discussed, this problem generalizes parallel convex optimization in f.x. The problem is more general in terms of the norms it considers and how it allows for stochastic gradients; we consider it as it could be useful more broadly and as it perhaps more tightly captures the performance of our optimization algorithm.
5

---

Definition 2.1 (Stochastic Convex Optimization in foc). In the stochastic convex optimization in So problem we have a (stochastic) subgradient oracle g I + R" such that Eg(z) 0f(z) and El1g(2))12 I o² for a convex function f IR"" + that is L-Lipschitz in & Given the guarantee that f has minimizer E I with || 2l S R. our goal is to compute E-approximate minimizer of f. i.e. 2 E IR" with f(x) - f(x.) +
Note that in Definition 2.1, foe appears only determine the norm in which f is Lipschitz. However, the bound on I, in & that can be easily converted to one in terms of & by using that ||x ll2 S v ||x=- Furthermore, convex function f: I + R is L--Lipschitz in tso and only if ||g|| I S for all g ((x) for R Since ||g/12 S |اا|| problem subsumes the (non-stochastic) problem of computing an E-approximate minimizer to a convex function that is L-Lipschitz in & given (deterministic) subgradient oracle. We define this more general problem as, interestingly, our algorithm tolerates this weaker stochastic oracle without any loss (as we discussed).
that this stochastic convex optimization
Our main result regarding stochastic convex optimization in & is given in the following theorem. Theorem 2.2 (Stochastic Convex Optimization in lzo). There is algorithm that solves the stochastic convex optimization problem (Definition 2) )) in 8.c. (Definition 2.1) in (((LR/e)2/3) rounds and ((())/))²) queries.
Due to the aforementioned connection between foo -ipschitz continuity and bounds on the sub- gradient, and the fact that ||== I implies 1| S vn, Theorem 2.2 immediately yields a O(n1/3g-2/3, -round, O )-qeery that 1-Lipschitz in Eo and minimized at a point with -nrm at most 1. As discussed in the introduction, the parallel complexity of this algorithm is near-optimal for constant [Nem94].
(query)- algorithm for the problem of minimizing a convex function
Theorem 1.2 (Parallel Convex Optimization in lxc). There is an algorithm that when given a subgradient oracle for convex f IR" - R that is 1-Lipschitz in loo and has a minimizer I., with || 1 computes an e-approximate minimizer of f 0(n2/3g rounds and O(ne-2) queries.
In Section 2.1, we show how use Theorem 2.2 obtain our results for SFM. We then present the ingredients in the proof of Theorem 2.2 (which we defer to Appendix A) in Section 2.2. As part of our reduction from SFM to Stochastic Convex Optimization in Loo Theorem 2.2, we provide general tool for reducing constrained to unconstrained minimization (Lemma 2.3); we use this lemma to facilitate our results both sections.
2.1 From Unconstrained Convex Optimization in fo to SFM
Here we show how to use Theorem 1.2 to prove the following theorem regarding SFM.
Theorem 1.3 (Sublinear Parallel SFM), There an algorithum that, when given an evaluation oracle for submodular f 2(m] + Z with f(0) = 0 and [f)] < M for all S C [n], finds a minimizer of f in 33333332/33 rounds and Ó 2 queries.
key ingredient of our proof is the following general, simple technical tool which allows one to reduce constrained Lipschitz optimization with only a very mild increase in parameters.
a ball in any norm unconstrained minimization
Lemma 2.3. Let I + be convex and L-Lipschitz with respect to norm ||+|| R" + R. For any c, x E 12" and r E IR let
(2g(2) == f(x) + 2L max (0, || cll - r).
(1)
Then (er(x) (I) is convex and -ipshich with respect I1-11- Additionally, for any y RD for which lly cll r, define yorr + パリーس (y c). Then,
yyy - cll = and fog (vf f(y (w)(w) - L -l)
-).
(2)
Consequently, fag (x) has an unconstrained minimizer x. and all such minimizers satisfy
|| 1 - c| S r and faa (x = =((4*)=
min x || f(x).
(3)

---

Lemma 2.3 implies that minimizing f subject to a distance constraint ||2 - cll S reduces to unconstrained minimization of for More formally, to compute an e-optimal solution to the con- strained minimization problem, mingeR" |e-ol] fx)), suffices to instead compute an e-optimal solution, Ze,, the unconstrained minimization problem min, freg (ar), and then output that point zg if ||0e -cl S r and output of -otherwiie... From (2), get (x= freg (zie) S opt + E, where opt min, Frag (z)
=R= fax) and the last equality follows from (3).
We remark that the 2L in the definition of freg can be changed to L + for any å 2 0 with the only effect of turning the L in (2) to ó and causing (3) to only hold for some minimizer (rather than all) if The proof of Lemma 2.3 deferred to Appendix A.
Next. we obtain Theorem 1.3 by applying Theorem 2.2 to the Lovász extension of the submodular function f extended an unconstrained minimization problem by Lemma 2.3.
Given a submodular function f defined over subsets of an n element universe, the Lovász extension fLov Rn IR is defined as follows: fLov()) Eiejn] Zxx (fS ((S),.i-))). where Tx [n] - [n]] is the permutation such that (1) 2 Ux, (2) 2 2 (n.(n) (ties broken in an arbitrary but consistent manner), and Sa.. the subset {T (1), ...., TT ())
Next we give standard properties of the Lovász extension and use them to prove Theorem 1.3.
Fact 2.4 (e.g.. [GLS88, JB11]) The following are true about the Lovász extension fLov
1. foov is convex with minze]o.1]= (L) minscy f(S). Indeed, given any E [0, 1]", in n queries one can find subset S with f(S) S [o)(x))
2. Given any x E IK and corresponding permutation Tas the vector 9 E R" where ((()) := (( -[(S=_a-1) is subgradient of fLo at Furthermore, g(x) can be computed in 1 round of n queries to an evaluation oracle for f.
3. f f has range in [-M, +M), then the ---oorm of the subgradient is bounded, in particular, [[(x))]| S 3M. Equivalently, fLov is 3M -ipschitzz with respect to the &e norm.
As discussed in Section 1.1, prove Theorem 1.3, it suffices prove the following more general result regarding approximately minimizing a submodular function.
Theorem 2.5 (e-approximate minimizer for SFM), There is an algorithm that, when given an evaluation oracle for submodular f: 2 + R with minimizer 2., f(0) = and [f()] S M, VS c [n), finds a set S with f(S) < f(x.) + eM in (/n2/3/2//)) rounds and a total of Ó(e (e2) queries.
Proof of Theorem 2.5. By Fact 2.4, SFM reduces to minimizing fLov over x E [0. 1 which is the same set {x E R || cl 0.5) where is the n-dimensional vector with all entries 0.5. do by applying Theorem 2.2 to the regularized version fa..5 of fLov
By Lemma 2.3, with respect to the lo--non -norm. This regularized function is guaranteed to have a minimizer x, with ||=.1|2 S Vni which also minimizes fLov in J0, 1]". The subgradient of this regularized function at any point can be computed from the subgradient of fLo at the same point which takes n evaluation oracle queries the submodular function. Hence, obtain an -appprxxima minimizer in 0/3//3//2/3) rounds and with a total of (n2//=?) queries to the evaluation oracle of f.
Now, we ready prove Theorem 1.3.
Proof of Theorem 1.3. Set = 2M and apply Theorem 2.5 to obtain, in Ö(n M2233 rounds and with total of Ö(n² 22 queries to the evaluation oracle of f. a E [0, 1]"h with (a) < mingeeoo.1j" fLow(2) (z) + 3. Then by property in Fact 2.4, one can get a subset A C V with f(A) <
minsgv S(S)+ + 2- As f is assumed to be integer valued, A must be the minimizer of the submodular function.
2.2 Parallel Stochastic Convex Optimization in txx
Here we present the key steps in proving Theorem 2.2 regarding our new parallel results for the stochastic convex optimization problem fox (Definition 2.1). Throughout this subsection, in our exposition, lemma statements, and proofs assume that we are in the setting of Definition 1.
7

---

To prove Theorem 2.2 we apply the approach of [CJJ*23] with two modifications. First, we consider the convolution of f with centered Gaussian density function with covariance p' However we show that in our setting, it is possible to use larger value of / without perturbing the function value too much, due to the lor geometry. Unfortunately, the minimizer of the convolved function may move outside the box of radius R. Thus, the second modification we make is working with regularized function, freg, which is pointwise close to f. still L-Lipschitz in the lo norm, and keeps the minimizer in the ball or radius It even after applying the convolution with a Gaussian.
In the remainder of this subsection we first present the ingredients going into the proof of Theorem 2.2, and then give brief explanation for how they fit into the proof of Theorem 2.2, deferring the complete proof to the appendix. We start with our bound on function perturbation after adding a Gaussian with covariance I'I, to an bo Lipschitz function (Lemma 2.6). We then introduce the concept of a ball optimization oracle, along with a result on how to implement it in low depth for the special case of function that is the result of Gaussian convolution (Proposition 2.8). Lastly, we present the result which allows us to use a ball optimization oracle black-box obtain the desired depth (Proposition 2.9).
Now, we are ready to present the lemma which allows us obtain better dependence of depth on the dimension n, compared to the naive 2/ obtained by directly applying the Ez-Lipschitz optimization result. We start with the definition of Gaussian convolution.
nn/2 exp(- [|=] be the probability density function Gaussian Convolution. Let % := (2mp) -n/2
of p') Given a function f : R" + R. we define its convolution with a Gaussian of covariance I'I, by fp == f* %pp i.e.
[d(x) B (s v)]
/ f(x f(x (( R2
(4)
Next, we present a lemma which allows us to obtain better dependence on the dimension n in depth, compared to the naive n²23 obtained by directly applying the Ez-Lipschitz optimization result. This lemma shows that we can perform more Gaussian smoothing (as compared to the fe-setingg) without perturbing the function too much (as mentioned in Section 1.1).
Lemma 2.6 (Gaussian Convolution Distortion Bound for lxc). Let f : R" + R be L-Lipschitz with respect to the Eo norm. Then for any point x E R", we have (f)(z) - f(x) S Lp v2 V2logg n.
Proof. Note that (f)(x) f(x)) s Ja-115(5 f(x))/( 2)dz < T. fz- x =1100 7/(x 2 2)d= where the first inequality follows from the definition of f, and the second follows as f is L-Lipschitz in lo norm. The RHS is simply the expected -nom of zero-mean random Gaussian vector with covariance L²n,, and this is ((pVlog n) (c.g., [Ver18]) More precisely, we get
(z))) - f(x)( S L Ey-,(O,FPL.)) |vll.c S Lp- /2log
As mentioned in Section 1.1, by contrast, convolving a function ff 'that is L- L-Lipschitz in & with Gaussian of covariance I²I,, could change the function value by ((p/n). Hence, the loo geometry allows us to add larger amount of Gaussian smoothing without changing the function value by more than E, which in turn allows for better rates.
Ball Optimization. A subroutine that we use for minimizing So is called ball optimization oracle. As suggested by [C], the concept of ball optimization oracle is related to the notion of trust regions, explored in several papers, such as [CGT00]. The particular ball optimization procedure we employ takes a function F : R" + IR and point き E R²", which is an approximate solution to F in small ball of x. More formally, we work with the following definition:
Definition 2.7 (Ball Optimization Oracle [C]]+ Let F P: R. + IR be a convex function. Ozo an ( X, -balll optimization oracle for if given any & E TR.", it returns an x. E Rg with the property
E
F(x)
+ 2
X
|| - 212
-
& F(
+ 2
> |1atoe - x1l2 + $.
where oio = arg min B, (F(x) + || =
8

---

From [CJJ 20] it is known is that for any Lipschitz convex function f. any stochastic subgradient oracle g as above, and any p. if we set p. then efficient ball-optimization oracles exist. More formally, we use the following proposition from [C]J+23] which is in turn inspired from [ACJ+21].
Proposition 2.8 (Proposition 3, [CJJ+ 23]). Let f I= + R be convex and R" + R" be stochastic subgradient oracle satisfying Blg(x)) E (x) and EE (1)(2))l2 2 S o² for all E R.. Let
Fp = ff* 7pp i.e.,
Tolx) = By y)) f (la-vyrolydde
(5)
Then there is a (Ø, A, pb-ball optimization oracle for Fo which makes ( total queries to g in constant number of rounds.
Highly Parallel Optimization. As shown in [CJJ+23], the ball optimization oracle above can be used for highly-paralin optimization as follows.
Proposition 2.9 (Proposition 2 in 23]). Fix function F R2 - I which is L-Lipschitz with respect to the f2-norm and convex. Suppose R 2 0 is parameter such that x² E arg ming F(x) satisfies |æ=1|2 S R. Let r E (0, Rt and Eopt E LR) be two parameters. Define the following quantities
LR
R (7)) (#)
Copt K2 log K.
K
= K K:
and X,
(6)
Copt
R²
Then, there exists a universal constant C > O and an algorithm BallAccel which runs in CK log iterations and produces a point x such that (EF(x)) F(x*) + Copt- Moreover,
1. Each iteration makes most C' Colog R calls to Ar² , r.rr-balll optimization oracle with values
of X
->= CL)
Eapt
2. For each j E [oog2 K + CT,, at most C 2 log(
Rs log 1og-2((0x)) r--blll optimization oracle for some X E 12 CL
iterations query a C22
Ar
fepe
While the proof of Theorem 2.2 deferred to Appendix A, we provide some intuition for how to use the stated components to obtain the result. A natural approach would be apply Proposition 2.9 to F fp. However, ensure that the minimizer of I has fn-m at most R, we will instead work with F = fea as defined in Lemma 2.3. The idea is to invoke Lemma 2.3 and apply BallAccel on the function F == Fro with respect to 11-112- c being the origin, and p T.v2log With this choice of p, by Lemma 2.6, we know [F(x) freg f=)[(()) S Copt everywhere. Noting that F has a minimizer J. with ||x: l| I 3R, this enables us to apply Proposition 2.9 to F, obtaining the stated bounds on the number of rounds and query complexity.
Kap.
3 2-Round (n -uuery Algorithm for SFM
algorithm for SFM. The algorithm AugmentingSets, given in A Algorithm iterates over every M-sparse S C [n] (i.e. |S| & M) (denoted F). For every such 5 the algorithm then builds the augmented set A(S), consisted the union of S and all elements i that have non-positive marginal with respect to S, i.e., fSS U (i) I f(S). The algorithm then outputs the set A(S) that has the smallest value.
Here we present our 2-round,
As show below, computing all the A(S) for M-sparse sets S can be done in 1 round and O(n queries, and then computing an element of A(S) with the smallest value can be done in another round and (n M+ MM -uuuries. The correctness of the algorithm is guaranteed by the fact that A(S). for some |S] < M, is the maximal minimizer of f. and therefore the algorithm outputs a set with the optimum v
Our main result of this section the following theorem.
'Note, however, that the algorithm doesn't necessarily output the maximal minimizer itself.

---

Algorithm 1: Augmenting Sets Algorithm
Input: Submodular function f 2 + E and M E Eso such that If(S) S M for all S S [x]] and f(0) =
Output: Sout, minimizer of function f Function AugmentingSets (f. M):
F F (S [n] || S M)
for S E - - Su
S(S (1) [(S) // Compute the augmentation of S
5
end
return Sout E s ((((S)
Theorem 1.4 (Two-round Parallel SFM). There is algorithm (Algorithm 1) that when given evaluation oracle for submodular f 2 + with f(0) and [f(S) S M for all C [m] finds minimizer of f in 2 rounds and 211) queries.
Proof. First, we bound the parallel and query complexity of the algorithm. Line 2 to Line 5 can be implemented in round as they simply evaluate f on all subsets of [n] of size S M + 1. Line can be implemented in I round by evaluating (A((S) for each S F in parallel. Consequently, the algorithm implementable in rounds. To bound the query complexity, note that |F] S Σx= (2) On and the algorithm only makes (n)) queries for each S E F (O(n) in Line and in Line 6). Consequently, the algorithm makes (n total queries.
only remains show that the algorithm outputs a minimizer of f. We prove this by showing that for some S E F, its augmented set A(S) is the maximal minimizer of f. i.e., the union of all minimizers, which is a minimizer itself by submodularity. This suffices as the algorithm outputs the A(S) for S e F of smallest value. Let S. be the maximal minimizer of f. We build subset T S S. of size [T] S M,, which we call anchor, as follows. Start with = 0 and an arbitrary ordering of elements of S... For each element E S. in this order, we add it to the current T if S(T U (i)) S(T). Since only takes integer values, this means that whenever we add an element to T, the value of f()) goes up by at least 1. At the end of the process we have f(T) 2 (T'. Since f(T) s M, it follows that [T' < M and therefore T E F.
We now claim that A(T") S.. For any element E S. Ar, we didn't add i to T because fTT {i]) (0))-f(11) f(T.) s where S T the value of T when element visited in the procedure above. By submodularity, f(T U {i})
f(T) I f(T, U {i)) f(T:) < 0. This implies that
S. ATT). Also note that for any j & S., we have f(S. (5}) ())== > f(S.) by the maximality of S..
It again follows from submodularity and T C S. that S(T (i)) S(T), which implies j A()).
This proves A(T) = and completes the proof of the theorem.
4 Conclusion
In this paper we designed two new parallel algorithms for minimizing submodular functions f 2|n] + Z n [-M, +M] with round complexities O(n (2233/32/33))) M2/3) and 2, and query complexities Ōnn 2 and 0+1 respectvell.. These M-dependent sublinear dependence on n in the round complexities stand in contrast the ((n))lower bound the number of rounds required for SFM when M (())) On the way to the first result, we obtain new efficient parallel algorithm for e-approximate minimization of -Lipschtt convex functions over [0, 1]" with round-complexity g/3 Given results of [Nem94, DG19] the dependence on is optimal for constant 8.
Two related open questions are whether one can obtain -round SFM algorithms with polyloga- rithmic dependence on M, and whether one can obtain algorithms for e-approximate minimization of Lio-hips convex functions over [0, 1]"h in Onn log(1 [1 -rondds or can one prove lower bounds ruling them out. Another related open question is whether one can perform SFM in O(poly(M) -rounds with query complexity poly(n.).
10

---

Acknowledgements
We thank the anonymous reviewers of NeurIPS 2023 for helpful comments. Part of this work was done while Deeparna Chakrabarty, Haotian Jiang, and Aaron Sidford were attending the Discrete Optimization trimester program the Hausdorff Research Institute for Mathematics.
References
[AC]+21] Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34: $4:10810-10822, 2021.
[ALS20] Brian Axelrod, Yang P Liu, and Aaron Sidford. Near-optimal approximate discrete and continuous submodular function minimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 837-853. SIAM, 2020.
[BJL* BJL+19) 19] Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in Neural Information Processing Systems, 2019.
11] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning. 3(1):1 1(2, 2011.
[BS18] Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimiza- tion: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint 03880, 2018.
[BS20] Eric Balkanski and Yaron Singer. A lower bound for parallel submodular minimization. In Proceedings of the 52nd annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 130-139, 2020.
[BV04] Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4):540-556, 2004.
[BVZ01] Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimiza- tion via graph cuts. IEEE Transactions on pattern analysis and machine intelligence, 23(1 13(11):1222-123) 1239, 2001.
[CCK21] Deeparnab Chakrabarty, Yu Chen, and Sanjeev Khanna. A polynomial lower bound on the number of rounds for parallel submodular function minimization and matroid intersection. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2021.
[CGJS22] Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford. Improved lower bounds for submodular function minimization. In 2022 IEEE 63rd Annual Sympo- sium on Foundations of Computer Science (FOCS), pages 245-254. IEEE, 2022.
[CGTO0] AR Conn, NIM Gould, and Ph L Toint. Trust region methods, mps/siam ser. Optim., SIAM, Philadelphia, PA, 2000.
[CJJ 20] Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with ball optimization oracle. Advances in Neural Information Processing Systems, 33:19052--1966 2020.
[CJJ [CJJ+23) Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. arXiv preprint XXXx:2301.00057, 2023.
[CLSW17] Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong, Sub- quadratic submodular function minimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1220-120 1231, 2017.
11

---

[DBW12] John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[DG19] Jelena Diakonikolas and Cristóbal Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, pages 1132-1157. PMLR,
2019.
[DVZ21] Daniel Dadush, László A. Végh, and Giacomo Zambelli. Geometric rescaling algorithms for submodular function minimization. Mathematics of Operations Research, 46(3):1081- 1 1108, 2021.
[Edm70] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Edited by G.
Goos, J. Hartmanis, and J. van Leeuwen, page 11, 1970.
[FG88] Awi Federgruen and Henry Groenevelt. Characterization and optimization of achievable performance in general queueing systems. Operations Research, 36(5):733-741 1988.
[F100] Lisa Fleischer and Satoru Iwata. Improved algorithms for submodular function minimiza- tion and submodular flow. In Proceedings of the thirly-second annual ACM symposium on Theory of computing, pages 107-116, 2000.
[GLS81] Martin Grötschel, Lászłó Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):199-177, 1981.
[GLS88] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer, 1988.
[GPRW20] Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New query lower bounds for submodular function minimization. 11th Innovations in Theoret- ical Computer Science Conference, ITCS, pages 64:1-64:16, 2020.
[GR18] Pontus Giselsson and Anders Rantzer. Large-scale and distributed optimization, volume 2227. Springer, 2018.
[Har08] Nicholas James Alexander Harvey. Matchings, matroids and submodular functions. PhD thesis, Massachusetts Institute of Technology, 2008
[IFFO]] Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial the algorithm for minimizing submodular functions. Journal the ACM (JACM), 48(4):761- 777, 2001.
[I009] Satoru Iwata and James B Orlin. A simple combinatorial algorithm for submodular function minimization. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 1230-1237. SIAM, 2009.
[Iwa03] Satoru Iwata. faster scaling algorithm for minimizing submodular functions. SIAM Journal on Computing. 92(4):833-844) 2003.
[JB11] Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR 2011, pages 1897-1904. IEEE, 2011.
[JBS13] Stefanie Jegelka, Francis Bach, and Suvrit Sra. Reflection methods for user-friendly submodular optimization. Advances Neural Information Processing Systems, 26, 2013.
[Ji221] Haotian Jiang. Minimizing convex functions with integral minimizers. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 976-985. SIAM, 2021.
[Jia22] Haotian Jiang. Minimizing convex functions with rational minimizers. Journal of the ACM, 70(1):1-27, 2022.
12

---

[JLSW20] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization. convex-coneave games, and its applications. In Proceedings of the 52nd annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 944 1533,,3, 2020.
[JISZZ33] Haotian Jiang, Yin Tat Lee, Zhao Song, and Lichen Zhang. Convex minimization with integer minima in Onn*) time. arXiv preprint arXiv:2304.03426, 2023.
[KB]+1]] KS Kumar, Alvaro Barbero, Stefanie Jegelka, Suvrit Sra, and Francis Bach. Convex optimization for parallel energy minimization. arXiv preprint 1503 015600,633, 2015.
[KC10] Andreas Krause and Volkan Cevher. Submodular dictionary selection for sparse repre- sentation. In International Conference on Machine Learning (ICML), number CONE, 2010.
[KG05] Andreas Krause and Carlos Guestrin. Optimal nonmyopic value of information in graphical models: efficient algorithms and theoretical limits. Carnegie Mellon University. Center for Automated Learning and Discovery, 2005.
[Kha80] Leonid G Khachiyan. Polynomial algorithms linear programming. USSR Computa- tional Mathematics and Mathematical Physics, 20(1):53-72, 1980.
[KKT08] Pushmeet Kohli, M Pawan Kumar, and Philip HS Torr. p² & beyond: Move making algorithms for solving higher order functions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3109):1445-1656, 2008
[KNTB09] Yoshinobu Kawahara, Kiyohito Nagano, Koji Tsuda, and Jeff A Bilmes. Submodularity cuts and applications. Advances in Neural Information Processing Systems, 22, 2009.
[KT10] Pushmeet Kohli and Philip HS Torr. Dynamic graph cuts and their applications in computer vision. In Computer Vision, pages 51-108. Springer, 2010.
[KTE88] Leonid G Khachiyan, Sergei Pavlovich Tarasov, and I. I. Erlikh. The method of inscribed ellipsoids. In Soviet Math. Dokl, volume 37, pages 226, 1988.
[LB11] Hui Lin and Jeff Bilmes. Optimal selection of limited vocabulary speech corpora. In Twelfth Anmual Conference of the International Speech Communication Association, 2011.
[Lev65] Anatoly eur'evich Levin. An algorithm for minimizing convex functions. In Doklady Akademii Nauk, volume 160, pages 1244-1247. Russian Academy of Sciences, 1965.
[Lov83] László Lovász. Submodular functions and convexity. Mathematical Programming The State of the Art: Bonn 1982, pages 235-257, 1983.
[LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049-1065. IEEE, 2015.
[Nem94] Arkadi Nemirovski. On parallel complexity of nonsmooth convex optimization. Journal of Complexity, 10(4):451 1994.
[New65] Donald Newman. Location of the maximum on unimodal surfaces. Journal of the ACM (JACM), 12(3):395-398, 1965.
[NN89] YE Nesterov and AS Nemirovskii. Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad. Sci. Moscow; USSR, 1989.
[Or109] James Orlin. faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming, 118(2):237-251. 2009.
13

---

[QS95] Maurice Queyranne and Andreas S Schulz. Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds. Integer Programming and Combinatorial Optimization: 4th International IPCO Conference Copenhagen, Denmark, May 29-31, 1995 Proceedings 4, pages 307-320. Springer, 1995.
[SBB 18] Kevin Scaman, Francis Bach, Sébastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Optimal algorithms for non-smooth distributed optimization in networks. Advances in Neural Information Processing Systems, 31, 2018.
[Sch00] Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2)346-355, 2000.
[Sho77] Naum Z Shor. Cut-off method with space extension in convex programming problems. Cybernetics, 13(1):94 96, 1977.
[Top98]] Donald Topkis. Supermodularity and complementarity. Princeton university press, 1998.
[Vai89] Pravin M Vaidya. A new algorithm for minimizing convex functions convex sets. In 30th Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 338-343 343, 1989.
[Ver18] Roman Vershynin. High-dimensional probubiliy:: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[Vyg03] Jens Vygen. A note on Schrijver's submodular function minimization algorithm. Journal of Combinatorial Theory, Series B, 88(2):399 402 2003.
[YN76] David B Yudin and Arkadii Nemirovski. Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody, 128- 142, 1976.
14

---

A Supplement
In this supplement, we provide the complete proofs of Lemma 2.3 and Theorem 2.2.
Proof of Lemma 2.3. First we show that (z) is convex and 3L-Lipschitz. Let h(z) == 2L([I= - cll - r). By triangle inequality and homogenity of norms, 2L( - cll - r) is convex and 2L-Lipschitz (with respect to II-ID. Further, it is straightforward to check that the maximum of two convex, L-Lipschitz functions is convex and L-Lipschitz and that the sum of a L- L-Lipschitz and 2L-Lipschitz function is convex and 3L-Lipschitz. Since frag (z) = f(x) max(0, h(x)) and constant functions are convex and O-Lipschitz the result follows.
Next, consider y E R. with lyy - 2 r. Since ||-I| is norm we see that [1 - ell and therefore Seeg(" (1**) = f(y Furthermore, -l yl = +l - cll - and so,
freg (v) = f(y) + 2L( cll -r) 2 f(y*)) L 1 - ul +-2 - cll -r)
= f(y"*) + T(lly - cll r)
where the inequality follows since f' is L-Lipschitz with respect to ||-I]- This yields the desired result as it implies that values of frng are all larger than those of points where | cll S for which freg (x) f(x). Further, since (ir R"I || cll S r) is closed and f is Lipschitz, ther exists minimizer of |1l= f(x) and the result follows.
Proof of Theurem 2.2. We invoke Lemma 2.3 and apply BallAccel on the function F == fe.R as
defined in Lemma 2.3 with respect to 11-112 being the origin, and p == L.V2logn' With this choice of P. by Lemma 2.6, we know [F(x) superscript (c, R) from freg for the remainder of the proof.
freg (x)) I Copt everywhere. For brevity, we remove the
We now claim that F has minimizer v. with ||==- llz S 3R. To see this, let y E RD be point with ||yl2 > 3R and consider ÿ = y
R. Therefore, T
Fwy)= 2 freg (v)
Copt = f(y) + 2L (Ilvll2 R) Eopt 2 freg (5) + L- (llvl12 Rt) Copt
where the first incquality follows from pointwise approximation of F and freg. and the second follows
since f is also L-Lipschitz in the I1-1|, norm, and so freg (ū) = (ū) < f(y) + L. [1e/l] R). Again
using the pointwise approximation of F and freg we get Fly) 2 FØ)) 2Copt + L- (lvll 2 R). and
if I|vil2- > 3R using that Cop: E (0, LR] we get contradiction to minimality of Fly).
2L for v E Oh(x)) where h(x)= max(0, ||0|||2 R). Note that ||0| < 1, so the stochastic gradient g' satisfies Ellg' (z) < 20 + 8T... It follows that by setting r = p. Proposition 2.8 implies that for any Φ, À >> 0, there exists (o, X, p)lball optimization oracle for F which makes O o² total queries g in O(1) parallel rounds (as o² > L by definition of L-Lipschitzness).
Note that the stochastic subgradient g' of freg is given by g' -g y
Next we apply ball acceleration in Proposition 2.9 to F. We have already argued above that the minimizer 2, of F satisfies | 2 I 3R.. We set the parameter r = p L. and the R and L multiplied by factor 3. Using these, the parameters of (6) in Proposition 2.9 become
fop
LR Eopt
[.R/2log
2/3
and X, <opt <opt K2 R22
K
llgg k.
Copt
Using Proposition 2.9 and Proposition 2.8, we get that the number of rounds of queries is (CK log k). (C lolo" (Rx/p)) which is ((LR//tapt) 12/3).
Next, we bound the query complexity. Adding up the queries made by the ball-optimization oracle calls made in all iterations per part of Proposition 2.9 is
a² = -K(Kk
(CKlogn) (C logg" (Rk/p) x20²
15

---

Adding up the queries made by the ball- ball-optimization oracle calls made in all iterations per part of Proposition 2.9
COo²² log
Σ jElllog, K+C1|
which is also δ x
X2p2
Substituting the values from above and (((R//co))))
we get that the total query complexity is Ly2logii
Fapt
Finally note that Proposition 2.9 applied computes an Copt approxixox minimizer which is of approximae minimizer of freg. By setting Copt = e/2, Lemma 2.3 implies that we can find an e-approximate minimizer x of f with ||>||2 I R. This completes the proof of the theorem.
16


Reviews:
[{"review_id": "f9QQ8PAwzl", "reviewer": "Reviewer_dKXF", "summary": "\tIn this paper, the author(s) investigate the classic submodular minimization problem within the parallel computing regime. The setting is an integral submodular function $f$ defined on $2^{[n]}$ which is bounded ($|f| \\le M$) and normalized ($f(\\emptyset) = 0$. There primary contribution is obtaining query-efficient $M$-dependent algorithms with sublinear in $n$ rounds. This is achieved by regularizing the Lov{\\'a}sz extension of the submodular function, and then using some prior results on parallel convex optimization. They also proving a 2-round $O(n^{M+1})$-query algorithm for submodular minimization.", "questions": "I have no further questions then the potential confusions stated in the weaknesses section. ", "limitations": "The author(s) clearly state the assumptions needed for their algorithms and end with some potential open questions on how their work may be improved. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The motivations and background to the results are clearly stated. The proof ideas are clearly written.", "weaknesses": "\tPage 2, line 69 capitalize section 2.1.\n\n\tPage 2, line 70 minmizer misspelled.\n\n\tPage 3, line 114 capitalize theorem 1.1.\n\n\tPage 5, line 225 comma needed after \"As discussed in the introduction.\n\n\tPage 6, Lemma 2.3 any $c,x \\in \\mathbb{R}^n$ I believe should be $c,r \\in \\mathbb{R}^n$.\n\n\tPage 9, line 359 in Algorithm 1 line 4, computing $A(S)$ may require an input of size $M + 1$, i.e., when $|S| = M$. The proof on this line only requires inputs of size $M$.\n\n\tPage 9 line 378, $f(S_* \\cup j)$ change to $f(S_* \\cup \\{j\\})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a careful reading of our paper and writing the review.\n\nIn the weakness section, the reviewer points out several typographical errors; we agree with them all, and will fix them in the next version. For line 359 specifically, indeed what we should have stated is that the size of all sets queried in Line 4 is at most $M+1$ not $M$ as initially stated. This still allows for the algorithm to be implemented in 2 rounds and does not change the query complexity of our algorithm. \n\nThank you!\n"}, {"review_id": "CDELCBhAtm", "reviewer": "Reviewer_T5ni", "summary": "This paper considers the submodular minimization problem (SFM), where the submodular function $f$ is bounded between $-M$ and $M$. There has been a large number of papers that focus on solving this problem in as few queries as possible, but the proposed algorithms are generally highly sequential (at least $\\Omega(n)$). On the other hand, there is a lot of work on the parallel complexity of SFM. The contribution of this paper is to propose and analyze algorithms with low parallel complexity.\n\nThey first propose an algorithm for SFM that runs in $\\tilde{O}(n^{1/3}M^{2/3})$ rounds. This algorithm uses a reduction from parallel SFM to parallel convex optimization in order to achieve this. They provide an improved method for parallel convex optimization to be used for their algorithm. Next, they propose an algorithm that is just 2 rounds but with query complexity $n^{O(M)}$, which is optimal if $M$ is constant. This second algorithm is very simple and clean.\n", "questions": "None", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The problem setting is very well motivated since SFM includes many applications that involve large datasets and therefore parallel algorithms are needed. This paper also fills an interesting gap in existing literature on SFM, where there is work on the parallel complexity but no algorithms that run in few rounds.\n- Very strong theoretical results and ideas, which could be useful for other problems.\n- Extremely clear and well-written.", "weaknesses": "- There is no experimental evaluation, but this paper is a theory paper so it is not much of an issue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a careful reading of our paper and writing the review.\n\nIn the weakness section, the reviewer points to the lack of experiments. As the reviewer also notes, the main focus of the paper is exploring algorithms for SFM and $\\ell_{\\infty}$ convex optimization through a theoretical lens.\n"}, {"review_id": "y8DPfbWObM", "reviewer": "Reviewer_RFBf", "summary": "The paper studies the parallel complexity (number of rounds of queries) for polynomial query-complexity submodular function minimization. The main result of the paper is  an $\\tilde{O}(n^{1/3} M^{2/3})$ bound for this, where $n$ is the size of the ground-set and the function is integer valued with an upper bound of $M$ on the its absolute value. The approach of this work is to reduce to the problem of minimizing the Lovasz extension (which is $L = 3M$-Lipschitz) over the unit $n$-dim $\\ell_\\infty$-ball, and then use a simple regularization term along with the $L$-Lipschitzness to reduce it to an unconstrained minimization problem. The algorithm for this optimization is derived from the \nrecent work of [Carmon et al. 23] who gave a  $\\tilde{O}(d^{1/3} \\epsilon^{-2/3})$-round parallel $\\epsilon$-approximation for $1$-Lipschitz (over $\\ell_2$) convex function minimization with a minimizer in the $d$-dim unit $\\ell_2$-ball and a subgradient oracle. To adapt this to the $\\ell_\\infty$ case, the paper first shows that a certain Gaussian convolution has better bounds with $\\ell_\\infty$-Lipschitzness, effectively canceling out the blowup incurred by the $\\ell_\\infty$ vs. $\\ell_2$ norm bound. This, along with the fact that the subgradients of the Lovasz extension can be efficiently computed by queries to the function, yields the result. Additionally, the paper also gives a simple combinatorial 2-round $O(n^{M+1})$ query algorithm for this problem.\n", "questions": "Editorial comments:\n1. Line 81: “an convex function” - - > “a convex function”.\n2. Lines 258-259: $\\pi_x$ should be used instead of $\\pi$.\n3. In Sec. 2.2 $d$ is used to denote the dimension, however $n$ is used instead in lines 302, 333.\n4. Line 285 mentions “above theorems”, which is unclear. Please refer to the relevant theorems.\n5. Line 311-312: refer to Fact 2.4 for the subgradient oracle $g$.\n6. Line 335: “subscript” - - > “superscript”.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "For small $M$, the main result of work improves upon previous algorithms which required $\\Omega(n)$ rounds, and gives the first bound which is sublinear in n, albeit dependent on M, with the dependence on $n$ matching the lower bound of $n^{1/3}$ given by [CCK21]. In the process, the paper extends the work of [Carmon et al. 23] to the $\\ell_\\infty$ case essentially matching the lower bound [Nem94, DG19] in terms of the dimension. Overall the algorithmic bounds achieved by the paper are notable improvements (and optimal in some parameters) for these problems. ", "weaknesses": "The main result of the paper is based on the recent result of [Carmon et al. 23]. The fact that SFM can be reduced via the Lovasz extension to optimization over $\\ell_\\infty$ is well-known and the main result of this work is to adapt the results on optimization over $\\ell_2$ of  [Carmon et al. 23] to the $\\ell_\\infty$ case. The techniques for this are fairly straightforward. Overall, the contributions do not provide substantially novel methodology for such problems, and may not be sufficiently insightful or deep. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time to carefully read and review our paper.\n\n\nIn the weakness section, the reviewer mentions how it is well known that SFM can be reduced to $\\ell_{\\infty}$-Lipschitz optimization. We agree. However, we believe that showing that the $\\ell_{\\infty}$ Lipschitzness of the Lovasz extension when coupled with our new parallel convex optimization methods tailored to $\\ell_{\\infty}$ Lipschitz functions lead to improved parallel SFM algorithms is an important new insight. Furthermore, to our knowledge the simple reduction we give from constrained to unconstrained for Lipschitz function was not explicitly known; we believe this may be useful for broader applications in convex optimization.\n\nWhile we agree that our techniques are somewhat straightforward given the framework in [Carmon et al. 23], our broader contribution is the aforementioned connection we make between parallel SFM and $\\ell_\\infty$-optimization and the near optimal depth algorithm for $\\ell_\\infty$-optimization for constant $\\epsilon$, these both constitute important progress on well-established open problems.  Though the observation that the quality of the Gaussian convolution for smoothing $\\ell_\\infty$ (as opposed to $\\ell_2$) Lipschitz function is straightforward, that we show it leads to near-optimal $\\ell_\\infty$-Lipschitz convex optimization in any regime is particularly striking. That we make this progress by simple technical insights is not necessarily a bad thing.\n\nIn the Questions section, the reviewer suggests many editorial comments. We agree with all of them, and we will incorporate these changes in the next version. Thank you!\n"}, {"review_id": "urlUcotHHT", "reviewer": "Reviewer_QKZK", "summary": "This paper studies the parallel complexity of submodular function minimization: given a submodular function defined on the $2^n$ subsets of $[n]$ taking values between $-M$ and $M$, find a minimizing subset of $[n]$. It provides two upper bounds: one algorithm with polynomial query complexity in both $M$ and $n$ and taking $O(n^{\\frac{1}{3}}M^{\\frac{2}{3}})$ rounds, and the other with query complexity $n^{O(m)}$ in two rounds.", "questions": "Could you clarify what \"polynomial time\" means in the context of line 26? In this model, we are only interested in query and round complexity, right?", "limitations": "All limitations seem to be addressed.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Writing is clear and convincing, with all relevant technical background and results clearly explained. Related work seems to be cited and placed in context, and open questions are identified in the conclusion. Although I am unfamiliar with the area, the problem seems fundamental and relevant to the conference and machine learning more widely.", "weaknesses": "My only (minor) criticism is that it took me a while to understand the difference between the \"parallel\" setting of SFM and the standard sequential setting. I eventually realized that the number of rounds used is essentially a measure of the *adaptivity* of an algorithm - the more adaptive an algorithm is, the more rounds it needs. I don't think the word adaptivity is mentioned in the paper, so maybe this intuition could be explained slightly better.\n\nPerhaps a couple more sentences on the wider implications of the results for machine learning more broadly might also be nice.\n\ntypo, line 253: \"then\" -> \"than\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time to carefully read and review our paper.\n\nIn the weakness section, the reviewer points to the clarification between “adaptivity” versus “parallelism”; we agree that explaining this clearly is a good idea, and we will include this explanation in the next version of our paper. The reviewer also asks about the wider implications to ML. In the past decade or so, submodular function optimization has arisen quite in multiple ML applications (see https://arxiv.org/pdf/2202.00132.pdf, for instance), and with the rise of infrastructure for massively parallel computation, it is an important question to understand parallel algorithms for the same, and “low-depth” algorithms would have implications to the ML applications. \n\nIn the questions section, the reviewer asks us to clarify the meaning of polynomial time, versus round and query complexity. In the context of SFM, polynomial *time* simply means that the additional computational work apart from the queries takes polynomial time; a little more formally, the total time is $O(n^c)$ additional arithmetic operations for some constant $c>0$. In the context of line 26, we are only talking about sequential algorithms, as we have not introduced the model of parallel computation yet at this point. For sequential algorithms, prior work has studied fast SFM algorithms that have both small query complexity and small additional computational cost. \n\nIn the parallel complexity model, we are primarily interested in the parallel round complexity and query complexity, but ideally the algorithm’s additional computational cost (also sometimes referred to as “work” in this community) should be polynomially bounded from its query complexity (which is the case for both of our algorithms). It is true, however, that the focus of our paper was on the round and query complexity. We hope this clarifies the reviewer’s question.\n"}, {"review_id": "sIOVNyaP49", "reviewer": "Reviewer_xv3B", "summary": "This paper considers the problem of parallel submodular function minimization, where the function is assumed to be integer valued with range $[-M, M]$. The authors propose two algorithms; one which runs in $\\tilde{O}(n^{1/3} M^{2/3})$ rounds with $\\tilde{O}(n^2 M^2)$ query complexity, and another which runs in 2 rounds with $n^O(M)$ query complexity. This improves over existing polynomial time submodular minimization algorithm which run in $\\Omega(n)$ rounds. ", "questions": "- Does Theorem 1.1 extends to minimizing non-integral valued submodular functions up to epsilon additive error? As far as I can tell the same proof holds. If yes, it would be good to include that.\n- [ALS20] showed how to compute a sparse stochastic gradient of the lov\\'asz extension of a submodular function using $O(1)$ queries. Would it be possible to reduce the query complexity of the first algorithm using a similar strategy as in  [ALS20]?\n\nMinor issues:\n- The section on related work is a bit repetitive. I suggest only mentioning additional related work not already discussed in the introduction.\n- In Lemma 2.3, RHS of Eq (1), $f^{c,r}\\_{reg}(y^{c,r})$ should be  $f^{c,r}\\_{reg}(y)$\n- In definition 1.2, $\\| f(x) - f(y)|$ should be $| f(x) - f(y)|$\n- In Lemma 2.5 and the discussion above it, you use d for the dimension, instead of n as in the rest of the paper.\n- In Eq. (3), the term inside the expectation should be $f(x - y)$", "limitations": "The authors clearly state the theoretical complexity of their algorithms, along with the assumptions required for their results to hold. But they don't address the practical performance of their algorithms", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of minimizing submodular functions efficiently in a highly parallel manner is a natural one to consider. Several lower bounds have been derived for this problem, while upper bounds are not well investigated, except for ones resulting from sequential algorithms which run in $\\Omega(n)$ rounds, and brute force search which runs in 1 round but uses $2^n$ queries. The algorithms proposed in this paper are the first upper bounds for this problem to improve over these results.\nThe first algorithm result also follows from improving the parallel complexity for minimizing $\\ell_\\infty$-Lipschitz convex functions from $\\tilde{O}(n^{2/3} / \\epsilon^{2/3})$ to $\\tilde{O}(n^{1/3} / \\epsilon^{2/3})$ rounds, which is tight in terms of dependence on n.\n\nThe results are correct and presented clearly.", "weaknesses": "The results of this paper are mostly based on existing work and two rather simple observations: a reduction from constrained to unconstrained optimization of L-Lipschitz functions and that convolving an $\\ell_\\infty$-Lipschitz function with a Gaussian changes the function less than in the case of $\\ell_2$-Lipschitz functions.\n\nThe proposed algorithms are mostly of theoretical interest, I expect that the first algorithm would not be efficient in practice (it is not clear how large is the universal constant C), and the second algorithm is essentially an exhaustive search over all M-cardinality sets, which is only efficient for very small M.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a careful reading of our paper and writing the review.\n\nIn the weakness section, the reviewer points out that our results follow from existing work and two observations namely (i) our reduction from constrained to unconstrained for Lipschitz functions and (ii) that we can convolve with a larger Gaussian for $\\ell_\\infty$ Lipschitz functions. We believe that our broader contribution is the connection we make between parallel SFM and $\\ell_\\infty$-optimization and the near optimal depth algorithm for $\\ell_\\infty$-optimization for constant $\\epsilon$, both of which are important and well-established problems. Though the observation that the quality of the Gaussian convolution for smoothing $\\ell_\\infty$ (as opposed to $\\ell_2$) Lipschitz function is straightforward, that we show it leads to near-optimal $\\ell_\\infty$-Lipschitz convex optimization in any regime is particularly striking. Furthermore, to our knowledge the simple reduction we give from constrained to unconstrained for Lipschitz function was not explicitly known; we believe this may be useful for broader applications in convex optimization. That we make this progress by simple technical insights is not necessarily a bad thing. Finally, we think our results might shed light on how the Lovasz extension of submodular function is similar to a general $\\ell_\\infty$-Lipschitz function, which aids algorithm design for parallel SFM more generally.\n\n\nThe reviewer also wonders about the practicality of our algorithms. Indeed, the main goal of this work is to theoretically investigate the parallel complexity of SFM. The empirical performance of our first algorithm would depend on the empirical performance of the [Carmon et al. 2023] algorithm.\n\nThe reviewer also asks some interesting questions! Thank you! To answer the first question as to whether Theorem 1.1 extends to minimizing real-valued functions, indeed it does, and we will mention this in the next iteration of the paper. The second question is whether the techniques from ALS20 could speed up the algorithm. While we are not sure of its answer, the approach in ALS20 for sampling subgradients via a data structure depends on the interplay between submodular properties of the Lovasz extension and the structure of the iterative methods applied. It is not immediately clear that such an approach extends to our setting given the different methods. Nevertheless, we agree that this suggests an interesting question for future work, e.g., is it possible to decrease the query complexity up our algorithm to something with subquadratic or near-linear dependence on $n$. We may remark on this in the final version.\n\nThe reviewer also points out some editorial comments; we thank the reviewer for pointing these out, and we will fix these in our next version.\n\n"}]

Author rebuttal:

Meta-review: This work obtains new query-efficient o(n)-round M-dependent algorithms for submodular function minimization.
Decision: Accept (spotlight)