{"id":"aa8a001c-f1b5-429f-a873-61024e6825ba","arxiv_id":"1909.00171","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A data-structure trick based on binary segment decomposition yields near-optimal ~O(n/ε²) oracle complexity for approximate submodular function minimization, down from ~O(n^{3/2}/ε²), with extensions to continuous submodular functions.","lead":"This paper gives a randomized algorithm that approximately minimizes any submodular function on n elements using only ~O(n/ε²) function evaluations, improving the previous best known bound of ~O(n^{3/2}/ε²). It also extends the technique to continuous submodular functions and gives the first sublinear-time algorithm for sparse minimizers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Lemma 3.4's sign-partition is terse but repairable, so the central claim stands.","rationale":"I read the main proof as: stochastic subgradient descent with ~O(1) variance and ~O(1) amortized oracle calls per iteration yields ~O(n/ε²). All counting, unbiasedness, and variance arguments in Section 3 check out. The weakest point is the sign-partition fact in Lemma 3.4. Investigating it, the fact is true and can be proved by a small modification: partition into maximal unchanged-coordinate blocks (constant sign by Lemma 3.2) and changed-coordinate singletons. The paper's '2k' can be 3k+1; constants are irrelevant. The algorithm's use of these data structures also assumes a consistent choice of subgradient at each point when it appears in multiple segments; a deterministic tie-breaking rule resolves this. The continuous and sparse extensions are sketched more thinly, but they are not the paper's central theorem. The 'near-optimal' optimality claim relies on a subgradient-oracle lower bound whose transfer to evaluation oracle is not argued, but that affects only the title and phrasing, not the upper bound. Overall, the central claim is credible and the reader's ACCEPT verdict is appropriate.","tokens_in":24988,"tokens_out":36553,"duration_ms":312978,"concrete_test":"Write out the interval decomposition in Lemma 3.4 explicitly: for d≥0 with support S, let C be the common subsequence of [n]\\S, cut C at the 2k insertion positions of S in Px and Py, and add singletons for S; verify each block has all differences nonpositive (Lemma 3.2) and each singleton has trivially constant sign, with O(k) intervals total. Test the tie case x=(0.4,0.2,0), y=(1,1,0), Px=(1,2,3), Py=(2,1,3), f(S)=-|S|²: the partition {3},{1},{2} has signs 0,-2,+2, is valid and covers [3]. If this decomposition fails for some inputs, Lemma 3.4 is false; otherwise the proof gap is closed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The only substantive risk to Theorem 1 is Lemma 3.4's claim that g(y)-g(x) partitions into O(k) constant-sign intervals. As written, the Appendix B proof attributes this to Lemma 3.2 for every element of each interval, which is not correct for support coordinates. However, the claim itself is true: after reducing to the all-nonnegative case, take the maximal common subsequences of the n-k unchanged coordinates as blocks (each is contiguous in both permutations and has all differences nonpositive by Lemma 3.2) and take each of the k changed coordinates as a singleton (trivially constant sign). This gives at most 3k+1 intervals, so the preprocessing and sampling argument in Lemma 3.4 goes through unchanged. A second minor gap is that the permutations consistent with x and y need to be chosen by a fixed tie-breaking rule across different calls, or the telescoping identity in Algorithm 1 could fail; specifying a deterministic tie-breaker fixes this. Neither issue invalidates the ~O(n/ε²) oracle bound; both are presentation gaps in the proof of a true lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a randomized algorithm for ε-approximate submodular function minimization on {0,1}^n with range [-1,1] using ~O(n/ε^2) evaluation-oracle calls, improving on prior ~O(n^{5/3}/ε^2) and ~O(n^{3/2}/ε^2) algorithms. It further gives an ~O(sM^2)-call algorithm for integer-valued SFM with an s-sparse minimizer, an ~O(nk^4/ε^2)-call algorithm for submodular functions on [k]^n, and an ~O(nL^6/ε^6)-call algorithm for continuous twice-differentiable functions with nonpositive mixed partials. The method runs projected stochastic subgradient descent on the Lovász extension and uses a data structure that samples sparse unbiased estimators of gradient differences; the binary decomposition of the iteration counter is used to amortize preprocessing costs.","tokens_in":25074,"tokens_out":17829,"duration_ms":145835,"significance":"If the main theorem is correct, it resolves the open problem of near-linear oracle complexity for approximate SFM posed by CLSW17 and HRRS19, and it is optimal up to the ε dependence given the subgradient-oracle lower bound. The sparse pseudopolynomial result gives the first sublinear-time SFM algorithm in the sparse regime, and the continuous extension substantially improves Bach's cubic dependence on n. The paper's high-level architecture is sound: Lemma 3.1 and Lemma 3.3 provide the needed norm and interval-sum tools, and the amortization of preprocessing costs over the trajectory is a genuine contribution. The main caveat is that the proof of the key data-structure lemma is incomplete as written, so the central claim currently rests on a gap that must be repaired.","major_comments":[{"comment":"The proof asserts that because Px and Py differ by k deletions and insertions, there are subsets I1,...,I_{2k} that are intervals in both permutations and carry a common sign for g(y)-g(x). This is not demonstrated: Lemma 3.2 supplies a sign only for coordinates outside the support of d=y-x, while the changed coordinates can have arbitrary signs, and a common interval containing changed coordinates need not be uniform in sign. The proposed alternative of taking maximal common subsequences of unchanged coordinates also needs an argument that those blocks are contiguous in both full permutations, which is not automatic. Since the O(k) preprocessing bound and the O(1) second-moment guarantee of the lemma both depend on this partition, the proof must supply an explicit construction of the intervals and a proof of the uniform-sign property.","section":"Appendix B, proof of Lemma 3.4"},{"comment":"Algorithm 1 uses g(x) as if it were a single-valued function, but g(x) is defined by a consistent permutation and is not unique at ties; at x0=0 every permutation is consistent. Without a deterministic tie-breaking rule, the same point can receive different subgradients in different calls to Process and Sample, and the telescoping identity used to form g⋆i can fail. The paper should fix a deterministic consistent-permutation rule, for example breaking ties by coordinate index, and prove that all invocations use the same rule.","section":"Algorithm 1, lines 3, 7, 8, 12; Appendix B"},{"comment":"Section 4 derives the exact-minimizer guarantee of Theorem 2 from Theorem 7, which only proves E[ˆf(x)] < min_T f(T) + 1. The step 'It is direct to see' omits the amplification argument that repeated runs, combined with Lemma 2.2 to convert each point to a set, give an exact minimizer with high probability. This should be stated because Theorem 2's contribution is exactness in the sparse regime.","section":"Section 4, proof of Theorem 7 and Theorem 2"}],"minor_comments":[{"comment":"There is a typo in 'weekl y polynomial' in the first sentence; it should read 'weakly polynomial.'","section":"Section 1.2"},{"comment":"The notation 'argminS⊆{0,1}nf(S)' should be written as 'argmin_{S⊆[n]} f(S)' for clarity.","section":"Theorem 2 statement"},{"comment":"The parameter ε is not used in the stated guarantee of SparseSFM, which returns a point with E[ˆf(x)] < min_T f(T) + 1; either rename the parameter or clarify that the guarantee is additive error 1.","section":"Algorithm 4 header"},{"comment":"The caption and diagram for the decomposition of [0,11] are hard to parse; adding explicit segment values such as (0,8), (8,10), (10,11) would improve readability.","section":"Figure 1"},{"comment":"The phrase 'use the proof of Lemma 3.2 above' should read 'use the proof of Lemma 3.4,' and the word 'coordiantes' is misspelled. More importantly, the reduction to points x′, y′ should explicitly note that g depends only on the consistent permutation, so the data structure for x′, y′ yields the same g(y)-g(x).","section":"Appendix B, proof of Lemma 4.4"},{"comment":"The sentence 'We can also verify that f′ is submodular' would benefit from a one-line verification, since the discrete submodularity of f′ follows from the continuous mixed-partial condition by integrating over grid cells.","section":"Section 5.3, proof of Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"I believe the main theorem is very likely correct and the paper is a strong candidate for publication after the proof of Lemma 3.4 is repaired. The reliance on prior co-authored lemmas is legitimate and not circular. The stress-test note's proposed fix for the interval-sign partition is not fully convincing as stated, so the authors should provide a detailed proof rather than a terse assertion."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper delivers what it claims — O~(n/ε²) oracle calls for approximate SFM, improving on the n^5/3 and n^3/2 bounds — and it does so with a genuinely new binary-representation amortization. I would send this to a serious referee.\n\nWhat's new: the segment decomposition using the binary representation of the iteration counter to amortize preprocessing is the real technical departure from CLSW17 and HRRS19. The proof of the main theorem is mostly coherent: unbiased stochastic gradients with O(1) second moment, and the oracle count summing Σ 2^{ν2(i)} = O~(T). The sparse-minimizer result (~O(sM²)) and the continuous result (~O(nL^6/ε^6)) are also new, though presented more sketchily.\n\nWhere I would push: Lemma 3.4's Appendix B proof asserts that g(y)-g(x) partitions into O(k) intervals of common sign based on deleting k elements. As written that is too fast: Lemma 3.2 gives the sign for coordinates where the difference is zero, but the moved coordinates need to be handled separately. The claim itself is true — take the unchanged runs as blocks plus the k changed coordinates as singletons — so this is a repairable presentation gap, not a flaw. Same for the need to fix a tie-breaking rule for consistent permutations; without it the telescoping in Algorithm 1 could pick different subgradients for the same point. A one-line deterministic tie-breaker fixes it.\n\nThe continuous sections are weaker: Lemma 5.7 and Theorem 7 are proof sketches, and the submodularity of the discretized function is asserted without proof (it does follow from the mixed-partial condition, but it should be stated). The 'near-optimal' phrasing in Section 1.1 leans on a subgradient-oracle lower bound, and the transfer to the evaluation-oracle model is not argued carefully; the result is probably optimal, but the claim is stronger than the argument. None of this changes my view that the central bound is correct.\n\nCitation pattern is fine: the CLSW17/HRRS19 comparisons are accurate, and reliance on LSW15 and CLSW17 lemmas is legitimate.\n\nWho this is for: anyone working on submodular optimization or oracle-efficient convex minimization. The main theorem resolves an open problem and should be cited. The paper deserves full peer review; it will need minor revisions to tighten Lemma 3.4's proof and the continuous-section sketches, but the core contribution stands.","headline":"Main theorem genuinely resolves the near-linear oracle complexity question for approximate SFM; the proof has a terse but repairable gap in Lemma 3.4, and the extensions are sketchier but sound.","tokens_in":25758,"tokens_out":4949,"would_cite":true,"duration_ms":42181,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Near-linear queries suffice to approximately minimize submodular functions","keywords":["submodular function minimization","oracle complexity","stochastic subgradient descent","Lovász extension","continuous submodularity","nonconvex optimization","sparse minimizer","near-linear algorithms"],"falsifier":"Exhaustively search all submodular functions on a small universe (say $n\\le 6$) for a pair of points $x,y$ with $y-x$ 1-sparse such that the coordinate-wise difference $g(y)-g(x)$, ordered by a permutation consistent with both points, changes sign more than a constant number of times. One such example would falsify Lemma 3.4 and with it the paper's $\\tilde{O}(n/\\epsilon^2)$ oracle bound.","tokens_in":88,"feed_emoji":"📉","tokens_out":12095,"duration_ms":225722,"temperature":0.7,"pith_summary":"This paper claims that approximate submodular function minimization—finding a set whose value is within $\\epsilon$ of the minimum of a set function on an $n$-element universe—can be solved with only $\\tilde{O}(n/\\epsilon^2)$ evaluations of the function, up to logarithmic factors. That improves the previous best oracle complexity of $\\tilde{O}(n^{3/2}/\\epsilon^2)$ and matches the known lower bound for subgradient-based algorithms up to polylogarithmic factors. The algorithm runs projected stochastic subgradient descent on the Lovász extension of $f$ and uses a data structure that samples sparse, low-variance gradient estimates without reading all $n$ coordinates. The same machinery extends to submodular functions on $[k]^n$ and to a class of nonconvex continuous functions with nonpositive mixed partial derivatives, yielding nearly linear oracle complexity in those settings as well.","feed_headline":"Near-linear queries suffice to minimize submodular functions","feed_subtitle":"It also handles a broad class of nonconvex continuous functions in nearly linear time","key_machinery":"The Lovász extension $\\hat f$ of $f$—the convex set function obtained by ordering coordinates by size—turns set minimization into convex optimization. The load-bearing mechanism is a gradient-difference data structure (Lemma 3.4): when $y-x$ is $k$-sparse, after $O(k)$ evaluations it can sample, in $\\tilde{O}(1)$ further evaluations, a 1-sparse random vector $z$ with $\\mathbb{E}[z]=g(y)-g(x)$ and $\\mathbb{E}[\\|z\\|_2^2]=O(1)$. The algorithm chains these sampled differences along a binary decomposition of the iteration counter, so the stochastic subgradient at step $t$ is an estimate of $g(x_0)+\\sum_j (g(x_{k_{j+1}})-g(x_{k_j}))$, and the binary structure makes the total preprocessing cost $\\tilde{O}(1)$ per iteration. A continuous analogue of the extension, defined for submodular functions on $[k]^n$, plays the same role for the nonconvex minimization results.","core_discovery":"The central claim is Theorem 1: for any submodular function $f:\\{0,1\\}^n \\to [-1,1]$ and any $\\epsilon>0$, the algorithm returns a random set $S$ with $\\mathbb{E}[f(S)] \\le \\min_{T\\subseteq [n]} f(T)+\\epsilon$ while making $\\tilde{O}(n/\\epsilon^2)$ calls to an evaluation oracle for $f$. The argument constructs a stochastic subgradient oracle for the Lovász extension whose estimates are 1-sparse with expected squared norm $\\tilde{O}(1)$, so projected stochastic subgradient descent converges in $\\tilde{O}(n/\\epsilon^2)$ iterations. The key is avoiding the naive $\\Omega(n)$ cost of forming a full subgradient: the algorithm writes each new subgradient as a sum of differences between nearby points and samples each difference from a data structure maintained at amortized cost $\\tilde{O}(1)$ per iteration. The same reduction also yields an exact $\\tilde{O}(sM^2)$-query algorithm when $f$ is integer valued with range $[-M,M]$ and an $s$-sparse minimizer, and a $\\tilde{O}(nL^6/\\epsilon^6)$-query algorithm for nonconvex continuous functions with nonpositive mixed partial derivatives and $L^\\infty$-Lipschitz constant $L$.","pith_inferences":["The binary-counter amortization used here suggests a general recipe: any projected subgradient method whose iterates move by sparse steps and whose objective admits cheap interval-sum queries can enjoy the same near-linear amortized oracle cost; coordinate descent is a natural next test case.","The sparse-minimizer theorem has a consequence the authors leave implicit: when the optimum is small and the integer range is bounded, exact SFM need not inspect all $n$ elements, which points toward streaming or local-search versions of cut and matroid-rank minimization.","One testable reading of the continuous theorem is as a discretization lemma: functions with pairwise nonpositive mixed partials and Lipschitz constant $L$ can be minimized on a grid of step $\\epsilon/(2L)$; applying that to $g(\\sum_i c_i x_i)$ with concave $g$ gives a near-linear primitive for a class of nonconvex resource-allocation problems."],"forward_implications":["Oracle complexity for $\\epsilon$-approximate discrete submodular function minimization drops from $\\tilde{O}(n^{3/2}/\\epsilon^2)$ to $\\tilde{O}(n/\\epsilon^2)$, matching the subgradient-oracle lower bound up to polylogarithmic factors.","For integer-valued $f$ with range $[-M,M]$ and an $s$-sparse minimizer, exact minimization uses $\\tilde{O}(sM^2)$ oracle calls; this becomes the first sublinear-time algorithm when $sM^2=o(n)$.","For continuous $f$ on $[0,1]^n$ with all mixed partial derivatives $\\le 0$ and Lipschitz constant $L$, an $\\epsilon$-additive global minimizer can be found in $\\tilde{O}(nL^6/\\epsilon^6)$ evaluations, replacing a cubic dependence on $n$ with a nearly linear one.","The extension to submodular functions on $[k]^n$ runs in $\\tilde{O}(nk^4/\\epsilon^2)$ oracle calls, so the improvement is not tied to the Boolean lattice."],"supporting_citations":[{"why":"Supplies the projected stochastic subgradient descent convergence theorem that sets the iteration count $T=O(R^2B^2/\\epsilon^2)$.","marker":"[Bub15]"},{"why":"Provides the baseline $\\tilde{O}(n^{5/3}/\\epsilon^2)$ algorithm and the subgradient lemmas about $\\ell^1$ bounds, monotonicity, and interval sums on which the new data structure is built.","marker":"[CLSW17]"},{"why":"Gives the previous best $\\tilde{O}(n^{3/2}/\\epsilon^2)$ oracle bound that the main theorem improves.","marker":"[HRRS19]"},{"why":"Defines the continuous extension for submodular functions on $[k]^n$ and $[0,1]^n$ and its convexity and subgradient properties used in Theorems 3 and 9.","marker":"[Bac19]"},{"why":"Establishes the Lovász extension, its convexity, and its subgradient formula that underlie the whole descent approach.","marker":"[Lov83]"},{"why":"Credited with the $\\ell^1$ bound on Lovász subgradients that keeps the stochastic estimates low-variance and sparse.","marker":"[JB11]"}],"fun_headline_variants":["Submodular minimization in near-linear queries","Sparse subgradients make submodular minimization near-optimal","Near-optimal submodular minimization, discrete and continuous","Query-efficient submodular minimization: O~(n/ε²) calls","Efficient submodular minimization via stochastic subgradients"],"cache_read_input_tokens":27776,"weakest_assumption_plain":"The entire near-linear oracle bound rests on Lemma 3.4's assertion that when two points differ in only $k$ coordinates, the difference of their subgradients splits into $O(k)$ contiguous blocks whose entries all share a sign, so each block's sum can be evaluated in one oracle call; if that sign-partition property fails, the amortized per-iteration sampling cost stops being $\\tilde{O}(1)$ and the $\\tilde{O}(n/\\epsilon^2)$ bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Submodular minimization in near-linear queries","Sparse subgradients make submodular minimization near-optimal","Near-optimal submodular minimization, discrete and continuous","Query-efficient submodular minimization: O~(n/ε²) calls","Efficient submodular minimization via stochastic subgradients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000398,"raw_usage":{"total_tokens":2142,"prompt_tokens":1063,"completion_tokens":1079,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":995}},"tokens_in":679,"tokens_out":1079,"duration_ms":169148,"temperature":1.0,"reasoning_tokens":995,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T06:02:23.503354+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively search all submodular functions on a small universe (say $n\\le 6$) for a pair of points $x,y$ with $y-x$ 1-sparse such that the coordinate-wise difference $g(y)-g(x)$, ordered by a permutation consistent with both points, changes sign more than a constant number of times. One such example would falsify Lemma 3.4 and with it the paper's $\\tilde{O}(n/\\epsilon^2)$ oracle bound.","supporting_citations":[],"review_version":1}