# Convex lower as opposed to upper bound?

Fundamental Question: Which of the options give useful surrogate for a non-convex function, the tightest convex lower or the tightest upper bound? (By useful, I mean with theoretical guarantees.)

I know that minimizing a lower bound, gives a lower bound on the minimum of the original objective. However I am not sure what can be argued about minimizing an upper bound.

Reason for the question is confusing observations I have observed:

• Observation 1: Zero-one loss function is non-convex, so every one minimizes a tight "upper bound" instead such as hinge loss as a surrogate. Arguments tell it is a good choice.
• Observation 2: Rank is not convex, so every one minimizes the tightest convex "lower bound" (the biconjugate, i.e. the trace norm; which is sum of singular values). Arguments tell it is a good choice.
• Observation 3: There are cases where sum of a loss and a regularizer is optimized, where the former is an upper bound of an original loss and the second one, is the lower bound.
• Minimizing the upper bound gives an upper estimate of the minimum of the non-convex function. – daw Aug 18 '16 at 12:26
• Did you possibly create the tags lower-bound and upper-bound? Did you clear them with more experienced users? I want to discuss their fate in Meta – Jyrki Lahtonen Oct 17 '16 at 17:30
• Yes, I think it was me, with the correct spelling though :). Well, not sure how should one clear tags with more experienced users. Does your question mean you think they are not very appropriate? Would be happy to know why. – user25004 Oct 17 '16 at 19:06
• user25004 The linked post on meta would be probably better place for your reply and further discussion of the tag. Anyway, if you want that he sees you comment, you should probably have pinged @JyrkiLahtonen. – Martin Sleziak Oct 17 '16 at 21:50
• @JyrkiLahtonen Yes, I think it was me, with the correct spelling though :). Well, not sure how should one clear tags with more experienced users. Does your question mean you think they are not very appropriate? Would be happy to know why. – user25004 Oct 17 '16 at 22:08