I don't think you can do this without making some assumptions about the form of the distribution you're characterising.
Consider two different random variables:
x1 = 0 with probability 1
x2 = 0 with probability (1-d) for some very small d, and 1 otherwise.
If all the data points you sample have outcome 0, does that mean your distribution is x1? Or does it just mean you haven't sampled enough to get a single non-zero point? If you can't tell the difference between these two distributions, obviously you can't accurately estimate the maximum.
As another example, note that a binomial distribution with large n approximates a normal distribution, so as n becomes large it gets harder and harder to distinguish between the two by sampling. But a binomial is always bounded, and a normal distribution is not - it doesn't even have a minimum or maximum.
edit to add: This issue applies even with continuous distributions. For example, let x0 be a random variable uniformly distributed in [0,1] and define random variable x3:
- if x0 >= d for some small positive d, x3 = x0.
- if x0 < d, x3 = x0 - k(d-x0)/d for some positive k.
x0 has minimum 0 and maximum 1, obviously. x3 has minimum of -k (when x0 = 0), and maximum 1. Both these distributions are continuous.
For x >= d, the cumulative distributions for these two functions are identical: p(x3 >= x) = p(x0 >= x) = 1-x.
Suppose I give you some extra information: I tell you that your distribution is either x0, or x3 with k=100. Given this additional information, finding the minimum is equivalent to figuring out whether you're sampling from x0 or x3.
Let's make the problem easier again, by saying that you can sample uniformly from the mystery distribution.
Since these two variables have probability (1-d) of giving an identical outcome, it should be clear that you need O(1/d) samples to figure out which one it is. If you observe any negative value, you know you're sampling from x3 and hence minimum = -100; if you run >> 1/d samples without ever getting a negative, you can be pretty sure you're sampling from x0.
But if I don't tell you the value of d, then you can never be certain of the difference between "sampling from x0" and "sampling from x3 but haven't taken enough samples to hit the part of the distribution where they behave differently". In order to decide that you'd taken enough samples, you'd need some sort of prior assumptions about what values of d are plausible.
So if it's not possible to be sure of the minimum even with uniform sampling and that particular restriction on the possible distributions, it certainly isn't possible without uniform sampling or that restriction.
edit #2: x3 isn't bounded between 0 and 1, but it's trivial to construct examples within those bounds that have the same sort of "equal with very high probability" behaviour.
