betaFeedback

WorksMathematics

Limited-Memory First-Order Methods: Identification, Reconstruction, HH-Duality and Application to Optimized Methods

Abstract

In general, linear-span first-order methods add at every iteration a combination of all observed gradients to the previous iterate. However, many methods of interest can be implemented in a way that requires storing only a few auxiliary vectors, instead of all past gradients. We call such methods limited-memory first-order methods. A given fixed-coefficient first-order method can be described by a lower triangular coefficient matrix, which expresses each step as a combination of previous gradients. We show that the minimum number of running sums required to implement a method is equal to the minimum rank of a completion of the strict lower triangular part of its coefficient matrix, and propose a reconstruction algorithm. Moreover, taking the HH-dual of a method, which reflects the coefficient matrix across its anti-diagonal, preserves its memory and translates into a permutation and time-reversal on the coefficients of the running sum recurrences. We apply our results to two optimized first-order methods for smooth strongly convex functions. First, our reconstruction applied to a method numerically designed by Shu and Wang reveals a recurrence with one auxiliary vector, which is related to the Triple Momentum Method (TMM) of Van Scoy, Freeman and Lynch with a particular initialization. We prove that the reconstructed method, called TMM-GD, is minimax optimal at every horizon for the final distance to the minimizer relative to the initial gradient norm. Second, the Information-Theoretic Exact Method (ITEM) of Taylor and Drori, optimal for the final distance relative to the initial one, is known to be memory one. We give an explicit recurrence with one auxiliary vector for its HH-dual, called ITEM-GG, and prove that ITEM-GG is the unique minimax optimal nonadaptive linear-span method for the final gradient norm relative to the initial one.

Paper details

vlnc:W_fmfwh8qf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…