CS Paper Radar

AG-BFGS: Foundations for Accelerated Geometry Learning

Regina Carla Sousa, Denis Vargas, Elizabeth Wanner, Joshua Knowles

cs.LG math.OCcs.NEmath.NA ·submitted 2026-11-18 09:29 UTC · v1
theory

Abstract

We introduce an accelerated geometry-learning framework for BFGS that incorporates momentum into the learning of Hessian inverse approximations. We prove that the resulting accelerated updates satisfy explicit stability conditions and preserve positive definiteness within admissible parameter regions. Numerical experiments demonstrate consistent improvements over the corresponding non-accelerated schemes while maintaining numerical stability. These results provide the first rigorous theoretical foundation for accelerated quasi-Newton learning and bridge the gap between empirical observations and mathematical guarantees for accelerated second-order methods.

Comment
19 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Affine-invariant Cubic Newton with Weak Learners

cs.LG stat.MLmath.OC ·2026-10-24 ·Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon
top venue similarity 0.67
Abstract · Accepted to 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/γ^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $γ^{12}$ dependence on a worst-case `weak gradient edge' $γ$. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overlineΘ_k$ along the optimization path and directional improvements $δ_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $δ_k$. Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overlineΘ_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

0.34

Primal Acceleration of Newton's Method

cs.AI math.OCcs.LG ·2026-08-21 ·Nikita Doikov
similarity 0.64
Abstract

We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.

0.11

A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in $p$-norm geometry

cs.AI math.OCcs.LGstat.ML ·2026-11-03 ·Bowen Li, Danqing Zhou, Chuan He
similarity 0.59
Abstract

Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging ($\text{A}^2$ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on $p$-norm geometry for $p\in[2,\infty]$. The method is line-search-free and employs a new stepsize selection technique based on an aggregated affine lower model. Its update structure is simple and unified across $p\in[2,\infty]$, with the case $p>2$ requiring no more elaborate updates than the Euclidean case $p=2$. Under a generalized local smoothness condition, we derive a convergence bound that separates the effects of constant and gap-dependent curvature, with the latter potentially yielding faster-decaying terms. In the special case of local smoothness, this bound recovers a nearly optimal convergence rate.

0.21

Joint Structure Identification and Newton Acceleration via Proximal Line Search for Nonconvex Optimization

eess.SP ·2026-09-16 ·Yiming Zhou, Wei Dai
theory similarity 0.59
Abstract

We consider composite optimization with a smooth, possibly nonconvex function and a separable convex polyhedral term. Such problems have a simple nonsmooth structure but arise widely in applications. Existing Newton-type methods may fail to identify nonsmooth coordinates during direction computation, move coordinates away from those reached by the full step during line search, or rely on separate first-order steps for identification. In this work, we propose a unified inexact proximal Newton method that couples structure identification with second-order acceleration through a proximal line search designed to retain the nonsmooth structure revealed at the local model. In particular, on a predicted working set, we solve a quadratic model inexactly but enforce its constraints exactly, allowing coordinates to reach new kinks without leaving the selected affine intervals. This set also includes small-margin kink coordinates to exploit the Hessian coupling effect. To globalize the direction, we construct a proximal line search using an isotropic proximal model whose linear term is chosen so that the initial trial exactly recovers the full step. Backtracking increases the proximal curvature until sufficient decrease holds, allowing coordinates to remain at kinks reached by the full step while damping other components. Generating each trial point requires only proximal operator evaluations. We prove finite backtracking and finite active-set identification under strict complementarity and a non-singular reduced Hessian, together with local Q-superlinear convergence under a directional Dennis-More condition and vanishing relative inexactness. Numerical results verify the effectiveness of the proposed method.

0.12

Riemannian Newton Methods with Statistical Inference

cs.LG stat.ML ·2026-10-31 ·Xiaotian Chang, Qirui Hu, Yangdi Jiang, Nan Qiao
similarity 0.57
Abstract

We develop online statistical inference for Polyak-Ruppert averages of inexact Newton iterates on Riemannian manifolds. A local asymptotic representation separates observation noise, solver randomization, and accumulated implementation bias, and yields one-pass covariance estimators and asymptotically valid Wald regions under local regularity and centering conditions. Independent fresh solves add a positive semidefinite term to the score-sandwich covariance; averaging solver replicas reduces this term in inverse proportion to their number. Slowly varying predictable gains instead cancel from the first order law. Product torus simulations show how Newton scaling shortens an ill-conditioned transient and how retaining solver variation restores coverage. Intrinsic means and principal subspaces provide geometric applications, with a streaming data illustration.

0.29

Acceleration and its Limits in Gaussian Variational Inference

cs.LG stat.MLmath.OC ·2026-10-14 ·Jaesung R. Park, Uijeong Jang, Yifan Chen
similarity 0.57
Abstract · 52 pages, 9 figures

We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from $κ$ to $\sqrtκ$ for strongly convex, smooth objectives extends to Gaussian variational inference (GVI) for strongly log-concave, log-smooth target distributions. With exact Gaussian expectations, a convex composite formulation of GVI yields the classical accelerated $\sqrtκ$ convergence rate. However, when only pointwise derivatives are available, we construct a family of strongly log-concave targets for which any randomized algorithm requires $κ^{1-o(1)}$ queries to achieve a fixed objective accuracy, even when the initial objective gap is bounded independently of $κ$. Thus curvature bounds alone cannot guarantee uniform accelerated total-query complexity. We then ask which additional structure permits acceleration and give positive examples: under a Hessian-Lipschitz assumption, variance-reduced stochastic methods yield accelerated guarantees when the Hessian variation is sufficiently small. Finally, experiments on real datasets show substantial empirical speedups from acceleration across a broad range of methods.

0.18

Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity

cs.LG math.OC ·2026-10-19 ·Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang
similarity 0.57
Abstract

Bilevel optimization provides a framework for machine learning tasks such as hyperparameter optimization, data reweighting, and meta-learning. Existing Newton-based bilevel methods typically rely on the classical hypergradient formula, which is generally unavailable when lower-level solutions are nonunique and the lower-level Hessian is singular. We develop two Newton-based methods beyond lower-level strong convexity by exploiting curvature shared by the lower-level and multiplier updates. Newton-based GALET handles potentially singular lower-level curvature under a positive spectral-gap condition, exploiting its range structure to avoid the squared-Hessian multiplier system used in GALET. Newton-based BAMM uses a strongly convex aggregation model when the lower-level objective is convex and the upper-level objective is strongly convex in the lower-level variable. We establish convergence guarantees and improved complexity bounds relative to GALET and sl-BAMM under the corresponding assumptions. We further introduce GNBO, a generalized Newton-based framework that captures the shared-curvature structure of the proposed methods and several existing Newton and quasi-Newton bilevel methods. Experiments on synthetic problems, data hyper-cleaning, and GPT-2 data reweighting evaluate the proposed methods across different bilevel learning tasks.

0.07

dOPT: Differentiating Conic Optimization via Geometric Reduction

cs.LG math.OC ·2026-09-27 ·Fengyu Yang, Connor W. Magoon, Tyler Watts, Shahar Z. Kovalsky
similarity 0.56
Abstract

Optimization layers enable the incorporation of structured constraints and decision problems into learning systems. Training such systems requires differentiating through the embedded optimization problem, which can be challenging for general conic programs. We introduce dOPT, a solver-agnostic framework that, rather than differentiating the full conic formulation, reduces it at a computed primal-dual solution to an equality-constrained quadratic program that preserves the reference solution and its first-order sensitivity. The reduction captures the local first- and second-order conic geometry relevant to differentiation and remains well defined at singular configurations. Computing solution derivatives then requires a single symmetric linear solve, independently of the forward solver. We derive explicit reductions for convex NLPs, QPs, SOCPs, and SDPs. Numerical experiments validate the computed gradients and show favorable backward-pass scalability, with substantial speedups over existing differentiable conic optimization methods as problem size increases.

0.27