Understanding Memory-Computation Tradeoffs in Amortized Optimization

Learning-enabled decision systems often utilize offline data or computation to reduce the computational burden during online operations. Despite the empirical success of these strategies, there's a limited general understanding of how much offline information is truly necessary to achieve a specific accuracy level within a given online computation budget. This study investigates this fundamental question through the lens of amortized parametric optimization. In this framework, an offline phase involves storing a finite memory of previously solved problem instances. During the online phase, a solution to a new problem instance is generated by retrieving a "warm start" from this memory and then applying a fixed number of steps (K) of projected gradient descent. The research analyzes this setup for smooth convex parametric optimization over a compact domain. For objectives that are strongly convex, the study establishes matching upper and lower bounds on the memory required to guarantee a specific epsilon-accuracy under a fixed online iteration budget K. For convex objectives satisfying a growth condition, near-matching bounds are obtained, and a phase transition in K is identified where additional memory provides no further benefit. The work also provides a general proof framework that quantifies the memory cost of acceleration and highlights two key drivers: the online optimizer's convergence rate and the solution map's Lipschitz sensitivity to problem parameters. Experiments on parameterized ridge regression validate these predicted tradeoffs.