0
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Not knowing anything about the function, it is impossible. It could even contain rand() ! $\endgroup$
    – 1NN
    Commented Feb 6 at 16:42
  • $\begingroup$ @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. $\endgroup$
    – XerneraC
    Commented Feb 6 at 17:42
  • 3
    $\begingroup$ 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. $\endgroup$
    – 1NN
    Commented Feb 6 at 18:44
  • $\begingroup$ @1NN I'm pretty much certain my mystery function is both continuous and differentiable. I'm willing to just assume that about my function. $\endgroup$
    – XerneraC
    Commented Feb 8 at 16:29
  • $\begingroup$ This might be better suited for math.stackexchange.com, don't you think? $\endgroup$
    – fuz
    Commented Feb 8 at 16:48

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm sorry for not stating this in the original post. I'm assuming my function to be both continuous and differentiable. $\endgroup$
    – XerneraC
    Commented Feb 8 at 16:35
  • $\begingroup$ @XerneraC, see updated answer. $\endgroup$
    – D.W.
    Commented Feb 8 at 22:52
2
$\begingroup$

The answer by @D.W. is correct that any search space will need some structure in order to make progress. However, I think it would be pessimistic to conclude that the No Free Lunch theorems apply; since they assume uniform sampling from the space of all functions, which is unrealistic.

For example, it seems reasonable to limit ourselves to solving computable functions; and at least those are enumerable! It also seems reasonable to bias in favour of simple functions rather than complex ones (to avoid over-fitting, etc.), although there's lots of room to argue about the details of this.

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.

Once an approximation has been found, you can try minimising that using standard (white-box) optimisation procedures, and use that value as a (very!) approximate minimum for your original, unknown function. Note that your choice of optimisation method may also impose more assumptions on your search space (e.g. continuity, differentiability, etc.).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.