# Find minimum of a function only knowing the ordering of a set of input points

Suppose I have a function $$f: \mathbb{R}^n\rightarrow\mathbb{R}$$. All I know about the function is, I have a set of pairs of vectors ($$\vec{v}_a$$, $$\vec{v}_b$$) for which I know which one is greater (i.e. I know that $$f(\vec{v}_a)>f(\vec{v}_b)$$). I want to find the minimum of the function (or at least a good approximation). What is a way in which I could compute an approximation for the input for which the function is minimal, only given a set of pairs of vectors for which I know the ordering?

Edit: As a lot of people have pointed out, $$f$$ is not constrained enough. With the "All I know about the function" line, I've kind of overgeneralized my problem. I'm pretty much certain my mystery function is both continuous and differentiable. I'm willing to just assume that about my function.

• Not knowing anything about the function, it is impossible. It could even contain rand() !
– 1NN
Commented Feb 6 at 16:42
• @1NN I mean technically yes, but it is not. Function is somewhat well-behaved, I know that. I mean, neural networks are also considered "universal function approximators" even though they cannot approximate a rand() function. Commented Feb 6 at 17:42
• You can really only answer this in a general way if you know the function has continuity. "Continuity refers to a property of functions in which, intuitively, small changes in the input of the function result in small changes in the output. For a function to be continuous at a point, the limit of the function as it approaches that point must exist and be equal to the function's value at that point." Cited ChatGPT 4, verified by myself.
– 1NN
Commented Feb 6 at 18:44
• @1NN I'm pretty much certain my mystery function is both continuous and differentiable. I'm willing to just assume that about my function. Commented Feb 8 at 16:29
• This might be better suited for math.stackexchange.com, don't you think?
– fuz
Commented Feb 8 at 16:48

You can't. The function could be anything. For example, consider

$$f(x) = \begin{cases} g(x) &\text{if }x \ne \alpha\\ -10^{100} &\text{if } x = \alpha \end{cases}$$

where $$\alpha \in \mathbb{R}^n$$ is some obscure point (maybe very far from the origin). Then any reasonable algorithm might never evaluate $$f$$ on $$\alpha$$ and in that case will have no hope of finding the minimum.

You need additional structure on the function (e.g., that it come from a particular class of functions with nice properties) to be able to say anything. The best algorithm will depend on the specifics of that structure. (Just saying "somewhat well-behaved" is not specific enough to allow a good solution.) There is no free lunch.

Another approach might be to use Bayesian optimization. In this approach, we try to fit an inferred function $$f^*$$ that seems consistent with the observations, and then apply optimization to $$f^*$$. More precisely, we infer a conditional distribution on $$f^*$$, conditioned on the observations, and then use that distribution to figure out what is the best next value of $$x$$ to evaluate $$f$$ on.

The existing methods for Bayesian optimization assume that you have a way to observe the value of $$f$$ at specific points $$x$$, not just to compare pairs of outputs, so those methods can't be applied directly to your problem. It might be possible to extend existing methods to handle observations of the form you have. The Bradley-Terry model might also be helpful: you might be able to learn a model $$g:\mathbb{R}^n \to \mathbb{R}$$, e.g., a neural network, such that $$f(x_1)$$ is predicted by this model to be larger than $$f(x_2)$$ with probability $$e^{g(x_1)}/(e^{g(x_1)}+e^{g(x_2)})$$, and then fit $$g$$ to maximize the likelihood of the observations.

This all sounds terribly speculative, and it will probably easier to find a way to gather more data, e.g., to observe the actual value of $$f(x)$$, rather than just obtaining pairwise comparisons.

• I'm sorry for not stating this in the original post. I'm assuming my function to be both continuous and differentiable. Commented Feb 8 at 16:35
My first thought is to Universal Search, which is about the best we can do for inverting a black-box function $$f$$ on a given output $$y$$. It searches for an $$x$$, in order of increasing complexity, until it finds one such that $$f(x) = y$$. Your problem has more structure than this, but a naive approach could use Universal Search to find an approximation of your function, e.g. a program $$p$$ such that $$\bigwedge_{(a,b) \in V} eval(p, a) > eval(p, b)$$ for the given set of constraints $$V$$. Note that your choice of language for $$p$$ (and corresponding implementation of $$eval$$) determines what counts as "simple", as the complexity measure being minimised is $$length(p) + log(\sum_{(a,b) \in V} time(eval(p, a)) + time(eval(p, b)))$$. Traditionally Universal Search uses a Turing-complete programming language (e.g. Binary Lambda Calculus, if you want a "nothing up my sleeve" language); but that is usually impractical for real workloads, and can be weakened to some less-expressive (and hence more structured) model, like ANNs, polynomials, etc. making the approach more like Minimum Description Length.