{"id":"17c76208-ab96-4f3d-8f2e-ac85264352f4","arxiv_id":"2412.17050","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under convex (L0,L1)-smoothness, GD, NGD, Clip-GD, RCD and OrderRCD converge linearly while gradient norms stay above L0/L1, then revert to sublinear O(1/N) convergence.","lead":"This paper proves that gradient descent and several of its variants converge linearly, then sublinearly, when the objective is convex and has (L0,L1)-smoothness instead of the usual Lipschitz smoothness. The results refine earlier sublinear bounds and provide the first convergence analysis of coordinate descent and comparison-only coordinate descent in this setting.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The RCD proof's random-set conditioning is informal, and the stated linear exponent contradicts the proof, so the RCD/OrderRCD phase-split claim is not established.","rationale":"The reader's nominated weak point — the imported bound ||x_k−x*||≤R in Theorem 3.1 — is not actually load-bearing. From the descent lemma (8) (which is valid under Assumption 1.2 because the step satisfies ||x_{k+1}−x_k||≤1/L1), f(x_k)−f(x_{k+1}) ≥ ||∇f(x_k)||^2/[2(L0+L1||∇f(x_k)||)]. Since f(x_{k+1})≥f*, and convexity gives f(x_k)−f* ≤ ||∇f(x_k)|| ||x_k−x*||, one obtains ||x_{k+1}−x*||^2 ≤ ||x_k−x*||^2. Thus the distance bound is true and easily derivable from the paper's own assumptions; citing Gorbunov et al. is only a presentation shortcut. The genuinely load-bearing gap is in the RCD proof (Appendix D.1): the random set K is treated as deterministic, and the theorem's linear exponent N is stronger than the N/2 the proof actually yields. This does not undermine the GD/NGD/Clip-GD phase-split, which is the core of the paper, but it does invalidate the paper's claim that the same phase split is established for RCD and OrderRCD. A repair is plausible — the inequalities (43) and (46) are per-iteration and a careful martingale argument may recover a similar rate — so the verdict should remain CONDITIONAL rather than REJECT.","tokens_in":29984,"tokens_out":33684,"duration_ms":280380,"concrete_test":"Re-derive Appendix D.1 treating K as a random set: condition on the filtration generated by x_0,...,x_k and use the fact that for k∈K, E[F_{k+1}|x_k] ≤ (1−c1)F_k, while for k∉K, E[F_{k+1}|x_k] ≤ F_k − F_k^2/(8dL0R^2). Then check whether a Doob-decomposition / optional-stopping argument yields E[F_N] ≤ max{(1−c1)^{N/2}F0, 16dL0R^2/N} or only a bound with r in the exponent. If the sharper (1−c1)^N F0 is sought, supply the missing argument; otherwise change Theorem 4.1/4.3 to the N/2 exponent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Appendix D.1 (Proof of Theorem 4.1), the set K = {k : Σ_{i∈I_k} |∇_i f(x_k)|^2 > Σ_{i∉I_k} |∇_i f(x_k)|^2} is used to split iterations into a 'linear' subsequence and a 'sublinear' subsequence. But K depends on the random iterates, so r=|K| and the locations of the K/T indices are random objects. The proof applies the linear contraction (43) along the K-subsequence and then telescopes the complementary T-subsequence as though the indices were fixed; the notations E_{i∈K} and E_{i∈T} are not valid conditional expectations over the random stopping set. A rigorous argument would need a martingale/stopping-time treatment, and it is not present. Independently of this, the theorem statement claims E[f(x_N)]−f* = O(max{(1−ρ/(dR))^N F0, dL0R^2/N}) with ρ=1/(4√2 L1), whereas the proof's linear term is (1−1/(4√2 dL1R))^{N/2}F0, i.e., the same base with exponent N/2. Since (1−a)^N is strictly smaller than (1−a)^{N/2} for a∈(0,1), the proven linear rate is weaker than the stated one. Therefore the claim that RCD and OrderRCD enjoy the same phase split as the full-gradient methods is not supported by the written proof; the result may still be true, but the theorem and proof must be reconciled.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies convex (L0,L1)-smooth optimization and claims that gradient descent variants enjoy a two-phase convergence behavior: linear convergence while the gradient norm stays above L0/L1, and standard sublinear convergence afterward. The authors prove such rates for (L0,L1)-GD, Normalized GD, and Clipped GD, and extend the same phase-split claim to Random Coordinate Descent and to a coordinate descent method using only an order oracle. A strongly convex extension for (L0,L1)-GD is also provided. The full-gradient proofs are standard descent-plus-convexity arguments, while the coordinate-descent section relies on a subsequence argument that is written informally and whose stated rates do not match the proof.","tokens_in":30312,"tokens_out":11256,"duration_ms":97704,"significance":"If established, the full-gradient results would improve on prior (L0,L1)-smooth convex rates by making the linear initial phase explicit, and the RCD/OrderRCD results would be the first in this setting. The paper is clearly written and the qualitative phase-split claim is a crisp, falsifiable prediction. The step-size choice for (L0,L1)-GD is parameter-free and the comparison table with prior work is useful. However, the advertised coordinate-descent results are not currently supported by the written proof: the theorem states a stronger linear exponent than the proof delivers, and the random-set conditioning in Appendix D.1 is not rigorous. These issues are substantial because RCD/OrderRCD form a central claimed contribution.","major_comments":[{"comment":"The theorem states E[f(x_N)] - f* = O(max{(1 - 1/(4*sqrt(2)*d*L1*R))^N F0, d*L0*R^2/N}), but the proof concludes with max{(1 - 1/(4*sqrt(2)*d*L1*R))^{N/2} F0, 16*d*L0*R^2/N}. Since (1-a)^{N/2} cannot be bounded by a constant multiple of (1-a)^N as N grows, the stated linear rate is strictly stronger than what is proven. The theorem and proof must be reconciled, for example by stating the exponent N/2 or by supplying a sharper argument. In addition, the theorem claims the bound for every step size eta_k satisfying the inequality, while the proof uses the maximal step size; a smaller step size weakens descent inequality (38)-(40), so the statement should be restricted to the exact step size or a proof for all smaller steps should be provided.","section":"Theorem 4.1 and Appendix D.1"},{"comment":"The set K = {k : sum_{i in I_k} |grad_i f(x_k)|^2 > sum_{i not in I_k} |grad_i f(x_k)|^2} is random because it depends on the random iterates, so r=|K| and the indices k_j, t_j are random objects. The proof applies the linear contraction (43) along the K-subsequence and telescopes the complementary subsequence as though the indices were fixed, and the notation E_{i in K} is not a valid conditional expectation over a random stopping set. A rigorous treatment via stopping times, or a deterministic case analysis over all subsets of the iteration index set, is needed. This gap affects Theorem 4.1 and, through the identical argument referenced in Appendix D.2, Theorem 4.3.","section":"Appendix D.1, set K and subsequence telescoping"},{"comment":"The theorem states the linear contraction factor as (1 - rho/R)^T with rho = c/max{L0, L1*c}, which is (1 - 1/(L1*R))^T when c >= L0/L1 and (1 - c/(L0*R))^T when c < L0/L1. The proof in Appendix C.3, however, yields (1 - 1/(4*L1*R))^T and (1 - c/(4*L0*R))^T, respectively. The missing factor 1/4 in the exponent cannot be absorbed into the big-O notation for geometric rates, so the theorem and Table 1 overclaim the proven rate. The qualitative phase-split conclusion is unaffected, but the stated rates must be corrected.","section":"Theorem 3.5 and Table 1"}],"minor_comments":[{"comment":"In the derivation before equation (45), the displayed implication states sum_{i in I_k} |grad_i f(x_k)|^2 >= F_k^2/(2R^2), but the preceding inequality bounds the complementary sum over i not in I_k; as written the displayed line is false and should be corrected to sum_{i not in I_k} |grad_i f(x_k)|^2 >= F_k^2/(2R^2).","section":"Appendix D.1, k not in K case"},{"comment":"Several narrative passages and table entries report rates such as O((1 - 1/(L1*R))^N F0) for NGD and Clip-GD, while the corresponding proofs in Appendices C.2-C.3 give contractions with constants 1/4 in the exponent; please standardize the constants between the theorems, the table, and the surrounding text.","section":"Sections 3.2-3.3 and Table 1"},{"comment":"The proof repeatedly uses the distance bound ||x_k - x*|| <= ||x_0 - x*|| = R, attributed to Gorbunov et al. (2024, proof of Theorem 3.3), without stating it as a lemma. Since this bound is load-bearing for every linear-rate estimate in the paper, it should be stated explicitly with a proof or a precise reference to the exact lemma.","section":"Appendix C.1, Theorem 3.1 proof"},{"comment":"The input line of Algorithm 5 mentions a 'random generator R_alpha(L0,L1)' that is neither defined nor used in the algorithm or its analysis; please remove it or clarify its role.","section":"Algorithm 5"},{"comment":"The proof defines T as the first index with ||grad f(x_k)|| < L0/L1 and ||grad f(x_{k-1})|| >= L0/L1, while the theorem defines T as the smallest index satisfying only the first condition; these definitions should be aligned, especially to cover the case T=0 when the initial gradient is already below the threshold.","section":"Appendix C.1, definition of T"}],"recommendation":"major_revision","confidential_remarks":"The full-gradient core of the paper appears sound and worth publishing once the rate statements are cleaned up. The coordinate-descent section is the main concern: the stated linear exponent is not supported by the proof and the random-set conditioning is informal, so the advertised first results for RCD and OrderRCD need a rigorous revision. I recommend major revision rather than rejection because the issues are local and fixable within the manuscript's scope, and because the qualitative phase-split claim may survive a repaired proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the GD/NGD/Clip-GD phase-split results are real and worth knowing, and the RCD/OrderRCD material is a good idea with a proof gap. The paper deserves refereeing, but the coordinate-descent theorems need to be fixed before they can be trusted.\n\nWhat's actually new: for convex (L0,L1)-smooth objectives, the authors show that GD with step size 1/(L0+L1||grad f||) converges linearly while ||grad f|| >= L0/L1, then sublinearly. The same qualitative behavior is shown for NGD and Clip-GD, with Clip-GD handled for arbitrary clipping thresholds. These proofs are standard descent-plus-convexity arguments, and they look valid. The constant 1/(4L1R) in the linear rate may not be tight, but the claim is clear. This is a genuine refinement over the earlier O(L0R^2/N) bounds, and it's honest of them to cite the independent overlap with Vankov et al.\n\nThe RCD and OrderRCD results are new—no prior (L0,L1)-coordinate-smoothness analysis exists—and the idea of using the set K = {large-gradient coordinates dominate} to get a phase split is attractive. But the proof in Appendix D.1 has two problems. First, the theorem states a linear term (1 - rho/(dR))^N, while the proof yields (1 - rho/(dR))^{N/2}; since (1-a)^N < (1-a)^{N/2}, the stated rate is stronger than what is proven. That's a straightforward error in the theorem statement. Second, and more importantly, the set K depends on the random iterates, so the split into K and its complement is a random partition. The proof applies the linear contraction along the random subsequence and telescopes expectations in a way that isn't a valid conditional-expectation argument. A stopping-time treatment or a different decomposition is needed. This is not cosmetic; as written, the RCD/OrderRCD phase-split claim is not established.\n\nThe full-gradient part is otherwise in good shape. The distance bound ||x_k - x*|| <= R is imported from Gorbunov et al. rather than proven, which is acceptable if the citation is right. The monotonicity lemmas in Appendix B are careful. The strongly convex extension is a straightforward add-on. Minor point: the linear rate is only meaningful when 4L1R > 1; the paper doesn't flag this regime, but the sublinear bound still covers the other case.\n\nWho gets value: anyone working on generalized smoothness or adaptive GD variants. The full-gradient theorems are the quick win; the coordinate results are promising but need a v2.\n\nMy recommendation: send it to review. The central GD result is useful and likely correct, and the coordinate methods are worth getting right. But the report should make clear that the RCD/OrderRCD theorems must be reconciled with the proof.","headline":"Full-gradient phase-split results are solid and worth knowing, but the RCD/OrderRCD theorems are not yet supported by the written proof.","tokens_in":30872,"tokens_out":4552,"would_cite":true,"duration_ms":39777,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a broad class of convex functions with generalized smoothness, gradient descent converges linearly at first, then sublinearly, and the same two-phase behavior holds for normalized, clipped, and coordinate-descent variants.","keywords":["convex optimization","generalized smoothness","(L0,L1)-smoothness","gradient descent","linear convergence","clipping","coordinate descent","order oracle"],"falsifier":"Run $(L_0,L_1)$-GD on a convex, $(L_0,L_1)$-smooth function (for example the logistic loss with a small strongly convex regularizer) from a point with $\\|\\nabla f(x_0)\\|>L_0/L_1$, recording $\\|x_k-x_*\\|$ and $\\|\\nabla f(x_k)\\|$ at every step; if either quantity ever increases, the monotonicity and distance lemmas behind Theorem 3.1 fail, breaking the claimed rate. Absence of the predicted linear segment while the gradient norm stays above $L_0/L_1$ would also directly contradict the theorem.","tokens_in":29790,"feed_emoji":"📉","tokens_out":10946,"duration_ms":85518,"temperature":0.7,"pith_summary":"This paper proves that, for convex functions satisfying the $(L_0,L_1)$-smoothness condition—gradients change at a rate bounded by $L_0 + L_1$ times the current gradient norm—gradient descent with step size $1/(L_0+L_1\\|\\nabla f(x_k)\\|)$ converges linearly as long as $\\|\\nabla f(x_k)\\|\\ge L_0/L_1$, then switches to the usual sublinear rate after the gradient falls below that threshold. The same two-phase behavior is proved for normalized gradient descent, clipped gradient descent, random coordinate descent, and a coordinate method that only compares function values. If correct, the results give faster linear rates during the early phase of optimization, replacing sublinear-only guarantees in the regime where $L_0$ is small relative to $L_1$, as in logistic regression. The paper also extends the GD analysis to strongly convex objectives, where three distinct rates appear.","feed_headline":"For convex (L0,L1)-smooth problems, GD turns linear then sublinear","feed_subtitle":"The same two-phase behavior holds for normalized, clipped, and coordinate-descent methods, beating sublinear-only bounds.","key_machinery":"The load-bearing objects are the $(L_0,L_1)$-smoothness inequality $\\|\\nabla f(y)-\\nabla f(x)\\|\\le (L_0+L_1\\|\\nabla f(x)\\|)\\|y-x\\|$ for nearby points and the adaptive step size $\\eta_k=(L_0+L_1\\|\\nabla f(x_k)\\|)^{-1}$. The proof converts convexity into the bound $f(x_k)-f_*\\le \\|\\nabla f(x_k)\\|R$ via the imported distance estimate $\\|x_k-x_*\\|=\\|x_0-x_*\\|=R$, then splits the analysis at $\\|\\nabla f(x_k)\\|=L_0/L_1$: above the threshold the step is roughly $1/(L_1\\|\\nabla f(x_k)\\|)$, producing a contraction $\\eta_k\\|\\nabla f(x_k)\\|^2\\gtrsim (f(x_k)-f_*)/(4L_1R)$; below the threshold the descent lemma gives the usual $1/N$ recurrence. A separate monotonicity lemma shows the gradient norm never increases along the iterates, which is what makes the phase description a clean before/after story rather than an interleaving of rates.","core_discovery":"The central claim is that the threshold $\\|\\nabla f(x)\\|=L_0/L_1$ divides the behavior of the methods. For $(L_0,L_1)$-GD, Theorem 3.1 proves $f(x_N)-f_*\\le \\min\\{4L_0R^2/(N-T), (1-1/(4L_1R))^T F_0\\}$, where $T$ is the first index with $\\|\\nabla f(x_T)\\|<L_0/L_1$; the linear factor holds while the gradient norm is at or above the threshold and the sublinear factor afterwards. Because the gradient norm is shown to be non-increasing along the iterates, the switch between phases happens at most once. The same linear-then-sublinear split is established for normalized and clipped GD, with the clip radius $c$ determining the effective linear rate, and for random coordinate descent and its order-oracle version under coordinate-wise $(L_0,L_1)$-smoothness, with rates $(1-\\rho/(dR))^N F_0$ and $dL_0R^2/N$. In the strongly convex case the GD rate becomes a product of three geometric factors, each active in a different regime.","pith_inferences":["Editorial extension: the threshold $L_0/L_1$ is exactly where the adaptive step's $L_1$ term starts to dominate the $L_0$ term, so the same phase split should appear for other adaptive first-order methods—stochastic gradient descent with clipping, AdaGrad-like steps, and parameter-free methods—on objectives whose smoothness constant grows with the gradient norm.","The paper leaves open whether the distance bound $\\|x_k-x_*\\|\\le R$ can be replaced by a sublevel-set localization; if it can, the linear phase would extend to functions with unbounded minimizer sets, such as the logistic loss itself, where the paper's Appendix F uses a finite accuracy radius $R_s$ instead.","A testable extension: on a logistic-regression objective (satisfying $L_0=0$), the analysis predicts geometric decay $O((1-1/(2L_1R_s))^N)$ rather than a $1/N$ tail; running GD with $\\eta_k=1/(L_1\\|\\nabla f(x_k)\\|)$ and measuring the ratio of successive function gaps would verify the predicted transition."],"forward_implications":["Under convexity and $(L_0,L_1)$-smoothness, $(L_0,L_1)$-GD, NGD, and Clip-GD all converge linearly while $\\|\\nabla f(x_k)\\|$ stays above the threshold, with a rate of the form $O((1-\\rho/R)^T F_0)$ for a method-dependent $\\rho$.","Once the gradient norm drops below the threshold, the methods fall back to the standard sublinear $O(L_0R^2/(N-T))$ rate, matching previously known worst-case bounds.","Random coordinate descent and OrderRCD inherit the same phase split under coordinate-wise $(L_0,L_1)$-smoothness, with linear rate $(1-1/(4\\sqrt{2}dL_1R))^N$ and sublinear factor $dL_0R^2/N$; OrderRCD needs only $O(\\log(1/\\epsilon))$ function-comparison oracle calls per iteration.","In the strongly convex case, GD exhibits three regimes: rate $1-1/(4L_1R)$ while the gradient is large and $F_k\\ge 1$, rate $1-\\max\\{\\sqrt{\\mu}/(2\\sqrt{2L_1}),1/(4L_1R)\\}$ while the gradient is large, and rate $1-\\mu/(2L_0)$ once the gradient is small.","When $L_0=0$ (the strong-growth smoothness condition), all analyzed methods converge linearly to arbitrarily high accuracy, e.g., $O(L_1R\\log(F_0/\\epsilon))$ iterations for GD and $O(dL_1R\\log(F_0/\\epsilon))$ for RCD."],"supporting_citations":[{"why":"Supplies the prior $O(L_0R^2/N)$ rate for (L0,L1)-GD and Clip-GD and the distance bound $\\|x_k-x_*\\|\\le\\|x_0-x_*\\|$ imported in Appendix C.1.","marker":"Gorbunov et al. (2024)"},{"why":"Independently derived a related rate for (L0,L1)-GD; the present paper improves it with an explicit linear-phase rate.","marker":"Vankov et al. (2024b)"},{"why":"Introduces the (L0,L1)-smoothness assumption and the descent inequality used throughout the proofs.","marker":"Zhang et al. (2020b)"},{"why":"Provides the earlier Clip-GD analysis that the paper refines, including the cases summarized in Table 1.","marker":"Koloskova et al. (2023)"},{"why":"Introduced coordinate-wise (L0,L1)-smoothness (Assumption 1.3) and the inequality used in the RCD proofs.","marker":"Crawshaw et al. (2022)"},{"why":"OrderRCD algorithm and golden-ratio-method oracle complexity that Section 4 extends to (L0,L1)-smoothness.","marker":"Lobanov et al. (2024)"},{"why":"Baseline RCD convergence rate under coordinate smoothness that Theorem 4.1 generalizes.","marker":"Nesterov (2012)"},{"why":"Gradient method analysis whose Polyak inequality is invoked in the strongly convex proof.","marker":"Polyak (1963)"},{"why":"Together with Polyak's inequality, provides the $\\|\\nabla f(x)\\|^2\\ge 2\\mu F$ step used in Appendix E.","marker":"Lojasiewicz (1963)"}],"fun_headline_variants":["Two-phase GD rate: linear above L0/L1 threshold, then sublinear","All GD variants: linear above L0/L1, sublinear below","GD linear until gradient norm dips below L0/L1, then sublinear","Convex (L0,L1)-smooth GD: linear then sublinear rates","Linear-then-sublinear split for (L0,L1)-smooth GD and its variants"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the iterates never move farther from a minimizer than the starting point, $\\|x_k-x_*\\|\\le\\|x_0-x_*\\|=R$ for every $k$, which is the step where convexity is converted into the gradient-norm bound on suboptimality.","fun_headline_variants_meta":{"raw":{"variants":["Two-phase GD rate: linear above L0/L1 threshold, then sublinear","All GD variants: linear above L0/L1, sublinear below","GD linear until gradient norm dips below L0/L1, then sublinear","Convex (L0,L1)-smooth GD: linear then sublinear rates","Linear-then-sublinear split for (L0,L1)-smooth GD and its variants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002396,"raw_usage":{"total_tokens":9303,"prompt_tokens":1114,"completion_tokens":8189,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":730,"completion_tokens_details":{"reasoning_tokens":8096}},"tokens_in":730,"tokens_out":8189,"duration_ms":49553,"temperature":1.0,"reasoning_tokens":8096,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:50:43.098639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run $(L_0,L_1)$-GD on a convex, $(L_0,L_1)$-smooth function (for example the logistic loss with a small strongly convex regularizer) from a point with $\\|\\nabla f(x_0)\\|>L_0/L_1$, recording $\\|x_k-x_*\\|$ and $\\|\\nabla f(x_k)\\|$ at every step; if either quantity ever increases, the monotonicity and distance lemmas behind Theorem 3.1 fail, breaking the claimed rate. Absence of the predicted linear segment while the gradient norm stays above $L_0/L_1$ would also directly contradict the theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the earlier Clip-GD analysis that the paper refines, including the cases summarized in Table 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced coordinate-wise (L0,L1)-smoothness (Assumption 1.3) and the inequality used in the RCD proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"OrderRCD algorithm and golden-ratio-method oracle complexity that Section 4 extends to (L0,L1)-smoothness."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Baseline RCD convergence rate under coordinate smoothness that Theorem 4.1 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gradient method analysis whose Polyak inequality is invoked in the strongly convex proof."}],"review_version":1}