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

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 $H$-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 $H$-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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21611
Primary Topic
Stochastic Gradient Optimization Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Pierre Vernimmen, Adrien Taylor, François Glineur, Baptiste Goujaud
arXiv (Cornell University)
Stochastic Gradient Optimization Techniques
preprint

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

Pierre Vernimmen, Adrien Taylor, François Glineur, Baptiste Goujaud
preprint en

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 $H$-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 $H$-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.

arXiv (Cornell University)
Stochastic Gradient Optimization Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon