Paperlane

no. 16 · Tuesday 17 November 2026

Nonsmooth Convex and Strongly Convex Optimization from Noisy Comparisons

Evgeniy Kovalev, Fedor Stonyakin and Alexander Gasnikov

math.OC

Abstract

We study nonsmooth convex and strongly convex optimization problems using only noisy pairwise comparisons: each query specifies two points and returns a single binary response indicating which point has the smaller function value, subject to noise. We distinguish two observation models: Stochastic Order Oracles, which compare two evaluations of the same random loss, and Preference Oracles, whose conditional response mean is a transfer function of the objective difference. For Stochastic Order Oracles, we prove that no comparison-based algorithm can guarantee vanishing expected suboptimality in general, even when sample losses are convex and Lipschitz and the mean objective is strongly convex. Under a normalized probit calibration, we recover convergence and establish matching upper and lower rates for convex and strongly convex objectives. For Preference Oracles with a linear response model, the binary response $O \in \{\pm1\}$ satisfies $\E[O\mid y,z]=λ(f(y)-f(z))$, with $λ>0$. In dimension $d$, we obtain an upper bound of $\widetilde (d^{3/2}/(λ\sqrt N))$ and establish, to our knowledge, the first minimax lower bound of $Ω(d/(λ\sqrt N))$, matching the optimal budget $N$ exponent, for both convex and strongly convex nonsmooth objectives. Beyond exact linearity, we analyze a simple projected comparison method for nonlinear transfer functions and establish convergence rates that depend on how accurately these functions can be approximated by a linear model near zero. Our analysis requires neither oddness nor twice differentiability of the transfer function.

fields
Optimization and Control
pdf ↗ page arXiv:2611.19611 ↗