  Recent studies have shown that proximal gradient (PG) method and accelerated
gradient method (APG) with restarting can enjoy a linear convergence under a
weaker condition than strong convexity, namely a quadratic growth condition
(QGC). However, the faster convergence of restarting APG method relies on the
potentially unknown constant in QGC to appropriately restart APG, which
restricts its applicability. We address this issue by developing a novel
adaptive gradient converging methods, i.e., leveraging the magnitude of
proximal gradient as a criterion for restart and termination. Our analysis
extends to a much more general condition beyond the QGC, namely the
H\"{o}lderian error bound (HEB) condition. {\it The key technique} for our
development is a novel synthesis of {\it adaptive regularization and a
conditional restarting scheme}, which extends previous work focusing on
strongly convex problems to a much broader family of problems. Furthermore, we
demonstrate that our results have important implication and applications in
machine learning: (i) if the objective function is coercive and semi-algebraic,
PG's convergence speed is essentially $o(\frac{1}{t})$, where $t$ is the total
number of iterations; (ii) if the objective function consists of an $\ell_1$,
$\ell_\infty$, $\ell_{1,\infty}$, or huber norm regularization and a convex
smooth piecewise quadratic loss (e.g., squares loss, squared hinge loss and
huber loss), the proposed algorithm is parameter-free and enjoys a {\it faster
linear convergence} than PG without any other assumptions (e.g., restricted
eigen-value condition). It is notable that our linear convergence results for
the aforementioned problems are global instead of local. To the best of our
knowledge, these improved results are the first shown in this work.
