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

DOI10.1007/S10957-020-01632-XzbMATH Open1436.90154OpenAlexW3006648311MaRDI 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)

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

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)

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.

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

Cites work

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

Cited in

(3)

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

Describes a project that uses

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)