Cost-Aware Iteration Allocation for Sequential Multi-Fidelity First-Order Optimization
Abstract
Optimization can be expensive when evaluating the objective and its gradient requires a large dataset or a costly simulation. A cheaper approximation (i.e., a surrogate) can provide a useful initial point, but the work spent on that surrogate must be justified by the saving on the original problem. We study how many iterations to perform on each surrogate before switching to a more accurate objective. For a given sequence of smooth, strongly convex objectives, we use convergence bounds and distances between minimizers to construct a model of the total iteration cost. We derive closed-form two-level budgets for Nesterov's accelerated gradient method and a convex reformulation for multiple levels. We also develop an online switching rule that updates the cost comparison using the gradient at the current point. We test the techniques on a logistic-regression problem using HIGGS data. The online rule reduces weighted iteration cost in all 27 tested configurations, with a median cost of 52.8% of direct optimization. The results illustrate why updating the switching decision can be more effective than fixing the budget from an initial convergence bound.
Related
- Seq2Synth: Benchmarking Temporal Fidelity in Synthetic Sequential Tabular Data
- Multi-Trajectory Parallel-in-Iteration Optimization
- Randomized Adaptive Sequential Allocation and the Limits of Bounded Exposure to Inferior Treatments
- Multi-view Semantic-aware Resource Allocation for Edge AI
- Performance Analysis and Sensing-Aware Resource Allocation for Full-Duplex Massive MIMO ISCC Networks
BibTeX
@misc{ardestanijaafari2026costaware,
title = {{Cost-Aware Iteration Allocation for Sequential Multi-Fidelity First-Order Optimization}},
author = {Amir Ardestani-Jaafari and Warren Hare and Zhongda Huang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14295},
eprint = {2610.14295},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14295},
}
RIS
TY - UNPB
TI - Cost-Aware Iteration Allocation for Sequential Multi-Fidelity First-Order Optimization
AU - Amir Ardestani-Jaafari
AU - Warren Hare
AU - Zhongda Huang
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14295
UR - https://arxiv.org/abs/2610.14295
AB - Optimization can be expensive when evaluating the objective and its gradient requires a large dataset or a costly simulation. A cheaper approximation (i.e., a surrogate) can provide a useful initial point, but the work spent on that surrogate must be justified by the saving on the original problem. We study how many iterations to perform on each surrogate before switching to a more accurate objective. For a given sequence of smooth, strongly convex objectives, we use convergence bounds and distances between minimizers to construct a model of the total iteration cost. We derive closed-form two-level budgets for Nesterov's accelerated gradient method and a convex reformulation for multiple levels. We also develop an online switching rule that updates the cost comparison using the gradient at the current point. We test the techniques on a logistic-regression problem using HIGGS data. The online rule reduces weighted iteration cost in all 27 tested configurations, with a median cost of 52.8% of direct optimization. The results illustrate why updating the switching decision can be more effective than fixing the budget from an initial convergence bound.
ER -