An hybrid stochastic Newton algorithm for logistic regression
Bernard Bercu, Luis Fredes, Eméric Gbaguidi · 2025
Read An hybrid stochastic Newton algorithm for logistic regression by Bernard Bercu, Luis Fredes, Eméric Gbaguidi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01790.txt.
Introduction
Bernard Bercu, Luis Fredes, and Emeric Gbaguidi build a hybrid stochastic Newton method for logistic regression. Large-scale binary classification needs second-order speed. Pure Newton steps are too costly on big data. Stochastic gradients are cheap but noisy.
Their Hessian estimate blends two weighted parts. One part is the natural Hessian estimate. The other comes from stochastic gradient data. Blending aims for Newton-like speed at stochastic cost. Fast logistic fits serve fraud, medical, and recommendation systems with huge row counts. Logistic models sit inside credit and health scoring, so a faster second-order fit shortens the loop for testing fairness across groups.
Catalog record
| CREATOR | Bernard Bercu, Luis Fredes, Eméric Gbaguidi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01790
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An hybrid stochastic Newton algorithm for logistic regression Bernard Bercu, Luis Fredes, Eméric Gbaguidi 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. keywords [class=MSC] 49M15, 68W27, 62J12, 60B10, 60F05 keywords Stochastic optimization; stochastic Newton algorithm; logistic regression; almost sure convergence; central limit theorem , and ?? Institut de Mathématiques de Bordeaux, Université de Bordeaux , ?? ; ?? ?? 1 Introduction Our goal is to investigate the standard stochastic optimization problem in \mathds{R}^{d} \min_{h\in\mathds{R}^{d}}G(h), ( \mathcal{P} ) where G(h)=\mathds{E}[g(\Phi,Y,h)]. (1) In what follows, we focus our attention on the well-known logistic regression [ 1 , 3 , 6 ] . For that purpose, we introduce a sequence (\Phi_{n},Y_{n}) of random vectors taking values in \mathds{R}^{d}\times\{0,1\} . Furthermore, we assume that (\Phi_{n}) is a sequence of independent and identically distributed random vectors such that for all n\geqslant 1 , the conditional distribution of Y_{n} is a Bernoulli distribution given by \mathcal{L}(Y_{n}\lvert\Phi_{n})=\mathcal{B}(\pi(\theta^{T}\Phi_{n})),\qquad\text{where}\qquad\pi(x)=\dfrac{e^{x}}{1+e^{x}}, and \theta is the unknown parameter belonging to \mathds{R}^{d} of the logistic regression. Denote by G the convex function given, for all h\in\mathds{R}^{d} , by G(h)=\mathds{E}\left[\log\Big(1+\exp(h^{T}\Phi)\Big)-h^{T}\Phi Y\right], (2) where \mathcal{L}(Y\lvert\Phi)=\mathcal{B}(\pi(\theta^{T}\Phi)) and \Phi shares the same distribution as the sequence (\Phi_{n}) . The gradient and Hessian matrix of G are respectively given by \nabla G(h)=\mathds{E}\left[(\pi(h^{T}\Phi)-Y)\Phi\right], (3) and \nabla^{2}G(h)=\mathds{E}\Big[\pi(h^{T}\Phi)\big(1-\pi(h^{T}\Phi)\big)\Phi\Phi^{T}\Big]. (4) Hence, our goal is to find the unique solution of ( P ) which satisfies \nabla G(\theta)=0 . One can observe that \mathds{E}[Y\lvert\Phi]=\pi(\theta^{T}\Phi) and \displaystyle\Sigma(\theta)=\mathds{E}\left[\Big(\pi(\theta^{T}\Phi)-Y\Big)^{2}\Phi\Phi^{T}\right] \displaystyle=\mathds{E}\left[\mathds{E}\Big[\Big(\pi(\theta^{T}\Phi)-Y\Big)^{2}\Big\lvert\Phi\Big]\Phi\Phi^{T}\right] \displaystyle=\mathds{E}\Big[\pi(\theta^{T}\Phi)\big(1-\pi(\theta^{T}\Phi)\big)\Phi\Phi^{T}\Big] \displaystyle=\nabla^{2}G(\theta). (5) This simple calculation highlights our motivation to propose our hybrid stochastic Newton algorithm defined in Section 2 . Several methods have been investigated in order to find \theta such as the stochastic gradient descent and second-order algorithms [ 3 , 12 , 18 , 19 , 20 ] . Here, we shall focus our attention on the family of stochastic Newton algorithms. These methods are more able to deal with the problem where the Hessian matrix of the objective function has eigenvalues with significantly different values. A truncated version of the standard stochastic Newton algorithm has been proposed in [ 3 ] . This truncation was necessary to ensure the convergence of the algorithm but it significantly reduces the rate of convergence to the Hessian matrix. We also refer the reader to [ 6 , 9 , 11 ] for other references on truncated stochastic Newton algorithms. In this paper, we will avoid any truncation in our hybrid stochastic Newton algorithm. We highlight that in [ 3 ] , the inverse of the Hessian matrix estimation is updated recursively by using the Sherman-Morrison-Woodbury inversion formula [ 14 ] . This tool avoids the inversion of large matrix at each iteration. More recently, a weighted averaged version of the stochastic Newton algorithm was proposed in [ 6 ] for more general problems including the case of linear, logistic, and softmax regressions. The almost sure convergence of the iterates to the optimum and their rates of convergence as well as a central limit theorem have been established in [ 6 ] . As mentioned before, the same truncated version of stochastic Newton algorithm as [ 3 ] has been maintained in [ 6 ] for the specific case of logistic regression. Godichon-Baggioni et al. [ 11 ] focused on the recursive estimation technique for the inverse of the Hessian matrix using a Robbins-Monro procedure and considered a weighted averaged version to further enhance the rates of convergence. However, we will significantly improve their rates with our hybrid stochastic Newton algorithm. Bach [ 1 ] borrowed tools from self-concordance to analyze the statistical properties of logistic regression estimate and established some oracle inequalities on the excess risk based on concentration inequalities for U-statistics. For their part, De Vilmarest and Wintenberger [ 9 ] provided explicit bounds with high probability on this convergence for the same truncated stochastic Newton algorithm named there the static extended Kalman filter in the logistic regression case. They derived local bounds on the cumulative excess risk with high probability via a matrix concentration inequality. However, the result are proved under a strong convergence assumption which is that with high probability, there exists a convergence time after which the algorithm stays trapped in a local region around the optimum. Another variants of the stochastic Newton algorithm have been investigated to address large-scale applications [ 7 , 17 , 23 , 25 ] . For example, Kovalev et al. [ 16 ] proposed the stochastic cubic Newton algorithm which combines cubic regularization with the stochastic Newton technique for minimizing the average of a very large number of sufficiently smooth and strongly convex functions. Furthermore, in the deterministic case, Hazan [ 13 ] introduced the online Newton step which is also known as a quasi-Newton method or Gauss-Newton algorithm [ 2 , 8 , 22 ] . However, strictly speaking, this algorithm is first order, in the sense that it only uses gradient information. Next, Hazan [ 13 ] provided the logarithmic regret guarantee of the online Newton step algorithm for exp-concave functions. Recently, Wintenberger [ 24 ] showed that the stochastic online Newton step algorithm achieves fast-rate stochastic regrets under the stochastically exp-concave assumption. Moreover, Yousefian et al. [ 26 ] studied an iterative regularized stochastic quasi-Newton method for the regularized problems with nonstrongly convex objective functions and Lipschitz continuous gradient. They showed the almost sure convergence of this scheme towards the optimal value of the problem under the bounded variance hypothesis. In what follows, we highlight our main contributions. On the one hand, we introduce our new hybrid stochastic Newton algorithm motivated by ( 5 ). Our parametric approach incorporates two components in the Hessian matrix estimation: one from the natural Hessian estimate and the second from the stochastic gradient information. This helps to establish many convergence guarantees while avoiding the useless introduction of truncation as it was done in the previous literature. On the other hand, beyond the results of almost sure convergence, we have significantly improved the rate of convergence to the Hessian matrix compared to the current state of art. Lastly, we establish the central limit theorem for our hybrid stochastic Newton algorithm. The rest of the paper is organized as follows. In Section 2 , we describe our iterative hybrid stochastic Newton algorithm. Section 3 deals with our main results. We prove the almost sure convergence of our algorithm in Theorem 3.1 . Hereafter, we provide in Theorem 3.2 , the