Reference · Algorithm guarantees

rainbow.algorithms.proofs.newton

Algorithm guaranteessrc/rainbow/algorithms/proofs/newton.clj1 definitions, 1 theorems

Newton's method as the general descent skeleton with a Hessian-inverse step size. Where gradient descent uses a fixed rate, Newton scales the step by the reciprocal of the second derivative: the step size at a point is `1 / hessian(point)`, computed with exact rational division. On a quadratic objective this makes Newton reach the minimum in a single step (AHoF O26). Only the step-size function is new; the descent loop is the O13 skeleton. Scope (measured by the kernel): this module has 1 definitional unfoldings (true by unfolding a definition). None of its theorems is a guarantee about the algorithm for all inputs; `lein verify rainbow.algorithms.proofs.newton` prints this classification.

optimization/newton-rate :
  (hessian : ℚ → ℚ≥0) (point : ℚ)
  → ℚ≥0

optimization/newton-rate-unfold :
  (hessian : ℚ → ℚ≥0) (point : ℚ)
  → optimization/newton-rate hessian point = nnrat/reciprocal (hessian point)