Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization

• URL: http://arxiv.org/abs/2607.20769v1
• Date: Wed, 22 Jul 2026 22:36:27 GMT
• Title: Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
• Abstract summary: Learning-enabled decision systems often use offline data or computation to reduce online compute cost.<n>We study how much offline information is needed to achieve a desired accuracy under a fixed online computation budget.
• Score: 3.470927020824476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-enabled decision systems often use offline data or computation to reduce online compute cost. Despite the empirical success of such approaches, there is limited general understanding of how much offline information is needed to achieve a desired accuracy under a fixed online computation budget. We study this question through the lens of amortized parametric optimization: an offline phase stores a finite memory of solved problem instances, and an online phase produces a solution to a new instance by retrieving a warm start and applying $K$ steps of projected gradient descent. We analyze this setup for smooth convex parametric optimization over a compact domain, using a nonparametric predictor built from the stored offline solutions. For $μ$-strongly convex objectives, we establish matching upper and lower bounds on the memory required to guarantee $\varepsilon$-accuracy under a fixed online iteration budget $K$. For convex objectives satisfying a $β$-growth condition ($β>2$), we obtain near-matching bounds and identify a phase transition in $K$ beyond which additional memory provides no benefit. We further provide a general proof framework that (i) explicitly quantifies the memory cost of acceleration---how much offline memory is required to achieve a prescribed speedup over the unaided online optimizer---and (ii) identifies two key quantities driving this cost: the convergence rate of the online optimizer and the Lipschitz sensitivity of the solution map to the problem parameter. Experiments on parameterized ridge regression confirm the predicted memory--computation--accuracy tradeoffs.

Related papers

• Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
  We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation.<n>Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees.
  arXiv  Detail & Related papers  (2026-06-02T16:16:45Z)
• Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts [19.540758462427878]
  We propose a learning-augmented framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees.<n>We introduce RowDualNet, a lightweight row-independent architecture that avoids the $mathcalO(N2)$ memory bottleneck of graph-based models.
  arXiv  Detail & Related papers  (2026-05-10T07:15:49Z)
• Mild Over-Parameterization Benefits Asymmetric Tensor PCA [12.923414933046574]
  Asymmetric PCA (ATPCA) is prototypical model for studying the trade-offs between sample complexity, computation, and memory.<n>We focus on the setting where $overlinek geq 4$ is even and consider descent-based algorithms under a limited memory budget.
  arXiv  Detail & Related papers  (2026-04-11T13:34:48Z)
• Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization [54.723834588133165]
  We study online linear optimization with matrix variables by the operatorAML, a setting where the geometry renders designing datadependent and efficient adaptive algorithms challenging.<n>We instantiate this framework with two efficient methods that avoid projections.<n>We show both methods admit closed-form updates match one-sided Shampoo's regret up to a constant factor, while significantly reducing computational cost.
  arXiv  Detail & Related papers  (2026-02-09T03:09:47Z)
• Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization [2.0403774954994858]
  We introduce a machine-learning framework to learn the hyper Parameters sequence of first-order methods. We show how to learn the hyper Parameters for several popular algorithms. We showcase the effectiveness of our method with many examples, including ones from control, signal processing, and machine learning.
  arXiv  Detail & Related papers  (2024-11-24T04:58:36Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  We present efficient methods for optimizing dynamic regret and adaptive regret.<n>The proposed algorithms require only one gradient query and one function evaluation at each round.<n>We also study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from $O(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions [22.09320263962004]
  We find the spectra of the Kronecker-factored gradient covariance matrix in deep learning (DL) training tasks are concentrated on a small leading eigenspace. We describe a generic method for reducing memory and compute requirements of maintaining a matrix preconditioner. We show extensions of our work to Shampoo, resulting in a method competitive in quality with Shampoo and Adam, yet requiring only sub-linear memory for tracking second moments.
  arXiv  Detail & Related papers  (2023-02-07T21:50:06Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  We propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $tilde O(dsqrtH3K)$. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-12T18:58:59Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  We present a new family of minmax optimization algorithms that automatically exploit the geometry of the gradient data observed at earlier iterations. Thanks to this adaptation mechanism, the proposed method automatically detects whether the problem is smooth or not. It converges to an $varepsilon$-optimal solution within $mathcalO (1/varepsilon)$ iterations in smooth problems, and within $mathcalO (1/varepsilon)$ iterations in non-smooth ones.
  arXiv  Detail & Related papers  (2020-10-22T22:54:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.