PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Convex Optimization with Dueling Feedback

Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal

arXiv:2608.15050v1cs.LG

TL;DR

Adversarial online convex optimization with only binary dueling feedback has lacked regret guarantees because preferences provide severely limited information. The paper introduces DTFO to extract approximate gradients and obtains O(T^3/4) static, adaptive, and dynamic regret, with improved rates under additional structure.

  • Problem

    Adversarial online convex optimization with dueling feedback lacks established static, adaptive, and dynamic regret guarantees, despite applications with time-varying objectives.

  • Method

    DTFO uses smoothing and Taylor-based analysis of the preference transfer function to convert binary comparisons into approximate gradients for standard first-order algorithms.

  • Results

    O(T^3/4) regret is obtained for static, adaptive, and dynamic settings, improving to O(T^2/3) for smooth objectives and O(sqrt(T log T)) for strongly convex and smooth functions.

  • Takeaways & Limitations

    The results establish regret guarantees for adversarial convex optimization with strictly weaker 1-bit feedback than gradient-estimation-based one-point bandit feedback.

  • Takeaways & Limitations

    The uniform DTFO wrapper cannot surpass an O(T^2/3) floor under smoothness because spherical shrinkage introduces boundary projection error.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces adversarial online convex optimization with only 1-bit dueling feedback and asks how to obtain regret guarantees without function values or gradients. Its DTFO reduction converts dueling comparisons into approximate gradients, enabling first-order methods and yielding initial static, adaptive, and dynamic regret bounds with improved rates under structural assumptions.

  • Motivation: Adversarial online convex optimization with dueling feedback addresses time-varying, potentially adversarial convex objectives using only binary comparisons.Prior continuous-domain dueling work is restricted to stationary environments, while OCO methods require first-order feedback.
  • Problem: Dueling feedback provides only a 1-bit nonlinear transformation of function differences, creating a harder information bottleneck than two-point or one-point bandit feedback.Unlike bandit models, the learner observes no function values, so extracting reliable first-order information in adversarial settings is difficult.
  • Contributions: The DTFO wrapper converts dueling feedback into approximate gradient information, allowing standard first-order OCO algorithms to transfer regret guarantees to true convex objectives.The framework also introduces Expected Interval Regret, which can be reduced to static, adaptive, and dynamic regret metrics.
  • Results: O(T 2/3) regret is achieved for strongly convex and smooth objectives under additional structure.For strongly convex and smooth functions, the paper further obtains O(√T log T), matching best-known rates for gradient-estimation-based one-point bandit optimization.
  • Technical approach: A deterministically bounded spherical estimator extracts a scaled gradient signal by analyzing smoothed losses and applying Taylor expansion to the nonlinear preference transfer function.For ellipsoidal smoothing, a 4th-Moment Spherical Identity removes a potentially diverging condition-number penalty by evaluating bias in the comparator direction.

2 Preliminaries

The preliminaries define the Lipschitz online convex optimization setting, a perturbed feasible domain, and binary noisy dueling feedback. They also impose structural conditions on preference transfer and formalize interval-based regret notions.

  • Online Convex Optimization: The learner optimizes G-Lipschitz convex losses over a convex domain K with diameter D, containing the origin and a unit ball, using the non-empty δ-shrunken domain Kδ.The domain perturbation radius satisfies δ > 0, and Kδ must be non-empty.
  • Dueling Feedback: At each round, the learner queries two points and receives a noisy binary preference bit indicating which queried point has lower loss.The dueling oracle returns ot ∈ {−1, +1} according to a transfer function ρ applied to the loss difference.
  • Dueling Feedback: Strict pairwise preference requires an odd transfer function, ρ(x) = −ρ(−x), which implies ρ(0) = 0.This symmetry follows from reversing the query order in the dueling oracle.
  • Transfer Function: The transfer function has positive slope ρ′(0) = γ > 0 and bounded curvature |ρ′′(x)| ≤ M for x ∈ [−2G, 2G].The positive derivative ensures local comparisons provide a usable first-order signal.
  • Regret Measures: The analysis evaluates the exact queried points through generalized Expected Interval Regret over contiguous intervals and arbitrary comparator sequences.This formulation recovers static, dynamic, and adaptive regret as special cases.
  • Regret Measures: Static regret uses one best fixed decision over the full horizon, dynamic regret allows changing comparators, and adaptive regret uses the best fixed decision on each sub-interval.These notions correspond respectively to passages defining static, dynamic, and adaptive regret.

3 DTFO Reduction Framework

The DTFO wrapper converts noisy 1-bit dueling feedback into a scaled approximate gradient, allowing standard first-order online convex optimization algorithms to operate on a δ-shrunken domain. Its estimator has bounded magnitude and controlled bias, yielding interval, static, dynamic, and adaptive regret reductions, including an overall O(|I|3/4) rate after tuning δ.

  • DTFO Wrapper: DTFO is a modular wrapper that connects any standard first-order algorithm A to noisy 1-bit dueling feedback using spherical smoothing over the δ-shrunken domain.It queries perturbed points and constructs a scaled gradient estimator for feedback to A.
  • Gradient Estimator: The estimator satisfies the deterministic bound ∥ˆgt∥2 ≤ d 2γδ and has conditional expectation equal to the smoothed gradient plus a controlled bias.The bias is bounded by ∥Bt∥2 ≤dMG2.
  • Regret Reduction: Theorem 1 provides a universal expected interval-regret reduction by feeding the approximate estimator into any off-the-shelf first-order algorithm and accounting for smoothing, projection, and bias penalties.The reduction applies over any discrete time interval and comparator sequence projected onto Kδ.
  • Regret Corollaries: Static, dynamic, and adaptive regret reductions follow by applying Theorem 1 over the full horizon, arbitrary comparator sequences, and specific sub-intervals, respectively.The corresponding corollaries instantiate the same reduction framework for each comparator setting.
  • Parameter Tuning: O(|I|3/4) results from balancing the base algorithm’s surrogate regret with the DTFO penalty O(δ|I|) using δ ∝|I|−1/4.The estimator norm is exactly ∥ˆgt∥2 = d 2γδ.

4 Dueling Bandit Online Convex Algorithms as Results of DTFO Wrapper

The DTFO wrapper generates dueling-feedback online convex algorithms by combining a gradient-estimator reduction with different first-order base methods. This yields static, adaptive, and dynamic regret guarantees, with improved rates under strong convexity.

  • DTFO Wrapper: Substituting classic first-order algorithms into DTFO produces static, adaptive, and dynamic dueling optimization algorithms.The wrapper is instantiated with three classic online algorithms.
  • Static Regret: O(T 3/4) static regret is achieved by Online Relative Gradient Descent (ORGD) using OGD as its base algorithm.The tuning uses perturbation radius δ ∝ T −1/4.
  • Adaptive Regret: O(T 3/4) adaptive regret is achieved by Projection-Free ORGD using SO-OGD and a Separation Oracle over any interval I ⊆ [1, T].The method avoids computationally expensive projections through an infeasible projection subroutine.
  • Limitation: O(T 2/3) is a smoothness floor for the uniform DTFO wrapper because spherical shrinkage incurs boundary projection error O(δT).Further acceleration under smoothness requires abandoning uniform spherical shrinkage.

5 Improved Static Regret for Smooth Objectives via Ellipsoidal Estimators

The section develops an ellipsoidal-estimator FTRL reduction for smooth objectives, using Dikin-ellipsoid sampling to avoid boundary penalties and transfer dueling feedback into static regret guarantees. It recovers an O(T^(2/3)) rate for smooth convex objectives and extends the framework to strongly convex smooth objectives.

  • Estimator geometry: Dikin-ellipsoid sampling dynamically flattens near K’s boundary, eliminating the uniform wrapper’s linear O(δT) projection penalty.The approach exploits the O(δ^2) approximation error available for smooth functions while ensuring sampled points remain inside the domain.
  • Structural assumptions: The reduction assumes L-smooth objectives and a four-times continuously differentiable transfer function with bounded fourth derivative M4.The transfer-function condition controls the cubic Taylor remainder and residual estimation bias.
  • Reduction and guarantee: The method combines ellipsoidal estimators with a ν-self-concordant barrier in FTRL, yielding static regret bounds through a horizon-aggregated regularizer.Theorem 5 expresses the guarantee through standard FTRL regret on the unbiased surrogate sequence and a deterministic bias term Ψt.
  • Smooth convex objectives: O(T^(2/3)) expected static regret is obtained for smooth convex objectives by setting σ = 0 and tuning η ∝ T^-2/3, δ ∝ T^-1/6, and α ∝ T^-1/2.This recovers the sampling geometry of the Bandit OCO algorithm from [35].
  • Strongly convex objectives: For strongly convex and smooth objectives, setting σ > 0 produces shrinking sampling matrices and recovers the geometry of FTARL-σ.The stated tuning begins with η ∝ 1/T and δ = 1; the supplied passage truncates the resulting regret expression.

6 Conclusion

The paper studies adversarial online convex optimization with binary dueling feedback and introduces DTFO, a reduction to approximate gradients that enables standard first-order methods. It establishes regret transfer through this wrapper and instantiates it with classical algorithms.

  • 6 Conclusion: DTFO converts binary comparison feedback into approximate gradient estimates, enabling standard first-order online convex optimization algorithms.The reduction uses smoothing and a Taylor-based analysis of the transfer function.
  • 6 Conclusion: The analysis establishes a general regret transfer result for adversarial online convex optimization with dueling feedback.
  • 6 Conclusion: Instantiating DTFO with classical methods yields static, adaptive, and dynamic regret guarantees.

A Related Works

Prior dueling-bandit and continuous-dueling methods largely assume finite, structured, stochastic, or stationary settings, leaving adversarial online convex optimization with comparison-only feedback unresolved. This work addresses that gap by providing the first regret guarantees and converting binary comparisons into approximate gradients.

  • Preference-Based Learning and Dueling Bandits: Dueling-bandit approaches typically assume finite or structured action spaces and do not extend to general continuous convex optimization.The literature includes stochastic, adversarial, and contextual variants in discrete action spaces.
  • Continuous Dueling under Convex Objectives: Continuous-dueling methods study convex objectives under stochastic or stationary assumptions rather than adversarial, time-varying objectives.One strongly convex and smooth-objective approach uses DB-regret, which is unsuitable for non-stationary environments.
  • Bandit Online Convex Optimization: O(T^3/4) bounds match foundational gradient-estimation approaches based on one-point and two-point function evaluations.These estimators serve as the benchmark in Table 1.
  • Bandit Online Convex Optimization: State-of-the-art online Newton methods cannot apply to dueling feedback because they require exact continuous scalar loss evaluations, whereas comparisons provide only a 1-bit nonlinear transformation of unobserved differences.The work instead converts binary comparison feedback into an approximate gradient signal.
  • Contribution: The paper provides the first regret guarantees for adversarial online convex optimization with general convex objectives under purely comparison-based feedback.This establishes the paper’s central contribution in the previously unresolved adversarial setting.

B Technical Lemmas

This section establishes the technical bridge from true objectives to surrogate losses: spherical smoothing preserves convexity, supports gradient extraction from boundary evaluations, and controls approximation bias for Lipschitz functions.

  • Smoothing convexity: Spherically smoothing a convex function over a δ-radius ball preserves convexity.Lemma 2 proves convexity by applying the original convexity inequality inside the expectation and using linearity of expectation.
  • Gradient extraction: Spherical symmetry and Stokes’ Theorem yield an approximately unbiased gradient estimator for the smoothed function using boundary function evaluations.The construction uses a two-point symmetric difference estimator and the equivalence of u and −u under the uniform sphere distribution.
  • Approximation error: For G-Lipschitz functions, smoothing over a δ-radius ball produces a pointwise approximation-error bound relative to the original function.The proof applies Jensen’s or the triangle inequality, the G-Lipschitz property, and the unit-norm bound for samples from the solid unit ball.

C Infeasible Projection via Separation Oracle

This section presents SO-IP, an infeasible projection subroutine that replaces exact Euclidean projections with a separation oracle for computational efficiency over complex domains. The method returns a feasible point with a distance guarantee relative to the initial point and points in the shrunken set K_δ.

  • Subroutine purpose: SO-IP uses a separation oracle instead of exact Euclidean projections, preserving computational efficiency over complex domains.It is the infeasible projection subroutine used by Projection-Free ORGD.
  • Algorithm: The algorithm initializes within aff(K), repeatedly queries SOK, and uses returned separating hyperplanes to update infeasible iterates.It returns an iterate once the oracle identifies a point in K.
  • Guarantee: SO-IP stops after at most δ^-2 + 1 iterations and returns y ∈ K.The iteration bound and feasibility guarantee are stated in Lemma 5.
  • Guarantee: For every z ∈ K_δ, the returned point satisfies ∥y − z∥ ≤ ∥y0 − z∥.The proof obtains the bound first relative to the affine projection of y0, then transfers it to y0.

D Proof of Lemma 1

The proof bounds the gradient estimator and establishes that its conditional expectation equals the gradient of the spherically smoothed loss plus a controlled bias. It derives the bias bound from Lipschitzness, the transfer-function expansion, and bounded curvature.

  • Estimator bound: The estimator has a deterministic magnitude bound because the oracle feedback lies in {−1, 1} and the sampled direction has unit norm.The direction u_t is drawn uniformly from the unit sphere S^(d−1), so ∥u_t∥_2 = 1.
  • Transfer-function expansion: The loss difference satisfies |∆_t| ≤ 2Gδ ≤ 2G by G-Lipschitzness and the perturbation distance 2δ.The transfer-function expansion is exact, with the remainder represented by the second derivative at some c_t between 0 and ∆_t.
  • Remainder control: Because c_t ∈ [−2G, 2G] and Assumption 1 gives |ρ′′(c_t)| ≤ M, the remainder obeys |ϵ(∆_t)| ≤ 2MG^2δ^2.The interval for c_t follows from the bound on ∆_t, while the curvature bound controls the expansion remainder.
  • Conditional expectation: Conditioned on w_t and u_t, the estimator expectation is d/(2γδ) ρ(∆_t)u_t.The queried points are deterministic under this conditioning, leaving only the oracle feedback random.
  • Bias decomposition: The exact expansion ρ(∆_t) = γ∆_t + ϵ(∆_t) decomposes the expectation into the smoothed-loss gradient and bias vector B_t.The bias is defined as B_t = d/(2γδ) E_u_t[ϵ(∆_t)u_t | w_t], and the first term matches the gradient of the smoothed loss.

E Proof of Theorem 1

The proof derives Theorem 1 by applying convex regret analysis to the smoothed losses and controlling estimator bias, smoothing, and projection effects. It then transfers the surrogate bound to the queried true losses to obtain the final interval regret bound.

  • Surrogate analysis: The convexity of ˜ft enables comparison with the projected comparator, while algorithm A supplies the standard convex regret guarantee on {ℓt}t∈I.The expected gradient is replaced by the biased surrogate estimator E[ĝt | wt] − Bt before applying the regret guarantee.
  • Regret decomposition: The regret decomposition separates approximation error at wt, surrogate regret, and boundary projection error.These are the three labeled components used to relate the algorithm’s performance to the comparator.
  • Error control: Gδ bounds each smoothing approximation term, using the uniform inequality |ft(w) − ˜ft(w)| ≤ Gδ.The proof applies Lemma 4 to bound the first and third terms in the decomposition.
  • Final transfer: Gδ|I| is added when evaluating the G-Lipschitz losses at the queried points, producing the final interval regret bound.The proof first substitutes the surrogate regret bound into the central iterate interval regret and then accounts for queried-point evaluation.
  • Final bound: The proof concludes with the bound containing G(D + 3) + dMG2D.This expression is stated as the final result after summing the controlled terms.

F Improved Regret for Smooth Objectives via Ellipsoidal Estimators

This section develops an ellipsoidal estimator using self-concordant-barrier geometry to obtain approximately unbiased gradients for smoothed losses while eliminating condition-number penalties. With tuned learning, smoothing, and shrinkage parameters, the method achieves O(T^2/3) expected static regret for smooth objectives.

  • Barrier geometry: Self-concordant barriers keep iterates in the domain interior, while Dikin ellipsoids provide feasible, domain-adaptive exploration shapes.The local dual norm induced by the sampling matrix stabilizes gradient updates near the boundary.
  • Estimator construction: The Dueling Ellipsoidal Estimator provides an approximately unbiased gradient for the ellipsoidally-smoothed loss.Its construction uses a sampling matrix A_t and pairwise feedback from symmetric ellipsoidal perturbations.
  • Bias control: The fourth-moment spherical identity enables direct bias-inner-product analysis, causing ill-conditioned projection matrices to cancel from the expected bias penalty.The identity is E_u[<g,u>^3<v,u>] = 3/[d(d + 2)] ||g||^2<g,v>.
  • Bias control: O(δ^2T) bounds the principal bias penalty independently of the boundary shrinkage α after applying the uniform Hessian bound.The analysis also carries an explicit additive bias penalty through the regret sum.
  • Regret guarantee: O(T^2/3) expected static regret follows from tuning η ∝ T^-2/3, δ ∝ T^-1/6, and α ∝ T^-1/2.These parameter choices are stated for the smooth-objective result.
Loading 2608.15050v1…