Memory-length conjecture for tight IQC convergence rates

At least 5 years old · documented by

Let a first-order algorithm have TT steps of memory. For each integer n≥1n\geq 1, an off-by-nn pointwise IQC is the quadratic constraint associated with a pair of iterates (yk−n,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 n≤Tn\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.

References

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.