Home / Curated / Algorithms / K-BFGS and K-BFGS(L) (Kronecker-Factored Quasi-Newton Optimization)

K-BFGS and K-BFGS(L) (Kronecker-Factored Quasi-Newton Optimization)

Algorithms AIMech:KBfgsKroneckerFactoredQuasiNewtonOptimization DRAFT

Aliases: K-BFGS, K-BFGS(L), Kronecker-Factored Block-Diagonal BFGS, Kronecker-Factored Quasi-Newton Method for Deep Neural Networks

A stochastic Kronecker-factored quasi-Newton optimization method for deep neural networks that approximates each layer's block-diagonal inverse Hessian as the Kronecker product H_l = H_a^l (x) H_g^l of an inverse input-activation second-moment factor H_a^l and an inverse pre-activation Hessian factor H_g^l, updating H_g^l via BFGS (in K-BFGS) or non-loop limited-memory L-BFGS (in K-BFGS(L)) with a two-stage Powell Double Damping (DD) procedure on layer pre-activation secant pairs and updating H_a^l via Levenberg-Marquardt damped Hessian-action BFGS without cubic matrix inversions.

Identity Notes & Concept Scope Distinct from K-FAC (AIMech:KfacKroneckerFactoredApproximateCurvature), which approximates the Fisher information matrix using outer products of backpropagated predictive-distribution gradients and requires explicit O(d_i^3 + d_o^3) matrix inversions every T steps; K-BFGS and K-BFGS(L) approximate the true layerwise Hessian inverse via secant updates on pre-activation changes s_g^l = E[h_l^+ - h_l] and gradient changes y_g^l = E[g_l^+ - g_l] and require only O(d_i^2 + d_o^2) matrix-vector and matrix-matrix multiplications. Distinct from standard L-BFGS (AIMech:LimitedMemoryBfgsOptimization), which operates on the unfactored n-dimensional parameter vector rather than layerwise Kronecker factors.

Claims & Grounded Evidence

5 Claims

Mechanism #kbfgs-powell-double-damping-preactivation-secant-mechanism

To maintain positive definiteness and bounded eigenvalues of the inverse pre-activation Hessian approximation H_g^l under non-convex indefinite curvature without line search, Algorithm 3 (Double Damping) applies two sequential Powell damping steps to the moving-average pre-activation secant pair (s_g^l, y_g^l): first interpolating s_tilde = theta_1 * s + (1 - theta_1) * H * y so s_tilde^T y >= mu_1 * y^T H y, and second interpolating y_tilde = theta_2 * y + (1 - theta_2) * s_tilde with B = I so s_tilde^T y_tilde >= mu_2 * ||s_tilde||^2.

supports Source: Practical Quasi-Newton Methods for Training Deep Neural Networks · Locator: Section 3 Equations (6)-(10), Algorithm 3, and Appendix C, pages 4-5, 15

Mechanism #kbfgs-hessian-action-bfgs-sherman-morrison-theorem1-mechanism

Theorem 1 proves that for positive-definite A and H = A^{-1}, updating H via any Broyden-family quasi-Newton formula with the Hessian-action secant pair s = H a and y = A^+ s for A^+ = A + c a a^T (c > 0) produces the exact Sherman-Morrison inverse (A^+)^{-1}; K-BFGS applies this update to the Levenberg-Marquardt damped input-activation covariance A_l^LM = A_l + lambda_A I_A using s_a^l = H_a^l bar{a}_{l-1} and y_a^l = A_l^LM s_a^l.

supports Source: Practical Quasi-Newton Methods for Training Deep Neural Networks · Locator: Section 4 Equation (11), Theorem 1, and Appendix A Algorithm 4 lines 18-22, pages 5-6, 12

Scope #kbfgs-nonconvex-stochastic-convergence-rate-scope

Under L-Lipschitz gradients, bounded stochastic gradient variance sigma^2, and bounded activations |phi_l(h)| <= varphi (Assumptions AS.1-AS.3), Lemmas 1-3 and Theorem 2 prove that the Kronecker-factored inverse Hessian approximations H_k remain uniformly bounded above and below by positive-definite matrices (underline{kappa} I <= H_k <= bar{kappa} I) and achieve (1/N) sum_{k=1}^N E[||grad f(theta_k)||^2] < epsilon in at most O(epsilon^{-1/(1-beta)}) iterations for step sizes alpha_k propto k^{-beta} with beta in (0.5, 1).

supports Source: Practical Quasi-Newton Methods for Training Deep Neural Networks · Locator: Section 5 Lemmas 1-3, Theorem 2, and Appendix B, pages 6, 12-14

Application #kbfgs-deep-autoencoder-benchmark-application

On 9-layer and 13-layer ReLU deep autoencoder benchmarks (MNIST, FACES, and CURVES) at mini-batch sizes m = 1000 and m = 100, K-BFGS and K-BFGS(L) substantially outperform Adam, RMSprop, and SGD with momentum in both training loss and test reconstruction error while performing comparably to or better than K-FAC without cubic matrix inversions.

supports Source: Practical Quasi-Newton Methods for Training Deep Neural Networks · Locator: Section 6 Tables 1-2, Figure 1, and Appendix D.5 Figures 4-6, pages 7-9, 19-22

Limitation #kbfgs-second-forward-backward-pass-per-step-limitation

Computing the pre-activation secant differences s_g^l = E[h_l^+(i) - h_l(i)] and y_g^l = E[g_l^+(i) - g_l(i)] after updating W_l requires an additional forward-backward pass over the current mini-batch M_k at each curvature update step, doubling the per-step propagation cost.

supports Source: Practical Quasi-Newton Methods for Training Deep Neural Networks · Locator: Section 2 Algorithm 2 line 5 and Section 6 Table 2, pages 4, 7

⚠️ Curated Limitations & Negative Results

Requires a second forward-backward pass over the current mini-batch at each curvature update to evaluate the post-step pre-activation vectors h_l^+ and pre-activation gradients g_l^+.
The theoretical non-convex convergence proof (Theorem 2) requires bounded activation functions (Assumption AS.3) and skipping updates when the post-damping curvature ratio exceeds 1/mu_1.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:ArtificialNeuralNetwork` Artificial Neural Network	related_match	K-BFGS and K-BFGS(L) are layerwise Kronecker-factored quasi-Newton optimization algorithms designed for training deep neural networks.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r644-primary-pdf`	Practical Quasi-Newton Methods for Training Deep Neural Networks Donald Goldfarb, Yi Ren, Achraf Bahamou	primary paper full_text	ID: https://dblp.org/rec/conf/nips/GoldfarbRB20 sha256:36c538ec4bd5…
`r644-arxiv-abs`	Practical Quasi-Newton Methods for Training Deep Neural Networks (arXiv abstract) Donald Goldfarb, Yi Ren, Achraf Bahamou	primary paper abstract_only	ID: https://arxiv.org/abs/2006.08877 sha256:9976f202923d…
`r644-metadata-cr`	Practical Quasi-Newton Methods for Training Deep Neural Networks (Crossref metadata) Donald Goldfarb, Yi Ren, Achraf Bahamou	primary paper abstract_only	ID: https://dblp.org/rec/conf/nips/GoldfarbRB20 sha256:91ab42a05da6…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T12:07:00Z

Updated: 2026-10-19T12:07:00Z

Source File: data/curated/KBfgsKroneckerFactoredQuasiNewtonOptimization.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories