Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has any name, or has ever been solved.

Input: A Random Oracle to function $f:[0,1]^n \rightarrow [0,1]$ from a concept class $C$. Additionally, $n$ points $x_1,\ldots,x_n$ in the domain.

Goal: Select an $i$ such that $E[f(x_i)]$ is as large as possible. We assume the function $f$ is randomly distributed amongst all functions in the class $C$ that agree with all the samples we have drawn.

One way to solve this problem is to draw many samples from $f$, create a hypothesis $h$, and choose the $x_i$ whose $h(x_i)$ is largest. There are two problems with this:

  • $h$ might not be representative of the set of all $f$'s that agree with the samples we've drawn.
  • To solve our problem it is not clearly necessary to learn $f$: for some classes $C$ might be a more efficient way to select a good $i$ without trying to learn $f$.

An example setting is where $C$ is the set of linear classifiers. In that case it should probably be quite easy to solve the problem. But what about other, more complicated classes?

The real version I'm interested in is that of agnostic learning of linear functions? we assume the function $f$ is somewhat correlated with a linear function, and the goal is to choose an i which maximizes $E[f(x_i)]$ to the best of our ability.


1 Answer 1


What you describe is a non-stochastic version of the "functional multi-arm bandit problem": you know you have an unknown function from some class C (does not have to be randomly selected), and you have query access to this function. The goal is to find the element which maximizes the function. As you say, depending on the class C, this may or may not require learning the function.

This paper by Amin, Kearns, and Syed exactly characterizes the query complexity of the problem: http://www.cis.upenn.edu/~mkearns/papers/haystack.pdf

  • $\begingroup$ Thanks @Aaron!! MY problem is actually most similar to a problem called Maximizing from Queries, described in the paper you point to, in page 4. $\endgroup$
    – greg
    Mar 11, 2014 at 18:44

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.