Stochastic $L^\natural$-convex Function Minimization
Authors: Haixiang Zhang
Zeyu Zheng
Javad Lavaei
Venue: NeurIPS 2021 Poster (2021)
Keywords: L#-convex function minimization
stochastic optimization
simulation optimization
submodular function minimization

Abstract: We study an extension of the stochastic submodular minimization problem, namely, the stochastic $L^\natural$-convex minimization problem. We develop the first polynomial-time algorithms that return a near-optimal solution with high probability. We design a novel truncation operation to further reduce the computational complexity of the proposed algorithms. When applied to a stochastic submodular function, the computational complexity of the proposed algorithms is lower than that of the existing stochastic submodular minimization algorithms. In addition, we provide a strongly polynomial approximate algorithm. The algorithm execution also does not require any prior knowledge about the objective function except the $L^\natural$-convexity. A lower bound on the computational complexity that is required to achieve a high probability error bound is also derived. Numerical experiments are implemented to demonstrate the efficiency of our theoretical findings.

Stochastic Lo-coneex Function Minimization
Haixiang Zhang
Zeyu Zheng Department of IEOR University of California, Berkeley
Department of Mathematies University of California, Berkeley
Berkeley, CA 94704 haixiaag__danggberkkeee edu
Berkeley, CA 94704
zyzheng9berkeley edu
Javad Lavaei
Department of IEOR
University of California, Berkeley Berkeley, CA 94704 lavaei @aakeeeyy. edu
Abstract
We study an extension of the stochastic submodular minimization problem, namely, the stochastic Li-convex minimization problem. We develop the first polynomial- time algorithms that return a near-optimal solution with high probability. We design a novel fruncation operation to further reduce the computational complexity of the proposed algorithms. When applied to a stochastic submodular function, the computational complexity of the proposed algorithms is lower than that of the existing stochastic submodular minimization algorithms. In addition, we provide a strongly polynomial approximate algorithm. The algorithm execution also does not require any prior knowledge about the objective function except the co-convexity. A lower bound the computational complexity that is required to achieve high probability error bound is also derived. Numerical experiments are implemented to demonstrate the efficiency of our theoretical findings.
Introduction
As an important branch of optimization, discrete stochastic optimization problems (Futschik & Pflug. 1995; Gutjahr& & Pflug, 1996; Futschik & Pflug, 1997; Kleywegt et al., 2002; Semelhago al., 2020) appear in a wide range of applications such as image processing (Jegelka & Bilmes, 2011), pricing optimization (Ito & Fujimaki, 2016) and simulation-based optimization (Altman al., 2003; Freund et al., 2017). Since a discrete optimization problem is generally NP-hard to solve, specific structures are necessary guarantee the existence of polynomial- feasible set is {0, 1 for some positive integer d. submodular functions are viewed as the discrete analogy of convex functions in the field of combinatorial optimization. The submodular function minimization (SFM) problem has wide applications in computer vision, economics, game theory and is well-studied in literature (Lee et al., 2015: Axelrod et al., 2020; Zhang et al., 2020). However, for certain problems, because of the stochastic structure, the exact value of the objective function is not available but only noisy samples of the objective function value are available. These scenarios, for example, include the optimization of expected performances for complex stochastic systems. In contrast to the deterministic problem, the stochastic SFM problem is less understood (Ito, 2019; Chakrabarty et al., 2017; Blais et al., 2019; Axelrod et al., 2020).
algorithms. In the special case when the
In this work, we consider the stochastic minimization problem of a class of generalized sub- modular functions, named the L'-conve functions (Murota, 2003). More concretely, function
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

f: "I. + R is called an LÅ-convex function if it satisfies the discrete midpoint convexity:
+ f(z)+ f(y) 2 f([(z + v)/221 + f(l(=+))/2) 2)/21), Vz,y E [I....,NJ'.
where N, d are positive integers and L-] are the ceiling and flooring functions applied component- wisely to vectors. We note that L--convex functions are reduced to submodular functions if N 2. As an extension to the stochastic SFM problem, the stochastic -c-cove minimization problem also appears in a variety of decision making problems. For example, the user satisfaction function of a bike-sharing system (Freund et al., 2017) and the expected total waiting time of a service network (Altman et al., 2003) are proved to be multimodular functions, which is equivalent to an I.Accovvex function under linear transformation. Since the evaluation of both functions includes the simulation of random user behaviors, we only have access to noisy objective function value oracles and thus both problems can be formulated as stochastic L'-convex minimization problems. We refer the readers to the appendix and Murota (2003) for more concrete examples of L L'-convex minimization problems.
The contributions of this work are two-fold. For the algorithm design, we provide the first polynomial- time algorithms to achieve high-probability bounds for the stochastic L--convex function minimiza- tion problem. We note that only consider the number of objective function value evaluations in the computational complexity, since the function value evaluation oracle is usually the major contributor to the running time of algorithms. The first algorithm is based on the observation that the Lovász extension of an T,=-convex function transforms the original problem to an equivalent continuous convex optimization problem. Therefore, we can apply the stochastic subgradient method to solve the continuous convex problem and then round the solution to an integral solution. The idea of combining the Lovász extension and the stochastic subgradient method has already been considered in Hazan & Kale (2011); Ito (2019) for stochastic online convex optimization and stochastic submodular minimization, respectively. However, the direct application of the stochastic subgradient method will lead to a large computational complexity. We add an extra truncation step to the stochastic subgradient and the computational complexity reduced by (dd). We also implement numerical experiments to show the significance of the truncation step. In the special case when N = 2, our problem reduces to the stochastic SFM problem and the computational complexity of the truncated subgradient method is (d2) smaller than the stochastic cutting-plane -plane method in Blais et al. (2019). In addition, we propose the dimension reduction method and get a strongly polynomial approximate algorithm (see the definition in Section 4.2) with computational complexity Odd + log(N))e -² log(1/ (8)).. Finally, the uniform sampling method in Zhang et al. (2021) is extended to the multi-dimeenional case and the computational complexity is independent of N. Table 1 summarizes the upper bounds on the computational complexities to find a solution whose objective value is at most e larger than the optimum with probability at least 1 - 5.
On the other hand, we derive lower bounds on the computational complexity for achieving high- probability error bound. We construct set of T.F-convex functions whose landscapes are close to each other while their optima are different with each other. Intuitively, the algorithm requires sufficiently many evaluations to differentiate those "similar" Ld-convex functions, where the similarity between functions is characterized by the KL-divergence. More rigorously, we utilize the information inequality in Kaufmann et al. (2016) and get the lower bound O -2 log(1 1/)) on the complexity. Recently, Ito (2019) proved a lower bound for achieving an e-expected error. There is a difference in terms of d and 8 regarding the lower bound results between ours and Ito's. We note that these two lower bounds are established under different settings, i.c., the high- nigh-probability setting and the expectation setting. Hence, a directly comparison of the two lower bounds is unavailable; the discussion in Section 5.
1.1 Notation
For N E N, we define [N] = f1, N). For a given set S and an integer d E N, the product set Sd is defined as {[21,22 x2 .......... xa) : E S,i E [d]] For two vectors T, y E Rd. we use (a A y): == min(2;, }.} and (x V)); := max(x1, (I,, y4 } to denote the component-wise minimum and maximum. Similarly, the ceiling function [ and the flooring function [-] round each component to an integer when applied vectors. The failing probability of algorithms is denoted as 6. The notation O(g)) means that there exist absolute constants C2 > O such that f S cıg (resp. cıg < ʃ < c2g). Similarly, the notation ʃ Ö(g) (resp. ʃ -(g)) means that there exist absolute constants C1, 02 > O and constant C3 > independent of such that ʃ S cıg + c3 (resp. cıg < f < c2g + cz).
f= Og) (resp.
2

---

Table 1: Computational complexity for stochastic - co-coeeex function minimization. Constants except for d, N, 6, e,,, e omitted in the O(-) notation. The sub-optimality gap e refers to the objective function value gap between the global and the best sub-optimal solutions.
Unknown Sub-optimality Gap
Known Sub-optimality Gap
Algorithms
Truncated Subgradient
Old -2 Log(L/0)) log(1/6)) 1og
O[g)) log(1/0)) O(C*c
Multi-dim Uniform Sampling
(d c l log(1/6)
(d) log(N) N)) c c= 1/6)
Stochastic Cutting-plan
2 Problem Formulation
We have in mind complex stochastic system and consider the following discrete stochastic opti- mization problem
min f(x) := (x (x, Ex)] s.t. x x,
in which X' is the discrete feasible set, &.r summarizes all the randomness supported on some proper probability space (Y, By) and F X + R is deterministic function. Specifically, &x summarizes all the random variables and stochastic processes involved in the system for the decision variable x. The function F maps the decision and associated randomness into random system performance. For example, in service systems such as the bike-sharing service, this function F captures the full operational logic regarding how services are arranged. We write , ..., Ex.n independent and identically distributed (i.i.d.) copies of &.. We use Fx (z) == n. Σ F(z, Ex.;) to denote the empirical mean of the n independent evaluations for the choice of decision variables æ. The triad of the set X' the space of randomness (Y, By) and the function F(-.)) -) is called the model of problem (1). In this work, we assume the L L'-convexity of the objective function. For the case of presentation, we assume the feasible set = [AV]d, where d denotes the dimension and N represents the number of choices on each dimension for the decision variable r.
Assumption 1. The objective function f(-) is an c-oovvx function on X' = [N]], i.e.,
f(x) + f(v) 2 f([(= + v)/21) +
Vz, EX,
In general, the definition of c'-coveyxity also requires the feasible set X' to be an L convex set, namely, the indicator function of X' should be cc-cvoe on Zd In our case, the feasible set X = [N] is an L==convex set. Hence, we only need the discrete mid-point convexity property to define L convexx functions on X.
Remark 1.
Moreover, we assume that the distribution of the stochastic output F(x, Ex) is sub-Gaussian.
Assumption 2. The distribution of F(x,) :) is sub-Gaussian with a known parameter o² for all x E X.
The knowledge of o² represents the maximum level of stochasticity involved in the system perfor- mance. For scenarios where this o² is not known, it has to be adaptively learned and adds additional complexity the problem, but is not the focus of this work. We further note that our algorithm design and analysis can be generalized to any probability distribution with provable concentration inequalities. The set of all models satisfying both Assumption and Assumption is denoted as MC(X'), or simply MC. The main goal is to design algorithms that guarantee the selection of near-optimal solution with high probability. Formally, this criterion called the PPrbhalyy Approximately Correct (PAC) guarantee; see Even-Dar et al. (2002); Kaufmann et al. (2016); Ma & Henderson (2017). We say that a solution à, as the output of an algorithm, satisfies the (c, PPCC guarantee if
P min 2 < 8.
where the probability is calculated over the distribution of a.

---

An algorithm is called an [(e, PC-CC), MC if it always returns (e. 8)-AC solution for any model in MC. The computational complexity of an algorithm is defined as the number of evaluations of -(::)) before termination. The difficulty of satisfying the PAC guarantee for any model in MC characterized by the worst-case performance of optimal algorithm.
Definition 1. The computational complexity of the (c. 6)-AC guarantee and class MC is defined as
T(e, 6, MC) :=
inf sup IE [TA],
((C.6))PAC.,M)) MEMC
where the random variable TA is the computational complexity for each implementation of A.
The reminder of this paper is focused on providing upper bounds on T(c. 6.MC) by designing algorithms and providing lower bounds by an anformation-theortiiee analysis. In this paper, we consider the behavior of algorithms in the high-probability regime, namely, in the setting when the failing probability is small enough.
Assumption 3. The failing probability is sufficiently small.
In general, the sub-Gaussian randomness leads to
6, C(e, log (1/6) 0<8<)
where Cle,, is some function only depending on the precision and the model class M. For example, it is known that the sample complexity is O(N4c= (1/8) for the general best-arm selection problem (Even-Dat et al., 2002) when no convex structure in presence.
Truncated Stochastic Subgradient Algorithms
In this section, we develop gradient-based algorithms for problem (1). We first show that the properties of T.F-oovvxx functions make it possible to construct a continuous convex function on the continuous cube [1, NN that has the same set of optima as the original objective function. Then, rounding process is designed to round the solution of the continuous problem to an integral solution. Finally, the truncated stochastic subgradient algorithm proposed and its computational complexity is analyzed. Moreover, in this section, make the assumption that the foe -Lisschti constant of the objective function can be estimated a priori. For example, this estimation possible for service systems optimization, where it represents upper bound on how much impact additional server over a certain time range contributes to the system performance.
Assumption 4. The Lipschitt constant of ((x) is known to be a priori. Namely, we know beforehand that
f(x) - f(v) s L., Vz.y E & s.t. || vll 1
3.1 Reduction to continuous convex optimization problem
We first show that the original discrete minimization problem (1) can be equivalently transformed to continuous convex optimization problem. Based on the fact that the restriction of T.*convex function to a hypercube is a submodular function (Murota, 2003), we show that we can piece together the Lovász extension of the objective function in each hypercube to form continuous convex function on conv (2') N.d More importantly, it can shown that the continuous convex function has exactly the same global minima as the original _o-ovxx function and an unbiased subgradient estimator is available at each point at the cost of 2d evaluations to F(..)).
Theorem 1.
Suppose that function f(-) is an Lo-cvxexx function on [N] Then, there exists continuous convex function f(-) on [1, N]d, which we also name as the Lovász extension, such that
Ii holds f(x) = [(x) for any x E X.
The minimizers of i satisfy arg ging Fly) arg f(y).
For any point x E NJ4, there exists an unbiased estimator 9s to a subgradient of f(-) at point which can be evaluated via 2d evaluations F(..)).

---

Algorithm Rounding process to a feasible solution
Input: Model X, By, (ar, Er), optimality guarantee parameters 6, (e/2, solution . to problem (2). Output: An (e, 6)-PAC solution x" to problem (1).
1: Compute the neighbouring points (defined in the appendix) of ã. denoted as s S².
2: Simulate at S until the 1 - 8/((dd) confidence half-width of (n.(") is smaller than e/4 for all i.
3: Return the optimum x² arg m (S).
Algorithm 2 Projected and truncated SSGD method for the PAC guarantee
Input: Model X, By, F(x. E.), optimality guarantee parameters e, 6, number of iterations T, step size 7, truncation threshold M.
Output: An (e, PPC solution x to problem (1).
1: Choose the initial point 2º ((N 1)/2.-.., + 1)/2).
2: for =o.
do 3: Generate stochastic subgradient ğ' x'
4: Truncate the stochastic subgradient ge t TM (g)).
5: Update x1+1 P (a* ng"
6: end for
Compute the averaging point T + CETO x²) /T.
7:
8: Round 7 to an integral point by Algorithm
The proof along with a detailed discussion on L functions is provided appendix. Next, we describe the rounding process that takes approximate solution to the relaxed problem
min f(x) #E(1.N]4
an approximate integral solution the original problem (1). We list the pseudo-code in Algorithm 1. The following theorem proves the correctness of Algorithm and estimates the computational complexity. Note that all upper bounds on computational complexity in this paper are proved hold almost surely and thus also in expectation.
Theorem 2. Suppose that Assumptions 1-4 hold. The solution returned by Algorithm / satisfies the (c. PAC guarantee. The computational complexity of Algorithm I is at most
d
d log ())
0
log 2
+
+
Although we transform the original problem to continuous convex problem, the algorithm design in this work relies heavily on other two important properties of T.t-convex functions. The first property is that the global minima are integral points, which makes it possible to design strongly polynomial algorithms; see Section 4.2. The second property is that the Lovász extension a piecewise linear function. When the sub-optimality gap known, we prove that the Lovász extension satisfies the Weak Sharp Minima property and the subgradient descent method can be accelerated to achieve better dependence on the scale N; see the appendix.
3.2 Algorithm and complexity analysis
Utilizing the tools derived in the last subsection, (SSGD) method to find an approximate solution to problem (2) and then round the solution to get an approximate solution problem (1). The main difficulty of giving sharp upper bounds lies in the fact that the Lovász extension is neither smooth nor strongly-convex. This property of the Lovász extension prohibits the application of Nesterov's acceleration method (Nesterov, 1983) and variance reduction methods (Johnson & Zhang, 2013; Defazio et al., 2014).
first apply the stochastic subgradient
Now, propose the projected and truncated SSGD method for the (c, PPAC guarantec. The orthogonal projection onto the feasible set, which is defined as
P(x) (NAN1) V 1,, VI Rdd
5

---

is applied after each iteration to ensure the feasibility of iteration point. In addition to the projection, the component-wis truncation of stochastic subgradient critical in reducing expected computational complexities. The truncation operator with threshold M >> O is defined as
T == (g A MT) V (-M1), Vg E ER".
The pseudo-code of projected and truncated SSGD method is listed in Algorithm 2. With a suitable choice of the step size, the truncation threshold and the number of iterations, Algorithm 2 returns (c, 6)- solution and the computational complexity scales as N2)
Theorem 3. Suppose that Assumptions 1-4 hold. If we choose
ddN2 c2
log( ())
dNT
N M MVT
T=
M -
log
==
then Algorithm returns an (c, 6)-PA solution. Furthermore, we have
d2 2
d² log
(dNN
N2 = Ō
de N2 2 log 5
6, = 0
log( 5)
The intuition behind the truncation operation is that the truncation makes the norm of the subgradient smaller, which in turn allows the choice of a larger step size. With the larger step size, the convergence rate can be improved. Using the truncation operation accelerate the algorithms is novel in the context of the stochastic LÂ-convex function minimization problem. The truncation operation has been considered in other contexts, such as the sparse phase retrieval problem (Wang al.. 2017). We can prove that the computational complexity without the truncation step (i.c., M = oo) is
N
log
2
Hence, the truncation of stochastic subgradient is necessary for reducing the asymptotic expected computational complexity. This relation has also been observed in our numerical experiments. While the error the normal SSGD method only contains the optimization residual and the variance terms, the error of the truncated SSGD method has extra bias term. We note that the bias term can be made arbitrarily small with high probability by choosing large enough M and utilizing the tail bound for Sab-Gaussin random variables, and therefore the total eтror can be controlled similarly as the normal SSGD method. We mention that Algorithm 2 also applies when X' is a general L. set.
Next, we consider special case with additional condition that the norm of stochastic subgradients bounded almost surely. We then show that this additional condition, whenever available, can contribute further complexity reduction of our proposed algorithm.
Assumption 5. There exist constant G and an unbiased subgradient estimator 9 such that
IP [|lālla S G] = 1. Moreover, the cost of generating each ğ is at most 3 evaluations of F(--).
We note that G and 3 may depend on d and N. This assumption is common when analyzing the high-probabillity error bound of stochastic subgradient methods (Hazan Kale, 2011; Xu al., 2016). We first give two examples where Assumption 5 holds.
Example 1. Suppose that the randomness of each feasible x E X' shares the same measure space, i..., there exists a measure space (Z, B2) such that & can be any element in the measure space for all x E X. Moreover, for any fixed E Bz, the function F(-{E) is also L and has lx -ipiiischitz constant L. Then, the properties of Lc-cnee functions imply that there exists an unbiased subgradient estimator I such that the cost of evaluating 9 is d + 1 and llôll1 S 3L/2. Therefore, the Assumption 5 holds with G = 3Σ/2 and f = d + 1. We note that this example is similar the case when is in Ito (2019) while the noise of our problem can be unbounded.
When the distribution at each feasible point is bounded, we show that Assumption also holds. Example 2. Suppose that the distribution at each point & E X is bounded, namely, there exists constant 2 such that
IP... [| (x) < = We note that bounded distributions are sub-Gaussian with parameter 202, In this case, there exists an unbiased subgradient estimator such that Assumption 5 holds with G 2dC and 3 2.
E

---

More details about these two examples are provided in the appendix. Since the stochastic subgradient bounded, the truncation step is unnecessary Algorithm 2. The computational complexity of Algorithm 2 is estimated in the following theorem. The proof is similar to Lemma 10 in Hazan & Kale (201 I) and, since the feasible set is the hypercube [1, NJj, we replace the f--norm with the 80 norm to bound distances between points.
Theorem 4. Suppose that Assumptions 1-5 hold. we we skip the truncation step in Algorithm (i.e., set M 00) and choose
N2 ( + 2)² 22
dN2
T =
log 57)
TGP
then Algorithm returns (c, (PPA solution. Furthermore, have
BN2 L. + G)2 + log 8) +
G²22
T(c, =
BN2 + 2)2² +
log( ())
22
In the case of Example 1, we have 3 = = 3ł// and then the computational complexity of Algorithm 2 is at most ÖjdN" L) logg//1)0 If both Lipschitz constants are independent of d and N, the computational complexity becomes OldN2 (ooin/2-111(/// log(1/))], which is O(d) better than the general case without Assumption 5. Moreover, in the case of Example 2, we have G = d and / = Hence, the computational complexity at most Öld2 N (og((1))) even without the truncation.
Finally, we consider the case when the global optimum is unique and the sub-optimality gap is known to be at least > In this case, the Lovász extension satisfies the weak sharp minimum condition (Burke & Ferris, 1993) and we can design acceleration scheme similar to that in Xu et al. (2016). The acceleration scheme reduces the dependence on N from N22 to log(N) and we provide detailed discussions in the appendix.
4 Stochastic Localization Algorithms
Although the algorithms developed in Section 3 are guaranteed to find an approximate solution in polynomial time, gradient-based algorithms require the prior knowledge about the Lipschitz constant of the objective function to choose the optimal step size. In addition, the computational complexity of subgradient methods has quadratic dependence on the Lipschitz constant. However, for certain applications, the upper bound on the Lipschitz constant may be difficult to estimate priori or is very large so that the computational complexity is prohibitive for large-scale problems. To deal with those difficult scenarios, we utilize the discrete natural of problem (1) to design algorithms that do not require the prior knowledge about the objective function except the z.--convxxity and whose computational complexity has an upper bound that is independent of the Lipschitz constant. More specifically, we propose two approaches to deal with this problem. The first approach is to generalize the uniform sampling algorithm in Zhang al. (2021) to the multi- dintiiidiienionnal case. In the second approach, we propose a strongly polynomial approximate algorithm by gradually reducing the dimension.
4.1
uniform sampling algorithm
We first generalize the uniform sampling algorithm in Zhang et (2021) to the multi-dimensional case. The basic idea is that if the computational complexity for finding an (c, 8) PAC solution has the form Ce log(1 (1/5.. we can view the algorithm as (possibly biased) estimator with sub-Gaussian tails to the optimal value, where C > 0 is constant. For example, the uniform sampling algorithm provides a sub-Gaussian estimator for the optimal value of problem (1) in the one-dimensional case. Now suppose that have derived sub-Gau Gaussian estimator for the optimal value for the (d - di-dimensinnal case. Consider the function
(a1)) := min [ f(a..... Van [N].
(3)
7

---

which is an one- one-dimensional convex function. Since the (d - dimeensional algorithm has sub- Gaussian tail, we can view each implementation of the algorithm as a noisy function value oracle to (.) and the uniform sampling algorithm can be modified to solve the convex problem (3). By a similar method as Zhang et al. (2021), we can prove that the computational complexity of the resulting d-dimensional algorithm is a constant multiple of that of the (d - 1) --dimensional algorithm. By the induction method, we get an approximate algorithm for the multi-dimensional problem (I) whose computational complexity is independent of the Lipschitz constant L and the scale N in the high-probability regime. A rigorous proof to the following result is provided in the appendix.
Theorem 5. Suppose that Assumptions 1-3 hold. There exists an [(c, 8)-PAC, MC]-argorithn with computational complexity
[Cd log 5)
6 =
2
where C. is an absolute constant.
The exponential dependence on the dimension makes it impossible to use the generalized algorithm even for moderate dimension problems. However, this result implies that the computational com- plexity almost does not grow with N in the regime > d in the asymptotic regime with the failing probability 8 is very small. Therefore this algorithm can be preferable when d is small and N is large.
4.2 Dimension reduction algorithm
Next, we take an alternative approach and derive strongly polynomial approximate algorithm for problem (I). In this work, we do not treat the parameters d and N as input parameters. The message we hope to convey that the sample complexities are upper bounded by a constant independent of the objective function. This property is important for some applications of the stochastic I.2-function minimization problem where the objective function has unfavorable properties (e.g. large Lipschitz constant, small sub-optimality gap). Such unfavorable properties may not be known priori before the problem is solved. the parameters d and is treated as an input parameter, the proposed algorithms secudo-polyoomia
We observe that subgradient of convex function provides separation oracle to the global minima, which can be used to gradually shrink the set that contains global minima. This idea leads to the deterministic cutting- -plane methods (Vaidya, 1996; Bertsimas & Vempala, 2004; Lee et al., 2015). In this work, we develop a framework for extending cutting- outting-plane methods to the stochastic case. We prove that we average OddN' -2 log(1/ 1/))] stochastic subgradients, can get separation oracle for the set of e-approximate solutions with probability at least 1 8. Utilizing this stochastic separation oracle, we may extend the deterministic outting-plane methods to the stochastic
find PAC solutions.
However, the stochastic outting-plane methods still require the knowledge of the Lipschitz constant of the objective function. To design strongly polynomial algorithm, we observe that if convex body P C IRd has a volume smaller than (d!) = O Dlexp(-dd log(d)), then all integral points in P must lie on hyperplane. Otherwise, if there exist d + 1 points To..... .o......2. It E P that are not the same hyperplane, then the convex body P contains the polytope conv ,,, which has the volume
|det(x) - - -p...., mo)1 1 2 d! > vol(P), d!
where vol(P) is the volume of the polytope This leads to contradiction. Hence, we may use the stochastic version of Vaidya's method (Vaidya, 1996) or the random walk-based (Bertsi- mas & Vempala. 2004) cutting-plane method to reduce the volume of the search polytope to Olexp(-dlog(d)) and then reduce the problem dimension by projecting the polytope onto the hyperplane. After d dimension reductions, we have an one-dimensional convex problem and algorithms in Zhang et al. (2021) can be applied.
Theorem 6. Suppose that Assumptions 1-3 hold. Then, the dimension reduction algorithm is an [(c, PAC. MC) -llgorrii with computational complexity
T(e, MC) = [ N2 (d + log N))
log 1 {
22
The dimension reduction method the first algorithm for the stochastic T.*-convex function minimiza- tion that is strongly polynomial and does not require prior knowledge about the objective function
8

---

except the L'-coovexitt. Recently, Jiang (2020) proved that the LLL algorithm (Lenstra et al., 1982) able reduce the number of arithmetic operations to be polynomial and make the algorithm more practical, but the LLI. algorithm will not reduce the number of evaluations to the stochastic objective values. Their results can naturally extended to the stochastic case to achieve the PAC guarantee. We note that if we allow exponentially many arithmetic operations, the LLL algorithm is not necessary and the computational complexity can be reduced to Old' N log(1) (o)) Similar to the gradient-based method, the acceleration scheme can reduce the number of required objective function value evaluations if we have a positive lower bound to the sub-optimality gap.
5 Lower Bounds
In this section, we provide a lower bound result on [(c, 8)-P. MCT] alloorthtss This result shows the limit of algorithms that achieve the PAC guarantee for any stochastic Li-convex functions. To prove lower bounds, we make non-trivial extensions the construction in Graur et al. (2020) get several convex models that are "similar" to each other but they have distinct optimal solutions, where the similarity between two models is characterized by the KL-divergence between their distributions. Hence, algorithms need a large number of evaluations to differentiate these models. More rigorously, the
inequality in Kaufmann al. (2016) utilized to get the following lower
bound:
Theorem 7. Suppose Assumptions 1-3 hold. We have
6(c,6, 2 0 log )
2
Comparing with the lower bound for the expected error in Ito (2019), our high-probabilityy lower bound is ((d) smaller but includes extra term log(1/8). Since the failing probability 8 can be sufficiently small, the two lower bounds are not directly comparable. The results in Sections 3-4 imply that
T(e, MC)) ô min M4
log
Therefore, we conjecture that the optimal computational complexity is asymptotically independent of N and leave the design of optimal algorithms for future works.
6 Numerical Experiments
In this section, we present a brief account of numerical experiments to illustrate several of our theoretical findings. First, we show that the extra new truncation step in the gradient-based method can achieve better performance, compared to the mrudient-based method without the truncation step. We implement Algorithm with and without the truncation operation on staffing allocation stochastic optimization problem with staffing cost constraint, which can be formulated into the regularized and the constrained forms. Details about the problem setup are provided in the appendix. We summarize the computational complexities and the objective values in Table 2. We can see that the two algorithms achieve similar objective values but the "Truncated" version observes an advantage in the computational cost compared to the "Not Truncated" version. We note that our algorithms do not require the feasible region to be a hypercube and fact the problems considered in this section have more general feasible set with constraints. Especially, we can see that the truncation plays an important role in reducing the computational complexity, especially when the dimension is high.
Next. we compare the performances of the gradient-based methods and stochastic localization algorithms on multi-dimensional problems. To facilitate the comparison, we construct separable stochastic convex function, which is an [-=cvevex function by the results in Murota (2003). We have observed that using (Ne/4, 8/4)-SO oracles is enough for producing high probability guarantees using the dimension reduction method within the range < N < 150. More details about the experiment setup are provided in the appendix. We summarize the results Table 3, where the coverage rate refers to the percentage of implementations that produce an e-optimal solution. Since the coverage rates the algorithms are 100%, the PAC guarantee is satisfied by all of the algorithms except the (d, .N (20, 50) case for the dimension reduction method. This failure is because of

---

Table Complexity and returned objective value of Algorithm 2 on the optimal allocation problem. The cost refers to the average computational complexity in all the following tables.
Regularized
Constrained
Params.
Truncated
Not truncated
Truncated
Not truncated
Cost
Obj-
Cost
Obj.
Cost
Obj-
Cost
Obj-
4
10
2.99e5
2.10c2
6.56c5
2.11e2
3.00e5
4.76c1
4.99c5
4.97e1
20
1.21e5
3.53e2
2.61e5
3.53e2
1.14e5
5.23e1
1.77e5
5.38e1
4
30
8.85e4
4.75e2
1.68e5
4.76e2
7.38e4
5.24e1
1.23e5
5.21e1
4
40
6.25e4
5.91e2
1.34e5
6.07e2
5.28e4
5.31e1
9.24e4
5.28e1
50
5.34e4
7.07e2
1.08e5
7.07e2
4.66e4
5.64e1
6.61e4
5.51el
8
10
1.19c6
1.75c2
3.80c6
1.76e2
1.20c6
3.11e1
2.23e6
3.02e1
12
10
2.68e6
1.59e2
9.48e6
1.59e2
2.69e6
1.87e1
5.36e6
1.86e1
10
6.35e6
1.49e2
1.31e7
1.50e2
4.78e6
1.49e1
1.08e7
1.41el
20
10
9.91e6
1.43e2
2.09e7
1.46e2
9,43e6
1.17e1
1.70e7
1.28el
24
10
1.50e7
1.35e2
3.09e7
1.4122
1.36e7
9.43e0
2.10e7
1.17cl
Table Complexity and coverage rate of different algorithms on separable convex functions.
Params.
Truncated subgradient
Dimension reduction
N
Cost(10")
Rate(%)
Cost(10")
Rate(%)
50
0.39
100.0
100.0
100
0,44
100.0
0.22
100.0
150
0.51
100.0
0.25
100.0
50
0.96
100.0
1.51
100.0
6
100
1.07
100.0
1.76
100.0
150
1.24
100.0
1.92
100.0
10
50
1.26
100.0
3.47
100.0
10
100
1.43
100.0
4.02
100.0
10
150
1.64
100.0
4.33
100.0
50
1.52
100.0
4.14
100.0
20
50
1.69
100.0
4.28
99,00
loosened choice of the separation oracles. When the dimension is not large, the dimension reduction method has the best performance and has the advantage of not requiring any knowledge about the Lipschitz constant; when the dimension is large, the higher order dependence on makes the dimension reduction method inferior to the stochastic subgradient method. In addition, the computational complexity of the dimension reduction method has little dependence on N. This is because we choose the separation oracle to be (Ne/4, 6/4)-SO and the computational complexity of each evaluation is independent of N.
7 Conclusions
In this work, provide the first polynomial-time algorithms for the stochastic L*-convex minimiza- tion problem, which serves as an important extension of the stochastic submodular minimization problem. Comparing existing stochastic submodular minimization algorithms, our algorithms either achieve a lower computational complexity or do not require extra information about the objec- tive function. We also derive lower bound the computational complexity achieve the PAC guarantee. Numerical results are implemented to verify our theoretical findings.
Acknowledgments and Disclosure of Funding
Haixiang Zhang and Javad Lavaei were supported by grants from AFOSR, ARO, ONR, NSF and C3.ai Digital Transformation Institute.
10

---

References
Altman, E., Gaujal, B., and Hordijk, A. Discrete-event control of stochastic networks: Multimodular- ity and regularity. springer, 2003.
Axelrod, B., Liu, P.P. and Sidford, A. Near-optimal approximate discrete and continuous submodular function minimization. In Proceedings of the Fourieenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 837-853. SIAM, 2020.
Bach, F. Submodular functions: from discrete to continuous domains. Mathematical Programming, 175(1-2)419-455, 2019.
Balasubramanian, and Ghadimi, S. Zeroth-order nonconvex stochastic optimization: Handling constraints, high-dimensionality and saddle-points. arXiv preprint 1eXiv:1889) 06990 2018.
Bertsimas, D. and Vempala, S. Solving convex programs by random walks. Journal of the ACM (JACM), (4)5540-56, 2004.
Blais, E., Canonne, C. L., Eden, T., Levi, A., and Ron, D. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Transactions on Computation Theory (TOCT), (1(4): 1-33, 2019.
Borjesson, P. and Sundberg, C.-E. Simple approximations of the error function q (x) for communica- tions applications. IEEE Transactions on Communications, 27(3):639-643, 1979.
Burke, J. V. and Ferris, M. C. Weak sharp minima in mathematical programming SIAM Journal on Control and Optimization, 31(5)1144-1139) 1993.
Chakrabarty, D., Lee, Y. T., Sidford, A., and Wong, S. C.-w. Subquadratic submodular function mini- mization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 1220-1231, 2017.
Chen, X., Zhou, E., and Hu, J. Discrete optimization via gradient-based adaptive stochastic search methods. IISE Transactions, 50(9):789-805 2018.
Chick, S. E. Subjective probability and bayesian methodology. Handbooks in Operations Research and Management Science, 13:225-257, 2006.
Defazio, A., Bach, F., and Lacoste-Julien, S. Saga: fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
Duchi, J. Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788-2806 2015.
Eckman, D. J. and Henderson, S. G. Fixed-confidence, fixed-tolerance guarantees for selection-of- the-best procedures. Technical report, Working paper, Cornell University, School of Operations Research and 2018a.
Eckman, D. J. and Henderson, S. Guarantees on the probability of good selection. In 2018 Winter Simulation Conference (WSC), pp. 351-365. IEEE, 2018b.
Eckman, D. J., Plumlee, M., and Nelson, B. L. Plausible screening using functional properties for simulations with large solution spaces. Working paper, 2020.
Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes, In International Conference on Computational Learning Theory, pp. 255-270. Springer, 2002.
Fan, W. Hong, L. J., and Nelson, B. L. Indifference-zone-free selection of the best. Operations Research, 64(6): 199--114991 2016.
Favati, P. Convexity in nonlinear integer programming. Ricerca operativa, 53:3 44, 1990.

---

Frazier, P., Powell, W., and Dayanik, S. The knowledge-gradient policy for correlated normal beliefs. INFORMS journal on Computing, 21(4):599-613 2009.
Frazier, P. I. A fully sequential elimination procedure for indifference-zone ranking and selection with tight bounds on probability of correct selection. Operations Research, 62(():926-99) 992, 2014.
Freund, D., Henderson, S. G., and Shmoys. D. B. Minimizing multimodular functions and allocating capacity in bike-sharing systems. In International Conference on Integer Programming and Combinatorial Optimization, pp. 186-198. Springer, 2017.
Fu, .M. C. Optimization for simulation: Theory practice. INFORMS Journal on Computing, 14(3): 192-215, 2002.
Fujishige, S. Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions. Mathematical programming, 19(2):142-155, 1984.
Fujishige, S. Submodular finctions and optimization. Elsevier, 2005.
Futschik, and Pflug, G. Confidence sets for discrete stochastic optimization. Annals of Operations Research, 56(1):95-100) 1995.
Futschik, A. and Pflug, G. C. Optimal allocation of simulation experiments in discrete stochastic optimization and approximative algorithms. European Journal of Operational Research, 101(2): 1997.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
Graur, A., Pollner, T., Ramaswamy, V., and Weinberg, S. M. New query lower bounds for submodular function minimization. In 11th Innovations in Theoretical Computer Science Conference (ITCS für Informatik, 2020.
2020). Schloss Dagstuhl-Leibniz-ZZeeee
Gutjahr, W. J. and Pflug, G. C. Simulated annealing for noisy cost functions. Journal of global optimization, 8(1):1-13, 1996.
Hassani, H., Soltanolkotabi, M., and Karbasi, A. Gradient methods for submodular maximization. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 5843 5853, 2017.
Hassidim, A. and Singer, Y. Submodular optimization under noise. Conference on Learning Theory, pp. 1069-1122. PMLR, 2017.
Hazan, and Kale, Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 421-436, 2011.
Homem-de Mello, T. and Bayraksan, G. optimization. Surveys in Operations Research and Management Science, 19(1):56-85, 2014.
Monte carlo sampling-based methods for stochastic
Hong, L. J. and Nelson, B. L. Discrete optimization via simulation using compass. Operations Research, 54(1):115-12,, 2006.
Hong, J.J., Nelson, B. L.,, and Xu, J. Speeding up compass for high-dimensional discrete optimization via simulation. Operations Research Letters, 3866)550--555, 2010.
Hong, J.J Nelson, B. L.,, and J. Discrete optimization via simulation. In Handbook of simulation optimization, pp. 9-44. Springer, 2015.
Hong. J., Fan, W. and Luo, J. Review on ranking and selection: new perspective. arXiv preprins 0Bt1:2008.002444 2020.
Hu, J., Fu, M. C., and Marcus, T. A model reference adaptive search method for global optimization. Operations Research, 55(3):549-566 2007.
12

---

Hu, J., Fu, M. C., Marcus, S. I., et al. A model reference adaptive search method for stochastic global optimization. Communications in Information & Systems, 8()):255-276, 2008.
Hunter, S. R. and Nelson, B. L. Parallel ranking and selection. In Advances in Modeling and Simulation, pp. 249-275. Springer, 2017.
Ito, S. Submodular function minimization with noisy evaluation oracle. In Advances in Neural Information Processing Systems, pp. 12103-12113, 2019.
Ito. S. and Fujimaki, R. Large-scale price optimization via network flow. In NIPS, pp. 3855-3863, 2016.
Jegelka, S. and Bilmes, J. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR 2011. pp. 1897-1904. IEEE, 2011.
Jian, N., Freund, D.. Wiberg, H. M., and Henderson, G. Simulation optimization for a large-scale bike-sharing system. In 2016 Winter Simulation Conference (WSC), pp. 602-613. IEEE, 2016.
Jiang, H. Minimizing convex functions with integral minimizers. arXiv preprint arXiv:2007.01445, 2020.
Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. In Advances neural information processing systems, pp. 315-323, 2013.
Karimi, M. R., Lucie, M., Hassami, H., and Krause, A. Stochastic submodular maximization: the case of coverage functions. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6856-6866, 2017.
Kaufmann, E., Cappé, O., and Garivier, A. On the complexity of best-arm identification in multi- armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
Kim, S.-H. and Nelson, B. L. Selecting the best system. Handbooks in operations research and management science, 13:501-534, 2006.
Kleywegt, A. J., Shapiro, A., and Homem-de Mello, T. The sample average approximation method for stochastic discrete optimization. SIAM Journal Optimization, 12(2):479-55) 2002.
Larson, J., Menickelly, M., and Wild, S. M. Derivative-free optimization methods. arXiv preprint arXiv: 1585, 2019.
Lee, Y. T., Sidford, A., and Wong, S. C.-w. A faster cutting plane method and its implications for combinatorial and convex optimization. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049-1065. IEEE, 2015.
Lenstra, A. K., Lenstra, H. W., and Lovász, L. Factoring polynomials with rational coefficients. Mathematische annalen, 261 (6[(ARIICL)::5155555 1982.
Lim, E. Stochastic approximation over multidimensional discrete sets with applications to inventory systems and admission control of queueing networks. ACM Transactions on Modeling and Computer Simulation (TOMACS), 22(4):1-23, 2012.
Lovász, L. Submodular functions and convexity. In Mathematical programming the state of the art, pp. 235-257. Springer, 1983.
Ma, S. and Henderson, S. G. An efficient fully sequential selection procedure guaranteeing probably approximately correct selection. In 20/7 Winter Simulation Conference (WSC), pp. 2225-2236 2236.. IEEE, 2017.
Mokhtari, A., Hassani, H., and Karbasi, A. Conditional gradient method for stochastic submodular maximization: Closing the gap. In International Conference on Artificial Intelligence and Statistics, pp. 1886-1895. PMLR, 2018
Murota, K. Discrete convex analysis. Society for Industrial and Applied Mathematics. Citeseer, 2003.
13

---

Nelson, B. L. Optimization via simulation over discrete decision variables. In Risk and Optimization in an Uncertain World, pp. 193 207. Informs, 2010.
Nemirovsky, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983.
Nesterov, Y. Lectures on convex optimization, volume 137. Springer, 2018.
Nesterov, Y. and Spokoiny, V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):277-566, 2017.
Nesterov, Y. E. A method for solving the convex programming problem with convergence rate o (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Park, C. and Kim, S.-H. Penalty function with memory for discrete optimization via simulation with stochastic constraints. Operations Research, 63(5): 1eei1199-11222 2015.
Park, C., Telci, I. T., Kim, S.-H., and Aral, M. M. Designing an optimal water quality monitoring network for river systems using constrained discrete optimization via simulation. Engineering Optimization, 46(1):107-123) 2014.
Sekar, S., Vojnovie, M., and Yun, S.-Y. A test score-based approach to stochastic submodular 2021. doi: 10. wwt.128/mms..222203555 URL
optimization. Management Science, https://doi. org/ 10. 1287 /nsc/
Semelhago, M., Nelson, B. L., Song, E., and Wächter, A. Rapid discrete optimization via simulation with Gaussian Markov random fields. INFORMS journal on Computing, Articles in Advance, 2020.
Shaked, M. and Shanthikumar, J. G. Stochastic convexity and its applications. Advances in Applied Probability, 20(2)427-446, 1988.
Shamir, O. A variant of azuma's inequality for martingales with subgaussian tails. arXiv preprint 1eXiv:1110.239) 2011.
Singhvi, D., Singhvi, S., Frazier, P. I., Henderson, S. G., O'Mahony, E., Shmoys, D. B., and Woodard, D. B. Predicting bike usage for new york city's 's bike sharing system. AAAI Workshop: Computational Sustainability. Citeseer, 2015.
Sun, L.,, Hong, L. J., and Hu, Z. Balancing exploitation and exploration in discrete optimization via simulation through gaussian process-basee basedd search. Operations Research. 1416)11416 2014.
Vaidya, P. M. A new algorithm for minimizing convex functions over convex sets. Mathematical programming, 73(3):291-344 1996.
Wang, G., Zhang, L., Giannakis, G. B., Akçakaya, M., and Chen, J. Sparse phase retrieval via truncated amplitude flow. IEEE Transactions on Signal Processing, 66(2):499-911, 2017.
Wang, H., Pasupathy, R., and Schmeiser, B. W. Integer-ordered simulation optimization using r-spline: Retrospective search with piecewise-linear interpolation and neighborhood enumeration. ACM Transactions on Modeling and Computer Simulation (TOMACS), 23(3):1-24, 2013.
Wolff, R. W. and Wang, C.-L. On the convexity of loss probabilities. Journal of applied probability, pp. 402-406, 2002.
Xu, J., Nelson, B. L.,, and Hong, J. Industrial strength compass: A comprehensive algorithm and software for optimization via simulation. ACM Transactions on Modeling and Computer Simulation (TOMACS), 20(1):1-29, 2010.
Xu, Y. Lin, Q. and Yang, T. Accelerated stochastic subgradient methods under local error bound condition. arXiv preprint arXiv:1607.010077 2016.
Yang, T. and Lin, Q. Rsg: Beating subgradient method without smoothness and strong convexity. The Journal of Machine Learning Research, 19(1):236-266 2018.
14

---

Zhang, H., Zheng, Z., and Lavaei, J. Selection of the best under convexity. SSRN preprint 3848865, 2021.
Zhang. J., Lin, H., Sra, S., and Jadbabaie, A. On complexity of finding stationary points nonsmooth nonconvex functions. arXiv preprint arXiv:2002.04130, 2020.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
15


Reviews:
[{"review_id": "l2DkmbWf92", "reviewer": "Reviewer_sXUy", "summary": "This paper studies the minimization of a stochastic L$^\\\\natural$-convex function.\n- The authors analyze the convergence of three algorithms, truncated subgradient, multi-dim uniform sampling, and stochastic cutting-plane. The time complexity of these algorithms is typically $O(d^2N^2/\\\\epsilon^2)$ or something higher, where $d$ is the dimension, $N$ is the range of the feasible region, and $\\\\epsilon$ is the error-accuracy.\n- The authors also proved a lower bound that any algorithm takes $\\\\Omega(d/\\\\epsilon^2)$-time to find an $\\\\epsilon$-optimal solution.\n- In numerical experiments, the truncated subgradient method rapidly found an $\\\\epsilon$-optimal solution.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has solid algorithmic results and a lower bound. The algorithms exploit recent techniques developed in fast submodular function minimization using subgradients of the Lovász extension. This paper extends these techniques towards two directions, from submodular to L$^\\\\natural$-convex and from exact to stochastic oracles. These extensions seem nontrivial. Therefore, the theoretical contributions are novel and significant.\n\nOn the other hand, the writing is unclear in several places. There is undefined terminology, and the table of the experiment is difficult to understand. Furthermore, the lower bound result looks weaker than the known result.\n- Known sub-optimality gap: What does the known sub-optimality gap mean exactly? This concept seems crucial as it reduces $N$ to $\\\\log N$ in the time complexity. Unfortunately, almost nothing was explained. Is it equivalent to that the function is $1/c$-integer valued?\n- Lower bound: Ito (2019) proved an $\\\\Omega(d/\\\\sqrt{T})$ lower bound for the additive error of stochastic submodular function minimization, where $T$ is the number of oracle calls. This translates to $\\\\Omega(d^2/\\\\epsilon^2)$ oracle calls, which is larger than the claimed $\\\\Omega(d/\\\\epsilon^2)$ lower bound on the time complexity. How can I compare these lower bounds?\n- Experiments: Tables 2 and 3 are difficult to understand. What does \"Cost\" mean there? Is it the running time in sec? Furthermore, the range of $d$ and $N$ are somewhat small. Since the method used in the experiment is first-order, should it be scalable to larger instances?\n\nFor now, I would wait for the authors' response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hD-ocrj1No9", "reviewer": "Reviewer_2nJo", "summary": "This paper studies stochastic L# -convex minimization problem and develops the \"polynomial\" time algorithms that return a near-optimal solution.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Originality.\nThe algorithmic results on stochastic L# convex programs are new and important.\n\n2. Quality and Significance.\nMany results are simply applying existing ones, and the \"polynomial-time\" algorithm may be incorrect.\n1). All the algorithms presented in this paper have running time proportional to N, an input of the stochastic L# convex programs. This means that the proposed algorithms are rather pseudo-polynomial. This is an important concept, since the Knapsack problem admits a pseudo-polynomial algorithm but is NP-complete. Please carefully define it and clarify it.\n2). The paper is literally done by showing the Lovas extension (i.e., Theorem 1). \nFor example, Theorem 2 is due to convexity and Hoeffding bound.\nTheorems 3 and 4 are anazlying the stochastic subgradient method. What is fundamental difference between this theorem and others in the existing literature? Such as \n\nBoyd, Stephen, and Almir Mutapcic. \"Stochastic subgradient methods.\" Lecture Notes for EE364b, Stanford University (2008).\n\nDavis, Damek, et al. \"Stochastic subgradient method converges on tame functions.\" Foundations of computational mathematics 20.1 (2020): 119-154.\n\nRuszczyński, Andrzej. \"Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization.\" Optimization Letters (2020): 1-11.\n\nTheorem 6 is a simple application of Jiang (2020) via LLL algorithm (Lenstra et al., 1982)\n\n3). The lower bound result in Theorem 7 is interesting. Is there a polynomial-time algorithm for solving L# convex programs? At least we know that for [0,1} submodular minimization, it is a strongly polynomial-time solvable. \n\n3. Clarity.\nAlgorithm 1: please define the neighboring points in the main paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a theoretical work and potentially has a significant impact on the society. ", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "M55UsK108Dn", "reviewer": "Reviewer_QmRr", "summary": "This paper focuses on the problem of minimizing $f(x) = \\mathbb{E}_{\\xi}[F(x,\\xi_x)]$ where $f:[N]^d\\to\\mathbb{R}$ is an $L^\\natural$ function. This class of functions can be interpreted as a discrete analog of convex functions. The goal is to design polynomial time algorithms that guarantee a solution whose value is $\\epsilon$ away from the optimal value with probability at least $1-\\delta$ (in the paper referred as $(\\epsilon,\\delta)$-PAC guarantee).\n\nThe authors provide upper bounds and a lower bound for the computational complexity of the problem, which is defined as the worst-case expected time over all possible $(\\epsilon,\\delta)$-PAC algorithms. First, the authors present the standard Lovasz extension for $L^\\natural$ functions. This extension is convex so common techniques in convex optimization can be used. First, they present a truncated stochastic subgradient algorithm that has an appropriate rounding procedure as a final step. They show this method has a complexity of $\\tilde{O}(\\frac{d^2N^2}{\\epsilon^2}\\log(1/\\delta))$ when $f$ is $L$-Lipschitz. Later, they show that under the assumption that the subgradients of the function are uniformly bounded with probability 1, the same algorithm without truncation has an improved complexity. The authors also study the performance of the algorithms when the suboptimality gap is known. Then, they give two methods for the case when the Lipschitz constant is not known: multidimensional uniform sampling and dimension reduction. Finally, they give an information-theoretical lower bound of $\\Theta(\\frac{d}{\\epsilon^2}\\log(1/\\delta))$.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall well written and easy to follow. I think one of the main contributions of the paper is the rounding technique applied in the truncated gradient descent. The rest of the analysis uses standard techniques in convex optimization, which is possible since the Lovasz extension is convex. It would be great if the authors give more intuition on the role that the truncation plays, more than simply stating that it reduces the complexity. Also, they should mention if this technique has been used before in other contexts.\n\nThe lower bound seems a direct adaptation of the techniques used in [Zhang et al. 2021] and [Graur et al. 2020]; the authors should comment if there is any new technical contribution.\n\nIt is hard to analyze the impact of the results in Section 4, in particular because they heavily rely on two preprints [Zhang et al. 2021] and [Jiang 2020], and most of the analyses are in the Appendix.\n\nI think the paper has its merits, but the authors should emphasize the challenges that the $L^\\natural$ functions pose in each given analysis, in this way the technical contributions would be highlighted. Otherwise, my feeling (without being an expert on the specific techniques that are used) is that the paper forgets about $L^\\natural$ functions once the Lovasz extension is given, since the whole toolkit of convex optimization can be used. I carefully checked some of the proofs in the Appendix and, for example, it is not clear what role the Lovasz extension plays in the proof of Theorem 3 (Appendix C.2), besides convexity.\n\nMinor comments:\n-\tPage 2 Line 53: reference should be Hazan & Kale (2011)?\n-\tPage 2 Table 1: caption mentions $M$ but this term is not there.\n-\tPage 3 line 104: an\n-\tPage 3 line 119: algorithms -> algorithm\n-\tPage 4 line 137: clarify that $[1,N]^d$ corresponds to the continuous cube to avoid confusion with the discrete set $[N]^d$\n-\tPage 5 Alg. 2: in line 1, $T$ refers to transpose?\n-\tPage 7: there is a text in blue\n-\tPage 8 line 320: objective values\n-\tAppendix eq (17): extra N?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some of the limitations. The work is purely theoretical so there are no clear potential societal impacts", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "13"}, "extra_text": {}}, {"review_id": "5oZSwcYJ54B", "reviewer": "Reviewer_CCmo", "summary": "In this paper, the authors studied the problem of stochastic $L^{\\natural}$-convex function minimization. This problem is a extension of submodular minimization. Authors come up with an algorithm that uses projected gradient descent with truncated gradient on lovasz extension. They also provide lower bound for the complexity of this problem.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1)Author motivates the subject from a theoretical and practical point of view.\n2)In the introduction, the author reviewed the previous works. Still, related papers like [1,2] have not been appropriately discussed.\n\n3)the author successfully addressed the issue and recommended the algorithms. \n\n4)The authors successfully provide simulation results for their algorithm. \n\n5)The paper is well-organized and well-written.\n\n6)The proof is mathematically correct.\n\n7)the code is not included.\n\n\n[1]Chakrabarty, D., Lee, Y. T., Sidford, A., & Wong, S. C. W. (2017, June). Subquadratic submodular function minimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1220-1231).\n\n[2]Axelrod, B., Liu, Y. P., & Sidford, A. (2020). Near-optimal approximate discrete and continuous submodular function minimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 837-853). Society for Industrial and Applied Mathematics.\n\n\n----------- Post Rebuttal------------- \n\nI have read all the comments, and I don't change my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and potential negative social impact of their work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: From the SAC: after looking at the paper, reviews, rebuttal, and discussion, and questions about reviewer sXUy , I am going to concur with the AC's recommendation of accept as a poster. However, this was a borderline paper compared to other papers, so I strongly urge you to take these reviewer comments into account. By your own words, "We agree that the lower bound established in this work is a little counter-intuitive, when being compared to Ito (2019)", therefore, it behooves you to make sure in the next version of this paper that this fact is acknowledged in the paper, and that you strive in your edits to make it as non-counter-intuitive as possible. Also, please ensure that all questions and concerns raised by the reviewer are addressed in the next version of the paper. 
Decision: Accept (Poster)