On the quality of first-order approximation of functions with Hölder continuous gradient

DOI10.1007/S10957-020-01632-XzbMATH Open1436.90154arXiv2001.07946OpenAlexW3006648311MaRDI QIDQ1985266FDOQ1985266

Authors: Guillaume O. Berger, Raphaël M. Jungers, Yuri Nesterov, P.-A. Absil 

Publication date: 7 April 2020

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: We show that H"older continuity of the gradient is not only a sufficient condition, but also a necessary condition for the existence of a global upper bound on the error of the first-order Taylor approximation. We also relate this global upper bound to the H"older constant of the gradient. This relation is expressed as an interval, depending on the H"older constant, in which the error of the first-order Taylor approximation is guaranteed to be. We show that, for the Lipschitz continuous case, the interval cannot be reduced. An application to the norms of quadratic forms is proposed, which allows us to derive a novel characterization of Euclidean norms.

Full work available at URL: https://arxiv.org/abs/2001.07946

Recommendations

• Hölder continuity of the policy function approximation in the value function approximation
• On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
• Some remarks on Hölder approximation by Bernstein polynomials
• scientific article; zbMATH DE number 1098561
• On the Hölder semi-norm of the remainder in polynomial approximation

zbMATH Keywords

gradientTaylor approximationglobal upper boundHölder continuity

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Programming in abstract spaces (90C48)

Cites Work

• Gradient methods for minimizing composite functions
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Characterizations of inner product spaces
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Universal gradient methods for convex optimization problems
• Traces and Emergence of Nonlinear Programming
• On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
• Ellipsoids of maximal volume in convex bodies
• Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients
• Global rates of convergence for nonconvex optimization on manifolds

Cited In (3)

• The backtrack Hölder gradient method with application to min-max and min-min problems
• Functions on a convex set which are both $\omega$-semiconvex and $\omega$-semiconcave
• Linearly approximatable functions

Uses Software

• NESUN

This page was built for publication: On the quality of first-order approximation of functions with Hölder continuous gradient

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1985266)