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. Instead, our goal is to find a most-preferred feasible point, which we call an optimal solution. This model arises in preference- and ranking-based settings, where the objective values and derivatives are unavailable, meaningless, or non-identifiable. Even if a representative function exists for the preference relation, it may be nonsmooth, nonconvex, or even 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 a new optimality measure, the level-set optimality gap, defined as the distance from the preference level set to the optimal solutions, and also the regularity radius, which plays the role of a stationarity certificate. Under regularity of the preference relation in a \(d\)-dimensional Euclidean space, we propose a method for estimating normal directions to accuracy \(\epsilon\) using \(O(d \, \log(d/\epsilon))\) comparisons, nearly matching a lower bound of \(\Omega(d\, \log(1/\epsilon))\). Under convexity and regularity of the preference relation and a local growth condition on the regularity radius, the resulting normal direction descent method reaches an \(\epsilon\) level-set optimality gap using at most \(\widetilde O(dD^2/\epsilon^2)\) comparisons, over \(O(D^2/\epsilon^2)\) normal direction estimation steps. Here \(D\) is the distance from the initial point to the optimal set. This number of normal direction estimation steps matches the lower bound of \(\Omega(D^2/\epsilon^2)\) for normal direction span-based methods. Since prior knowledge in practical applications of function-free optimization is usually very limited, we also develop adaptive schemes for both estimating the normal direction and solving the optimization problem. These adaptive schemes match the fixed-parameter complexity bounds up to logarithmic factors.