Function-free Optimization via Comparison Oracles

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(dlog(d/ε)) comparisons, nearly matching a lower bound of Omega(dlog(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(dD2/ε2) comparisons over O(D2/ε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 Omega(D2/ε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.