{"id":"cdb6be95-18b2-4741-ab46-5931df1598d1","arxiv_id":"2506.01107","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The Markov move-acceptance hyper-heuristic with an only-worsening acceptance operator optimizes functions in the new SEQOPT_k class, including Jump and Cliff, in O(n^{k+1} log n) expected time.","lead":"This paper modifies a move-acceptance hyper-heuristic with a two-state Markov chain and a new only-worsening acceptance operator, proving faster expected runtimes on Jump and Cliff benchmark functions. It introduces the SEQOPT_k benchmark class and claims a runtime of O(n^{k+1} log n) for constant k, including O(n^3 log n) on Jump and Cliff regardless of the gap size.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6, the one-phase approximation, is stated without proof and is the linchpin of Theorem 15; without it the main O(n^{k+1} log n) runtime claim is unverified.","rationale":"The reader's weakest assumption is exactly the concern I judge most load-bearing: Lemma 6 is stated without proof and used repeatedly in the proof of Theorem 15. I did not find a separate flaw that would change the verdict. The paper's detailed drift computations, including Lemma 8, appear consistent with the stated formulas when read as fractions. However, the central theorem's correctness depends on a constant-probability-per-phase property for traversing arbitrary monotone segments, and that property is merely asserted. Supplying the missing proof of Lemma 6, or finding a counterexample to it, is the single check that would settle whether the main runtime bound is valid. I therefore agree with the reader's rejection on the grounds of incompleteness, with no adjustment to the verdict.","tokens_in":24372,"tokens_out":17432,"duration_ms":177856,"concrete_test":"Use Lemma 3 (and its OW analogue) to compute the probability that a single phase of the appropriate acceptance operator traverses a monotone segment of length D = d_ℓ - d_{ℓ+1} for the worst case D = Θ(n), with p = q = c/(n log n). Specifically, verify that the gamma ratio Γ(d_ℓ+1)Γ(np/(1-p)+d_{ℓ+1}+1) / (Γ(d_{ℓ+1}+1)Γ(np/(1-p)+d_ℓ+1)) is Ω(1) uniformly over all segments. If this probability is Ω(1) for all c > 0 and all segment lengths, then Lemma 6 admits the missing proof and Theorem 15 may stand; if it is o(1) for some segment, Lemma 6 is false and the claimed O(n^{k+1} log n) bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 6 ('one-phase approximation') is the load-bearing step of Theorem 15, but it is stated without proof. The paragraph preceding it argues from the ONEMAX case that 'reaching a neighboring local optimum ... only takes O(1) pairs of phases,' and then simply formalizes that as Lemma 6. The proof of Theorem 15 invokes Lemma 6 in the base case (E[k*_1] ≤ 1/p^0_n = O(1)), in the induction step (an average number of O(1) right-excursions suffice to reach L_{d_{ℓ+1}}), and again to bound the total length of right-excursions by O(n log n). None of these steps is derived. Lemma 6 is not a corollary of Lemma 4: Lemma 4 covers one full ONEMAX run from L_n to L_0, whereas Lemma 6 must hold for arbitrary monotone segments of length up to n, in either OI or OW direction, starting from every local optimum L_{d_ℓ}. The claimed extension 'again to SEQOPT' is exactly the missing argument. Since Theorem 15 is the central result and Corollary 16 depends on it, the main claims of the paper are not fully established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a Markov-chain variant of the move-acceptance hyper-heuristic (MMAHH) in which the choice between two acceptance operators is made by a two-state Markov chain, and it introduces a new 'only-worsening' (OW) acceptance operator. It claims that, for switching probabilities p,q = Θ(1/(n log n)), the MMAHH using OI and OW reaches the global optimum of every function in the newly defined class SEQOPT_k with k = O(1) in expected time O(n^{k+1} log n / (d_1 ... d_k)); in particular it obtains O(n^3 log n) on Jump_m and Cliff_d, independent of the gap parameter. The paper also gives an analysis of the OI+AM variant on Jump_m, proving an O(n^{m+1}) bound. The proofs rely on a phase decomposition with geometric phase lengths, on closed-form success probabilities for a single OI phase (Lemmas 3 and 4), and on a 'one-phase approximation' (Lemma 6) that is stated without proof and is used to control progress between successive local optima in Theorem 15.","tokens_in":24668,"tokens_out":25638,"duration_ms":224538,"significance":"If established, the main result would be significant: it would show that a simple operator-selection mechanism removes the exponential dependence on the jump-gap parameter, and the SEQOPT_k framework usefully unifies several classic benchmarks. The paper contains substantial genuine technical content: Lemma 3 gives an explicit formula for one-phase success probabilities, Lemma 4 identifies the constant e^{-1/c}, Lemma 5 is a clean minimality statement, and Theorem 7 for the OI+AM variant is a complete standalone contribution. The OW operator is a novel and falsifiable design idea. However, the significance of the OI+OW result is conditional: Theorem 15 and Corollary 16 rest on Lemma 6 and on several excursion arguments that are not rigorously derived, so the central claim is not fully established as written.","major_comments":[{"comment":"The 'one-phase approximation' is the linchpin of the main result but is asserted without proof. The motivating paragraph only analyzes full ONEMAX and then postulates the extension to arbitrary monotone segments of SEQOPT. In the base case of the proof of Theorem 15, the bound E[k*_1] ≤ 1/p0_n = O(1) is not a consequence of the formal statement of Lemma 6 (which concerns reaching a neighboring local optimum from a local optimum layer, not reaching the first local optimum from the boundary layer L_n), and the induction step uses the lemma to conclude that O(1) right-excursions reach L_{d_{ℓ+1}} and have total length O(n log n). Since Corollary 16 depends on Theorem 15, the central runtime claim is not formally established as written. This gap is fixable: a proof should show, via Lemma 5 and the geometric phase-length distribution, that on a monotone segment the appropriate operator reaches the opposite end with probability at least p0_n = Ω(1) per phase.","section":"Section 2.4, Lemma 6 and Section 4, Theorem 15"},{"comment":"The statement 'the length of any left-excursion can be upper-bounded by E[T_ℓ]' is asserted without argument. A left-excursion starts from a particular layer with a particular operator after leaving L_{d_ℓ}; it is not a copy of the original first-hitting problem from a random initial solution, so the claimed stochastic domination is not immediate. This needs a proof or a different bound, because the sum of left-excursion lengths contributes directly to the runtime bound E[T_{ℓ+1}].","section":"Section 4, induction step of Theorem 15"},{"comment":"The proof moves from 'O(1) phases suffice to cross a right slope' to 'the total length of all right-excursions is O(n log n)' and then multiplies by E[k*] = O(n/d_ℓ), but the dependence between the random number of excursions and their lengths is not made precise. The simplified Wald equation is cited, yet the condition E[X_i | T ≥ i] ≤ C is not verified for the excursion lengths λ(e_i) plus waiting times. This is a rigor gap that should be closed; it is likely fixable with the phase-length lemmas.","section":"Section 4, induction step and Theorem 17"}],"minor_comments":[{"comment":"The display should be typeset as (2i-n)/(2+q(n-2)); as extracted it reads as (2i-n)/2 + q(n-2). The proof actually derives the fraction, so this is a notation/clarity issue rather than an algebra error.","section":"Section 2.4, Lemma 8"},{"comment":"The corollary refers to CLIFFJUMP_{d,r,s} without defining it in the manuscript; please define the function or provide an explicit definition/reference in Section 2.1.","section":"Corollary 16 (iii)"},{"comment":"The straight path from L_m to x* requires m accepted steps, so the phase-survival factor is (1-q)^{m-1}, not (1-q)^{m-2}. The displayed bound is stronger by a factor (1-q); this does not change the asymptotic conclusions for the parameter regimes considered, but the computation should be corrected.","section":"Proof of Lemma 11"},{"comment":"Chains such as L_{d_ℓ} ≺ ... ≺ L_{d_{ℓ+1}} over decreasing indices are confusing; please state explicitly that the relation is applied to consecutive layers L_{h+1} ≺ L_h, so that the ONEMAX example is not read as contradictory.","section":"Definition 2"},{"comment":"The notation p,q = Θ(1/n log(n)) should be written with parentheses as Θ(1/(n log n)) to avoid ambiguity about the mode of convergence.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The reader's reject verdict is understandable, but I judge it too harsh: the load-bearing gap is the unproved Lemma 6, and that is a local, fixable issue rather than a fatal inconsistency. The alleged algebra error in Lemma 8 does not land once the display is read as a fraction. If the authors supply a rigorous proof of Lemma 6 and tighten the excursion arguments in Theorem 15, the paper would be publishable in a theory-oriented venue; I would not require additional experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a genuine step forward for move-acceptance hyper-heuristics. It introduces Markov-chain selection of acceptance operators, the only-worsening operator, and a clean unifying benchmark class, SEQOPT_k. The OI+AM result on Jump functions — O(n^{m+1}) instead of Omega(n^{2m-1}) — is new, and the proof structure there looks sound. The OI+OW runtime bounds on Jump, Cliff, and SEQOPT_k are the kind of result people in this subfield will want to know, assuming they hold up.\n\nThe main soft spot is exactly what the stress-test flags: Theorem 15 leans on Lemma 6, the one-phase approximation, which is stated without proof. The paragraph before it gives intuition from ONEMAX but does not justify the extension to arbitrary monotone segments of SEQOPT functions. That is load-bearing, so the central O(n^{k+1} log n) claim is not fully established as written. I would not call the paper wrong; I would call it incomplete. The gap looks fillable — the ingredients in Lemmas 3 and 4 are probably enough — but the authors need to supply the derivation.\n\nThe Lemma 8 arithmetic concern is less serious. The extraction makes it ambiguous, but the algebra in the appendix gives the correct drift (2i-n)/(2+q(n-2)), and the later proof of Lemma 13 uses that correct form. If the typesetting in the published version is genuinely missing the fraction bar, that is a minor typo, not a conceptual error.\n\nThe citation pattern is honest; the paper builds on Lissovoi et al. and the authors' own earlier MAHH analysis without hiding the negative result that motivated the fix. No circularity.\n\nWho is it for: anyone working on runtime analysis of hyper-heuristics or black-box optimization on multimodal benchmarks. The OI+AM section alone justifies a serious referee. With Lemma 6 supplied, the paper would be a solid contribution. I would send it to review and ask for a proof of Lemma 6 (or a rewrite that avoids it) before accepting.","headline":"A promising hyper-heuristic paper with a real result and a real gap: the OI+AM bound is solid, but the main OW/SEQOPT theorem rests on an unproved one-phase approximation.","tokens_in":25190,"tokens_out":3760,"would_cite":true,"duration_ms":35081,"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":"A Markov chain that alternates between accepting only improvements and only worsenings lets a simple hyper-heuristic find global optima of Jump and Cliff functions in $O(n^3 \\log n)$ expected time, independent of the gap size.","keywords":["hyper-heuristics","runtime analysis","Markov chain operator selection","only-worsening acceptance","local optima","Jump benchmark","Cliff benchmark","SEQOPT benchmark"],"falsifier":"Take a fixed $\\mathrm{Cliff}_d$ function with $d = n/2$ and run the MMAHH with $p = q = 1/(c n \\log n)$, starting in the local maximum at layer $L_{n-d}$; record the number of operator phases until the algorithm first reaches layer $L_{n-d-1}$. If this expected number grows with $n$ rather than staying $O(1)$, the one-phase approximation fails and the $O(n^3 \\log n)$ bound on $\\mathrm{Cliff}_d$ would not follow from the given proof.","tokens_in":24161,"feed_emoji":"⚡","tokens_out":7519,"duration_ms":60317,"temperature":0.7,"pith_summary":"The paper proposes two changes to a move-acceptance hyper-heuristic and proves that together they remove the main cause of slow escape from local optima. First, the random per-iteration choice between acceptance operators is replaced by a two-state Markov chain, which creates long runs of the same operator. Second, the all-moves operator is replaced by an only-worsening operator that accepts a new solution only when it is strictly worse, a deliberate inversion of elitist search. On the new benchmark class $\\mathrm{SEQOPT}_k$, the resulting algorithm reaches the global optimum of any function with $k$ successive local optima in expected time $O(n^{k+1} \\log n \\,/\\, (d_1 \\cdots d_k))$, and in particular solves $\\mathrm{Jump}_m$ and $\\mathrm{Cliff}_d$ in $O(n^3 \\log n)$ independent of $m$ or $d$. The paper's central message is that leaving a local optimum is best done by explicitly searching downward, and that operator selection should be persistent rather than independent.","feed_headline":"Only-worsening operator cuts hyper-heuristic runtime to O(n^3 log n)","feed_subtitle":"A two-state Markov chain and an only-worsening rule escape local optima on Jump and Cliff.","key_machinery":"The load-bearing objects are the two-state Markov chain governing operator selection and the only-worsening acceptance operator OW. In each phase the current operator is kept with probability $1-p$ (for OI) or $1-q$ (for OW), so phases have geometric lengths and, with $p, q = \\Theta(1/(n \\log n))$, long stretches of one operator are common. The phase-level probability lemma gives an exact formula for the chance that one OI phase starting in layer $k$ reaches layer $h$ on $\\mathrm{ONEMAX}$, and an OW counterpart for descending; these feed the one-phase approximation, the assertion that a neighboring local optimum is reached in $O(1)$ phases on average, which is the step that carries the induction in the main theorem.","core_discovery":"The central claim is that a move-acceptance hyper-heuristic whose operator choice follows a two-state Markov chain, using only-improving (OI) and only-worsening (OW) acceptance, optimizes every function in a broad class $\\mathrm{SEQOPT}_k$ in expected time $O(n^{k+1} \\log n)$ when $k$ is constant. This class contains functions with $k$ successive local optima arranged in monotone layer intervals, including $\\mathrm{ONEMAX}$, $\\mathrm{TRAP}$, $\\mathrm{Jump}_m$, and $\\mathrm{Cliff}_d$. For $k = 2$ the bound becomes $O(n^3 \\log n)$, independent of the difficulty parameters $m$ and $d$; for $\\mathrm{Jump}_m$ the paper proves that the Markov-chain selection alone, with OI and all-moves, already improves the previous lower bound from $\\Omega(n^{2m-1})$ to $O(n^{m+1})$. The proof proceeds by induction on the sequence of local optima, using phase-level estimates of how often an OI phase climbs to a prescribed layer and how often an OW phase descends, and bounding the number of failed excursions before the next local optimum is reached.","pith_inferences":["If the one-phase approximation can be proved rigorously, the same phase-level argument should extend to acceptance operators that accept equal-fitness moves, removing the plateau restriction the paper notes as a limitation.","The OW operator suggests a general design heuristic for local-optimum escape: instead of random neutral or accepting-all moves, spend a phase deterministically decreasing fitness, and let the Markov chain control the phase length.","The exact phase-probability formula for $\\mathrm{ONEMAX}$ may be reusable for other operator pairs with geometric phase lengths, since it depends only on the switching probabilities and the layer structure.","A testable prediction is that on functions with a wider local-optimum basin, the optimal switching probability should scale with the basin width; the paper's choice $p, q = \\Theta(1/(n \\log n))$ is tuned to the shallowest single-layer case."],"forward_implications":["On $\\mathrm{Jump}_m$ and $\\mathrm{Cliff}_d$ with constant $m$ or $d$, the expected runtime is $O(n^3 \\log n)$, so the gap size stops appearing in the exponent and the earlier exponential-in-$m$ gap penalty disappears.","The same theorem covers the $\\mathrm{CliffJump}_{d,r,s}$ benchmark with $O(n^3 \\log n \\,/\\, (d(d-r)))$ expected runtime, a class not previously analyzed in this unified way.","For functions in $\\mathrm{SEQOPT}_k$ with constant $k$, the runtime scales as $O(n^{k+1} \\log n \\,/\\, (d_1 \\cdots d_k))$, meaning the difficulty is governed by the product of the distances between successive local optima.","The Markov-chain selection alone, before OW is introduced, already reduces the $\\mathrm{Jump}_m$ runtime from $\\Omega(n^{2m-1})$ to $O(n^{m+1})$, showing that operator persistence, not just operator choice, is what drives the speedup."],"supporting_citations":[{"why":"Baseline move-acceptance hyper-heuristic with OI and all-moves; supplies the $O(n^3)$ Cliff result and the comparisons the new algorithm improves.","marker":"[Lissovoi et al., 2023]"},{"why":"Shows the MAHH needs $\\Omega(n^{2m-1})$ on $\\mathrm{Jump}_m$; its lower-bound proof motivates the Markov-chain modification.","marker":"[Doerr et al., 2023a]"},{"why":"Introduces the move-acceptance hyper-heuristic and the random mixing framework that the MMAHH replaces.","marker":"[Lehre and Özcan, 2013]"},{"why":"Provides Wald's equation, used to bound expected sums of phase lengths in the runtime proofs.","marker":"[Wald, 1944]"},{"why":"Provides the additive drift theorem with overshooting used to bound the time to climb the slope in the OI+AM analysis.","marker":"[Kötzing and Krejca, 2019]"},{"why":"Provides the multiplicative drift theorem used to bound the time spent in the jump gap.","marker":"[Doerr et al., 2012]"},{"why":"Gives the $O(n^m)$ runtime of the (1+1) EA on $\\mathrm{Jump}_m$, the reference point against which the new $O(n^{m+1})$ and $O(n^3 \\log n)$ bounds are compared.","marker":"[Droste et al., 2002]"}],"fun_headline_variants":["Only-worsening operator cuts Jump runtime to O(n^3 log n)","Markov chain plus only-worsening: O(n^3 log n) on Jump","Counter-intuitive only-worsening operator escapes local optima on Jump","Hyper-heuristic with only-worsening rule achieves O(n^3 log n) on Jump","Two-state Markov chain and only-worsening acceptance speed up hyper-heuristics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theorem assumes that from any local optimum the algorithm reaches a neighboring local optimum after a constant expected number of operator phases, a step the paper states as Lemma 6 without a proof.","fun_headline_variants_meta":{"raw":{"variants":["Only-worsening operator cuts Jump runtime to O(n^3 log n)","Markov chain plus only-worsening: O(n^3 log n) on Jump","Counter-intuitive only-worsening operator escapes local optima on Jump","Hyper-heuristic with only-worsening rule achieves O(n^3 log n) on Jump","Two-state Markov chain and only-worsening acceptance speed up hyper-heuristics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001462,"raw_usage":{"total_tokens":5957,"prompt_tokens":1096,"completion_tokens":4861,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":4754}},"tokens_in":712,"tokens_out":4861,"duration_ms":35057,"temperature":1.0,"reasoning_tokens":4754,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:53:36.603328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed $\\mathrm{Cliff}_d$ function with $d = n/2$ and run the MMAHH with $p = q = 1/(c n \\log n)$, starting in the local maximum at layer $L_{n-d}$; record the number of operator phases until the algorithm first reaches layer $L_{n-d-1}$. If this expected number grows with $n$ rather than staying $O(1)$, the one-phase approximation fails and the $O(n^3 \\log n)$ bound on $\\mathrm{Cliff}_d$ would not follow from the given proof.","supporting_citations":[{"cited_title":"Oliveto, and John Alasdair Warwicker","cited_arxiv_id":null,"evidence_quote":"Baseline move-acceptance hyper-heuristic with OI and all-moves; supplies the $O(n^3)$ Cliff result and the comparisons the new algorithm improves."},{"cited_title":"A runtime analysis of simple hyper-heuristics: to mix or not to mix operators","cited_arxiv_id":null,"evidence_quote":"Introduces the move-acceptance hyper-heuristic and the random mixing framework that the MMAHH replaces."},{"cited_title":"On cumulative sums of ran- dom variables","cited_arxiv_id":null,"evidence_quote":"Provides Wald's equation, used to bound expected sums of phase lengths in the runtime proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the additive drift theorem with overshooting used to bound the time to climb the slope in the OI+AM analysis."},{"cited_title":"On the analysis of the (1+1) evolution- ary algorithm","cited_arxiv_id":null,"evidence_quote":"Gives the $O(n^m)$ runtime of the (1+1) EA on $\\mathrm{Jump}_m$, the reference point against which the new $O(n^{m+1})$ and $O(n^3 \\log n)$ bounds are compared."}],"review_version":1}