Memory-length conjecture for tight IQC convergence rates
Memory-length conjecture for tight IQC convergence rates
Let a first-order algorithm have steps of memory. For each integer , an off-by- pointwise IQC is the quadratic constraint associated with a pair of iterates . Consider the semidefinite program governing the convergence-rate bound obtained from the IQC framework. Memory-length conjecture. For first-order algorithms with steps of memory, off-by- pointwise IQCs with suffice to obtain the tightest convergence rate in this framework; adding off-by- pointwise IQCs with to the semidefinite program does not improve the bound. The conjecture is motivated by numerical simulations, while the preceding discussion notes that all off-by- IQCs need not exactly characterize the underlying nonlinearity. It remains open whether the stated cutoff at the memory length holds for the algorithms covered by the framework.
Sources & referencesView supporting material
Primary source
Guodong Zhang, Xuchan Bao, Laurent Lessard and Roger Grosse, “A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints”, arXiv:2009.11359 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.