Adversarial bandit optimization for approximately linear functions

• URL: http://arxiv.org/abs/2505.20734v6
• Date: Wed, 24 Sep 2025 07:06:50 GMT
• Title: Adversarial bandit optimization for approximately linear functions
• Abstract summary: We consider a bandit optimization problem for non-smooth and non-smooth functions.<n>In each trial the loss function is the sum of a linear function and a small but arbitrary perturbation chosen after observing the player's choice.<n>Our result implies an improved high-probability regret bound for optimization.
• Score: 0.6321283533425183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a bandit optimization problem for nonconvex and non-smooth functions, where in each trial the loss function is the sum of a linear function and a small but arbitrary perturbation chosen after observing the player's choice. We give both expected and high probability regret bounds for the problem. Our result also implies an improved high-probability regret bound for the bandit linear optimization, a special case with no perturbation. We also give a lower bound on the expected regret.

Related papers

• Black-box optimization of noisy functions with unknown smoothness [28.994787715086872]
  We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise.<n>Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting.<n>We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms.
  arXiv  Detail & Related papers  (2026-05-04T11:04:31Z)
• Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards [3.396415446890748]
  We study the tail behavior of regret in multi-armed bandits for algorithms that are optimal in expectation.<n>We derive a novel upper bound on the regret tail probability.<n>Our results provide a unified and tight characterization of regret tails for optimal KL-based UCB algorithms.
  arXiv  Detail & Related papers  (2026-04-16T11:05:30Z)
• Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses [0.6321283533425183]
  We study a class of adversarial bandit optimization problems in which the loss functions may be non-smooth.<n>As a special case of our analysis, we recover an improved high-probability for classical bandit optimization.
  arXiv  Detail & Related papers  (2026-03-27T04:33:08Z)
• A Convex Loss Function for Set Prediction with Optimal Trade-offs Between Size and Conditional Coverage [0.554780083433538]
  We consider supervised learning problems in which set predictions provide explicit uncertainty estimates.<n>We propose a convex loss function for nondecreasing subset-valued functions obtained as level sets of a real-valued function.<n>We show how to naturally obtain sets with optimized conditional coverage.
  arXiv  Detail & Related papers  (2025-12-22T08:41:31Z)
• Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses [4.509643050721454]
  "Decision swap regret" generalizes prediction for downstream swap regret and omniprediction.<n>We also give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings.
  arXiv  Detail & Related papers  (2025-02-18T06:01:52Z)
• Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
  This paper considers the distributed online bandit optimization problem with non loss functions over a time-varying digraph. Players select an adversary and then the adversary assigns an arbitrary non-linear loss function to this player. The expected regret of our algorithms is comparable to existing algorithms that use two-point deviation.
  arXiv  Detail & Related papers  (2024-09-24T02:37:33Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• A conversion theorem and minimax optimality for continuum contextual bandits [70.71582850199871]
  We study the contextual continuum bandits problem, where the learner sequentially receives a side information vector and has to choose an action in a convex set.<n>The goal is to minimize all the underlying functions for the received contexts, leading to the contextual notion of regret.<n>We show that any algorithm achieving a sub-linear static regret can be extended to achieve a sub-linear contextual regret.
  arXiv  Detail & Related papers  (2024-06-09T10:12:08Z)
• No-Regret Linear Bandits beyond Realizability [34.06789803260447]
  We study linear bandits when the underlying reward function is not linear. Existing work relies on a uniform misspecification parameter $epsilon$ that measures the sup-norm error of the best linear approximation. We describe a more natural model of misspecification which only requires the approximation error at each input $x$ to be proportional to the suboptimality gap at $x$.
  arXiv  Detail & Related papers  (2023-02-26T07:15:31Z)
• 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)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  We study first-order methods when the inner optimization problem is convex but non-smooth. We show that the forward-mode differentiation of proximal gradient descent and proximal coordinate descent yield sequences of Jacobians converging toward the exact Jacobian.
  arXiv  Detail & Related papers  (2021-05-04T17:31:28Z)
• Optimal Stochastic Nonconvex Optimization with Bandit Feedback [45.675080529219365]
  We analyze continuous armed bandit problems for non cost functions under certain smoothness and sublevel set assumptions. We then propose an adaptive splitting method, which can significantly improve the performance.
  arXiv  Detail & Related papers  (2021-03-30T05:21:12Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)

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.