{"id":"f10a1944-416b-4be1-80a4-d3a75ba1822d","arxiv_id":"2509.07901","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A modular algorithm for online convex-concave optimization achieves near-optimal dynamic duality gap bounds by combining adaptive experts with a multi-predictor aggregator.","lead":"This paper introduces a modular algorithm for two-player online convex-concave games that adapts to non-stationary environments and leverages multiple predictors to keep the dynamic duality gap small. The method combines adaptive experts, a meta-algorithm, and predictor aggregation to achieve bounds that are minimax optimal up to a log factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9's strong-monotonicity claim for the stacked operator G in Eq. (7) is false, so Algorithm 1's linear convergence for the coupled expert/meta update is unsupported and the implementability of the modular algorithm is not established.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing gap: Theorem 9 asserts strong monotonicity of the stacked gradient operator from component-wise strong convexity without proof, and Algorithm 1 depends on that strong monotonicity for its linear convergence. I verified the concern with an explicit numerical counterexample using the paper's own gradient formulas (Proposition 12), which shows the inner product is negative and therefore G is not 1-strongly monotone. This undermines the claim that Equations (3b) and (4b) can be solved efficiently by Algorithm 1, and consequently the implementability of the modular algorithm in Algorithm 2. The D-DGap bound itself may still be true under an oracle that exactly solves the coupled system, and the mathematical architecture is otherwise coherent, so a conditional accept with a request to fix the solver argument remains the right verdict. No evidence of fraud or bad faith; this is an ordinary proof gap that could be repaired by a different monotonicity argument or a different solver with convergence guarantees.","tokens_in":25357,"tokens_out":21834,"duration_ms":187022,"concrete_test":"Recompute the monotonicity inequality for the counterexample above: set h_t(x,y)=xy, X=Y=[-1,1], phi=psi=z^2/2, ex=ey=x_t=y_t=0, eta=gamma=100, theta=upsilon=1, w=0.999, omega=0.01, and evaluate <G(x)-G(x'), x-x'> for x=(1,1,w,omega), x'=(0,0,w,omega). If the value is negative, Theorem 9's strong-monotonicity assertion is false. As a second check, run Algorithm 1 on this instance for a large number of iterations to see whether it converges to a solution of Equations (3b) and (4b); if it oscillates or fails to converge linearly, the solver guarantee in Proposition 13 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 9 claims that since each objective ell_i in Eq. (7) is 1-strongly convex in its own coordinate, the stacked operator G is 1-strongly monotone in the norm ||x||^2 = ||x||^2 + ||y||^2 + w^2 + omega^2. This implication is false: strong convexity of individual components does not control the off-diagonal cross terms of the Jacobian. A concrete counterexample is h_t(x,y)=xy on X=Y=[-1,1], phi=psi=z^2/2, ex=ey=x_t=y_t=0, eta=gamma=100, theta=upsilon=1, w=0.999, omega=0.01. Using the gradient formulas in Proposition 12, at x=(1,1,w,omega) and x'=(0,0,w,omega), the first two blocks of G(x)-G(x') are (2, -98.9), giving <G(x)-G(x'), x-x'> = 2*1 + (-98.9)*1 = -96.9 < 0, whereas 1-strong monotonicity would require at least ||x-x'||^2 = 2. Thus G is not 1-strongly monotone, and the Browder-Minty argument in Theorem 9 does not apply. Algorithm 1, which is invoked to solve Equations (3b) and (4b), relies on the strong-monotonicity constant mu=1 for its linear convergence rate (Proposition 13). Without a valid convergence guarantee for the coupled solver, the pseudocode in Algorithm 2 may not compute the (bx_t, by_t, w_t, omega_t) needed for Theorems 6-8 and hence for Theorem 14. The central D-DGap bound may still be salvageable, e.g., by proving monotonicity with a different norm or by adding regularization, but as written the algorithmic claim is not fully supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies non-stationary Online Convex-Concave Optimization (OCCO) with the dynamic duality gap (D-DGap) as the performance metric. It proposes a modular algorithm with three components: an Adaptive Module running two ADER-like algorithms, a Prediction-Error Expert using optimistic implicit updates, and a Meta-Layer combining the two experts via clipped Hedge; a Multi-Predictor Aggregator further selects among several predictors. The main claim, Theorem 14, is an Õ(min{min_k Σ_t ρ(f_t,h^k_t), sqrt((1+min{P_T,C_T})T)}) bound on D-DGap, with the minimax-optimal adaptive term and a prediction-error-driven term. The analysis is developed in Sections 3.2–3.4, with proofs in Appendix A, and Section 4 reports experiments on synthetic quadratic games. The paper's central technical innovation is an interdependent update between the expert and meta layers, whose coupled saddle-point equations are solved by a strongly monotone VI solver (Algorithm 1).","tokens_in":25723,"tokens_out":41834,"duration_ms":325844,"significance":"The manuscript introduces a clean modular architecture for non-stationary OCCO and a new decomposition of the dynamic duality gap into expert and meta terms. Theorems 6 and 7, which bound the prediction-error expert and the meta layer, are plausible adaptations of established optimistic implicit OCO templates, and the multi-predictor aggregation via clipped Hedge is a useful add-on. The paper also ships an experimental evaluation on several non-stationary regimes. If the two proof gaps identified below are repaired, the claimed bound would be a meaningful contribution to the online learning literature. As it stands, however, two load-bearing steps in Theorems 8 and 9 are not supported, so the main theorem is not established in the current form.","major_comments":[{"comment":"The proof of Theorem 9 asserts that since each ℓ_i in Eq. (7) is 1-strongly convex in its own coordinate, the stacked operator G is 1-strongly monotone with respect to the norm ‖x‖²=‖x‖²+‖y‖²+w²+ω². This implication is false: component-wise strong convexity of the diagonal blocks does not control the off-diagonal cross terms. A concrete instance satisfying the assumptions is f_t(x,y)=xy on X=Y=[-1,1], φ(z)=ψ(z)=z²/2, ex_t=ey_t=0, η_t=γ_t=100, θ_t=ϑ_t=1, w=0.999, ω=0.01. Using the explicit formula for G in Eq. (25), at x=(1,1,w,ω) and x'=(0,0,w,ω) the first two blocks of G(x)-G(x') are (2,-98.9), so ⟨G(x)-G(x'),x-x'⟩ = 2-98.9 = -96.9, whereas 1-strong monotonicity would require at least ‖x-x'‖²=2. Thus the Browder-Minty argument does not apply, and Proposition 13's linear rate, which explicitly sets the strong-monotonicity constant μ=1, is unsupported. Because Algorithm 1 is the proposed method for computing the coupled solutions (3b)-(4b) used in Theorems 6-8 and hence in Theorem 14, the implementability of the central algorithm is not established.","section":"Section 3.3, Theorem 9 and Eq. (7)"},{"comment":"The inequality in Eq. (6) is not an identity and is not generally true. The middle term M_t := w_t^T A_t [0;1] - [0,1] A_t ω_t equals w_t[f_t(bx_t,by_t)-f_t(x_t,by_t)] + (1-ω_t)[f_t(x_t,by_t)-f_t(x_t,y_t)], which can be negative. For the instance f_t(x,y)=xy, X=Y=[-1,1], φ=ψ=z²/2, x_t=y_t=1, ex_t=ey_t=0, ew_t=eω_t=1/2, and η_t=γ_t=θ_t=ϑ_t=1, a numerical solution of the coupled first-order conditions for (3b)-(4b) gives approximately w_t≈0.676, ω_t≈0.502, bx_t≈-0.495, by_t≈-0.012, and M_t≈-0.49. With comparators u_t=v_t=0.5, the left-hand side of Eq. (6) is approximately -0.251, while the right-hand side is approximately -0.74, contradicting the claimed inequality. Consequently the adaptive-module bound in Theorem 8 and the second term inside the minimum of Theorem 14 are not proven.","section":"Section 3.3, Theorem 8 and Eq. (6)"}],"minor_comments":[{"comment":"The stopping rule 'until (L/(L+1))^{k/2}↓0' is asymptotic; please specify a finite tolerance and analyze how the approximation error propagates into the bounds of Theorems 6-8.","section":"Algorithm 1, line 9"},{"comment":"The rate in Proposition 13 is quoted from Nesterov and Scrimali (2006) after setting μ=1, but the dependence on the initial residual ||G(y_0)|| and on the dimension of K is not stated; the statement should be self-contained.","section":"Proposition 13"},{"comment":"The notation w^TΛ_t(x,y)ω/w in ℓ1 and the analogous /ω in ℓ2 is confusing because w and ω denote both scalars and vectors; please add an explicit explanation of the intended scaling.","section":"Equation (7)"},{"comment":"The text refers to 'Figure 2c' and 'Figure 2f' for panels that appear in Figure 3; the cross-references need to be corrected.","section":"Section 4"},{"comment":"Please clarify how the output of Algorithm 1 is split into (bx_t,by_t) and (w_t,ω_t), and note that the Lipschitz constant L in Algorithm 1 must be recomputed at each round from the current predictor h_t.","section":"Algorithm 2, lines 5-6"}],"recommendation":"major_revision","confidential_remarks":"The two issues above are substantive and affect the main theorem; I would not accept the paper in its current form. The authors should be asked either to prove strong monotonicity of G (or replace the solver with one whose convergence does not require it) and to repair or replace the adaptive-module decomposition in Theorem 8. The modular idea and the prediction-error bounds are worth preserving, but the current proof of the central claim is incomplete."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces the dynamic duality gap (D-DGap) for online convex-concave optimization and proposes a modular algorithm combining an ADER pair, a prediction-error expert, and a multi-predictor Hedge aggregator. The main contribution is the combined bound: D-DGap ≤ Õ(min{min_k Σ_t ρ(f_t,h^k_t), √((1+min{P_T,C_T})T)}). That's a genuine extension—previous work focused on dynamic Nash regret or static duality gap, and this unifies several metrics with minimax optimality up to logs. The adaptive part mostly follows from composing two ADER algorithms, and the paper says so; the prediction-error part via the interdependent expert/meta update is new and looks like the real work.\n\nNow the soft spot. The proof of Theorem 9 claims the stacked gradient operator G in Eq. (7) is 1-strongly monotone because each component ℓ_i is 1-strongly convex in its own coordinate. That implication is false. Off-diagonal cross terms, especially the bilinear terms with coefficients η_t, γ_t, can destroy strong monotonicity. The stress-test counterexample is concrete and checks out: with h_t(x,y)=xy, η=γ=100, the inner product ⟨G(x)-G(x'), x-x'⟩ is negative even when ||x-x'|| is large. So Theorem 9 as stated does not hold, and Algorithm 1's linear convergence (Proposition 13) rests on that unsupported strong-monotonicity constant. This matters because Algorithm 2 calls Algorithm 1 to compute the coupled (b x_t, b y_t, w_t, ω_t) needed for Theorems 6–8. Without a valid solver guarantee, the implementability of the method is not established.\n\nIs this a load-bearing gap? Not necessarily fatal. The D-DGap bounds may be salvageable by proving monotonicity in a different norm or by adding regularization to the coupled subproblem. But as written, the algorithmic claim is not fully supported. Also worth noting: experiments lack error bars and code, so the empirical claims are weak. The citation pattern is fine; the single self-citation motivates the metric and does not carry the proofs.\n\nWho is this for? Researchers working on non-stationary online learning in games. The metric and modular design are useful even if the solver needs repair. I'd send it to peer review with a request to fix the strong-monotonicity gap—either by correcting the norm, changing the solver, or adding a sound convergence proof. A serious referee can handle this.\n\nRecommendation: accept for review, conditional on a revision that addresses the solver gap.","headline":"Introduces dynamic duality gap for OCCO with a modular algorithm and prediction-error bounds, but the solver's strong-monotonicity claim in Theorem 9 is unproven and likely false; needs a fix before publication.","tokens_in":26285,"tokens_out":2403,"would_cite":true,"duration_ms":19439,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C25","91A26","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"A modular algorithm achieves, up to logarithmic factors, the minimax optimal dynamic duality gap for online convex-concave optimization, and uses multiple predictors to shrink the gap to near-constant in predictable environments.","keywords":["non-stationary online learning","online convex-concave optimization","dynamic duality gap","modular algorithm","interdependent update","meta-expert framework","multi-predictor aggregation","minimax optimality"],"falsifier":"Take a simple instance with $X=Y=[-1,1]$, quadratic regularizers, and a bilinear predictor $h_t(x,y)=xy$, then compute the smallest value of $\\langle G(x)-G(x'),x-x'\\rangle/\\|x-x'\\|^2$ for the operator $G$ in Equation (7). If this infimum is below 1 (equivalently, if the symmetric part of the Jacobian of $G$ has an eigenvalue below 1), the strong-monotonicity premise of Theorem 9 fails, Algorithm 1's linear-rate guarantee does not apply, and the exact $(\\hat x_t,\\hat y_t,w_t,\\omega_t)$ needed by Theorems 6–8 may not be computable by the proposed subroutine.","tokens_in":25099,"feed_emoji":"🧩","tokens_out":12553,"duration_ms":97279,"temperature":0.7,"pith_summary":"The paper studies two players who repeatedly pick strategies in a time-varying convex-concave game, with the goal of keeping the dynamic duality gap small against any hindsight comparator sequence. It claims that a modular algorithm—an adaptive pair of expert learners, a pool of predictors aggregated by clipped Hedge, and an integration layer with a coupled expert/meta update—achieves the minimax optimal duality gap up to logarithmic factors. The same algorithm also guarantees a prediction-error-driven bound: if any of $d$ predictors tracks the true payoff well, the gap drops to near-constant rather than growing like $\\sqrt{T}$. This matters because existing algorithms for online convex-concave optimization either pay the full worst-case regret even in benign environments or lack tight guarantees. Experiments on stationary, periodic, and adversarial payoff sequences illustrate the predicted adaptability.","feed_headline":"Modular algorithm hits optimal regret in two-player online games","feed_subtitle":"Same method stays optimal under non-stationarity and uses side predictors, up to a log factor.","key_machinery":"The load-bearing objects are the dynamic duality gap itself, the modular expert/meta decomposition, and the coupled best-response system that joins the expert and meta layers. The D-DGap is split into two dynamic-regret terms plus a static duality-gap term; a pair of ADER or ADER-like learners controls the path-length part, an optimistic proximal update built on Fenchel coupling controls the prediction-error part, and a clipped-Hedge meta-layer selects among $d$ predictors. The distinctive mechanism is the interdependent update: the expert advice $(\\hat x_t,\\hat y_t)$ and the meta-weights $(w_t,\\omega_t)$ are computed together as the solution of the coupled system in Equations (3b) and (4b), reformulated as a four-player best-response game. Existence and uniqueness come from the Browder–Minty theorem applied to a stacked gradient operator $G$, and Algorithm 1, a strongly monotone variational-inequality solver, computes the solution at a linear rate.","core_discovery":"The central claim is Theorem 14: the modular algorithm guarantees, for every comparator sequence, $$\\mathrm{D-DGap}(u_{1:T},v_{1:T}) \\le \\tilde O\\left(\\min\\left\\{\\min_{k\\in\\{1,\\dots,d\\}}\\sum_{t=1}^T \\rho(f_t,h^k_t),\\ \\sqrt{(1+\\min\\{P_T,C_T\\})T}\\right\\}\\right),$$ where $\\rho(f,h)=\\max_{x,y}|f(x,y)-h(x,y)|$ is the pointwise prediction error, $P_T$ is the path length of the comparator sequence, and $C_T$ is a data-dependent upper threshold for it. The first term means that when any of $d$ predictors models the payoff sequence well, the duality gap is driven by that predictor's cumulative error—near-constant in stationary or periodic environments. The second term is the minimax-optimal dynamic-regret floor, up to a logarithmic factor. The proof decomposes the D-DGap into two dynamic-regret terms handled by the Adaptive Module and a static duality-gap term handled by the meta-layer, then couples the expert and meta updates through a joint variational inequality solved by a linearly convergent algorithm.","pith_inferences":["Editorial inference: replacing Algorithm 1 by any other linearly convergent monotone-operator solver with the same Lipschitz constant would preserve the D-DGap theorem while removing dependence on the specific strong-monotonicity assertion.","Editorial inference: the aggregator's loss vector $L_t$ is built from evaluations at the algorithm's own query points, so the same multi-predictor construction would work for arbitrary finite sets of side-information signals, not only for payoff functions as predictors.","Editorial inference: the bound $\\min_k \\sum_t \\rho(f_t,h^k_t)$ suggests that deliberately injecting a family of candidate-world models (for example, periodic models with different periods) turns model selection into an online subproblem; the paper's own experimental predictor set could be used to test how the bound degrades when the true period is not among the candidates."],"forward_implications":["In stationary or fully predictable environments, where some predictor has cumulative error $\\sum_t \\rho(f_t,h^k_t)=O(1)$, the D-DGap collapses to $\\tilde O(1)$ instead of growing with $T$.","When no predictor helps, the bound falls back to $\\tilde O(\\sqrt{(1+\\min\\{P_T,C_T\\})T})$, which Proposition 3 shows is minimax optimal up to logarithmic factors.","The meta-layer alone achieves a static duality gap of $\\tilde O(\\min\\{\\sum_t \\rho(f_t,h_t), \\sqrt{T\\ln T}\\})$, so the algorithm is never worse than parameter-free Hedge even with no side information.","Because the Adaptive Module is exchangeable, any ADER-like base learner with its own dynamic-regret guarantee can be plugged in and inherit the same overall D-DGap bound.","With $d$ predictors, the algorithm automatically identifies the best one after the fact, so environments whose period matches one of the predictors (periods 2, 3, 4, 7, 8 in the experiments) enjoy near-constant duality gap, while adversarial environments remain at the minimax floor."],"supporting_citations":[{"why":"Introduces online convex optimization and dynamic regret, the single-player ancestor of the D-DGap metric.","marker":"(Zinkevich, 2003)"},{"why":"Provides the ADER algorithm and the minimax lower bound that the Adaptive Module inherits and that Proposition 3 uses for the D-DGap lower bound.","marker":"(Zhang et al., 2018)"},{"why":"Develops implicit updates whose temporal-variability regret bound is the template for the prediction-error expert and its learning-rate schedule.","marker":"(Campolongo and Orabona, 2021)"},{"why":"Supplies optimistic implicit updates with predictor-error-based dynamic regret, one of the ADER-like bases in the Adaptive Module.","marker":"(Scroccaro et al., 2023)"},{"why":"Introduces a parameter-free algorithm for time-varying zero-sum games and dynamic Nash equilibrium regret, the main OCCO baseline that D-DGap unifies and tightens.","marker":"(Zhang et al., 2022b)"},{"why":"Algorithm 1 from this work solves the coupled expert/meta system with global linear convergence under strong monotonicity.","marker":"(Nesterov and Scrimali, 2006)"},{"why":"Supplies the Browder–Minty theorem used to prove that the coupled best-response system has a unique solution.","marker":"(Brezis, 2011)"},{"why":"Provides the tracking-the-best-expert clipped Hedge scheme that the Multi-Predictor Aggregator adapts with a time-varying learning rate.","marker":"(Herbster and Warmuth, 2001)"},{"why":"Defines the Fenchel coupling used as the regularizer in the expert and meta proximal updates.","marker":"(Mertikopoulos and Sandholm, 2016)"}],"fun_headline_variants":["Modular design nails near-optimal duality gap in two-player games","Adaptive multi-predictor algorithm achieves near-optimal dynamic duality gap","Modular method leverages side predictors for near-optimal two-player gap","Non-stationary two-player games: modular algorithm reaches near-optimal duality gap","Modular two-player algorithm with side predictors achieves near-optimal duality gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on the assumption that the joint best-response map used to solve the two coupled updates is strongly monotone—a property that does not automatically follow from the individual blocks being strongly convex, so the cross-coupling terms must actually preserve it for the linear-convergence solver to work.","fun_headline_variants_meta":{"raw":{"variants":["Modular design nails near-optimal duality gap in two-player games","Adaptive multi-predictor algorithm achieves near-optimal dynamic duality gap","Modular method leverages side predictors for near-optimal two-player gap","Non-stationary two-player games: modular algorithm reaches near-optimal duality gap","Modular two-player algorithm with side predictors achieves near-optimal duality gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002747,"raw_usage":{"total_tokens":10489,"prompt_tokens":977,"completion_tokens":9512,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":9416}},"tokens_in":593,"tokens_out":9512,"duration_ms":61538,"temperature":1.0,"reasoning_tokens":9416,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:10:01.288256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a simple instance with $X=Y=[-1,1]$, quadratic regularizers, and a bilinear predictor $h_t(x,y)=xy$, then compute the smallest value of $\\langle G(x)-G(x'),x-x'\\rangle/\\|x-x'\\|^2$ for the operator $G$ in Equation (7). If this infimum is below 1 (equivalently, if the symmetric part of the Jacobian of $G$ has an eigenvalue below 1), the strong-monotonicity premise of Theorem 9 fails, Algorithm 1's linear-rate guarantee does not apply, and the exact $(\\hat x_t,\\hat y_t,w_t,\\omega_t)$ needed by Theorems 6–8 may not be computable by the proposed subroutine.","supporting_citations":[],"review_version":2}