← All setups

Strongly Convex Minimization with Comparisons

Descriptions may be stale. Consult the linked Lean sources.

Strongly Convex Minimization with Comparisons

We minimize a continuously differentiable function f:Rd→R over the closed Euclidean unit ball B in dimension d≥1. On B, f is strongly convex and Lipschitz with Lipschitz gradient. For each query x,y∈B, the oracle uses a fresh independent sample to return a sign in {−1,1} with mean ρ(f(x)−f(y)), where ρ is an unknown odd, nondecreasing function with local derivative bounds. Given ε>0, the goal is a feasible output x¯∈B with E[f(x¯)−f(x⋆)]≤ε, where x⋆ minimizes f on B and the expectation includes algorithm and oracle randomness.

With ∥⋅∥ denoting the Euclidean norm, the constrained problem is minx∈Bf(x),B={x∈Rd:∥x∥≤1}. The algorithm receives the dimension d, the objective constants μ,L,G>0, the transfer parameters r,c,M>0 and k∈{0,1,2,…}, and the tolerance ε.

Our assumptions:

Assumption 1 (Objective regularity and strong convexity). The function f is continuously differentiable on Rd. For every x,y∈B, it satisfies |f(y)−f(x)|≤G∥y−x∥,∥∇f(y)−∇f(x)∥≤L∥y−x∥,f(y)−f(x)≥⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 2 (Comparison transfer). The transfer function ρ:R→[−1,1] is continuously differentiable, odd, and nondecreasing. Its derivative satisfies c|t|k≤ρ′(t)≤M,|t|≤r, where |t|0=1 for every t.

Assumption 3 (Pairwise comparison oracle). Let Z1,Z2,… be independent random variables with common law ν on a measurable space Z, independent of the algorithm’s randomness. On call j with ordered pair (x,y)∈B×B, the oracle returns the bit g(x,y,Zj) encoded as a sign, where g:B×B×Z→{−1,1} is jointly measurable. For every x,y∈B, EZ∼ν[g(x,y,Z)]=ρ(f(x)−f(y)).

After the allotted comparisons, the output x¯ must be a measurable B-valued random variable. For a minimizer x⋆∈B, the gap f(x¯)−f(x⋆) must be integrable under the joint law of the algorithm’s randomness and the oracle samples and satisfy E[f(x¯)−f(x⋆)]≤ε.

Results

On the closed Euclidean unit ball B⊂Rd, f∈C1(Rd) is μ-strongly convex, L-smooth and G-Lipschitz. Each pair x,y∈B yields one sign from a jointly measurable oracle with fresh IID noise and mean ρ(f(x)−f(y)). The unknown odd, nondecreasing C1 link satisfies |ρ|≤1 and c|t|k≤ρ′(t)≤M for |t|≤r. The parameters are public, with d≥1, integer k≥0 and μ,L,G,r,c,M,ε>0. The target is E[f(x^)−minBf]≤ε for a measurable x^∈B.

Sufficient comparison budgets for strongly convex optimization with dueling feedback.
Result Oracle complexity Novelty Limitations
(1) LocalReferenceDueling (Ours) (⋆⋆⋆) (review) O(1+d2C2s2με+d2M2L2s4μ2ε2)
(2) Epoch-PDD (Saha et al. 2025, Thm. 4) Derived bound on B for expected gap, using tolerance ε/2 and δ=ε/(4G): O(K+dc2(aLdμε)2k+2log⁡(eK/δ)). Here 0<δ<1 and ε/2<5Lmin{4d,2dr/G}. (1): For fixed k≥1 and sufficiently small ε with other parameters fixed, fixed-distance opponents reduce d2k+3/ε2k+2 to d2/ε2 (at k=1, d5/ε4 before logs). At k=0, the leading polynomial cost improves for d≫(M/c)2. All queries stay feasible, even for constrained boundary minima. (1): Weighted-average expectation only. (2) gives a high-probability final epoch point on general bounded domains containing a global minimizer, with exterior queries allowed. (1) needs an odd C1 link and M; its accuracy term carries C8kμ−(4k+2) versus μ−(2k+2).
(3) NC-SMD (Kumagai 2017, Thms. 4, 13) Derived bound on B with full-range slope bounds (k=0): O((A+H)log⁡(e+A+H) +AH+GM0/(mε)). (1): Removes the accuracy logarithm at fixed parameters. Allows C1 objectives and locally controlled flat links. For ρ=tanh, r=1 and maxBf−minBf≍G, dependence on large G is polynomial versus exponential. (1): The ε−2 coefficient can be larger for small G and large ML/(cμ). (3) also bounds online regret on compact convex domains with a barrier, assuming C2 objectives and a thrice differentiable link with positive, nonincreasing slope on the positive gap range.
(4) Coordinate descent (Jamieson et al. 2012, Thm. 2) O(d2k+3ε−2(k+1) polylog(d,1/ε,1/δ)) for fixed class and oracle parameters, margin exponent κ=k+2, confidence 1−δ. (1): Covers constrained minima with in-ball comparisons. Rates are not directly comparable: (4) assumes unconstrained optimization on Rd. (1) needs a fixed link. (4) requires only a lower margin on the probability of a correct comparison.

Abbr: C=max{1,8G/r}, s=c(μ/(4C2))k, K=1+max{0,⌈log2⁡(4L/ε)⌉}, and a>0 is a universal constant. Over the attained gap range, m≤ρ′≤M0 and |ρ″|≤B2 in (3). A=d2/(mε)2 and H=1+[B2G2+(G+1)M0L]/(mμ).

Jamieson, Kevin G., Robert D. Nowak, and Benjamin Recht. 2012. “Query Complexity of Derivative-Free Optimization.” Advances in Neural Information Processing Systems 25. https://doi.org/10.48550/arXiv.1209.2434.
Kumagai, Wataru. 2017. “Regret Analysis for Continuous Dueling Bandit.” Advances in Neural Information Processing Systems 30. https://doi.org/10.48550/arXiv.1711.07693.
Saha, Aadirupa, Tomer Koren, and Yishay Mansour. 2025. “Dueling Convex Optimization with General Preferences.” In Proceedings of the 42nd International Conference on Machine Learning, edited by Aarti Singh, Maryam Fazel, Daniel Hsu, et al., vol. 267. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v267/saha25a.html.

Lean setup