Delphi.science

Nonsmooth Convex and Strongly Convex Optimization from Noisy Comparisons

Source: arxiv.org/abs/2611.19611

Evgeniy Kovalev, Fedor Stonyakin, Alexander Gasnikov

arXivarxiv/2611.19611Nov 14, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.19611
curl -X POST /api/v1/records/arxiv/2611.19611/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.19611/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'