{"id":"f8c0232a-bb42-4c11-ae0c-14aa16b5ba5d","arxiv_id":"2608.04884","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For convex (H0,H1)-smooth objectives, restarted accelerated gradient methods achieve O(sqrt(H0 R^2/eps)+sqrt(H1 R^2) log(F0/eps)) iterations, and accelerated coordinate variants pay a standard factor d or use importance sampling.","lead":"The paper develops accelerated full-gradient and coordinate descent methods for convex optimization problems whose curvature is bounded by H0 plus H1 times the remaining optimality gap, a class broader than (L0,L1)-smooth objectives. It proves the first accelerated iteration guarantees for this class and verifies them on small numerical examples.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All three complexity theorems require exact knowledge of f*, which is needed for the curvature estimates, non-uniform sampling probabilities, and the restart acceptance test; without f* the algorithms are not implementable for general convex (H0,H1)-smooth problems.","rationale":"I read the full-gradient proof (Appendix B), the uniform-coordinate proof (Appendix C), and the non-uniform-coordinate proof (Appendix D) in good faith. The potential arguments are internally consistent: Lemma 10 correctly bounds the local-radius curvature term by C*(H0+H1F(x)); the phase-length rules square to the needed contraction; the ceilings are handled through T0>=sqrt(2); and the coordinate proofs use the correct conditional moments and nonpositive potential coefficients. I found no algebraic error that would invalidate the stated rates. The main theorems are conditional on knowing f* and on valid upper bounds for H0,H1 (and initially eR), exactly as Section 7 discloses. This is the load-bearing limitation: without f* the algorithm cannot compute M_k, the non-uniform probabilities, or the restart acceptance, and a lower bound alone does not certify the final epsilon accuracy. The reader's weakest_assumption identified the same concern, and my independent reading agrees. Since the limitation is disclosed and the conditional statements are proved in detail, the appropriate verdict remains CONDITIONAL; I would not change the reader's verdict.","tokens_in":48854,"tokens_out":20854,"duration_ms":191516,"concrete_test":"Shift the Section 6 chain-cosh objective by a positive constant c so that f*=c while all gradients, Hessians, and the valid constants (H0,H1)=(1,4) remain unchanged. Run Algorithms 1–2 with Algorithm 5's restart acceptance test computed from a lower bound l=c-2*epsilon instead of the true f*, and record whether the method ever certifies f(z_S)-c <= epsilon. Because f(z)-l = f(z)-c + 2*epsilon > epsilon for every feasible point, the acceptance test is unsatisfiable and the method cannot certify the claimed accuracy; this directly demonstrates that the epsilon guarantee depends on knowing f* (or a lower bound within epsilon of it).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 7 (Discussion and Limitations) states that all proposed methods require the exact value f*, because the optimality gap enters the local curvature in Algorithms 2–4 (lines 4–5, 4, and 4 respectively), the non-uniform sampling probabilities in Algorithm 4, and the restart test in Algorithm 1 and Algorithm 5. This is load-bearing, not merely a practical caveat. If f* is unknown, F0=f(x0)-f* is unknown, so the phase schedule Delta_s=F0/2^s cannot be computed, and the phase-length rules N(Delta) lose their meaning. Replacing f* by a valid lower bound l<f* inflates the curvature estimates, which is safe for step sizes, but the acceptance test f(z_{s+1})-l <= Delta/2 is equivalent to f(z_{s+1})-f* <= Delta/2 - (f*-l); it cannot certify the required true gap unless the lower bound is within about Delta/2 of f*. For the final accuracy epsilon, the algorithm therefore needs a lower bound within epsilon of f*, which is generally as hard as solving the problem. The internal algebra of the proofs is consistent, but the central claim is a conditional guarantee for problems where f* (or an extremely accurate lower bound) is supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops accelerated first-order methods for convex minimization under (H0,H1)-smoothness, a gap-dependent curvature condition in which the Hessian is bounded by H0 + H1(f(x)-f*). The main algorithmic structure is a restart meta-algorithm (Algorithm 1) combined with three inner methods: an accelerated full-gradient method with small-dimensional segment relaxation (Algorithm 2), a uniformly sampled coordinate version (Algorithm 3), and a non-uniformly sampled coordinate version (Algorithm 4). The main results, Theorems 5, 6, and 8, give iteration complexities of order eR sqrt(H0/eps) + eR sqrt(H1) log(F0/eps) for the full-gradient method, the same rate multiplied by d for uniform coordinates, and a rate governed by coordinate-wise sums S_{1/2}^{(0)}, S_{1/2}^{(1)} for non-uniform sampling. The paper also provides separation examples showing that the (H0,H1)-smooth class is strictly broader than the (L0,L1)-smooth class, numerical experiments, and appendices containing complete proofs together with extensions for inexact segment relaxation and adaptive phase lengths.","tokens_in":49048,"tokens_out":12064,"duration_ms":100723,"significance":"If the results are taken as stated, the paper would provide the first accelerated full-gradient and coordinate guarantees for the convex (H0,H1)-smooth class, with a clean separation of the H0 and H1 contributions and with a natural extension to importance-sampled coordinates. The appendix supplies full proofs of the three main theorems, and the experiments are relevant to the claimed acceleration and to the gains from non-uniform sampling. The main qualification is that all proposed algorithms require the exact value f*, and this requirement is load-bearing for implementability; the theorem statements do not currently state this information assumption, so the contribution must be reframed before the claims can be accepted at face value.","major_comments":[{"comment":"All three complexity results require the exact value f*, and this is load-bearing rather than a practical caveat. The curvature M_k in line 4 of Algorithm 2 (and the analogous lines of Algorithms 3 and 4) is defined through F(y_k)=f(y_k)-f*; the sampling probabilities p_{k,i} in Algorithm 4 also depend on F(y_k); and the restart schedule Delta_s=F0/2^s, together with the acceptance test in Algorithm 1 and Algorithm 5, requires F(z_s)=f(z_s)-f*. If f* is unknown, the phase lengths N(Delta) cannot be computed and the updates cannot be executed. A valid lower bound l<f* does not resolve the issue: certifying F(z_{s+1})<=Delta/2 would require l to be within Delta/2 of f*, and for the final accuracy this is as hard as solving the problem. The theorem statements currently present unconditional 'returns a point with F(z_S)<=eps' guarantees. They should be restated explicitly as conditional on an f*-oracle, or the class of instances (for example, realizable losses with f*=0) for which the algorithms are implementable should be delimited.","section":"Section 7 / Algorithms 2–4 / Theorem 5"},{"comment":"The novelty claims about coordinate methods are internally inconsistent. Table 1 lists Vankov et al. (2025) as an accelerated coordinate method for convex (L0,L1)-smooth functions, with both Acceleration and CM checked, while Section 2 states that 'no previous coordinate method is both accelerated and applicable to convex (L0,L1)-smooth objectives'. Since Section 4.2's claim that Theorem 6 is the first accelerated coordinate guarantee depends on this point, the contradiction must be resolved by correcting the table or the text. Several other checkmark patterns in the same table (for example, the Nesterov & Stich and Lobanov et al. rows) also appear inconsistent with the surrounding discussion and should be checked.","section":"Table 1 / Section 2 / Section 4.2"}],"minor_comments":[{"comment":"The theorem statements say that the exact segment solve in line 3 is treated as one call per iteration, but an exact one-dimensional minimization may require an unbounded number of oracle queries in general; the paper should either define this as an idealized small-dimensional relaxation oracle or state the additional regularity needed for the logarithmic-cost inexact solver in Appendix F.1.","section":"Theorems 5, 6, 8"},{"comment":"The symbol M_k is used both for the individual coordinate curvatures M_{k,i} and for their normalizing sum; using a distinct symbol for the normalizer would improve readability and avoid confusion in the proofs.","section":"Algorithm 4"},{"comment":"The claim that the inexact line search preserves the same total oracle complexity relies on an L_{seg,k}-Lipschitz assumption on the derivative of the one-dimensional restriction, which is not part of Assumptions 1 or 2; this extra condition should be stated explicitly wherever the logarithmic-cost line-search claim is made.","section":"Appendix F.1 / Section 7"}],"recommendation":"major_revision","confidential_remarks":"The f*-knowledge issue is the main obstacle: it is an information requirement on the algorithm, not merely a limitation of the model, and the current theorem statements do not flag it. I would not support acceptance without the authors either removing the requirement or explicitly reframing all theorems as f*-oracle guarantees and correcting the related-work table. The proofs themselves appear internally consistent, so a revision addressing these points is feasible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper delivers what it promises: accelerated full-gradient and coordinate descent rates for convex functions satisfying the (H0,H1)-smoothness condition, stated in the native H0,H1 parameters. As far as I can tell from the cited literature, these are indeed the first such guarantees, and the appendices go to unusual lengths to make the proofs checkable. The restart potential arguments in Appendices B–D are detailed and internally consistent; I did not find a gap in the central complexity claims. The separation examples (H0,H1) vs (L0,L1) are correct, and Appendix G adds a genuinely useful incomparability result with general ℓ-smoothness. Credit where due: the paper is careful, honest about its limitations, and does not oversell the practical reach.\n\nThe soft spot is the one the stress-test note flags: every algorithm needs the exact value of f*. This is not a minor practical caveat. The optimality gap enters the curvature estimates, the non-uniform sampling probabilities, and the restart acceptance test. Without f* you cannot compute the phase schedule, and replacing f* by a lower bound only works if that bound is within O(epsilon) of f*, which is generally as hard as solving the problem. The authors disclose this in Section 7 and point to realizable zero-loss settings where f* is known, so the results are honest as conditional guarantees. But the condition is load-bearing: for general convex (H0,H1)-smooth problems with unknown f*, the theorems do not give implementable algorithms. I would rate this a significant limitation, not a fatal one, because the paper is explicitly framed around the known-f* case and the theory is still meaningful there.\n\nMinor additional notes: the experiments are illustrative but ship no code or data, so the numerical claims are not independently reproducible. The exact segment minimization in the inner loop is idealized, but Appendix F.1 shows a verifiable inexact variant with logarithmic extra cost, which is a reasonable response.\n\nWho is this for? Researchers working on generalized smoothness, warm-up theory, or coordinate methods who want to know the state of the art for (H0,H1)-convex optimization. The paper deserves a serious referee: the proofs are worth checking in detail, the contribution is real, and a good referee could push the authors to clarify the f* limitation in the abstract and introduction rather than burying it in Section 7. I would accept it for peer review with the expectation of revision, mainly to sharpen the message about the known-f* assumption.","headline":"Solid, honestly-written theory paper: first accelerated full-gradient and coordinate rates for convex (H0,H1)-smooth functions, with complete proofs; main caveat is the exact-f* requirement, which is disclosed but genuinely restrictive.","tokens_in":49656,"tokens_out":1415,"would_cite":true,"duration_ms":16254,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C06","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"First accelerated full-gradient and coordinate guarantees for convex $(H_0,H_1)$-smooth functions: $\\tilde O(\\tilde R\\sqrt{H_0/\\epsilon} + \\tilde R\\sqrt{H_1}\\log(F_0/\\epsilon))$ iterations, with coordinate variants paying the usual factor…","keywords":["(H0,H1)-smoothness","generalized smoothness","accelerated gradient method","coordinate descent","non-uniform sampling","convex optimization","restart scheme","optimality-gap curvature"],"falsifier":"On the paper's own chain-$\\cosh$ objective ($H_0=1$, $H_1=4$), Theorem 5 predicts iteration counts growing like a constant plus $\\log(F_0/\\epsilon)$ in the gap-dominated regime; if counts were observed to grow faster than logarithmically as the relative gap goes from $10^{-2}$ to $10^{-8}$, the rate would be wrong. A sharper test: a pure gap-curvature objective with $H_0 = 0$ (e.g., the $\\cosh$-type term in Section 6 with the quadratic baseline removed) should require only $O(\\tilde R\\sqrt{H_1}\\log(F_0/\\epsilon))$ iterations — counts scaling like $1/\\sqrt{\\epsilon}$ would refute the claimed separation of $H_0$ and $H_1$. Separately, re-running Algorithm 1 with $f^*$ replaced by $f^* + c$ for $c > 0$ should destroy the $\\Delta/2$ phase contraction, confirming that exact $f^*$ is genuinely load-bearing.","tokens_in":48582,"feed_emoji":"⚡","tokens_out":15150,"duration_ms":110506,"temperature":0.7,"pith_summary":"This paper establishes the first accelerated optimization guarantees for convex functions whose curvature is not a global constant but shrinks as the function value approaches its minimum — the $(H_0,H_1)$-smooth class, where $\\|\\nabla^2 f(x)\\| \\le H_0 + H_1(f(x)-f^*)$. The central claim is that a restart scheme whose inner accelerated method estimates curvature from the current gap reaches accuracy $\\epsilon$ in $\\tilde O(\\tilde R\\sqrt{H_0/\\epsilon} + \\tilde R\\sqrt{H_1}\\log(F_0/\\epsilon))$ full-gradient iterations, with randomized coordinate variants paying only the usual dimension factors. A careful reader should care because all prior rates for this class were non-accelerated, and the natural alternative of freezing curvature on the initial sublevel set would replace the logarithmic $H_1$-term by a $1/\\epsilon$-type penalty. When $H_1 = 0$, the bound reduces to the classical Nesterov rate, so the result is a genuine generalization rather than a different model.","feed_headline":"Accelerated rates proven for convex objectives with fading curvature","feed_subtitle":"The baseline curvature costs 1/√ε; the gap-dependent part only a log factor. A first for this class.","key_machinery":"The load-bearing mechanism is the restart meta-algorithm (Algorithm 1): a geometric schedule of certified gap levels $\\Delta_s$ makes the effective curvature $H_0 + H_1\\Delta_s$ that each inner phase must control decay by half each phase. The inner methods (Algorithms 2–4) are accelerated gradient schemes with small-dimensional segment relaxation; each step chooses $M_k$ in the interval between $\\hat{M}_k = \\max\\{2(H_0 + H_1 F(y_k)), \\|\\nabla f(y_k)\\|/r_1\\}$ and $\\tau C_\\star(H_0 + H_1 F(y_k))$, where $r_1$ is the radius of validity of the local quadratic model and $C_\\star = 19 + 12\\sqrt{2}$ (Lemma 10). The accelerated potential $\\Phi_k = A_k F(x_k) + \\tfrac{1}{2}\\|v_k - x^*\\|^2$ is non-increasing (in expectation, for coordinate variants), and the weight growth $A_N \\ge \\theta N^2/(4\\tau C_\\star(H_0 + H_1\\Delta))$ converts potential decay into the per-phase contraction $F(z_{s+1}) \\le \\Delta_s/2$ that the wrapper needs.","core_discovery":"Under convexity and local $(H_0,H_1)$-smoothness (Assumptions 1–2), the paper claims that a restart wrapper which halves a certified gap level $\\Delta_s = F_0/2^s$ each phase, driving a Nesterov-type inner method whose curvature estimate $M_k$ is pinned to the current gap $H_0 + H_1 F(y_k)$ and to the local-model radius $r_1$, reaches $F(z_S) \\le \\epsilon$ in $N_{tot} = O(\\tilde R\\sqrt{H_0/\\epsilon} + \\tilde R\\sqrt{H_1}\\log(F_0/\\epsilon))$ full-gradient iterations (Theorem 5). Uniformly sampled coordinate updates pay the standard extra factor $d$ (Theorem 6), and non-uniform sampling with probabilities $p_{k,i} \\propto \\sqrt{H_{0,i} + H_{1,i}F(y_k)}$ replaces $d\\sqrt{H_j}$ by $S^{(j)}_{1/2} = \\sum_i \\sqrt{H_{j,i}}$ (Theorem 8). The $H_1$ contribution enters only logarithmically in the accuracy $\\epsilon$ — a strongly-convex-like dependence — instead of the $F_0/\\epsilon$ penalty that freezing curvature at the initial sublevel set would cost. The paper also argues these are the first accelerated full-gradient and coordinate guarantees for this convex class.","pith_inferences":["An implication the authors leave implicit: whenever $H_1 F(x) \\gg H_0$ along most of the trajectory, the same restart schedule makes the gap contract geometrically, so $(H_0,H_1)$-smoothness offers a curvature-fading explanation for the near-linear training curves that warm-up schedules produce in practice — a claim the paper does not make.","A testable extension: substituting a valid upper bound on $f^*$ (dual certificate, realizable-loss value, or Polyak-type estimate) into the restart test should preserve the three rates, because the proofs use $F(\\cdot)$ only through upper bounds; the paper states the exact-$f^*$ requirement remains a limitation.","Remark 9's phase-frozen sampling probabilities are proven rate-equivalent, which suggests an implementation could refresh the distribution once per phase and still keep Theorem 8's complexity — worth an experiment the paper does not run beyond its own sweep.","The U-shaped cost curve in Appendix E.3 (optimal fixed residual near $10^{-6}$ on the chain-cosh problem) implies the practical bottleneck is the segment solver's stopping rule; an adaptive tolerance matching the per-phase allowance $A_{k+1}\\delta_k \\le A_{s,N}\\Delta_s/(4N_s)$ would be the natural follow-up test."],"forward_implications":["When $H_1 = 0$ the bound collapses to $O(\\tilde R\\sqrt{H_0/\\epsilon})$, the classical Nesterov rate, so the method is a strict generalization of accelerated gradient descent.","Because the $(H_0,H_1)$ class strictly contains the convex $(L_0,L_1)$-smooth class, the results give the first accelerated guarantees for $(L_0,L_1)$-smooth convex functions as well, including functions that satisfy no finite $(L_0,L_1)$ condition.","The $H_1$-term enters only as $\\sqrt{H_1}\\log(F_0/\\epsilon)$, a strongly-convex-like dependence: in the gap-dominated regime the phases contract geometrically, whereas freezing curvature on the initial sublevel set would incur a $\\sqrt{F_0/\\epsilon}$-type penalty.","Non-uniform sampling replaces the uniform factor $d\\sqrt{H_j}$ by $S^{(j)}_{1/2} = \\sum_i \\sqrt{H_{j,i}}$, so curvature concentrated on $m \\ll d$ coordinates lowers the coordinate rate from $d$ to $O(m)$-type sums.","The inexact segment relaxation with the phase-wise residual schedule from Corollary 14 preserves all three iteration bounds up to constants, with one-dimensional solver calls counted separately, so the theory supports implementable line searches."],"supporting_citations":[{"why":"Supplies the strict-inclusion facts (Propositions B.1, B.4, B.5): every $(L_0,L_1)$-smooth function is $(H_0,H_1)$-smooth, and the new class is strictly broader.","marker":"Alimisis et al. (2025)"},{"why":"Closest predecessor AGMsDR: provides the small-dimensional segment relaxation and accelerated coupling that Algorithms 2–4 adapt from $(L_0,L_1)$- to $(H_0,H_1)$-smoothness.","marker":"Vankov et al. (2025)"},{"why":"Origin of the accelerated method with small-dimensional relaxation whose inner scheme Algorithm 2 generalizes to gap-dependent curvature.","marker":"Nesterov et al. (2021)"},{"why":"Introduces $(H_0,H_1)$-smoothness and the lemma that converts the Hessian condition into the first-order local model in Assumption 2.","marker":"Liu et al. (2025b)"},{"why":"Baseline accelerated coordinate descent: the uniform rate's factor $d$ and the $S_{1/2}$ non-uniform sampling summary that Theorems 6 and 8 generalize.","marker":"Nesterov & Stich (2017)"},{"why":"The non-accelerated $O(H_0R^2/\\epsilon + H_1R^2\\log(F_0/\\epsilon))$ rate for convex $(H_0,H_1)$-smooth problems that Theorem 5's square-root $H_1$-dependence is compared against.","marker":"Lobanov & Koloskova (2026)"},{"why":"Classical accelerated $O(1/k^2)$ rate, recovered exactly when $H_1 = 0$; sets the baseline term's $\\sqrt{H_0/\\epsilon}$ dependence.","marker":"Nesterov (1983)"},{"why":"Introduced the $(L_0,L_1)$-smoothness model in deep-learning contexts; the broader $(H_0,H_1)$ class and the acceleration results here extend that line.","marker":"Zhang et al. (2020b)"}],"fun_headline_variants":["First accelerated guarantees for convex (H0,H1)-smooth optimization","Convex optimization: fading curvature adds only a log factor","Accelerated full-gradient and coordinate methods for fading curvature","Fading Hessians: convex solvers get faster with new acceleration"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing input is the exact optimum value $f^*$: the step sizes, the coordinate sampling odds, and the restart test are all computed from the gap $f(x) - f^*$, and Section 7 states that if $f^*$ is unknown the algorithms cannot compute their own parameters and its removal remains an open limitation.","fun_headline_variants_meta":{"raw":{"variants":["First accelerated guarantees for convex (H0,H1)-smooth optimization","Convex optimization: fading curvature adds only a log factor","Accelerated full-gradient and coordinate methods for fading curvature","Fading Hessians: convex solvers get faster with new acceleration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00103,"raw_usage":{"total_tokens":4396,"prompt_tokens":1058,"completion_tokens":3338,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":3266}},"tokens_in":674,"tokens_out":3338,"duration_ms":25377,"temperature":1.0,"reasoning_tokens":3266,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:37:46.195265+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the paper's own chain-$\\cosh$ objective ($H_0=1$, $H_1=4$), Theorem 5 predicts iteration counts growing like a constant plus $\\log(F_0/\\epsilon)$ in the gap-dominated regime; if counts were observed to grow faster than logarithmically as the relative gap goes from $10^{-2}$ to $10^{-8}$, the rate would be wrong. A sharper test: a pure gap-curvature objective with $H_0 = 0$ (e.g., the $\\cosh$-type term in Section 6 with the quadratic baseline removed) should require only $O(\\tilde R\\sqrt{H_1}\\log(F_0/\\epsilon))$ iterations — counts scaling like $1/\\sqrt{\\epsilon}$ would refute the claimed separation of $H_0$ and $H_1$. Separately, re-running Algorithm 1 with $f^*$ replaced by $f^* + c$ for $c > 0$ should destroy the $\\Delta/2$ phase contraction, confirming that exact $f^*$ is genuinely load-bearing.","supporting_citations":[],"review_version":2}