Nonsmooth Optimization with Zeroth Order Comparison Feedback
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917256582135808 |
|---|---|
| author | Bakkali, Taha El Chayti, El Mahdi Saadi, Omar |
| author_facet | Bakkali, Taha El Chayti, El Mahdi Saadi, Omar |
| contents | We study unconstrained optimization problems of nonsmooth, nonconvex Lipschitz functions, using only noisy pairwise comparisons governed by a known link function. Our goal is to compute a $(δ,\varepsilon)$-Goldstein stationary point. We combine randomized smoothing with a novel unbiased reduction from comparisons to local value differences. By leveraging a Russian-roulette truncation on the Bernoulli-product expansion of the inverse link, we construct an exactly unbiased estimator for directional differences. This estimator has finite expected cost and variance scaling quadratically with the function gap, $\mathcal{O}(B^2)$, under mild conditions. Plugging this into the smoothed gradient identity enables a standard nonconvex SGD analysis, yielding explicit comparison-complexity bounds for common symmetric links such as logistic, probit, and cauchit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05622 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nonsmooth Optimization with Zeroth Order Comparison Feedback Bakkali, Taha El Chayti, El Mahdi Saadi, Omar Optimization and Control We study unconstrained optimization problems of nonsmooth, nonconvex Lipschitz functions, using only noisy pairwise comparisons governed by a known link function. Our goal is to compute a $(δ,\varepsilon)$-Goldstein stationary point. We combine randomized smoothing with a novel unbiased reduction from comparisons to local value differences. By leveraging a Russian-roulette truncation on the Bernoulli-product expansion of the inverse link, we construct an exactly unbiased estimator for directional differences. This estimator has finite expected cost and variance scaling quadratically with the function gap, $\mathcal{O}(B^2)$, under mild conditions. Plugging this into the smoothed gradient identity enables a standard nonconvex SGD analysis, yielding explicit comparison-complexity bounds for common symmetric links such as logistic, probit, and cauchit. |
| title | Nonsmooth Optimization with Zeroth Order Comparison Feedback |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.05622 |