Function-free Optimization via Comparison Oracles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918509977534464 |
|---|---|
| author | Scheinberg, Katya Xiong, Zikai |
| author_facet | Scheinberg, Katya Xiong, Zikai |
| contents | In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. The goal is to find the most preferred feasible point, which we call the optimal solution. This model arises in preference- and ranking-based settings where objective values and derivatives are unavailable or meaningless. Even when a representative function exists, it may be nonsmooth, nonconvex, or discontinuous. We develop an analytical and algorithmic framework based on the geometry of preference level sets, which remains well-defined from comparisons alone. We introduce the level-set optimality gap, the distance from a preference level set to the optimal solutions, and the regularity radius, a stationarity certificate. Under regularity of the preference relation in a $d$-dimensional Euclidean space, we estimate normal directions to accuracy $ε$ using $O(d\log(d/ε))$ comparisons, nearly matching a lower bound of $Ω(d\log(1/ε))$. Under convexity, regularity, and a local growth condition on the regularity radius, the resulting normal direction descent method reaches an $ε$ level-set optimality gap using at most $\widetilde O(dD^2/ε^2)$ comparisons over $O(D^2/ε^2)$ normal direction estimation steps, where $D$ is the distance from the initial point to the optimal solutions. This number of steps matches the lower bound of $Ω(D^2/ε^2)$ for normal direction span-based methods. Since prior knowledge in practical applications is usually limited, we also develop adaptive schemes for estimating the normal direction and solving the optimization problem. They match the fixed-parameter complexity bounds up to logarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26867 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Function-free Optimization via Comparison Oracles Scheinberg, Katya Xiong, Zikai Optimization and Control In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. The goal is to find the most preferred feasible point, which we call the optimal solution. This model arises in preference- and ranking-based settings where objective values and derivatives are unavailable or meaningless. Even when a representative function exists, it may be nonsmooth, nonconvex, or discontinuous. We develop an analytical and algorithmic framework based on the geometry of preference level sets, which remains well-defined from comparisons alone. We introduce the level-set optimality gap, the distance from a preference level set to the optimal solutions, and the regularity radius, a stationarity certificate. Under regularity of the preference relation in a $d$-dimensional Euclidean space, we estimate normal directions to accuracy $ε$ using $O(d\log(d/ε))$ comparisons, nearly matching a lower bound of $Ω(d\log(1/ε))$. Under convexity, regularity, and a local growth condition on the regularity radius, the resulting normal direction descent method reaches an $ε$ level-set optimality gap using at most $\widetilde O(dD^2/ε^2)$ comparisons over $O(D^2/ε^2)$ normal direction estimation steps, where $D$ is the distance from the initial point to the optimal solutions. This number of steps matches the lower bound of $Ω(D^2/ε^2)$ for normal direction span-based methods. Since prior knowledge in practical applications is usually limited, we also develop adaptive schemes for estimating the normal direction and solving the optimization problem. They match the fixed-parameter complexity bounds up to logarithmic factors. |
| title | Function-free Optimization via Comparison Oracles |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.26867 |