{"id":"d5f3dd54-4fee-40f1-a88a-ee3b151971c1","arxiv_id":"2508.17288","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Twin Polyak estimates the unknown optimal function value with a second iterate sequence and claims linear convergence for strongly convex functions, but the key assumption is unproven and can be violated.","lead":"This paper proposes Twin Polyak, a gradient descent method that runs two iterate sequences and uses the gap between their function values as a parameter-free Polyak stepsize, so the optimal value never has to be known. A generalist might read it because removing the learning-rate tuning step from optimization could simplify machine learning pipelines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stopping rule uses twin-gap as an optimality certificate; TP can return a non-optimal point immediately, so the central parameter-free convergence claim is unsupported.","rationale":"The reader's weakest assumption (Assumption 1) is indeed load-bearing, and I agree with the rejection. My stress-test sharpens the issue: even when Assumption 1 is satisfied (the near-equal initialization above gives a=ε), the algorithm's stopping rule can return a point whose suboptimality is arbitrarily larger than ε. This is not a minor gap; it invalidates the practical interpretation of Theorem 1. A conditional rate for the iterates is fine, but Algorithm 1 is claimed to be a solver, and its output guarantee is absent. The experiments do not cover this failure mode, and the stochastic variant STPm additionally requires a momentum parameter, undercutting the 'without parameters' claim, though that is secondary. My recommendation is unchanged from the reader: reject, primarily because the central claim is not established for the algorithm as stated.","tokens_in":16173,"tokens_out":28418,"duration_ms":296300,"concrete_test":"Run Algorithm 1 as written on f(x)=1/2||x||^2 with x0=(1,0), y0=(sqrt(1-ε),0) for ε=10^-3; record the returned point and f(x)-f*. The algorithm stops at k=0 with suboptimality 0.5, which is 500 times the requested accuracy, demonstrating that the twin-gap stopping rule is not an optimality certificate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central result, Theorem 1, is conditional on Assumption 1, which the paper only proves for quadratics (Lemma 1) and does not enforce. But there is a more direct failure. Algorithm 1 line 4 stops as soon as |f(x_k)-f(y_k)| < ε, and this difference is not a certificate of f*-suboptimality. Take f(x)=1/2||x||^2, x0=(1,0), y0=(sqrt(1-ε),0) with ε∈(0,1). Then f(x0)-f*=1/2 while |f(x0)-f(y0)|=ε/2 < ε, so TP returns x0 at k=0, with suboptimality 1/2 instead of ε. Assumption 1 holds at this point with a=ε, so the failure is not merely a violated assumption; the stopping rule itself severs the link between the algorithm's output and the claimed ε-neighborhood guarantee. The paper's own limitation section admits initialization sensitivity, but the issue is stronger: a positive-measure set of initializations (any pair with f-values within ε, including points far from the optimum) makes TP terminate immediately with an arbitrarily bad solution. Consequently, the headline claim that TP is a parameter-free method that provably estimates f* and converges is not supported for the algorithm as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Twin Polyak (TP), a deterministic parameter-free variant of the Polyak stepsize that maintains two sequences of iterates and uses the higher-valued sequence to update with a stepsize based on the functional gap between the two iterates, treating the lower value as a proxy for f*. The authors claim that TP is entirely parameter-free, scaling- and translation-invariant, and that it provides linear convergence for strongly convex smooth functions (Theorem 1) and O(1/sqrt(k)) rates under bounded gradients (Lemma 2), conditional on two assumptions that are proved only for quadratics. The paper also presents stochastic extensions STP and STPm, along with extensive numerical comparisons on LIBSVM datasets and a public code repository.","tokens_in":16511,"tokens_out":10034,"duration_ms":102414,"significance":"If the central claims were valid, the twin-sequence construction would be a noteworthy contribution to parameter-free optimization, and the explicit quadratic analysis in Lemma 1 plus the invariance properties are genuinely interesting. The experiments are broad and reproducible, with comparisons against several tuned baselines. However, the main theorem is conditional on an assumption that is not established for the algorithm, and the algorithm's stopping rule can return an arbitrarily suboptimal point even when all stated assumptions hold. These issues are load-bearing: the paper's headline claim that TP provably estimates f* and converges to an epsilon-neighborhood is not supported as written.","major_comments":[{"comment":"The stopping rule |f(x_k)-f(y_k)| < epsilon does not certify epsilon-optimality of x_k. For f(x) = 1/2 ||x||^2, x0 = (1,0), y0 = (sqrt(1-epsilon),0) with epsilon in (0,1), we have |f(x0)-f(y0)| = epsilon/2 < epsilon, so Algorithm 1 returns x0 at iteration 0, while f(x0)-f* = 1/2. Assumptions 1 and 2 hold at this point with a = epsilon and b = 1-epsilon, so the failure occurs even when the assumptions of Theorem 1 are in force. The claimed epsilon-neighborhood guarantee of Theorem 1 is therefore false for the algorithm as written.","section":"Section 2, Algorithm 1, line 4"},{"comment":"The existence of a uniform constant a in (0,1) along the TP trajectory is proved only for quadratics (Lemma 1). For general mu-strongly convex and L-smooth functions, the paper provides no argument that the generated sequences satisfy Assumption 1, and nothing in the update rule prevents the ratio |f(x_k)-f(y_k)|/(max{f(x_k),f(y_k)}-f*) from becoming arbitrarily small or zero before x_k reaches the optimum. Since Theorem 1's lower bound eta_k >= a/L and the linear rate both depend on Assumption 1, the conclusion in Section 7 that TP provably enjoys linear convergence for strongly convex functions is unsupported.","section":"Section 3.1, Assumption 1"},{"comment":"In Algorithm 1 exactly one of the twin sequences is updated per iteration, so the sequence {x_k} changes only on iterations where f(x_k) > f(y_k). The proof via Proposition 2 applies only to those update steps, yet the theorem states ||x_k - x*||^2 <= (1 - a mu/L)^k ||x0 - x*||^2 for every TP iteration k. This is not justified; the effective number of x-updates is about k/2, so the rate and the complexity bound O((1/a)(L/mu) log(1/epsilon)) need an additional factor of two.","section":"Theorem 1, iteration counter"}],"minor_comments":[{"comment":"The proof of equation (19) replaces E_zeta[s_{i,zeta} \\nabla f_i(x)] with E_zeta[s_{i,zeta}] \\nabla f_i(x), which is exactly the independence that the lemma aims to establish. As written, the proof is circular and the lemma is not established.","section":"Appendix C, Lemma 3"},{"comment":"The claim that TP and STPm are completely parameter-free is overstated: Algorithm 1 requires a stopping tolerance epsilon, and Algorithm 2 requires a momentum parameter alpha in [0,1). These are user-specified quantities, even if they are not problem-dependent like L or mu.","section":"Sections 1.3 and 7"},{"comment":"The stated limitation about initialization sensitivity is too weak. As shown in the first major comment, a positive-measure set of initializations (any pair with |f(x)-f(y)| < epsilon) makes TP terminate at k=0 with suboptimality arbitrarily large relative to epsilon, not merely 'suboptimal performance'.","section":"Section 6, Limitations"}],"recommendation":"reject","confidential_remarks":"The main theoretical claim is invalidated by the stopping-rule counterexample, and the assumptions underlying Theorem 1 are not established for the proposed algorithm. The twin-sequence idea may be salvageable by removing the early-stopping rule and adding a certified stopping criterion, but that would require substantial revision and is beyond the scope of a minor or even major revision of the current manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the twin-iterate idea is real, the quadratic invariant is neat, but the algorithm as stated has a load-bearing bug in its stopping rule, and the general convergence theory rests on an assumption that is neither proven nor enforced. It deserves referee time, not a desk reject, but the authors need to fix the stopping rule and either prove Assumption 1 or scope the claims.\n\nWhat's new: TP maintains two iterates and always updates the one with higher function value, using the other as a stand-in for f*. That is genuinely different from the lower-bound/restart approach of Hazan-Kakade or SPSmax. Lemma 1—for quadratics, the ratio of squared norms of the two iterates is preserved across updates—is clean and correct, and it does imply Assumptions 1 and 2 for quadratics. The linear rate conditioned on Assumption 1 is standard Polyak analysis (Theorem 1 really does follow from their Proposition 2), and it is correctly derived.\n\nSoft spots. The big one is the stopping rule. Algorithm 1 returns xk as soon as |f(xk)-f(yk)| < ε. That difference is not a certificate of optimality. On f(x)=½||x||², take x0=(1,0) and y0=(√(1-ε),0). Then |f(x0)-f(y0)|=ε/2<ε, so TP returns x0 at k=0 with f-suboptimality 1/2, not ε. Assumption 1 can hold at that point (with a≤ε), so this is not merely a violated assumption; the stopping criterion itself severs the link between output and the claimed ε-neighborhood. The limitation section mentions initialization sensitivity but does not flag this. A fix could be to stop on a gradient norm, or on a bound that actually implies near-optimality, and state the guarantee for the returned point.\n\nSecond, Assumption 1 is only proven for quadratics. For general strongly convex smooth functions, there is no argument that the twin gap stays proportional to f(x_k)-f*. The paper says 'for quadratic functions, both a and b are guaranteed to exist,' but then states Theorem 1 for general strongly convex functions. That is a mismatch. Either scope the theorem to functions where Assumption 1 can be verified, or support the assumption with real analysis.\n\nThird, the parameter-free claim is overstated for STPm, which needs a momentum parameter α and is what the experiments actually use. The experiments also omit parameter-free baselines like DoG and DoWG. For a paper whose pitch is 'no tuning,' that is an odd omission.\n\nCitation pattern looks fine; related work is appropriately placed. Code is available. This is a serious paper with a fixable flaw. I recommend sending it to review with a request to resolve the stopping-rule issue and either prove or properly scope Assumption 1. If those are fixed, the twin-sequence idea is a worthwhile contribution.","headline":"Genuinely new twin-sequence estimator for f*, but the stopping rule invalidates the stated guarantee and Assumption 1 is unproven outside quadratics; worth refereeing, not a desk reject.","tokens_in":16992,"tokens_out":2720,"would_cite":false,"duration_ms":27023,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Twin iterates make the Polyak stepsize fully parameter-free by estimating the optimal value from above.","keywords":["parameter-free optimization","Polyak stepsize","twin iterates","strong convexity","linear convergence","adaptive stepsize","stochastic gradient descent","scale invariance"],"falsifier":"Run Twin Polyak from two starting points with equal functional values on any strongly convex smooth function, for instance f(x)=x² with x₀=1 and y₀=−1; Algorithm 1 stops at line 4 because |f(x₀)−f(y₀)| < ε, even though x₀ is far from the optimum. More generally, find any smooth strongly convex f where the ratio |f(x_k)−f(y_k)|/(max{f(x_k),f(y_k)}−f*) tends to 0 along the TP trajectory, which would directly violate Assumption 1 and invalidate the linear-rate conclusion.","tokens_in":15994,"feed_emoji":"🎯","tokens_out":4955,"duration_ms":49473,"temperature":0.7,"pith_summary":"The paper tries to establish that the classic Polyak stepsize, which normally requires knowing the optimal functional value f*, can be made entirely parameter-free by running two sequences of iterates at once. The higher-valued sequence takes a Polyak-like step using the lower-valued sequence as an ever-improving upper estimate of f*. Under a gap condition that the paper proves for quadratics, the authors show linear convergence for smooth strongly convex problems with no tunable step size, and sublinear convergence for convex problems with bounded gradients. A stochastic momentum variant is also proposed, and experiments show it competing with tuned baselines across classification and regression tasks.","feed_headline":"Twin iterates make the Polyak stepsize fully parameter-free","feed_subtitle":"Two gradient-descent sequences estimate the unknown optimal loss from above, giving linear convergence with no tuned step size.","key_machinery":"The load-bearing object is the pair of twin sequences x_k and y_k together with the loss-difference stepsize η_k = 2(f(x_k)−f(y_k))/‖∇f(x_k)‖², where the sequence with the higher functional value is updated and the lower-valued sequence acts as a dynamic upper bound on f*. Assumption 1 is the mechanism converting the unknown gap to f* into a controlled fraction of the observed loss gap, which ensures the stepsize cannot vanish and drives the linear convergence result.","core_discovery":"The central claim is Theorem 1: if f is μ-strongly convex and L-smooth, and the Twin Polyak trajectory satisfies Assumption 1, then the stepsize η_k = 2(f(x_k)−f(y_k))/‖∇f(x_k)‖² is at least a/L and the iterates converge linearly to x* with rate 1 − aμ/L. The proof is a direct application of the standard Polyak descent bound once the stepsize is shown to be bounded below by a/L. The paper also establishes a O(1/√k) guarantee for convex functions with bounded gradients under gap assumptions, proves that for quadratics the twin iterates alternate and converge with ratio ‖y₀‖²/‖x₀‖², and provides a stochastic variant that replaces full losses and gradients with batches plus momentum for practical use.","pith_inferences":["Assumption 1 is only verified for quadratics; the linear-rate theorem is conditional on an unproven property of general strongly convex trajectories, so a natural test is to record the ratio |f(x_k)−f(y_k)|/(max{f(x_k),f(y_k)}−f*) along TP on simple strongly convex losses and check whether it stays bounded away from zero.","If the gap ratio turns out to fail only in contrived cases, the algorithm could be made more robust by handling the near-equal-loss stopping condition, since TP currently stops when |f(x_k)−f(y_k)| < ε even if the iterates are still far from the optimum.","The twin-sequence idea is a general recipe: any method that needs an optimal-value estimate could use a second trajectory as an upper oracle, and the unbiasedness caveat of Lemma 3 suggests that stochastic adaptive stepsizes generally sacrifice gradient unbiasedness, pointing toward momentum-based corrections like STPm as a practical necessity."],"forward_implications":["If Assumption 1 holds along the trajectory, TP converges linearly at rate 1 − aμ/L for smooth strongly convex functions, matching gradient descent with a well-chosen constant stepsize.","TP reaches an ε-accurate solution in O((1/a)(L/μ) log(1/ε)) iterations without ever receiving f*, L, μ, or any stepsize parameter.","Because the stepsize depends only on current losses and gradients, TP is invariant under transformations f → c·f and f → c + f, so dataset rescaling or translation does not change the iterates.","For convex losses with uniformly bounded gradients, TP has sublinear convergence O(1/√k) under the same type of gap conditions.","The stochastic momentum variant STPm is shown numerically to reach performance competitive with tuned SPSmax, DecSPS, SLS, and SGD on binary classification and regression datasets."],"supporting_citations":[{"why":"Introduces the Polyak stepsize η_k = (f(x_k)−f*)/‖∇f(x_k)‖² that TP adapts into a parameter-free form.","marker":"[Polyak, 1969]"},{"why":"Prior work estimating f* by restarting with improved lower bounds; TP's contribution is to estimate f* from above using a twin sequence instead.","marker":"[Hazan and Kakade, 2019]"},{"why":"Defines SPSmax, the stochastic Polyak baseline that requires exact optimal values f*_i and a clipping parameter γ, which TP aims to remove.","marker":"[Loizou et al., 2021]"},{"why":"Introduces DecSPS, which relaxes f*_i to lower bounds but still needs a schedule parameter c₀, a sensitivity TP contrasts with.","marker":"[Orvieto et al., 2022]"},{"why":"Provides a bisection-based parameter-free SGD, one of the parameter-free methods that motivates removing prior knowledge of f*.","marker":"[Carmon and Hinder, 2022]"},{"why":"Supplies the momentum models that STPm borrows to make the stochastic loss and gradient estimators practical.","marker":"[Schaipp et al., 2023]"},{"why":"Introduces DoG, a distance-based parameter-free stepsize that can diverge, motivating the need for a stable parameter-free Polyak variant.","marker":"[Ivgi et al., 2023]"}],"fun_headline_variants":["Polyak stepsize without the oracle value","Twin iterates estimate optimal loss for Polyak","Parameter-free Polyak with linear convergence","No-tune Polyak: two sequences, one estimate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Assumption 1, that the loss gap between the two iterates stays at least a fixed fraction a of the larger iterate's distance to f*, is the only route to the stepsize lower bound a/L; the paper proves this only for quadratics, leaving it unverified for general strongly convex functions.","fun_headline_variants_meta":{"raw":{"variants":["Polyak stepsize without the oracle value","Twin iterates estimate optimal loss for Polyak","Parameter-free Polyak with linear convergence","No-tune Polyak: two sequences, one estimate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1347,"prompt_tokens":830,"completion_tokens":517,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":446,"completion_tokens_details":{"reasoning_tokens":458}},"tokens_in":446,"tokens_out":517,"duration_ms":5495,"temperature":1.0,"reasoning_tokens":458,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:07:34.567396+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Twin Polyak from two starting points with equal functional values on any strongly convex smooth function, for instance f(x)=x² with x₀=1 and y₀=−1; Algorithm 1 stops at line 4 because |f(x₀)−f(y₀)| < ε, even though x₀ is far from the optimum. More generally, find any smooth strongly convex f where the ratio |f(x_k)−f(y_k)|/(max{f(x_k),f(y_k)}−f*) tends to 0 along the TP trajectory, which would directly violate Assumption 1 and invalidate the linear-rate conclusion.","supporting_citations":[],"review_version":2}