A Scale-Shape Dual Newton Method for Entropic Least Squares
This work provides a robust and efficient solver for entropy-regularized least-squares, a problem arising in various applications, with theoretical guarantees and practical improvements over existing methods.
The paper introduces a damped inexact Newton method for entropy-regularized least-squares that achieves global linear convergence with O(log ε^{-1}) iteration complexity and local superlinear-to-quadratic convergence, while avoiding finite-precision overflow issues. Experiments on quantum Monte Carlo data confirm overflow resilience and convergence behavior.
We give a damped inexact Newton method for entropy-regularized least-squares on the nonnegative orthant that converges globally at a linear rate with $O(\logε^{-1})$ iteration complexity, locally at a superlinear-to-quadratic rate, and is immune to the finite-precision overflow that limits classical dual solvers. A scale-shape decomposition of the primal -- separating its scale from its direction -- produces a dual with a nonsingular Jacobian. Objectives and Jacobians are evaluated through stable log-sum-exp and softmax primitives. Lambert W bounds on the scale uniformly control the Jacobian's spectrum, from which both rates follow. The solution map is jointly Lipschitz in the data, regularization parameter, and reference measure, and extends continuously to the vanishing-regularization limit. Experiments on a problem from analytic continuation of quantum Monte Carlo data confirm the predicted overflow resilience and convergence behavior.