| Autor: |
Cai, HanQin, Mckenzie, Daniel, Yin, Wotao, Zhang, Zhenliang |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Applied and Computational Harmonic Analysis, 60 (2022): 242-266 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.acha.2022.03.003 |
| Popis: |
We study zeroth-order optimization for convex functions where we further assume that function evaluations are unavailable. Instead, one only has access to a $\textit{comparison oracle}$, which given two points $x$ and $y$ returns a single bit of information indicating which point has larger function value, $f(x)$ or $f(y)$. By treating the gradient as an unknown signal to be recovered, we show how one can use tools from one-bit compressed sensing to construct a robust and reliable estimator of the normalized gradient. We then propose an algorithm, coined SCOBO, that uses this estimator within a gradient descent scheme. We show that when $f(x)$ has some low dimensional structure that can be exploited, SCOBO outperforms the state-of-the-art in terms of query complexity. Our theoretical claims are verified by extensive numerical experiments. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
