2022/12/22 by M. J. V. Streeter, Joshua V. Dillon, Streeter, Matthew +1 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2212.11429
openalex publication_date 2022/12/22 · openalex created_date 2023/01/04 · openalex updated_date 2026/07/28
We present a new algorithm for automatically bounding the Taylor remainder series. In the special case of a scalar function f: ℝ → ℝ, our algorithm takes as input a reference point x0, trust region [a, b], and integer k ≥ 1, and returns an interval I such that f(x) - ∑i=0k-1 \frac 1 i! f(i)(x0) (x - x0)i ∈ I (x - x0)k for all x ∈ [a, b]. As in automatic differentiation, the function f is provided to the algorithm in symbolic form, and must be composed of known atomic functions. At a high level, our algorithm has two steps. First, for a variety of commonly-used elementary functions (e.g., exp, log), we use recently-developed theory to derive sharp polynomial upper and lower bounds on the Taylor remainder series. We then recursively combine the bounds for the elementary functions using an interval arithmetic variant of Taylor-mode automatic differentiation. Our algorithm can make efficient use of machine learning hardware accelerators, and we provide an open source implementation in JAX. We then turn our attention to applications. Most notably, in a companion paper we use our new machinery to create the first universal majorization-minimization optimization algorithms: algorithms that iteratively minimize an arbitrary loss using a majorizer that is derived automatically, rather than by hand. We also show that our automatically-derived bounds can be used for verified global optimization and numerical integration, and to prove sharper versions of Jensen's inequality.