{"id":"abcb5380-f70b-4e1b-b8a6-089e4cb245de","arxiv_id":"2412.08424","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Logistic regression with gradient descent and infinite step size is the batch perceptron, and a normalized version achieves an n times better iteration complexity.","lead":"This paper shows that gradient descent on logistic regression with an infinitely large step size turns into the classical batch perceptron algorithm for linearly separable data. That limit result explains why very large step sizes still solve the classification problem, and it leads to a normalized method with provably faster convergence.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's flagged weakness, that pointwise convergence without uniformity does not justify the finite-gamma iteration bound, does not land because the perceptron iteration count is finite for each dataset. For any fixed tau, pointwise convergence at t=1,...,tau immediately gives a common gamma threshold by taking the maximum of the individual thresholds. Thus the paper's explanation of why LR+GD with large step sizes solves (1) is rigorous. The theorem's reliance on Assumption 3.1 is a standard generic-condition measure-zero exclusion and is well motivated by the perturbation argument. I also checked the proofs of Theorems 3.3, 4.1, 5.1, and 6.1 and found them sound; the only minor issues are typos in theorem statements (e.g., 'Proof in Section D' in Theorem 5.3) which do not affect correctness. Therefore the recommended verdict remains as the reader's (CONDITIONAL due to minor presentation issues) or could be ACCEPT; since the reader's condition is not a correctness issue, I leave the verdict unchanged.","tokens_in":19320,"tokens_out":27691,"duration_ms":257381,"concrete_test":"Independent verification of the transfer: for a small separable dataset, compute the exact batch perceptron iterate theta_hat_tau that first solves (1), then run LR+GD with increasing gamma and confirm that theta_tau/gamma converges to theta_hat_tau and that theta_tau solves (1) for all gamma above a finite threshold. This checks that the pointwise limit at t=tau is indeed enough.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.2 is correct and its proof is internally consistent. The pointwise convergence theta_t/gamma -> theta_hat_t for each fixed t is sufficient to transfer the perceptron iteration bound to finite large gamma: for a given dataset, the batch perceptron solves at some finite tau <= nR^2/mu^2, and since theta_hat_tau is a strict separator, the pointwise limit at t=tau implies that for all sufficiently large gamma, theta_tau/gamma lies in a separating neighborhood of theta_hat_tau. Uniformity over t up to the iteration bound is not actually required because the set {1,...,tau} is finite, so the maximum of the individual gamma thresholds is finite. Assumption 3.1 is a generic non-degeneracy condition that excludes boundary cases, and the paper explicitly notes it holds for almost all datasets. The lower bound and the proposed Normalized LR+GD are also consistent with the limit identification. I find no load-bearing concern that threatens the central claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes gradient descent on logistic loss (LR+GD) for linearly separable data and shows that, as the step size γ tends to infinity, the normalized iterates θ_t/γ converge pointwise to the iterates of a batch perceptron (Theorem 3.2). This gives a simple mechanistic explanation for the empirically observed ability of LR+GD with very large step sizes to solve classification, and it identifies the limiting iteration count as nR²/μ². The paper further shows that logistic loss and gradient norms can be misleading indicators of progress (Theorem 4.1), proves a lower bound of Ω(n) iterations for the batch perceptron on a worst-case dataset (Theorem 5.1), and proposes Normalized LR+GD, with an iteration bound of R²/μ² + O(log n/(γμ²)) (Theorem 6.1). Numerical experiments on CIFAR-10, FashionMNIST, EuroSAT, and MNIST support the claimed alignment between large-step LR+GD and the batch perceptron.","tokens_in":19465,"tokens_out":25115,"duration_ms":232551,"significance":"If correct, the paper provides a clean and novel reduction of large-step-size logistic regression to the perceptron, connecting edge-of-stability behavior to a classical algorithm. The main theorem has a short, self-contained proof; the proof of Theorem 6.1 is a transparent potential argument; and the classical perceptron bound is reproved in the appendix. The paper also makes a useful conceptual point about evaluating optimization methods for classification by iteration count rather than by function values. No fitted parameters enter the theoretical claims, and the experiments are described in enough detail to be reproduced. The result should be of interest to the machine-learning theory community.","major_comments":[{"comment":"The case analysis misidentifies which class is misclassified. After θ̂1 = (0.25, (n−2)/(2n)), the misclassified sample is the class +1 sample (0.5,−1), not the class −1 sample; the displayed update +(1/n)(0.5,−1) is y_i a_i for the class +1 sample. The later stopping conditions are likewise written for the wrong class. The recurrence for θ̂_t is correct, and the Ω(n) bound follows once the labels are corrected, but as written the proof is not internally consistent.","section":"Section 5.1, proof of Theorem 5.1"}],"minor_comments":[{"comment":"The transfer from pointwise convergence to a statement about finite γ is not spelled out. Since the batch perceptron terminates at a finite τ, one only needs the pointwise limit at t=τ plus the fact that θ̂_τ has positive margin on every sample; no uniformity in t is required. Please add this one-sentence argument to remove any appearance of a gap.","section":"Section 3, after Theorems 3.2 and 3.3"},{"comment":"The claimed limit '∇f(θ_t) → 1/|S_t| ∑_{i∈S_t} y_i a_i' is incorrect. From (3), ∇f(θ_t) → −(1/n)∑_{i∈S_t} y_i a_i and β_t → |S_t|, so the quantity that converges to 1/|S_t|∑_{i∈S_t} y_i a_i is −β_t∇f(θ_t), not ∇f(θ_t). Please correct the sign and normalization in this motivating statement.","section":"Section 6, paragraph before Theorem 6.1"},{"comment":"The assumption 'θ1 = 0' does not match the proof, where θ0=0 and θ1 is computed explicitly. Please change it to θ0=0.","section":"Theorem 4.1 statement"},{"comment":"The displayed stopping condition involving 0.5×0.25(...) + (−1)×(n−2k)/(2n) > 0 is the margin of the positive sample, not of the negative sample; please correct the attribution or the expression.","section":"Theorem 5.1 proof, final paragraph"},{"comment":"Consider noting explicitly that for θ̂_t = (1/n)∑_{i=1}^n (0.5+k_i)y_i a_i, the condition y_j a_j^T θ̂_t ≠ 0 is exactly the non-intersection of the hyperplane with (0.5+k_1, ..., 0.5+k_n), which will help readers connect the assumption to the proof.","section":"Assumption 3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid theoretical contribution, and the issues identified are local and correctable. The main issue is the garbled case analysis in the proof of Theorem 5.1; once that is fixed, I would support acceptance. I do not see any circularity or novelty concern, and the related work discussion is adequate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the one thing you should know: the central result is real and non-obvious. As gamma → infinity, the iterates of gradient descent on the logistic loss, scaled by 1/gamma, converge exactly to the batch perceptron. The proof is half a page and uses the sigmoid as a soft threshold. This is a clean mechanistic explanation for the empirically observed fact that LR+GD with huge step sizes still separates linearly separable data. The closest prior work (Wu, Braverman, Lee 2024; Wu et al. 2024) proved convergence rates without identifying this limit, so this is new.\n\nThe paper does more than the limit theorem. It gives a simple construction showing the batch perceptron can need Omega(n) iterations, so the nR^2/mu^2 bound for LR+GD is tight and therefore LR+GD is suboptimal compared to the classical perceptron's R^2/mu^2. It then proposes Normalized LR+GD, which is essentially the gradient descent analog of the normalized batch perceptron, and proves an R^2/mu^2 + O(1/gamma) bound. The experiments on four datasets show the large-step LR+GD accuracy curves line up almost exactly with the batch perceptron, which is good supporting evidence.\n\nNow the soft spots. The reader flagged a uniformity issue in transferring the pointwise limit to a finite-time guarantee. On reading the proof, that is not actually a problem: the batch perceptron stops at some finite tau ≤ nR^2/mu^2, and since theta_hat_tau is a strict separator, pointwise convergence at t=tau is enough to make theta_tau/gamma a separator for all large gamma. No uniformity over t is needed. The stress-test note is right.\n\nRemaining issues are minor. Assumption 3.1 is a non-degeneracy condition to avoid samples lying exactly on a perceptron decision boundary. It is stated in a somewhat opaque hyperplane-intersection form, but the paper argues it excludes a measure-zero set, which is fine. There are several typos: a dangling reference to \"(Duda, Hart, and G.Stork 2001), Theorem 5.1\" in Theorem 5.2, and a sign typo in the proof of Theorem 3.3. The claim that larger step sizes always converge faster is empirical; the theory covers only the infinite-step-size limit. That is fine as long as the paper does not overstate it, and it mostly doesn't.\n\nWho should read this: anyone working on the edge of stability, large step size phenomena, or the dynamics of logistic regression on separable data. It deserves a serious referee; with a bit of cleanup it should be publishable at a good theory venue.","headline":"LR+GD with infinite step size is exactly the batch perceptron; new, clean proof, plus a solid suboptimality lower bound and a normalized variant.","tokens_in":19974,"tokens_out":3714,"would_cite":true,"duration_ms":36319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"In the infinite-step-size limit, logistic regression with gradient descent becomes the batch perceptron algorithm, and this limit explains why arbitrarily large steps still solve linearly separable classification problems.","keywords":["logistic regression","gradient descent","large step sizes","perceptron algorithm","edge of stability","iteration complexity","separable data","loss landscape metrics"],"falsifier":"Run LR+GD on a linearly separable dataset that violates Assumption 3.1 (e.g., a dataset where a batch perceptron iterate passes exactly through a sample) with a sequence of step sizes γ_k → ∞; if the rescaled iterates θ_t/γ_k still match the batch perceptron for all t, the assumption is unnecessary, while if they deviate, the theorem's stated scope fails. A second check: on the paper's lower-bound dataset with n samples, count iterations to perfect accuracy for LR+GD with very large γ and compare with Ω(n); a matching linear dependence supports the claim, and a sublinear count would refute it.","tokens_in":19066,"feed_emoji":"♾️","tokens_out":8594,"duration_ms":87831,"temperature":0.7,"pith_summary":"The paper aims to explain a paradox: logistic regression trained by gradient descent (LR+GD) still solves linearly separable classification problems when the step size is arbitrarily large, even though classical optimization theory says GD should diverge past the smoothness threshold. The central claim is that in the limit γ→∞, the rescaled LR+GD iterates θ_t/γ converge to the iterates of a batch version of the perceptron algorithm, so LR+GD inherits the classic perceptron convergence bound. It also claims that in this regime the logistic loss and gradient norm become misleading: larger steps raise the loss while speeding up the search for a separator. Finally, it argues that the batch perceptron's dependence on the number of samples n is a real weakness, proves an Ω(n) lower bound, and introduces Normalized LR+GD, a simple adaptive rescaling, to recover an n-free rate.","feed_headline":"Logistic regression with huge steps reduces to the perceptron","feed_subtitle":"The infinite-learning-rate limit of LR+GD is the classic perceptron, explaining why oversized steps still separate data.","key_machinery":"The load-bearing object is the rescaling θ_t/γ together with the sigmoid-to-threshold convergence: (1 + exp(γ y_i a_i^T (θ_t/γ)))^{-1} → 1 if y_i a_i^T θ̂_t < 0 and → 0 otherwise. Because each batch perceptron iterate is a nonnegative combination of samples, Assumption 3.1 ensures no sample sits exactly on the decision boundary, so the thresholds are well defined. This pointwise limit is what lets one transfer the classical perceptron analysis to LR+GD, and its failure mode—samples on the boundary—is exactly the technical assumption the paper needs.","core_discovery":"The paper's central discovery is a limit identity: under a mild non-degeneracy condition, for every fixed t, θ_t/γ → θ̂_t as γ→∞, where θ_t is the t-th LR+GD iterate from θ0=0 and θ̂_t is the t-th iterate of the batch perceptron algorithm. The mechanism is that the logistic sigmoid factors (1+exp(y_i a_i^T θ_t))^{-1} become hard thresholds 1[y_i a_i^T θ̂_t < 0] in the limit, so each gradient step converges to the batch perceptron update θ̂_t + (1/n)∑_{i∈S_t} y_i a_i. Because the classical perceptron bound guarantees separation in at most nR²/µ² steps, this gives a direct explanation of large-step-size success and identifies the effective iteration complexity of LR+GD in that regime. The paper further shows that this rate is suboptimal in n, proves an Ω(n) lower bound on a specific dataset, and introduces Normalized LR+GD, whose step is rescaled by the inverse average sigmoid, to recover the n-free rate R²/µ² while keeping the connection to the perceptron.","pith_inferences":["Extension: the same thresholding mechanism should apply to any smooth margin loss whose gradient approaches a hard indicator at large arguments, so other losses may inherit perceptron-like dynamics at large step sizes.","Extension: if loss and gradient values are unreliable on separable problems, existing benchmark comparisons of optimizers may be ranking methods by the wrong metric; reporting iterations-to-perfect-accuracy could reorder those rankings.","Extension: a formal measure-theoretic statement that degenerate datasets (Assumption 3.1 failures) have probability zero under any continuous data distribution would strengthen the paper's 'almost all datasets' claim without changing the argument.","Extension: on imbalanced data, where the paper observes normalized variants winning, an adaptive per-class normalization of the step might yield further iteration-count gains; this is directly testable with the paper's experimental setup."],"forward_implications":["For any separable dataset satisfying Assumption 3.1, LR+GD with γ→∞ solves the classification problem in at most nR²/µ² iterations.","Larger step sizes in LR+GD drive the logistic loss and gradient norm up while speeding up the search for a separator, so loss and gradient values are unreliable indicators of progress toward a solution.","The dependence on n in the iteration bound is essential for LR+GD with γ→∞: there are separable datasets with constant margin and radius on which it needs Ω(n) iterations.","Normalized LR+GD, which rescales the gradient step by the inverse average sigmoid, solves the problem in at most R²/µ² + 2 log(2n−1)/(γµ²) iterations, improving on LR+GD by a factor of n as γ→∞.","The max-margin implicit bias of small-step LR+GD does not carry over to the γ→∞ limit, since the batch perceptron does not generally return a max-margin separator."],"supporting_citations":[{"why":"Supplies the classical perceptron convergence bound R²/µ² that the γ→∞ reduction inherits.","marker":"Novikoff 1962"},{"why":"Textbook statement of the perceptron and batch perceptron convergence results used in Theorems 3.3 and 5.2.","marker":"Duda, Hart, and G.Stork 2001"},{"why":"Closest prior work proving LR+GD converges for any fixed step size; the paper's limit analysis explains the non-stable regime it identified.","marker":"Wu, Braverman, and Lee 2024"},{"why":"Refines the dependence on γ and shows the transition between unstable and stable regimes, motivating the large-step-size focus.","marker":"Wu et al. 2024"},{"why":"Establishes the max-margin implicit bias of small-step logistic regression, which the paper contrasts with the perceptron limit.","marker":"Soudry et al. 2018"},{"why":"Provides the smoothness-based small-step analysis of LR+GD and risk/parameter convergence results used as the baseline.","marker":"Ji and Telgarsky 2018"},{"why":"Establishes optimality of GD for nonconvex problems by gradient norm, the benchmark against which the paper's suboptimality claim is drawn.","marker":"Carmon et al. 2020"}],"fun_headline_variants":["Huge steps morph logistic regression into the perceptron","Infinite step size reveals LR+GD as batch perceptron","Large-step gradient descent becomes the perceptron","Why oversized learning rates still work: perceptron limit","Logistic regression's big steps match the perceptron"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole limit story rests on the non-degeneracy assumption that no training sample ever lies exactly on a decision boundary of a batch perceptron iterate, and on the unproven uniformity of the pointwise limit θ_t/γ → θ̂_t, which is needed to conclude that LR+GD finds a separator within the perceptron's nR²/µ² iteration bound.","fun_headline_variants_meta":{"raw":{"variants":["Huge steps morph logistic regression into the perceptron","Infinite step size reveals LR+GD as batch perceptron","Large-step gradient descent becomes the perceptron","Why oversized learning rates still work: perceptron limit","Logistic regression's big steps match the perceptron"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1598,"prompt_tokens":1054,"completion_tokens":544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":468}},"tokens_in":670,"tokens_out":544,"duration_ms":6370,"temperature":1.0,"reasoning_tokens":468,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:51:02.592140+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LR+GD on a linearly separable dataset that violates Assumption 3.1 (e.g., a dataset where a batch perceptron iterate passes exactly through a sample) with a sequence of step sizes γ_k → ∞; if the rescaled iterates θ_t/γ_k still match the batch perceptron for all t, the assumption is unnecessary, while if they deviate, the theorem's stated scope fails. A second check: on the paper's lower-bound dataset with n samples, count iterations to perfect accuracy for LR+GD with very large γ and compare with Ω(n); a matching linear dependence supports the claim, and a sublinear count would refute it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical perceptron convergence bound R²/µ² that the γ→∞ reduction inherits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Textbook statement of the perceptron and batch perceptron convergence results used in Theorems 3.3 and 5.2."},{"cited_title":"S.; Gunasekar, S.; and Srebro, N","cited_arxiv_id":null,"evidence_quote":"Establishes the max-margin implicit bias of small-step logistic regression, which the paper contrasts with the perceptron limit."},{"cited_title":"C.; Hinder, O.; and Sidford, A","cited_arxiv_id":null,"evidence_quote":"Establishes optimality of GD for nonconvex problems by gradient norm, the benchmark against which the paper's suboptimality claim is drawn."}],"review_version":1}