{"id":"66ba5598-9f73-4f20-bfee-56b5ded2b0f9","arxiv_id":"1909.01994","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"L-BFGS with line search or trust region is applied to deep learning and deep Q-learning, with convergence theorems that rely on strong convexity and mixed empirical results on MNIST and Atari.","lead":"This chapter applies limited-memory BFGS optimization, a quasi-Newton method, to train deep neural networks for image classification and deep reinforcement learning on Atari games. It reports faster training than stochastic gradient descent on some tasks, but its theoretical convergence proofs assume a strongly convex objective, which deep learning problems are not.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's convergence proof is internally invalid: Eq. (37)–(39) do not follow (the second-order term is mishandled, the contraction factor is never shown to be <1), and Eq.","rationale":"The abstract's headline claim is formal convergence plus robust convergence and fast training time. The empirical sections are suggestive (small CNN on MNIST; six Atari games; code is provided), but the formal component is load-bearing because the paper repeatedly explains superior performance through the convergence properties of L-BFGS. Theorem 4 is the only convergence result for the deep Q-learning method, and its proof is internally inconsistent with Algorithm 4 and algebraically invalid. The mismatch between Eq. (36) and Algorithm 4 is not a matter of interpretation: the algorithm computes stochastic multi-batch gradients and subsampled secant pairs, while the theorem's proof uses one experience and a full-batch-looking gradient. The alleged contraction factor is asserted, not derived, and the exponent in Eq. (33) is wrong. Even the empirical-risk result Theorem 3 is stated under strong convexity, which the paper's own problem (1) is not; its iteration formula also appears to miss a 1/(1−ρ) factor. Because the central proof fails at the point where the theory is supposed to meet the algorithm, the reader's REJECT verdict stands. I do not see this as a disagreement with the field's consensus; it is an internal logical gap.","tokens_in":20216,"tokens_out":9812,"duration_ms":100082,"concrete_test":"Re-derive Theorem 4 line by line using the actual multi-batch estimator of Algorithm 4 (Eqs. 24–27) instead of Eq. (36). In particular, write the full Taylor expansion of Q(w_k−α_k H_k ∇L_k) with ∇L_k equal to the batch average from Eq. (26), and check whether the error term can be factored as in Eq. (38). If the second-order term is quadratic in (Q_k−Q*) or involves averages over J_k and O_k, then Theorem 4 does not apply to Algorithm 4. Also check whether the step-size condition (34) has any solution with contraction modulus μ<1 under the stated eigenvalue bounds; if no α_k exists, the theorem is vacuous.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central 'formal convergence analysis' is not established. The most load-bearing failure is Theorem 4 (Section 6.6). Eq. (36) replaces the multi-batch gradient used in Algorithm 4 with a single-experience approximation ∇L(w_k) ≈ (Q_k−Q*)∇Q_k; no argument connects this approximation to the actual update in Eq. (26), which averages gradients over two batches of size b. Even granting Eq. (36), the Taylor expansion in Eq. (37) is inconsistent: substituting ∇L=(Q_k−Q*)∇Q_k makes the second-order term quadratic in (Q_k−Q*), yet Eq. (38) factors the error linearly as (Q_k−Q*)[1−α∇QᵀH∇Q + (α²/2)∇QᵀH∇²Q H∇L]. The contraction condition in Eqs. (39) and (34) is never shown to have a feasible step size with |·|≤μ<1; the coefficient can exceed 1, and the constants (η, η′, η″) are not used consistently. Eq. (33) also places an exponent k inside the product in a way that does not follow from the recursion. In addition, Theorem 3's bound (30) assumes strong convexity (28a)–(28c), which the paper's own nonconvex ERM problem (1) violates, and iterating Eq. (32) gives an extra factor 1/(1−ρ) not present in Eq. (30). The failure of Theorem 4 alone is sufficient to invalidate the claimed RL convergence.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes limited-memory BFGS (L-BFGS) quasi-Newton methods for training deep neural networks and deep reinforcement learning agents. It presents a trust-region algorithm called TRMinATR for supervised classification, a multi-batch line-search L-BFGS algorithm for deep Q-learning, formal convergence theorems for both settings, and experiments on MNIST with LeNet-5 and on six ATARI 2600 games. The central claims are that these methods converge robustly, generalize better than SGD, and train faster than SGD/DQN while requiring fewer tuned hyperparameters.","tokens_in":20439,"tokens_out":4940,"duration_ms":51733,"significance":"If the convergence analysis were valid, the paper would provide a formal justification for using quasi-Newton methods in deep RL and would strengthen the case for L-BFGS as an alternative to SGD in nonconvex deep learning. The paper also ships code for its experiments, and the empirical comparison between trust-region and line-search L-BFGS on MNIST is clearly described. However, the formal convergence results are the main advertised contribution, and those results are not established: Theorem 3 relies on strong convexity assumptions that contradict the paper's own nonconvex problem formulation, and Theorem 4's proof has internal algebraic and logical gaps. The empirical results, while interesting, are limited to a small set of games and a narrow baseline comparison, so the current contribution is mainly experimental rather than theoretical.","major_comments":[{"comment":"The convergence analysis assumes that the empirical risk L(w) is strongly convex and twice differentiable with globally bounded Hessian eigenvalues and bounded gradients, but the paper's own ERM problem in Eq. (1) and the deep RL loss in Eq. (23) are nonconvex and, for ReLU networks, not twice differentiable. Lemma 1 and Theorem 3 therefore do not apply to the LeNet-5 MNIST experiments in Section 5 or to the ATARI experiments in Section 6.8. No local or regional variant of the assumptions is stated, so the claimed formal convergence for the proposed applications is not established.","section":"Section 6.5, Assumptions (28a)-(28c) and Theorem 3"},{"comment":"The bound in Eq. (30) does not follow from the recursion in Eq. (32). Iterating the inequality δ_{k+1} ≤ (1-2αλλ')δ_k + C with C = α^2Λ'^2Λη^2/(4λ'λ) gives a residual term C(1-(1-2αλλ')^k)/(2αλλ'), which contains an extra factor 1/(2αλλ') compared with the residual shown in Eq. (30). In addition, Theorem 3 assumes a fixed step length α_k, whereas Algorithm 4 computes α_k adaptively by Wolfe conditions; no argument connects the fixed-step analysis to the actual line-search procedure. The claimed linear convergence of Algorithm 4 is therefore not proven.","section":"Section 6.5, Eq. (30) versus Eq. (32)"},{"comment":"Theorem 4's proof replaces the gradient used in Algorithm 4 with a single-experience approximation ∇L(w_k) ≈ (Q_k - Q^*)∇Q_k, but Algorithm 4 computes gradients over the multi-batch sample J_k = O_{k-1} ∪ O_k, each of size b, as specified in Eq. (26). No argument is given that the single-experience approximation is equivalent to, or even stochastically consistent with, the batched update actually implemented. Theorem 4 therefore does not analyze the proposed algorithm.","section":"Section 6.6, Eq. (36) and Algorithm 4"},{"comment":"The Taylor expansion in Eq. (37) and the factorization in Eq. (38) are algebraically inconsistent. Substituting ∇L_k ≈ (Q_k - Q^*)∇Q_k into the second-order term makes that term quadratic in (Q_k - Q^*), yet Eq. (38) factors out only one power of (Q_k - Q^*) and leaves a bracket containing ∇L_k, which itself depends on (Q_k - Q^*). The contraction inequality (34) is asserted but never proved: no feasible range of α_k is shown for which |1 - α_k η''^2 λ + α_k ηη'Λ'^2Λ''/2| < 1, and the constants η, η', η'' are not used consistently across Eqs. (33), (34), and (39). Finally, Eq. (33) places an exponent k on each factor in the product, which does not follow from the recursion in Eq. (40). The proof of Theorem 4 is invalid, and this invalidates the claimed Q-learning convergence.","section":"Section 6.6, Eqs. (37)-(39)"}],"minor_comments":[{"comment":"There are typographical errors such as \"Universiy\" in the affiliations and \"hyperapameters\" in Section 1.2; these should be corrected.","section":"Title page and Section 1.2"},{"comment":"The notation in Eq. (33) is confusing because the upper index k in the product and the exponent k on each factor are not justified by the recursion; the intended expression is likely a product without that exponent.","section":"Eq. (33)"},{"comment":"The caption states that results are shown for different memory parameters m, but the figure panels only display m = 20; the caption should either match the displayed values or additional panels should be included.","section":"Figure 3"},{"comment":"The phrase \"quasi-Newton decent direction\" should be \"quasi-Newton descent direction,\" and the sentence in Section 6.9 that says \"The results are form simulations\" should read \"The results are from simulations.\"","section":"Section 6.8"},{"comment":"The paper reports coefficients of variation across batch sizes and memory sizes but does not provide per-configuration results or statistical significance tests; adding error bars or a table of all configurations would make the robustness claim more transparent.","section":"Section 6.9 and Table 2"}],"recommendation":"reject","confidential_remarks":"The central theoretical contribution is not sound: Theorem 3's assumptions exclude the paper's own target problems, and Theorem 4's proof is internally inconsistent and does not apply to Algorithm 4. Since these theorems are the advertised 'formal convergence analysis,' the manuscript's main claim is unsupported. The empirical portion could potentially be reshaped into a systems-oriented paper without the theoretical claims, but that would require substantial rewriting and new comparisons, which is beyond a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Rafati & Marcia. The useful part is the empirical setup: they take multi-batch L-BFGS with overlap (from Berahas et al.) and run it on deep Q-learning for six Atari games, with code released. That specific combination is new, and the MNIST comparison between line-search and trust-region L-BFGS is clean. The authors also cite their own prior work on TRMinATR and L-BFGS initialization honestly.\n\nThe serious problems are in the theory and in how the empirical claims are framed. Section 6.5 assumes strong convexity of L(w), which the paper's own nonconvex problem (1) contradicts. So Theorem 3's linear convergence bound does not apply to MNIST or Atari. Theorem 4 is worse. The proof swaps in a single-experience gradient (Eq. 36) that does not match the batched update in Algorithm 4, the Taylor expansion in Eq. (37) mis-handles the second-order term, and the contraction factor in (39)/(34) is never shown to be <1. The exponent inside the product in Eq. (33) is also not derived. The stress-test note is on target: Theorem 4 alone invalidates the claimed convergence. This is not a minor gap; it is the central theoretical contribution.\n\nEmpirically, the method scores below the DQN baselines on most games, and the tables omit the Nature 2015 DQN the text references. The training-time savings rest on a cost model with assumed parameters (z=5, f=4) rather than measured DQN time; Table 3 only compares against their own SGD runs. So 'fast training time' and 'preferred generalization' are not established against state-of-the-art.\n\nWhat is genuinely good: the code is public, the multi-batch L-BFGS DQN procedure is described in enough detail to reproduce, and the MNIST experiments are a useful sanity check. There is a kernel of a reproducibility contribution here.\n\nBut the paper overclaims. I would not send this to peer review in its current form. If the venue is willing to accept a heavily revised version with the convergence analysis removed or corrected and with a real DQN baseline in the tables, it could be worth a look. As submitted, I would reject.","headline":"A reproducible empirical chapter on multi-batch L-BFGS for DQN, but the convergence theory is internally invalid and the benchmark comparisons are too weak to support the claims.","tokens_in":21070,"tokens_out":3895,"would_cite":false,"duration_ms":35268,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C53","65K05","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that quasi-Newton L-BFGS optimizers can replace stochastic gradient descent as a practical training method for deep learning and deep reinforcement learning.","keywords":["L-BFGS","quasi-Newton methods","deep learning optimization","deep reinforcement learning","trust-region methods","line search","Q-learning","empirical risk minimization"],"falsifier":"Run Algorithm 4 on one Atari game and log every line-search step: if the Wolfe conditions frequently fail and the step size is pinned at the $\\alpha_k \\ge 0.1$ lower bound, the curvature assumptions behind the contraction argument are not in effect. On the theory side, test the bound in Eq. (30) on $\\ell^2$-regularized logistic regression, where strong convexity holds; if the observed loss offset does not follow the claimed linear contraction, the proof has a gap independent of nonconvexity.","tokens_in":19892,"feed_emoji":"🕹️","tokens_out":8925,"duration_ms":85240,"temperature":0.7,"pith_summary":"This paper sets out to show that quasi-Newton methods, specifically limited-memory BFGS (L-BFGS), can serve as practical alternatives to stochastic gradient descent for training deep neural networks. It proposes a trust-region L-BFGS algorithm (TRMinATR) for supervised learning and a line-search multi-batch L-BFGS algorithm for deep Q-learning, and argues that both converge steadily while avoiding the learning-rate tuning that SGD requires. The paper claims that on MNIST with LeNet-5, L-BFGS matches SGD accuracy with a smaller generalization gap, and on six Atari 2600 games it trains agents in about one to four hours with scores that beat SGD baselines and some policy-gradient methods. A sympathetic reader would care because if the claim holds, curvature-aware optimizers could become drop-in replacements for SGD across deep learning and deep reinforcement learning, reducing sensitivity to step-size selection. The formal analysis is conditional: the convergence theorems assume strong convexity and bounded gradients, which deep-network losses do not satisfy globally.","feed_headline":"L-BFGS trains deep networks and Atari agents with less tuning","feed_subtitle":"Trust-region and line-search L-BFGS train MNIST and six Atari games with less tuning and smaller generalization gaps.","key_machinery":"The load-bearing object is the limited-memory BFGS Hessian approximation $B_k$ and its compact representation $B_k = B_0 + \\Psi_k M_k \\Psi_k^T$, with $B_0 = \\gamma_k I$. The trust-region variant uses the eigendecomposition of this representation to obtain a closed-form solution of the trust-region subproblem via the Sherman-Morrison-Woodbury formula. In the reinforcement learning setting, the central device is the overlap gradient difference $y_k = \\nabla L(w_{k+1})(O_k) - \\nabla L(w_k)(O_k)$, computed on the overlap of consecutive experience batches to produce curvature pairs without extra gradient evaluations. These objects carry the argument by giving each update curvature information at a per-iteration cost linear in the number of parameters.","core_discovery":"The central claim is that second-order information can be obtained cheaply from first-order gradients and used to accelerate deep learning. The paper's L-BFGS methods maintain a positive-definite approximation of the Hessian via low-rank updates from displacement-gradient pairs $(s_k,y_k)$, build a quadratic model of the loss, and choose steps either by Wolfe line search or by solving a trust-region subproblem with a closed-form solution based on a compact representation of the BFGS matrix. For deep Q-learning, the paper introduces a multi-batch line-search L-BFGS update that computes gradient differences on overlapping experience batches, so the curvature pairs are formed without extra gradient evaluations. The paper proves a linear convergence bound for the empirical risk under strong convexity and bounded Hessian and gradient assumptions, and a contraction bound for the Q-function to the optimal value function; empirically it reports reliable convergence, smaller train-test gaps than SGD on MNIST, and competitive Atari scores with much shorter training times than the DQN baseline.","pith_inferences":["The overlap-gradient construction is a general recipe: any stochastic optimizer that forms gradient differences can reuse overlapping batch gradients to estimate curvature, so the idea transfers to other second-order methods and to distributed training.","If the MNIST generalization-gap result extends to larger datasets, curvature-aware search directions themselves, not just lower training loss, may be what narrows the gap, a hypothesis testable on ImageNet-scale training.","The proof's strong-convexity assumption suggests a direct stress test: run the same L-BFGS update on a genuinely nonconvex architecture and check whether the Wolfe conditions still hold; sustained satisfaction would be evidence that the practical regime is wider than the theorem.","A clean theoretical target would be to replace the single-experience gradient approximation in Eq. (36) with the actual batch gradient used in Algorithm 4; a contraction proof for that version would connect the theorem to the experiments."],"forward_implications":["On LeNet-5/MNIST, both L-BFGS variants reach accuracies comparable to SGD while keeping training and test curves close, implying that the learned solutions generalize at least as well as SGD solutions without a learning-rate sweep.","The Wolfe line search and trust-region mechanisms remove the need to hand-tune a learning-rate schedule for the tested problems, reducing the trial-and-error that SGD requires.","The multi-batch L-BFGS Q-learning update can train six Atari agents in roughly one to four hours with only two million interaction steps, outperforming SGD baselines in 11 of 12 runs and beating several published baselines on Space Invaders.","Under the stated convexity and bounded-curvature assumptions, the empirical risk converges linearly to a neighborhood of the minimizer, and the Q-function contracts to the optimal value function, so the algorithm is not merely heuristic within that regime."],"supporting_citations":[{"why":"Supplies the line-search, Wolfe-condition, and trust-region framework the paper builds on, plus the L-BFGS two-loop recursion used in Algorithm 3.","marker":"[18]"},{"why":"Provides the Sherman-Morrison-Woodbury closed-form solution to trust-region subproblems that TRMinATR exploits.","marker":"[20]"},{"why":"Introduces the TRMinATR trust-region L-BFGS algorithm whose empirical results on MNIST the paper extends.","marker":"[26]"},{"why":"Shows how to combine limited-memory quasi-Newton matrices with trust-region subproblems efficiently, supporting the trust-region design.","marker":"[27]"},{"why":"Supplies the deep Q-learning baseline and reference scores used in the Atari comparison table.","marker":"[36]"},{"why":"Supplies the DQN architecture, exploration schedule, and SGD/RMSProp comparison baseline for the deep reinforcement learning experiments.","marker":"[37]"},{"why":"Defines the limited-memory BFGS update whose two-loop recursion and positive-definite matrices are the core optimizer.","marker":"[43]"},{"why":"Provides the compact representation of quasi-Newton matrices used for the eigendecomposition and closed-form subproblem solution.","marker":"[45]"},{"why":"Supplies the multi-batch L-BFGS method and the overlap-gradient technique used to compute $y_k$ in Algorithm 4.","marker":"[50]"},{"why":"Supplies the stochastic quasi-Newton convergence analysis that Lemma 1 and Theorem 3 invoke for bounded Hessian approximations.","marker":"[51]"}],"fun_headline_variants":["L-BFGS quasi-Newton beats SGD on deep nets and Atari","Second-order speed without Hessian: L-BFGS for deep learning","Line-search and trust-region L-BFGS: faster deep learning","Low-rank Hessian approximations train deep nets and Atari faster","Quasi-Newton methods cut tuning for deep learning and RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof assumes the empirical risk is strongly convex with bounded Hessian eigenvalues and bounded gradients, conditions that deep neural network losses do not satisfy; on top of that, the Q-function contraction proof approximates the Q-learning gradient with a single experience even though the algorithm uses batches.","fun_headline_variants_meta":{"raw":{"variants":["L-BFGS quasi-Newton beats SGD on deep nets and Atari","Second-order speed without Hessian: L-BFGS for deep learning","Line-search and trust-region L-BFGS: faster deep learning","Low-rank Hessian approximations train deep nets and Atari faster","Quasi-Newton methods cut tuning for deep learning and RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1427,"prompt_tokens":1056,"completion_tokens":371,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":278}},"tokens_in":672,"tokens_out":371,"duration_ms":3492,"temperature":1.0,"reasoning_tokens":278,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:05:22.740249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 4 on one Atari game and log every line-search step: if the Wolfe conditions frequently fail and the step size is pinned at the $\\alpha_k \\ge 0.1$ lower bound, the curvature assumptions behind the contraction argument are not in effect. On the theory side, test the bound in Eq. (30) on $\\ell^2$-regularized logistic regression, where strong convexity holds; if the observed loss offset does not follow the claimed linear contraction, the proof has a gap independent of nonconvexity.","supporting_citations":[{"cited_title":"Nocedal and S","cited_arxiv_id":null,"evidence_quote":"Supplies the line-search, Wolfe-condition, and trust-region framework the paper builds on, plus the L-BFGS two-loop recursion used in Algorithm 3."},{"cited_title":"Brust, J","cited_arxiv_id":null,"evidence_quote":"Provides the Sherman-Morrison-Woodbury closed-form solution to trust-region subproblems that TRMinATR exploits."},{"cited_title":"Rafati, O","cited_arxiv_id":null,"evidence_quote":"Introduces the TRMinATR trust-region L-BFGS algorithm whose empirical results on MNIST the paper extends."},{"cited_title":"Burdakov, L","cited_arxiv_id":null,"evidence_quote":"Shows how to combine limited-memory quasi-Newton matrices with trust-region subproblems efficiently, supporting the trust-region design."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the DQN architecture, exploration schedule, and SGD/RMSProp comparison baseline for the deep reinforcement learning experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the limited-memory BFGS update whose two-loop recursion and positive-definite matrices are the core optimizer."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the compact representation of quasi-Newton matrices used for the eigendecomposition and closed-form subproblem solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the multi-batch L-BFGS method and the overlap-gradient technique used to compute $y_k$ in Algorithm 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the stochastic quasi-Newton convergence analysis that Lemma 1 and Theorem 3 invoke for bounded Hessian approximations."}],"review_version":1}