An hybrid stochastic Newton algorithm for logistic regression

• URL: http://arxiv.org/abs/2512.01790v1
• Date: Mon, 01 Dec 2025 15:27:40 GMT
• Title: An hybrid stochastic Newton algorithm for logistic regression
• Authors: Bernard Bercu, Luis Fredes, Eméric Gbaguidi,
• Abstract summary: We make use of a new hybrid Newton algorithm that includes two weighted components in the Hessian matrix estimation.<n>We show a surprising result on the almost sure convergence of the cumulative excess risk.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate a second-order stochastic algorithm for solving large-scale binary classification problems. We propose to make use of a new hybrid stochastic Newton algorithm that includes two weighted components in the Hessian matrix estimation: the first one coming from the natural Hessian estimate and the second associated with the stochastic gradient information. Our motivation comes from the fact that both parts evaluated at the true parameter of logistic regression, are equal to the Hessian matrix. This new formulation has several advantages and it enables us to prove the almost sure convergence of our stochastic algorithm to the true parameter. Moreover, we significantly improve the almost sure rate of convergence to the Hessian matrix. Furthermore, we establish the central limit theorem for our hybrid stochastic Newton algorithm. Finally, we show a surprising result on the almost sure convergence of the cumulative excess risk.

Related papers

• Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
  We analyze two classical algorithms for solving additively composite convex optimization problems.<n>We focus on the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates.<n>Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.
  arXiv  Detail & Related papers  (2026-02-05T09:50:06Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods [37.1630298053787]
  We propose a new framework, which we call the helper framework.<n>It provides a unified view of the variance and second-order algorithms equipped with global complexity guarantees.
  arXiv  Detail & Related papers  (2023-02-23T12:18:28Z)
• Robust empirical risk minimization via Newton's method [9.797319790710711]
  A new variant of Newton's method for empirical risk minimization is studied. The gradient and Hessian of the objective function are replaced by robust estimators. An algorithm for obtaining robust Newton directions based on the conjugate gradient method is also proposed.
  arXiv  Detail & Related papers  (2023-01-30T18:54:54Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization [20.189732632410024]
  The quasi-Newton method provides curvature information by approximating the Hessian using the secant equation. We propose an approximate Newton step-based DP optimization algorithm for large-scale empirical risk of convex functions with linear convergence rates.
  arXiv  Detail & Related papers  (2021-10-16T14:04:51Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
  We focus on the class of Hamiltonian methods and provide the first convergence guarantees for certain classes of smooth games. Using tools from the optimization literature we show that SHGD converges linearly to the neighbourhood of a gradient. Our results provide the first global non-asymotic last-rate convergence guarantees for the class of general games.
  arXiv  Detail & Related papers  (2020-07-08T15:42:13Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  Community detection in graphs that are generated according to symmetric block models (SBMs) has received much attention lately. We show that in the logarithmic sparsity regime of the problem, with high probability the proposed two-stage method can exactly recover the two communities down to the information-theoretic limit in $mathcalO(nlog2n/loglog n)$ time. We also conduct numerical experiments on both synthetic and real data sets to demonstrate the efficacy of our proposed method and complement our theoretical development.
  arXiv  Detail & Related papers  (2020-06-29T07:03:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.