Memory-length conjecture for tight IQC convergence rates

Let a first-order algorithm have TT steps of memory. For each integer n1n\geq 1, an off-by-nn pointwise IQC is the quadratic constraint associated with a pair of iterates (ykn,yk)(y_{k-n},y_k). Consider the semidefinite program governing the convergence-rate bound obtained from the IQC framework. Memory-length conjecture. For first-order algorithms with TT steps of memory, off-by-nn pointwise IQCs with nTn\leq T suffice to obtain the tightest convergence rate in this framework; adding off-by-nn pointwise IQCs with n>Tn>T 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-nn 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.