{"id":"f4a05e13-0fe7-4a86-bdb0-78cad48f3952","arxiv_id":"2602.20578","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Non-monotone DR-submodular maximization over down-closed convex sets is 1/e-upper-linearizable, giving O(sqrt(T)) static regret with one gradient query per round.","lead":"This paper proves that maximizing a class of hard online reward functions — non-monotone DR-submodular objectives over down-closed convex sets — can be reduced to much simpler linear optimization with a 1/e approximation guarantee. This reduction yields the first O(sqrt(T)) regret algorithms that use only one gradient query per round, and it adds new adaptive and dynamic regret guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 3's dynamic regret bound uses a path length over surrogate-linear optimizers, not the true maximizers, so the advertised dynamic regret guarantee is not proven.","rationale":"The paper's structural theorem (1/e-upper-linearizability) appears sound after checking Lemma 1's derivation: the stronger \\bar{x} claim is indeed unfounded, but the weaker e^{-z} inequality used in the proof follows from B&F Lemma 4 and non-negativity. The main unresolved issue is the dynamic regret analysis, which conflates two different comparator sequences. This is a concrete, checkable flaw in a headline contribution. The bandit rate inconsistency (Prop 6 vs Table 1) is a secondary issue. Since the theoretical structure may be repairable by correcting the path length definition, the appropriate verdict remains CONDITIONAL.","tokens_in":16157,"tokens_out":28608,"duration_ms":231303,"concrete_test":"Re-derive the dynamic regret bound in Prop. 3 by setting the comparator sequence in Theorem 4 to u_t^* = argmax_{u∈K} f_t(u), and write out the path length term that appears. If the bound contains P_T = Σ||u_t^* - u_{t-1}^*|| rather than the surrogate optimizers' path length, Proposition 3 as stated is incorrect and must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central linearizability inequality (6) is likely correct: Lemma 1's weaker e^{-z} form follows from B&F Lemma 4 via the non-negativity of the dropped series, and the proof of Theorem 1 is internally consistent. However, Proposition 3 makes a load-bearing error: it defines P_T = Σ ||x_t^* - x_{t-1}^*|| for 'optimal minimizers for the surrogate linear functions,' but dynamic regret (Eq. 2) is measured against u_t^* = argmax f_t. Applying the regret transfer (Theorem 3) to a comparator sequence u yields a bound with path length P_T(u); to bound the standard dynamic regret one must choose u = u^*, incurring P_T(u^*). The proof instead substitutes the surrogate path length, which is a different quantity and does not bound the original. Thus the claimed Õ(√(T(1+P_T))) dynamic guarantee is unsupported as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online maximization of non-negative, non-monotone DR-submodular functions over down-closed convex sets K ⊆ [0,1]^d. Its main claim is a structural theorem (Thm. 1): such functions are 1/e-upper-linearizable with h(x)=1-e^{-x} and surrogate potential g=∇F defined in Eq. (5). The proof uses a lower bound from Buchbinder and Feldman and an integration-by-parts cancellation. Based on this reduction, the paper claims O(T^{1/2}) static 1/e-regret with one gradient query per round, adaptive O(T^{1/2}) regret, dynamic regret of order Õ(√(T(1+P_T))), and improved rates for semi-bandit, zeroth-order full-information, and bandit feedback.","tokens_in":16365,"tokens_out":20490,"duration_ms":179357,"significance":"If Theorem 1 is correct, it is a valuable structural contribution: it reduces a hard non-convex stochastic optimization class to online linear optimization with the optimal 1/e approximation factor and a single-query oracle budget. The derivation of the linearizability inequality is explicit, and the BQND estimator is shown to be unbiased and bounded. The static and adaptive consequences are plausible and would improve the state of the art. However, the dynamic-regret analysis and several limited-feedback rate claims are not currently supported, and the bandit rates are internally inconsistent. The core result deserves publication once these gaps are closed.","major_comments":[{"comment":"Dynamic regret in Eq. (2) is defined against u*_t = argmax_u f_t(u), with path length P_T = Σ ||u*_t - u*_{t-1}||. Proposition 3 instead defines P_T as the path length of 'optimal minimizers for the surrogate linear functions'. The regret-transfer argument (Thm. 3 plus Thm. 4) bounds DR_{1/e}(u) by β R^IA_1(u) for a comparator sequence u in the linearized problem. To match Eq. (2), one must take u = u*, which yields a bound in terms of P_T(u*). No argument is given that the surrogate path length equals or bounds P_T(u*). Thus the claimed bound (15) is unsupported as written. This is repairable by restating P_T as the true path length and re-proving the transfer, but it is a load-bearing gap in the current version.","section":"§5.2, Prop. 3; Eq. (2)"},{"comment":"The bandit rates are inconsistent. Table 1 lists O(T^{4/5}) for Prop. 6 (static and adaptive) and ~O(T^{4/5}) for Prop. 7 (dynamic). In the text, Prop. 6 states O(T^{2/3}) and Prop. 7 states ~O(T^{5/6}√(1+P_T)). These are different rates. The proof of Prop. 6 invokes Lemma 6, but the quoted lemma (with δ=T^{-1} preserving the rate up to replacing the gradient bound by kM1) is not demonstrated and does not transparently yield either of the two printed rates. The authors must reconcile the stated guarantees and supply the missing conversion argument.","section":"Table 1 and §5.3, Props. 6 and 7"},{"comment":"Prop. 7 asserts dynamic regret bounds for semi-bandit, zeroth-order full-information, and bandit feedback, but no proof is given. The preceding paragraph says Lemmas 5–7 transfer guarantees 'regardless of the choice of base learner' and one can 'consequently' instantiate Improved Ader. Those lemmas are static/adaptive regret-transfer statements for the wrappers; none proves a dynamic-regret transfer with respect to a time-varying comparator in the original nonlinear problem. A dynamic guarantee requires controlling the path length of the f_t-maximizers through SFTT/FOTZO/STB, which is absent. This is a separate load-bearing gap in one of the paper's headline contributions.","section":"§5.3, Prop. 7"}],"minor_comments":[{"comment":"The proof of the e^{-z\\bar{x}} form in Eq. (4) is not valid as written: after establishing f ≥ e^{-z} f(y), the observation e^{-z\\bar{x}} ≥ e^{-z} does not imply f ≥ e^{-z\\bar{x}} f(y). The weaker e^{-z} form, which is the only one used in Theorem 1, does follow from Buchbinder-Feldman's Lemma 4 by dropping the nonnegative series. Please either prove the stronger form or weaken the lemma statement.","section":"Appendix B, Lemma 1"},{"comment":"The well-definedness argument for F bounds the integrand by M1/(1-e^{-1}) using ∥1-e^{-zx}∥≤1; to control the z→0 singularity one needs the sharper ∥1-e^{-zx}∥≤z∥x∥ or a coordinate-wise bound. The conclusion is unaffected, but the displayed bound as written is not quite correct.","section":"Theorem 1 proof, Eq. (5)"},{"comment":"The header 'Oracle F eedback' has a typo; also, the dynamic regret entries in the table omit the √(1+P_T) factor that the text and column header state.","section":"Table 1"},{"comment":"The sentence 'because the function F takes values in R≥0' should refer to f (the integrand), not the surrogate F defined in Theorem 1.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper has one genuinely new result that appears to hold up, and a set of further claims that are messier than the abstract suggests. The main theorem — that non-monotone DR-submodular functions over down-closed convex sets are 1/e-upper-linearizable via the exponential reparameterization — is the real contribution. The proof is largely self-contained, the integration by parts works, and the constants are analytic rather than tuned. If that theorem is sound, the O(T^{1/2}) static regret with one gradient query per round follows cleanly from the existing regret-transfer framework, improving the previous O(T^{2/3}) single-query bound. That alone is worth a referee's time.\n\nThe problems are in the extensions. Proposition 3's dynamic regret bound uses a path length defined over the surrogate linear optimizers, not the true maximizers that appear in the definition of dynamic regret. The regret-transfer theorem gives a bound in terms of the comparator sequence you actually apply it to; plugging in the surrogate sequence does not control the standard dynamic regret. So the advertised dynamic guarantee is not established. This is the weakest spot, and it is load-bearing for the dynamic claims including Proposition 7.\n\nThere is also an internal inconsistency in the bandit rates: Proposition 6 states O(T^{2/3}) for bandit static and adaptive regret, while Table 1 lists O(T^{4/5}) for the same entries. From the meta-lemmas quoted, the O(T^{2/3}) figures look like the intended ones; the table seems to be the mistake. Either way, a paper can't have the summary disagree with the proposition.\n\nA smaller issue: Lemma 1 proves the weak form f(h_z(x)⊕y) ≥ e^{-z} f(y), which is what the main proof uses, but it also asserts a stronger e^{-z\\bar{x}} bound that does not follow from the argument and is not needed. The extraneous claim should be removed.\n\nIf the structural theorem is correct, this is a meaningful advance in a narrow subfield. The dynamic regret part needs real work — either prove the bound with the true maximizer path length or scale back the claims — and the bandit numbers need to be reconciled. There is nothing here that looks like curve-fitting or circular reasoning.\n\nI'd send it to peer review with a request for major revision. It's worth engaging with for the linearizability result, but the current version's advertised dynamic guarantees should not be taken at face value.","headline":"The 1/e-linearizability theorem is the real contribution and looks correct; the dynamic regret claims are not proven as written, and the bandit numbers in the table contradict Proposition 6.","tokens_in":16878,"tokens_out":8005,"would_cite":true,"duration_ms":63535,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that non-monotone DR-submodular maximization over down-closed convex sets is 1/e-upper-linearizable via an exponential reparameterization, reducing the online problem to online linear optimization.","keywords":["DR-submodular maximization","non-monotone","down-closed convex sets","upper-linearizability","online optimization","regret bounds","projection-free","adaptive and dynamic regret"],"falsifier":"Run a grid search over small non-monotone DR-submodular functions (e.g., random quadratics with non-positive Hessian entries, restricted to [0,1]^d) and check the pointwise inequality at x=y: it requires f(1-e^{-x}) ≥ (1/e)f(x) for every x∈K. A single violation would refute Theorem 1 and the claimed regret bounds.","tokens_in":16054,"feed_emoji":"⚡","tokens_out":9138,"duration_ms":73647,"temperature":0.7,"pith_summary":"This paper sets out to show that a class of online optimization problems that looks non-convex and hard is, in a precise sense, linear in disguise. The class is online maximization of non-negative, non-monotone DR-submodular functions over down-closed convex sets in the unit cube. The core structural claim is 1/e-upper-linearizability: after the coordinate change h(x)=1-e^{-x}, the scaled reward (1/e)f(y) is bounded above by a linear function of y-x, up to a term f(h(x)). If this holds, every low-regret online linear optimizer becomes a low-regret 1/e-approximate maximizer for the original problem, with a single gradient query per round. The payoff is O(T^{1/2}) static regret and the first adaptive and dynamic regret bounds for this regime, with improved rates under semi-bandit, bandit, and zeroth-order feedback.","feed_headline":"Sqrt(T) regret with one query for non-monotone DR-submodular","feed_subtitle":"A new reduction makes this non-convex problem as tractable as online linear optimization.","key_machinery":"The machinery is the pair (h,F): the coordinate-wise exponential map h_z(x)=1-e^{-zx} and the surrogate potential F(x)=∫_0^1 [e^{z-1}/((1-e^{-1})z)](f(h_z(x))-f(0)) dz. The gradient ∇F(x) equals E_Z[∇f(h_Z(x))⊙e^{-Zx}] where Z has density e^{z-1}/(1-e^{-1}) on [0,1]; this expectation is unbiasedly estimated by the BQND query routine with one oracle call. The proof of Theorem 1 decomposes (1-e^{-1})⟨∇F(x), y-x⟩ into a y-term and an -x-term; the y-term is lower bounded using the structural inequality f(h_z(x)⊕y)≥e^{-z}f(y), and the -x-term is integrated by parts so the two integral terms cancel, leaving (1/e)f(y)-f(h(x)). The key structural inequality comes from a previously established coordi","core_discovery":"Theorem 1 is the load-bearing result: for every non-negative, differentiable, non-monotone DR-submodular function f on a down-closed convex K⊆[0,1]^d with 0∈K, the inequality (1/e)f(y)-f(h(x)) ≤ (1-e^{-1})⟨∇F(x), y-x⟩ holds for all x,y∈K, where h(x)=1-e^{-x} and F(x)=∫_0^1 [e^{z-1}/((1-e^{-1})z)](f(1-e^{-zx})-f(0)) dz. This is the defining condition for f to be 1/e-upper-linearizable. The proof constructs F so that its gradient has an expectation form that can be estimated by one stochastic gradient query at the reparameterized point 1-e^{-zx}; the constant 1/e emerges from integrating e^{z-1} against e^{-z} over z∈[0,1]. The authors then invoke a regret-transfer theorem for linearizable fun","pith_inferences":["The exponential reparameterization suggests a logarithmic-coordinate view: the map x↦1-e^{-x} is the inverse of a 'logit' transform; this may connect to mirror descent with an entropic regularizer, potentially extending the technique beyond DR-submodular functions.","If the 1/e constant is tight (it matches the known information-theoretic approximation barrier), then this framework likely extracts the best possible constant from the linearizable reduction, meaning further gains must come from the base linear optimizer, not from the reduction.","The same surrogate potential could be tested in offline settings: it may yield a new 1/e-approximation algorithm for non-monotone DR-submodular maximization over down-closed sets without continuous greedy.","The query algorithm uses a single point 1-e^{-zx} with random z; an experimental check on small instances (random negative-semidefinite quadratics) could quickly probe whether the inequality is tight and whether the z-sampling distribution is near-optimal."],"forward_implications":["Static 1/e-regret improves to O(√T) with O(1) gradient queries per round, beating the previous O(T^{2/3}) for single-query methods.","Adaptive regret O(√T) is obtained for the full-information first-order setting, the first such guarantee for this problem class.","Dynamic regret Õ(√(T(1+P_T))) follows by plugging a non-stationary linear optimizer as the base learner.","Semi-bandit, zeroth-order full-information, and bandit feedback all inherit improved rates (O(T^{2/3}), O(T^{3/4}), O(T^{4/5}) static/adaptive), with matching dynamic variants.","Any future improvement in online linear optimization base learners transfers automatically to this non-convex setting."],"fun_headline_variants":["1/e-linearizable: sqrt(T) regret with one query","One query per round, sqrt(T) regret for DR-submodular","Non-monotone DR-submodular: optimal regret with single gradient","1/e upper-linearizable: sqrt(T) regret, one gradient oracle","Single-query reduction yields sqrt(T) regret for non-monotone DR-submodular"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole result leans on a previously established exponential lower bound for non-negative DR-submodular functions; if that bound has hidden conditions that non-monotone functions fail, or if the stronger x-bar inequality claimed in Lemma 1 is needed rather than the derived e^{-z} version, the linearizability inequality fails and the regret results collapse.","fun_headline_variants_meta":{"raw":{"variants":["1/e-linearizable: sqrt(T) regret with one query","One query per round, sqrt(T) regret for DR-submodular","Non-monotone DR-submodular: optimal regret with single gradient","1/e upper-linearizable: sqrt(T) regret, one gradient oracle","Single-query reduction yields sqrt(T) regret for non-monotone DR-submodular"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000767,"raw_usage":{"total_tokens":3239,"prompt_tokens":745,"completion_tokens":2494,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":489,"completion_tokens_details":{"reasoning_tokens":2396}},"tokens_in":489,"tokens_out":2494,"duration_ms":15051,"temperature":1.0,"reasoning_tokens":2396,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T21:16:58.960716+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a grid search over small non-monotone DR-submodular functions (e.g., random quadratics with non-positive Hessian entries, restricted to [0,1]^d) and check the pointwise inequality at x=y: it requires f(1-e^{-x}) ≥ (1/e)f(x) for every x∈K. A single violation would refute Theorem 1 and the claimed regret bounds.","supporting_citations":[],"review_version":1}