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

We propose a new method to accelerate the convergence of optimization algorithms. This method, termed Powerball method , simply adds a power coefficient <tex-math notation="LaTeX">γ ∈ [0,1 </tex-math> ) 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 <tex-math notation="LaTeX">p </tex-math> -norm, where <tex-math notation="LaTeX">p=1+(1/γ ) </tex-math> . 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.