Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
A general proof framework is provided that explicitly quantifies the memory cost of acceleration---how much offline memory is required to achieve a prescribed speedup over the unaided online optimizer---and identifies two key quantities driving this cost: the convergence rate of the online optimizer and the Lipschitz s...