Online Convex Optimization with Dueling Feedback

• URL: http://arxiv.org/abs/2608.15050v1
• Date: Sat, 15 Aug 2026 05:26:27 GMT
• Title: Online Convex Optimization with Dueling Feedback
• Abstract summary: We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two points queried.<n>We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods.<n>We show that regret guarantees transfer under this reduction, yielding the first results for this setting, including $mathcalO(T3/4)$ static, adaptive, and dynamic regret.
• Score: 40.61353645255313
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. While dueling feedback is well understood in discrete or stochastic settings, the adversarial convex setting has remained unexplored. We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods. We show that regret guarantees transfer under this reduction, yielding the first results for this setting, including $\mathcal{O}(T^{3/4})$ static, adaptive, and dynamic regret. Under additional structure, we obtain improved rates of $\mathcal{O}(T^{2/3})$ for smooth objectives and $\mathcal{O}(\sqrt{T \log T})$ for strongly convex functions.

Related papers

• Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback [17.238068736229014]
  We consider the problem of Online Convex Optimization with two-point bandit feedback.<n>We provide the first high-probability regret bound of $O(d(log T + log (1/))/)$ for $$-strongly convex losses.
  arXiv  Detail & Related papers  (2026-03-26T04:52:19Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  We focus on the class of (strongly) convex $(L0)$-smooth functions and derive new convergence guarantees for several existing methods.<n>In particular, we derive improved convergence rates for Gradient Descent with smoothnessed Gradient Clipping and for Gradient Descent with Polyak Stepsizes.
  arXiv  Detail & Related papers  (2024-09-23T13:11:37Z)
• 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)
• Two-Timescale Optimization Framework for Sparse-Feedback Linear-Quadratic Optimal Control [3.746304628644379]
  A $mathcalHfeedback$-guaranteed sparse-feedback linear-quadratic (LQ) optimal control with convex parameterization and convex-bounded uncertainty is studied.
  arXiv  Detail & Related papers  (2024-06-17T03:17:33Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  We consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway comparisons. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates.
  arXiv  Detail & Related papers  (2023-12-19T01:52:13Z)
• 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)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback [28.679167097106813]
  We propose a new one-point feedback method for online optimization. We show that using residual feedback can produce much smaller variance compared to conventional one-point feedback methods. Our regret bounds are tighter compared to existing regret bounds for ZO with conventional one-point feedback.
  arXiv  Detail & Related papers  (2020-10-14T19:52:25Z)

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.