Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: 1)Author motivates the subject from a theoretical and practical point of view.
2)In the introduction, the author reviewed the previous works. Still, related papers like [1,2] have not been appropriately discussed.

3)the author successfully addressed the issue and recommended the algorithms. 

4)The authors successfully provide simulation results for their algorithm. 

5)The paper is well-organized and well-written.

6)The proof is mathematically correct.

7)the code is not included.


[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).

[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.


----------- Post Rebuttal------------- 

I have read all the comments, and I don't change my score.
limitations_and_societal_impact: The authors discussed the limitations and potential negative social impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).

The 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))$.

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.

The 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.

It 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.

I 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.

Minor comments:
-	Page 2 Line 53: reference should be Hazan & Kale (2011)?
-	Page 2 Table 1: caption mentions $M$ but this term is not there.
-	Page 3 line 104: an
-	Page 3 line 119: algorithms -> algorithm
-	Page 4 line 137: clarify that $[1,N]^d$ corresponds to the continuous cube to avoid confusion with the discrete set $[N]^d$
-	Page 5 Alg. 2: in line 1, $T$ refers to transpose?
-	Page 7: there is a text in blue
-	Page 8 line 320: objective values
-	Appendix eq (17): extra N?

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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the minimization of a stochastic L$^\\natural$-convex function.
- 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.
- The authors also proved a lower bound that any algorithm takes $\\Omega(d/\\epsilon^2)$-time to find an $\\epsilon$-optimal solution.
- In numerical experiments, the truncated subgradient method rapidly found an $\\epsilon$-optimal solution.
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.

On 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.
- 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?
- 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?
- 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?

For now, I would wait for the authors' response.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies stochastic L# -convex minimization problem and develops the "polynomial" time algorithms that return a near-optimal solution.
main_review: 1. Originality.
The algorithmic results on stochastic L# convex programs are new and important.

2. Quality and Significance.
Many results are simply applying existing ones, and the "polynomial-time" algorithm may be incorrect.
1). 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.
2). The paper is literally done by showing the Lovas extension (i.e., Theorem 1). 
For example, Theorem 2 is due to convexity and Hoeffding bound.
Theorems 3 and 4 are anazlying the stochastic subgradient method. What is fundamental difference between this theorem and others in the existing literature? Such as 

Boyd, Stephen, and Almir Mutapcic. "Stochastic subgradient methods." Lecture Notes for EE364b, Stanford University (2008).

Davis, Damek, et al. "Stochastic subgradient method converges on tame functions." Foundations of computational mathematics 20.1 (2020): 119-154.

Ruszczyński, Andrzej. "Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization." Optimization Letters (2020): 1-11.

Theorem 6 is a simple application of Jiang (2020) via LLL algorithm (Lenstra et al., 1982)

3). 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. 

3. Clarity.
Algorithm 1: please define the neighboring points in the main paper.
limitations_and_societal_impact: It is a theoretical work and potentially has a significant impact on the society.
review_title: null

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)