Research map / Optimization / Nonconvex and smooth optimization
Dueling Convex Optimization with General Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies convex optimization from 1-bit dueling comparisons with a general, unknown transfer function, proposing Projected Dueling Descent (O(ε^-4p) for smooth convex) and an epoch-wise variant (eO(ε^-2p) for smooth strongly convex).
Problem
Minimizing a convex function when access is only through noisy pairwise comparisons whose expected value is a general, unknown transfer function of the difference in function values.
Approach
Estimate a p-th order "relative gradient" from 1-bit comparisons of perturbed points using a random unit direction, relying only on the transfer's local polynomial behavior around zero (minimal nonzero degree p), and analyze the resulting normalized-gradient-style descent with a stopping-time/supermartingale argument; an epoch-wise restart yields faster rates under strong convexity.
Key results
- Projected Dueling Descent achieves O(ε^-4p) pairwise queries for smooth convex objectives with general transfer functions.
- Epoch-PDD achieves eO(ε^-2p) query complexity for smooth strongly convex objectives, matching existing lower bounds for certain transfer functions.
- Theory covers transfer functions admitting a series expansion about zero with uniformly bounded coefficients, e.g., arctan, tanh, erf (M=1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Projected Dueling Descent with a general transfer function | smooth convex objectives · Smooth convex objectives | pairwise queries to reach ϵ-optimality: O(ϵ−4p) | Helped |
| use epoch-wise warm-started Projected Dueling Descent | smooth strongly convex objectives · Smooth strongly convex objectives | pairwise queries to reach ϵ-convergence: O(ϵ−4p) -> eO(ϵ−2p) | Helped |
Surprising findings
- The strongly convex rate does not follow by reducing to the general convex case, since adding strongly convex regularization breaks comparison-oracle access.
Limitations
- Smooth convex guarantee only certifies that some iterate along the trajectory is ε-optimal; identifying it requires an extra tournament of comparisons.
- Analysis restricted to smoothness; beyond-smoothness settings left open.
- Lower bound for smooth convex case is unclear.
Experimental setup
Metrics: query complexity convergence rate
Baselines: Jamieson et al. 2012 Saha et al. 2021b
Builds on: Jamieson et al. 2012 dueling convex optimization Saha et al. 2021 dueling convex optimization with sign transfer Flaxman et al. 2005 zeroth-order gradient estimation
Closest papers by meaning
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.86)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.86)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.85)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.85)
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.84)
- Non-geodesically-convex optimization in the Wasserstein space (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.