{"id":"60be47b9-b338-433f-af56-fc84abbf3741","arxiv_id":"2508.06743","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A Lyapunov framework yields O(1/log T) and O(log T/T) gradient-norm rates for Schedule-Free on smooth nonconvex objectives, with the faster rate depending on an unproven assumption.","lead":"This paper proves convergence-rate bounds for the Schedule-Free optimizer on smooth nonconvex problems, using a Lyapunov potential that treats averaging and momentum in one framework. The headline rates are horizon-agnostic, but the faster ones rely on an unproven bounded-growth condition and part of the result was already known.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's O(log T/T) claim hinges on unproven Assumption 2; the PEP support is convex, so the 'only smoothness' framing is not established.","rationale":"The reader's weakest assumption is exactly Assumption 2, and my reading agrees that this is the load-bearing gap. The paper is otherwise candid: it labels Assumption 2 as an assumption, discusses the finite-horizon PEP limitation, and acknowledges the spikes and upward tail. Theorems 3 and 5 appear to provide a real O(1/log T) / O(T^{-(1-alpha)}) framework under Assumption 1, and the algebra errors noted by the reader are fixable without destroying the asymptotic rates. The main issue is that the abstract and Section 5 overstate the scope by saying all rates hold under only smoothness and lower-boundedness, when Theorem 4 additionally requires an unproven trajectory bound whose only numerical support is convex PEP. That warrants keeping the verdict CONDITIONAL, not ACCEPT, but does not rise to REJECT because the paper explicitly flags the assumption and the rest of the framework is plausibly correct. No change to the reader's verdict is needed; the condition should be: prove Assumption 2 or clearly demote Theorem 4 to a conditional result, and align the PEP description with the actual nonconvex problem class.","tokens_in":30236,"tokens_out":12531,"duration_ms":136919,"concrete_test":"Re-run the PEP experiment for the exact SF update with eta_t = eta0(t+1), c_{t+1}=1/(t+1), beta_t=1 over a genuinely nonconvex L-smooth lower-bounded function class (e.g., PEP with nonconvex interpolation constraints or randomized smooth nonconvex functions), for T in {200, 400, 800}. Compute the worst-case ratio ||z_T - x_T||^2/(T+1). If this ratio grows with T, Assumption 2 is false and Theorem 4's O(log T/T) rate is unsupported; if it remains bounded, the assumption is plausibly valid and the main concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's advertised central contribution is that a Lyapunov framework, under only L-smoothness and lower-boundedness (Assumption 1), yields horizon-agnostic nonconvex rates including O(log T/T) for a linearly growing step-size (Theorem 4). That rate rests entirely on Assumption 2 (Section 4.2): there exists D>0 with ||z_t - x_t||^2 <= D^2(t+1) for all t. Assumption 2 is a trajectory-level bound, not a function-class assumption, and it is not proved. The only evidence offered is PEP up to T=100 (Figure 1), and Section 5 itself notes intermittent spikes and an upward tail in the linear-step plot. More importantly, the PEP experiments in Appendix F use PEPit's SmoothFunction and the SDP in Section 3.6 is formulated for smooth convex functions (C^{1,1}_L), so the numerics do not validate a nonconvex worst case. If Assumption 2 fails for some L-smooth lower-bounded nonconvex objective, Theorem 4's O(log T/T) bound collapses to at best the O(1/log T) rate of Theorem 3. Because Theorem 4 is the paper's headline acceleration over the constant-step regime, this is the single most load-bearing gap: the 'under only L-smoothness' claim in the abstract and Section 5 is not supported for the linearly growing step-size result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Lyapunov framework for the Schedule-Free (SF) method in smooth nonconvex optimization. Under L-smoothness and lower boundedness, it claims O(1/log T) for the constant-step regime with ct+1=1/(t+1) and βt=1 (Theorem 3), O(log T/T) for a linearly growing step-size under an additional bounded-growth assumption on ||zt−xt||² (Theorem 4), and a continuum of O(T^{-(1−α)}) rates for polynomial averaging (Theorem 5). The proofs center on Lemma 1, a one-step descent inequality for a potential Vt = f(xt) − f* + At||δt||². PEP experiments up to T=100 are reported as numerical support. The central idea is promising, but several load-bearing proof steps are currently invalid or rely on an unproven trajectory-level assumption; the abstract also overstates the conditions under which the linear-step rate is established.","tokens_in":30559,"tokens_out":11082,"duration_ms":120173,"significance":"If fully corrected, the Lyapunov framework would provide a unified and simple analysis of SF-type methods under minimal assumptions, and the explicit PEP code and honest discussion of limitations are strengths. The O(1/log T) rate for constant step is not new (it is attributed to Liu et al.), but the framework's breadth across averaging schedules is a useful contribution. However, the advertised headline acceleration to O(log T/T) depends on an unproven trajectory assumption, and the current proofs of Theorems 3 and 4 contain invalid telescoping steps. The significance of the paper therefore depends on whether these gaps are fixable; as printed, the central claims are not fully established.","major_comments":[{"comment":"The telescoping step is invalid. The proof derives S_T · min_{2≤t≤T−1} ||∇f(xt)||² ≤ V2 + (σ²η/2)S_T, where S_T = Σ_{t=2}^{T−1} 1/(t+1). It then replaces S_T by log T on the left, writing (η/4) log T · min ≤ V2 + ... . Since S_T < log T, this is a stronger inequality and does not follow. The correct conclusion, min ≤ 4V2/(η S_T) + 2σ², still yields O(1/log T), so the theorem's rate is salvageable, but the printed proof must be corrected.","section":"§D.1 (Theorem 3)"},{"comment":"Theorem 4's O(log T/T) rate rests entirely on Assumption 2, a trajectory-level bound ||δt||² ≤ D²(t+1) that is not proved for the L-smooth lower-bounded nonconvex class. The PEP evidence is finite-horizon (T≤100) and is computed with PEPit's SmoothFunction, which is convex; Section 5 itself notes intermittent spikes and an upward tail in the linear-step plot, and says the O(log T/T) bound 'may not hold uniformly in the true worst case.' The abstract's claim of O(log T/T) 'under only L-smoothness and lower-boundedness' is therefore not supported. This needs to be reframed as conditional on Assumption 2, or Assumption 2 must be proved or replaced by a condition implied by Assumption 1.","section":"§4.2 / Theorem 4"},{"comment":"Even conditional on Assumption 2, the final telescoping step uses the wrong denominator. The proof sums t=2,...,T−1, so the first term should be 4V2/(η0(T−2)), not 4V2/(η0T). The printed bound is stronger than what the displayed inequality proves. The asymptotic O(1/T) rate is preserved after this correction, but the proof as written is invalid.","section":"§D.2 (Theorem 4)"},{"comment":"The index convention for At is inconsistent between the main text and the proof. Eq. (4) defines At = c_{t+1}(1−Lηt c_{t+1})/(2ηt(1−c_{t+1})²), while in the proof of Lemma 1, At+1 is set to c_{t+1}(1−Lηt c_{t+1})/(2ηt(1−c_{t+1})²) and the final bracket contains c_t-terms. Since Lemma 1 underpins all theorems, the coefficient sequence must be defined consistently and the cancellation step re-verified.","section":"Eq. (4) vs §C.5 (Lemma 1)"}],"minor_comments":[{"comment":"The SDP in Eq. (3) lists matrices Ai,j, Bi,j, Ci, Di, but their definitions are incomplete. Also, the PEP code uses SmoothFunction (convex), so claims that the numerics validate nonconvex behavior should be qualified.","section":"§3.6"},{"comment":"The displayed bound writes '+2σ²' inside the denominator: 'ηT − 2η − αη log T + 2σ²'. The proof gives 4V2/(ηS) + 2σ²; the theorem statement should match the proof.","section":"Theorem 5 (increasing c)"},{"comment":"The proof line 'which is always true for t ≥ 2' condenses a nontrivial inequality chain. Please expand it; the current derivation does not make the sufficient condition explicit.","section":"§D.3 (Theorem 5, decreasing c)"},{"comment":"There are typos and rendering artifacts: 'by by Ahn', 'Defazio et al. and and Sebbouh', and figure axes showing 'uni00A0'. These should be cleaned up.","section":"General presentation"}],"recommendation":"major_revision","confidential_remarks":"The paper has a promising core Lyapunov idea and is transparent about the empirical nature of Assumption 2. The main issue is rigor: the telescoping in Theorems 3 and 4 is invalid as printed, and the abstract overclaims the conditions for the linear-step rate. I would like to see a revised version that fixes the telescoping, clarifies the At indexing, and either proves Assumption 2 or honestly presents Theorem 4 as conditional. If Assumption 2 cannot be established, the paper may still be publishable for Theorems 3 and 5 plus a conditional linear-step result, but the advertising in the abstract must change."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a genuinely new Lyapunov potential that reduces Schedule-Free analysis to a one-step descent inequality, and the polynomial averaging family in Theorem 5 is new as far as I can tell. But the proof of Theorem 3 has a telescoping slip, and Theorem 4's O(log T/T) rate rests entirely on an unproven trajectory bound (Assumption 2). It deserves a serious referee, not a desk reject, but it is not ready as is.\n\nThe framework itself is the real contribution. The potential V_t = f(x_t) - f* + A_t ||z_t - x_t||^2 cleanly handles the three-sequence update, and Lemma 1 gives a single inequality from which the constant-step and polynomial averaging rates follow. The paper is candid: it credits Liu et al. for the O(1/log T) result, labels the possible O(1/T) improvement a conjecture, and in Section 5 openly notes the finite-horizon PEP evidence, the spikes in the distance plot, and the upward tail for the linear step. That honesty is worth acknowledging.\n\nThe soft spots are the ones the reader flagged. In Appendix D.1, the telescoping step replaces S = sum 1/(t+1) with log T, but S < log T, so the inequality direction is wrong. The asymptotic rate survives because S = Theta(log T), but the printed bound is stronger than the proof supports. More serious is Theorem 4: the O(log T/T) rate depends on Assumption 2, a uniform bound on ||z_t - x_t||^2 that is not implied by L-smoothness and lower boundedness. The PEP support is finite-horizon and noisy; the paper's own figures show the bound does not yet look stable. There is also an internal mismatch: the SDP in Section 3.6 is stated for smooth convex functions, while the code in Appendix F uses PEPit's SmoothFunction, which is not necessarily convex. So the 'only smoothness' claim in the abstract is not supported for the linear-step result, whichever way the mismatch is resolved.\n\nMinor issues include some notational sloppiness (A_t vs A_{t+1}) and terse algebra in parts of Appendix D.3. These are fixable. The core Lyapunov idea is sound and worth building on.\n\nI'd send this to peer review: the framework and Theorem 5 are legitimate, and the authors already know where the gaps are. But I would not trust Theorem 4's rate until Assumption 2 is either proven or honestly reduced to a formal conjecture. For a reading group, the Lyapunov structure makes for a good session; for a citation, the framework is citable if you are working on schedule-free methods, but not the O(log T/T) claim.\n\nRecommendation: engage with it, but treat Theorem 4 as conditional.","headline":"A clean Lyapunov framework with one new rate (Theorem 5) and one unproven load-bearing assumption (Theorem 4); worth a real referee, but the headline O(log T/T) claim needs a proof or a proper caveat.","tokens_in":31055,"tokens_out":4171,"would_cite":true,"duration_ms":45017,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single Lyapunov potential extends Schedule-Free's horizon-free guarantees to smooth nonconvex optimization, without global Lipschitz assumptions.","keywords":["schedule-free optimization","nonconvex optimization","Lyapunov framework","horizon-free convergence","Polyak-Ruppert averaging","momentum","performance estimation problem","smooth nonconvex"],"falsifier":"Run the paper's PEP SDP for T beyond 100 steps with eta_t = (t+1)/L and check whether the worst-case ||z_t - x_t||^2 stays below a $D^{2}$(t+1) envelope; if it eventually exceeds that linear bound, Assumption 2 fails and Theorem 4's O(log T/T) rate collapses. Alternatively, a smooth nonconvex function whose min gradient norm decays slower than C/log T would falsify the claim that O(1/log T) is the achievable rate for the constant-step SF regime.","tokens_in":30065,"feed_emoji":"🧮","tokens_out":7246,"duration_ms":74169,"temperature":0.7,"pith_summary":"The paper aims to give worst-case convergence guarantees for the Schedule-Free (SF) optimization method in nonconvex settings, dropping the global Lipschitz-gradient and well-behaved assumptions that limited earlier analyses. It claims that one Lyapunov potential reduces SF's analysis to a single-step descent inequality, yielding horizon-agnostic rates: O(1/log T) for the classic constant step with Polyak–Ruppert averaging, O(log T/T) for a linearly growing step, and a continuum of O($T^{{-(1-alpha)}}$) rates for polynomial averaging weights. If sound, this means SF's horizon-free property—no need to know the total training time T—extends to smooth nonconvex problems. The paper also uses Performance Estimation Problem experiments up to T=100 to validate these rates and to suggest that the O(1/log T) bound may be improvable to O(1/T).","feed_headline":"Nonconvex rates proven for Schedule-Free with only smoothness","feed_subtitle":"No horizon needed: constant steps give O(1/log T), growing steps give O(log T/T) on smooth nonconvex losses.","key_machinery":"The Lyapunov potential V_t = f(x_t) - f* + A_t||delta_t||^2, where delta_t = z_t - x_t and A_t = c_{t+1}(1 - L eta_t c_{t+1}) / (2 eta_t (1 - c_{t+1})^2). The coefficient A_t is engineered so that, under the step-size constraint L eta_t c_{t+1} <= 1, the potential is non-negative and the bracketed discrepancy term in Lemma 1 is non-positive when beta_t = 1. Telescoping this one-step descent inequality over t yields all the stated rates; the bounded-growth Assumption 2 is what lets the linearly-growing-stepsize regime pass the discrepancy term through the telescope without losing the O(log T/T) rate.","core_discovery":"The central claim is that for an L-smooth, lower-bounded objective, the Schedule-Free three-sequence update admits a Lyapunov function V_t = f(x_t) - f* + A_t||z_t - x_t||^2, where A_t is chosen from the step size and averaging coefficient so that V_t decreases monotonically in the deterministic setting. Lemma 1 converts the entire convergence analysis into one descent inequality that charges the gradient norm of the slow sequence against the telescoping of V_t. From this, the paper derives horizon-agnostic worst-case rates: O(1/log T) with SF's original constant step and uniform averaging (Theorem 3), O(log T/T) with a linearly growing step under a bounded-growth condition on the z-x discre","pith_inferences":["If the O(1/T) conjecture from the PEP curves holds, SF's constant-step guarantee would become optimal in the deterministic nonconvex sense, eliminating the remaining gap between SF and scheduled momentum at the level of rates.","The framework's recommendation to set beta=1 in worst-case analysis implies that any certified robustness of SF to the averaging-versus-momentum tradeoff will require either a different potential or a late-start averaging scheme; the present one-step descent cannot handle beta<1 without weakening the bound.","Assumption 2 is the most fragile point in practice: the paper's own numerics show spikes in ||z_t - x_t||^2 under the linear step size, so testing the linear envelope beyond T=100 is a direct way to see whether the O(log T/T) rate extends to realistic horizons.","The stochastic extension in the appendix adds only an additive variance term, but it relies on standard bounded-variance assumptions; extending the framework to variance-reduced or adaptive-step variants would require re-deriving the one-step inequality for those updates."],"forward_implications":["With constant step size and uniform averaging (c_{t+1}=1/(t+1), beta=1), SF reaches min gradient norm O(1/log T) on any L-smooth lower-bounded function, with no horizon-dependent hyperparameters.","With the linearly growing step eta_t = eta_0(t+1) and Assumption 2, the same guarantee improves to O((V_2/eta_0 + D^2 log T)/T), matching momentum-style rates up to a log factor.","Polynomial averaging weights c_{t+1} = (t+1)^{-alpha} interpolate between uniform averaging (alpha=0) and the tail-averaging regime (alpha=1), with rates O(1/T^{1-alpha}) for alpha in [0,1) that collapse to a constant for alpha>1.","Increasing averaging weights c_{t+1} = (t/(t+1))^alpha preserve an O(1/T) rate up to a mild logarithm for alpha in [0,1).","PEP experiments up to T=100 support the stated rates and suggest the O(1/log T) bound for the constant-step case may actually be O(1/T), meaning the log factor could be an artifact of the proof technique."],"supporting_citations":[{"why":"Defines the Schedule-Free algorithm whose nonconvex analysis this paper supplies.","marker":"[1]"},{"why":"Establishes the equivalence between primal averaging and SGD with momentum, justifying the SPA form used in the proofs.","marker":"[13]"},{"why":"Proves an O(1/T) rate for SGD with momentum with rapidly decaying averaging, the benchmark that Theorem 3 recovers up to a log factor.","marker":"[14]"},{"why":"Introduces the PEP/SDP framework used here to numerically validate rates and to provide partial evidence for Assumption 2.","marker":"[2]"},{"why":"Prior nonconvex analysis of SF requiring global gradient Lipschitzness and well-behavedness, the assumptions this work removes.","marker":"[9]"}],"fun_headline_variants":["Schedule-free nonconvex rates with only smoothness","Lyapunov proof: schedule-free hits O(1/log T) on nonconvex","Horizon-agnostic bounds for schedule-free nonconvex","Nonconvex schedule-free: from O(1/log T) to O(log T/T)","Smooth nonconvex: schedule-free gets explicit rates"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The O(log T/T) bound for the linearly growing step size rests on an unproved assumption that the distance between the two iterate sequences stays at most linear in time; the evidence is only finite-horizon numerical experiments up to 100 steps, which the paper itself notes show spikes and a possible upward tail.","fun_headline_variants_meta":{"raw":{"variants":["Schedule-free nonconvex rates with only smoothness","Lyapunov proof: schedule-free hits O(1/log T) on nonconvex","Horizon-agnostic bounds for schedule-free nonconvex","Nonconvex schedule-free: from O(1/log T) to O(log T/T)","Smooth nonconvex: schedule-free gets explicit rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000151,"raw_usage":{"total_tokens":1052,"prompt_tokens":776,"completion_tokens":276,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":194}},"tokens_in":520,"tokens_out":276,"duration_ms":3283,"temperature":1.0,"reasoning_tokens":194,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:34:48.911416+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's PEP SDP for T beyond 100 steps with eta_t = (t+1)/L and check whether the worst-case ||z_t - x_t||^2 stays below a $D^{2}$(t+1) envelope; if it eventually exceeds that linear bound, Assumption 2 fails and Theorem 4's O(log T/T) rate collapses. Alternatively, a smooth nonconvex function whose min gradient norm decays slower than C/log T would falsify the claim that O(1/log T) is the achievable rate for the constant-step SF regime.","supporting_citations":[{"cited_title":"Performance of First-Order Methods for Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Introduces the PEP/SDP framework used here to numerically validate rates and to provide partial evidence for Assumption 2."}],"review_version":1}