On the Powerball Method: Variants of Descent Methods for Accelerated Optimization

Abstract

We propose a new method to accelerate the convergence of optimization algorithms. This method, termed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Powerball method</i> , simply adds a power coefficient <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma \in [0{,}1$ </tex-math></inline-formula> ) to the gradient used in various gradient-based optimization schemes. In its essence, the Powerball method can be regarded as the steepest gradient descent with respect to the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> -norm, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p=1+{(}{1}/{\gamma }{)}$ </tex-math></inline-formula> . As a motivation, we first present the continuous-time models of the proposed optimization schemes and analyze their finite-time convergence properties. We then develop several variants of the Powerball method that empirically outperform the standard descent methods, especially during the initial iterations. On multiple real datasets, we demonstrate that the proposed methods can provide a tenfold speedup of the convergence of both (stochastic) gradient descent and limited-memory Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) methods.