Adaptive proximal gradient methods are universal without approximation
Konstantinos A. Oikonomidis Emanuel Laude Puya Latafat Andreas Themelis Panagiotis Patrinos
We show that adaptive proximal gradient methods for convex problems are not
restricted to traditional Lipschitzian assumptions. Our analysis reveals that a
class of linesearch-free methods is still convergent under mere local H\"older
gradient continuity, covering in particular continuously differentiable
semi-algebraic functions. To mitigate the lack of local Lipschitz continuity,
popular approaches revolve around $\varepsilon$-oracles and/or linesearch
procedures. In contrast, we exploit plain H\"older inequalities not entailing
any approximation, all while retaining the linesearch-free nature of adaptive
schemes. Furthermore, we prove full sequence convergence without prior
knowledge of local H\"older constants nor of the order of H\"older continuity.
In numerical experiments we present comparisons to baseline methods on diverse
tasks from machine learning covering both the locally and the globally H\"older
setting.