# Minimizing an upper bound of objective function

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!

• Can you link us to a paper for minimising the upper bound of a cost?
– Sam
Jul 19, 2018 at 11:13
• Thank you for the question, I will try to find examples and add them to the description. Jul 22, 2018 at 1:28

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.