class_docstr: Newton solver for GLMs.
  
  This class implements Newton/2nd-order optimization routines for GLMs. Each Newton
  iteration aims at finding the Newton step which is done by the inner solver. With
  Hessian H, gradient g and coefficients coef, one step solves:
  
      H @ coef_newton = -g
  
  For our GLM / LinearModelLoss, we have gradient g and Hessian H:
  
      g = X.T @ loss.gradient + l2_reg_strength * coef
      H = X.T @ diag(loss.hessian) @ X + l2_reg_strength * identity
  
  Backtracking line search updates coef = coef_old + t * coef_newton for some t in
  (0, 1].
  
  This is a base class, actual implementations (child classes) may deviate from the
  above pattern and use structure specific tricks.
  
  Usage pattern:
      - initialize solver: sol = NewtonSolver(...)
      - solve the problem: sol.solve(X, y, sample_weight)
  
  References
  ----------
  - Jorge Nocedal, Stephen J. Wright. (2006) "Numerical Optimization"
    2nd edition
    https://doi.org/10.1007/978-0-387-40065-5
  
  - Stephen P. Boyd, Lieven Vandenberghe. (2004) "Convex Optimization."
    Cambridge University Press, 2004.
    https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
  
  Parameters
  ----------
  coef : ndarray of shape (n_dof,), (n_classes, n_dof) or (n_classes * n_dof,)
      Initial coefficients of a linear model.
      If shape (n_classes * n_dof,), the classes of one feature are contiguous,
      i.e. one reconstructs the 2d-array via
      coef.reshape((n_classes, -1), order="F").
  
  linear_loss : LinearModelLoss
      The loss to be minimized.
  
  l2_reg_strength : float, default=0.0
      L2 regularization strength.
  
  tol : float, default=1e-4
      The optimization problem is solved when each of the following condition is
      fulfilled:
      1. maximum |gradient| <= tol
      2. Newton decrement d: 1/2 * d^2 <= tol
  
  max_iter : int, default=100
      Maximum number of Newton steps allowed.
  
  n_threads : int, default=1
      Number of OpenMP threads to use for the computation of the Hessian and gradient
      of the loss function.
  
  Attributes
  ----------
  coef_old : ndarray of shape coef.shape
      Coefficient of previous iteration.
  
  coef_newton : ndarray of shape coef.shape
      Newton step.
  
  gradient : ndarray of shape coef.shape
      Gradient of the loss w.r.t. the coefficients.
  
  gradient_old : ndarray of shape coef.shape
      Gradient of previous iteration.
  
  loss_value : float
      Value of objective function = loss + penalty.
  
  loss_value_old : float
      Value of objective function of previous itertion.
  
  raw_prediction : ndarray of shape (n_samples,) or (n_samples, n_classes)
  
  converged : bool
      Indicator for convergence of the solver.
  
  iteration : int
      Number of Newton steps, i.e. calls to inner_solve
  
  use_fallback_lbfgs_solve : bool
      If set to True, the solver will resort to call LBFGS to finish the optimisation
      procedure in case of convergence issues.
  
  gradient_times_newton : float
      gradient @ coef_newton, set in inner_solve and used by line_search. If the
      Newton step is a descent direction, this is negative.
docstr: Backtracking line search.
  
  Sets:
      - self.coef_old
      - self.coef
      - self.loss_value_old
      - self.loss_value
      - self.gradient_old
      - self.gradient
      - self.raw_prediction
docstr_tok: ["Backtracking","line","search",".","Sets",":","-","self.coef_old","-","self.coef","-","self.loss_value_old","-","self.loss_value","-","self.gradient_old","-","self.gradient","-","self.raw_prediction"]
code: def line_search(self, X, y, sample_weight):
      """Backtracking line search.
  
      Sets:
          - self.coef_old
          - self.coef
          - self.loss_value_old
          - self.loss_value
          - self.gradient_old
          - self.gradient
          - self.raw_prediction
      """
      # line search parameters
      beta, sigma = 0.5, 0.00048828125  # 1/2, 1/2**11
      eps = 16 * np.finfo(self.loss_value.dtype).eps
      t = 1  # step size
  
      # gradient_times_newton = self.gradient @ self.coef_newton
      # was computed in inner_solve.
      armijo_term = sigma * self.gradient_times_newton
      (
          _,
          _,
          raw_prediction_newton,
      ) = self.linear_loss.weight_intercept_raw(self.coef_newton, X)
  
      self.coef_old = self.coef
      self.loss_value_old = self.loss_value
      self.gradient_old = self.gradient
  
      # np.sum(np.abs(self.gradient_old))
      sum_abs_grad_old = -1
  
      is_verbose = self.verbose >= 2
      if is_verbose:
          print("  Backtracking Line Search")
          print(f"    eps=10 * finfo.eps={eps}")
  
      for i in range(21):  # until and including t = beta**20 ~ 1e-6
          self.coef = self.coef_old + t * self.coef_newton
          raw = self.raw_prediction + t * raw_prediction_newton
          (
              self.loss_value,
              self.gradient,
          ) = self.linear_loss.loss_gradient(
              coef=self.coef,
              X=X,
              y=y,
              sample_weight=sample_weight,
              l2_reg_strength=self.l2_reg_strength,
              n_threads=self.n_threads,
              raw_prediction=raw,
          )
          # Note: If coef_newton is too large, loss_gradient may produce inf values,
          # potentially accompanied by a RuntimeWarning.
          # This case will be captured by the Armijo condition.
  
          # 1. Check Armijo / sufficient decrease condition.
          # The smaller (more negative) the better.
          loss_improvement = self.loss_value - self.loss_value_old
          check = loss_improvement <= t * armijo_term
          if is_verbose:
              print(
                  f"    line search iteration={i+1}, step size={t}\n"
                  f"      check loss improvement <= armijo term: {loss_improvement} "
                  f"<= {t * armijo_term} {check}"
              )
          if check:
              break
          # 2. Deal with relative loss differences around machine precision.
          tiny_loss = np.abs(self.loss_value_old * eps)
          check = np.abs(loss_improvement) <= tiny_loss
          if is_verbose:
              print(
                  "      check loss |improvement| <= eps * |loss_old|:"
                  f" {np.abs(loss_improvement)} <= {tiny_loss} {check}"
              )
          if check:
              if sum_abs_grad_old < 0:
                  sum_abs_grad_old = scipy.linalg.norm(
                      self.gradient_old, ord=1
                  )
              # 2.1 Check sum of absolute gradients as alternative condition.
              sum_abs_grad = scipy.linalg.norm(self.gradient, ord=1)
              check = sum_abs_grad < sum_abs_grad_old
              if is_verbose:
                  print(
                      "      check sum(|gradient|) < sum(|gradient_old|): "
                      f"{sum_abs_grad} < {sum_abs_grad_old} {check}"
                  )
              if check:
                  break
  
          t *= beta
      else:
          warnings.warn(
              (
                  f"Line search of Newton solver {self.__class__.__name__} at"
                  f" iteration #{self.iteration} did no converge after 21 line search"
                  " refinement iterations. It will now resort to lbfgs instead."
              ),
              ConvergenceWarning,
          )
          if self.verbose:
              print(
                  "  Line search did not converge and resorts to lbfgs instead."
              )
          self.use_fallback_lbfgs_solve = True
          return
  
      self.raw_prediction = raw
  
imports: import warnings
  from abc import ABC, abstractmethod
  import numpy
  import scipy.linalg
  import scipy.optimize
  from ..._loss.loss import HalfSquaredError
  from ...exceptions import ConvergenceWarning
  from ...utils.optimize import _check_optimize_result
  from .._linear_loss import LinearModelLoss
label_desc: Use image node_id 6 for calling the NewtonSolver obj's underlying member method code with example usage: obj.line_search(X, y, sample_weight) without return types