Adaptive multi-fidelity optimization with fast learning rates

• URL: http://arxiv.org/abs/2604.16239v1
• Date: Fri, 17 Apr 2026 16:59:07 GMT
• Title: Adaptive multi-fidelity optimization with fast learning rates
• Abstract summary: This paper studies the problem of optimizing a locally smooth function with a limited budget.<n>We first prove lower bounds for the simple regret under different assumptions on the fidelities.<n>We then present the Kometo algorithm which achieves the same rates without any knowledge of the function.
• Score: 14.941820094179747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In multi-fidelity optimization, biased approximations of varying costs of the target function are available. This paper studies the problem of optimizing a locally smooth function with a limited budget, where the learner has to make a tradeoff between the cost and the bias of these approximations. We first prove lower bounds for the simple regret under different assumptions on the fidelities, based on a cost-to-bias function. We then present the Kometo algorithm which achieves, with additional logarithmic factors, the same rates without any knowledge of the function smoothness and fidelity assumptions, and improves previously proven guarantees. We finally empirically show that our algorithm outperforms previous multi-fidelity optimization methods without the knowledge of problem-dependent parameters.

Related papers

• Simultaneous Learning and Optimization via Misspecified Saddle Point Problems [4.904092547705666]
  We study a class of misspecified saddle point (SP) problems, where the optimization objective depends on an unknown parameter.<n>We propose two algorithms based on the accelerated primal-dual (APD) by Hamedani & Aybat 2021.<n>Both methods achieve a provable convergence rate of $mathcalO(log K / K)$, while the learning-aware approach attains a tighter $mathcalO(1)$ constant.
  arXiv  Detail & Related papers  (2025-10-06T18:07:02Z)
• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand.<n>We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
  We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the $epsilon$-contamination model.<n>Our algorithms do not require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions.<n>We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.
  arXiv  Detail & Related papers  (2024-12-15T00:52:08Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds [1.6385815610837167]
  In this work, we introduce innovative learning-rate-free algorithms for optimization over Riemannian. We establish high probability convergence guarantees that are optimal, up to logarithmic factors, compared to the best-known optimally tuned rate in the deterministic setting. Our approach is validated through numerical experiments, demonstrating competitive performance against learning-rate-dependent algorithms.
  arXiv  Detail & Related papers  (2024-06-04T13:17:24Z)
• Distributed Fractional Bayesian Learning for Adaptive Optimization [12.158466416574448]
  This paper considers a distributed adaptive optimization problem, where all agents only have access to their local cost functions with a common unknown parameter.<n>We aim to provide valuable insights for addressing parameter uncertainty in distributed optimization problems and simultaneously find the optimal solution.
  arXiv  Detail & Related papers  (2024-04-17T13:09:33Z)
• Principled Preferential Bayesian Optimization [22.269732173306192]
  We study the problem of preferential Bayesian optimization (BO) We aim to optimize a black-box function with only preference feedback over a pair of candidate solutions. An optimistic algorithm with an efficient computational method is then developed to solve the problem.
  arXiv  Detail & Related papers  (2024-02-08T02:57:47Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs [28.254408148839644]
  We propose a non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous evaluation costs. Our acquisition function outperforms existing methods in a variety of synthetic and real problems.
  arXiv  Detail & Related papers  (2021-11-12T02:18:26Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.