Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks

• URL: http://arxiv.org/abs/2506.01625v1
• Date: Mon, 02 Jun 2025 13:04:18 GMT
• Title: Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks
• Authors: Artun Saday, Yaşar Cahit Yıldırım, Cem Tekin,
• Abstract summary: We consider a robust satisficing objective, where the goal is to consistently achieve a predefined performance threshold $tau$, even under adversarial conditions.<n>We propose two novel algorithms based on distinct formulations of robust satisficing, and show that they are instances of a general robust satisficing framework.<n>Specifically, we derive two regret bounds: one that is sublinear over time, assuming certain conditions on the adversary and the satisficing threshold $tau$, and another that scales with the perturbation magnitude but requires no assumptions on the adversary.
• Score: 7.701333337093469
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address the problem of Gaussian Process (GP) optimization in the presence of unknown and potentially varying adversarial perturbations. Unlike traditional robust optimization approaches that focus on maximizing performance under worst-case scenarios, we consider a robust satisficing objective, where the goal is to consistently achieve a predefined performance threshold $\tau$, even under adversarial conditions. We propose two novel algorithms based on distinct formulations of robust satisficing, and show that they are instances of a general robust satisficing framework. Further, each algorithm offers different guarantees depending on the nature of the adversary. Specifically, we derive two regret bounds: one that is sublinear over time, assuming certain conditions on the adversary and the satisficing threshold $\tau$, and another that scales with the perturbation magnitude but requires no assumptions on the adversary. Through extensive experiments, we demonstrate that our approach outperforms the established robust optimization methods in achieving the satisficing objective, particularly when the ambiguity set of the robust optimization framework is inaccurately specified.

Related papers

• Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidence [0.562479170374811]
  We introduce a novel problem setting in bandit optimization that addresses maximizing expected reward and minimizing associated uncertainty.<n>We propose a unified meta-budgetalgorithmic framework capable of operating under both fixed-confidence and fixed-optimal regimes.<n>Our approach outperforms existing methods in terms of both accuracy and sample efficiency.
  arXiv  Detail & Related papers  (2025-06-27T14:21:03Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  We propose SITAlign, an inference framework that addresses the multifaceted nature of alignment by maximizing a primary objective while satisfying threshold-based constraints on secondary criteria.<n>We provide theoretical insights by deriving sub-optimality bounds of our satisficing based inference alignment approach.
  arXiv  Detail & Related papers  (2025-05-29T17:56:05Z)
• An Optimisation Framework for Unsupervised Environment Design [88.29733214939544]
  unsupervised environment design (UED) aims to maximise agent's general robustness.<n>We provide a provably convergent algorithm in the zero-sum setting.<n>We empirically verify the efficacy of our method.
  arXiv  Detail & Related papers  (2025-05-27T03:07:26Z)
• Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
  We formulate a knowledge-gradient-based acquisition function to jointly optimize the first variables, establish a guarantee of consistency, and provide an approximation.<n>We demonstrate comparable empirical results to an alternative we formulate with fewer focuss, which alternates between the two variable types.
  arXiv  Detail & Related papers  (2024-08-30T16:26:31Z)
• Bayesian Optimization with Conformal Prediction Sets [44.565812181545645]
  Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity. In many cases we find that query coverage can be significantly improved without harming sample-efficiency.
  arXiv  Detail & Related papers  (2022-10-22T17:01:05Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• 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)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  We present a novel distributionally robust Bayesian optimization algorithm (DRBO) for zeroth-order, noisy optimization. Our algorithm provably obtains sub-linear robust regret in various settings. We demonstrate the robust performance of our method on both synthetic and real-world benchmarks.
  arXiv  Detail & Related papers  (2020-02-20T22:04:30Z)

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.