### Estimating Max with Only Definite Integrals

Posted:

**Fri Sep 29, 2017 8:28 pm UTC**Hi guys! It's been a while.

I've hit a problem in my work that I could use a little help in. Unfortunately I cannot divulge the full details, so I'm formulating it as a purely mathematical problem.

The Problem:

I have a function f(x) that is defined over some real domain x = 0 to n, where n is known. f(x) is assumed to be continuous, smooth, and non-negative everywhere in the domain. My objective is to estimate a x

The Catch:

f(x) is unknown and inaccessible.

However, I do have access to an "oracle", O, which allows me to compute definite integrals of f(x) over any region in the domain.

O: (a,b) --> (|b-a|/n)(Integral{f(x)dx} from a to b)

Each query to the oracle is associated with a cost Q.

I can choose to have the oracle do multiple queries in parallel (ie. respond to multiple queries simultaneously for a single cost of Q). However this option requires I pay a one-time upfront cost of S per each additional query stream. S is on the order of 10Q.

Naive Solution:

1. Choose a desired accuracy, k.

2. Divide [0,n] into 1/k spaced intervals.

3. Compute the definite integrals across each 1/k interval.

4. Set x

This would solve the problem as long as f(x) doesn't have "spikes" with width narrower than 1/k. For a sufficiently large k, I can make this work.

The cost would be Q(n/p)k + S(p-1) if I choose to use p parallel streams. This is not ideal since it grows linearly with k and I have to make k large to ensure high probability of success.

Suggestions or tips for a more efficient approach?

I've hit a problem in my work that I could use a little help in. Unfortunately I cannot divulge the full details, so I'm formulating it as a purely mathematical problem.

The Problem:

I have a function f(x) that is defined over some real domain x = 0 to n, where n is known. f(x) is assumed to be continuous, smooth, and non-negative everywhere in the domain. My objective is to estimate a x

_{max}where f(x_{max}) >= f(x) for all x in the domain. The "accuracy" of my estimation is measured by 1/|x_{max}-x_{est}|.The Catch:

f(x) is unknown and inaccessible.

However, I do have access to an "oracle", O, which allows me to compute definite integrals of f(x) over any region in the domain.

O: (a,b) --> (|b-a|/n)(Integral{f(x)dx} from a to b)

Each query to the oracle is associated with a cost Q.

I can choose to have the oracle do multiple queries in parallel (ie. respond to multiple queries simultaneously for a single cost of Q). However this option requires I pay a one-time upfront cost of S per each additional query stream. S is on the order of 10Q.

Naive Solution:

1. Choose a desired accuracy, k.

2. Divide [0,n] into 1/k spaced intervals.

3. Compute the definite integrals across each 1/k interval.

4. Set x

_{est}= midpoint of interval with maximum definite integral.This would solve the problem as long as f(x) doesn't have "spikes" with width narrower than 1/k. For a sufficiently large k, I can make this work.

The cost would be Q(n/p)k + S(p-1) if I choose to use p parallel streams. This is not ideal since it grows linearly with k and I have to make k large to ensure high probability of success.

Suggestions or tips for a more efficient approach?