Minimizing an upper bound of objective function

Question

In many machine learning problems, you often have an objective function (e.g., cost, loss, error) that you want to minimize. Instead of directly minimizing this objective function, I sometimes see papers that derive the upper bound of the objective function, and then minimize the upper bound version instead. The reason for this seems to be that the original objective cannot be obtained by the data we have at hand, or just hard to minimize for some reasons.

My question is, does it make sense to minimize the upper bound? Are there guarantees that they lead to the same solution? My concern is that the minimizer can obviously become different in the two cases. If this is the case, do we know how close the two can be? Are there good textbooks or papers that explain these issues?

Thank you very much for your help!

Answer 1

In many cases, the real function that you want to minimize is something that you cannot reasonably compute explicitly (e.g. in Bayesian statistics, you oftentimes have a formula integrating over all the possible combinations of something, which are too much for even the best supercomputer), or for which there is no known formula or procedure that can minimize it directly (e.g. in discrete optimization).

In that case, if you cannot compute or minimize the function itself, it makes sense to minimize something that either correlates highly with the function (e.g. a sampled estimate, or some approximation that replaces true values with other estimations), or an upper-bound (as long as it is a reasonable) - in the second case, you know that if you take this upper bound from something like $10^{20}$ to $10^-3$, the initial parameters would very likely have resulted in a worse value for the function that the ones you obtained by minimizing the upper bound.

In some cases, it can be proved that the optimal value of the function is within some percentage of the solution that maximizes the upper bound (quite common in discrete optimization), but this is oftentimes not the case (e.g. in Bayesian statistics), and what you get is NOT BY ANY MEANS the true global optimum for the original function, but something that is nevertheless better than random and feasible to calculate on your computer.

Now, you might argue that there are black-box methods such as evolutionary search that could minimize pretty much any function that you can evaluate directly, but these oftentimes lead to worse solutions than minimizing the upper bound, require more function evaluations, are much, much slower, and impractical if you have too many parameters, while the upper bounds can oftentimes be reasonably minimized with faster methods that rely on assumptions such as differentiability, smoothness, Lipschitz continuity, etc.

In short: the optimal solution for the original function and for the upper bound are indeed different, but if you cannot minimize the original function directly, you can still get a decent solution (not the best one) by minimizing the upper bound.