Abstract
Surrogate regret bounds, also known as excess risk bounds, bridge the gapbetween the convergence rates of surrogate and target losses, with linearbounds favorable for their lossless regret transfer. While convex smoothsurrogate losses are appealing in particular due to the efficient estimationand optimization, the existence of a trade-off between the smoothness andlinear regret bound has been believed in the community. That being said, thebetter optimization and estimation properties of convex smooth surrogate lossesmay inevitably deteriorate after undergoing the regret transfer onto a targetloss. We overcome this dilemma for arbitrary discrete target losses byconstructing a convex smooth surrogate loss, which entails a linear surrogateregret bound composed with a tailored prediction link. The construction isbased on Fenchel-Young losses generated by the convolutional negentropy, whichare equivalent to the infimal convolution of a generalized negentropy and thetarget Bayes risk. Consequently, the infimal convolution enables us to derive asmooth loss while maintaining the surrogate regret bound linear. Weadditionally benefit from the infimal convolution to have a consistentestimator of the underlying class probability. Our results are overall a noveldemonstration of how convex analysis penetrates into optimization andstatistical efficiency in risk minimization.