I came across a paper but the smooth approximation for the hinge loss function is wrong. Can someone guide me to the proper smooth approximation (using polynomials) of the function $$h(x)=\max(0,1x)$$ which is exact when $x \ge \rho$, where $\rho$ can be made arbitrarily small?

$\begingroup$ You might as well work with $max(0,x)$, which makes your bound involving $\rho$ make sense. And then you can work with a fixed $\rho$ ( $= 1$, say) $\endgroup$– David Roberts ♦Jan 7, 2011 at 5:35

$\begingroup$ But I don't know if you can do it with polynomials. $\endgroup$– David Roberts ♦Jan 7, 2011 at 5:35

$\begingroup$ The paper that you have linked works only for UIUC; please fix the link so that others can see what paper you are referring to. $\endgroup$– SuvritJan 7, 2011 at 10:03

$\begingroup$ Also, what about the approximation in: people.csail.mit.edu/jrennie/writing/smoothHinge.pdf $\endgroup$– SuvritJan 7, 2011 at 10:06

$\begingroup$ Sorry about the link. The paper can be viewed here: cs.uiuc.edu/homes/afarhad2/index_files/scene_discovery.pdf. Actually, I found the proper coefficients for the order 4 polynomial. The paper has a typo on page 5. Instead of $\frac{3}{2}x$ it should be $\frac{1}{2}x$. The link for the smooth quadratic hinge function was a great help. Thanks Suvrit. $\endgroup$– BernardJan 7, 2011 at 11:59
3 Answers
Here are the details for those who might feel too lazy to chase the links in the comments above.
The Hinge loss for $x \in R$ is defined as $$H(x) = \max(0, 1x)$$
Jason Rennie in his article "Smooth Hinge Classification" describes the following smooth version of the Hinge loss (a smoothed version was being sought because of discontinuity in the derivative at $x=1$).
Rennie defines (the definition seems natural enough that somebody might have also found a similar one; I will be happy to be corrected) the smoothed Hinge loss: $$H_s(x) = \begin{cases} \tfrac{1}{2}x & x \le 0,\\\\ \tfrac{1}{2}(1x)^2 & 0 < x < 1\\\\ 0 & x \ge 1 \end{cases}$$
This loss is smooth, and its derivative is continuous (verified trivially).
Rennie goes on to discuss a parametrized family of smooth Hingelosses $H_s(x; \alpha)$. Additionally, several other variations are possible, depending on what numerical behavior seems more appropriate for an application.

4$\begingroup$ Note that $H_s$ is $C^1$, not smooth in the usual sense (infinitely differentiable) (this is for random students wandering by, in case they are confused) $\endgroup$– David Roberts ♦Feb 4, 2011 at 22:34
The paper Differentially private empirical risk minimization by K. Chaudhuri, C. Monteleoni, A. Sarwate (Journal of Machine Learning Research 12 (2011) 10691109), gives two alternatives of "smoothed" hinge loss which are doubly differentiable.
The paper is linked here (pdf); the approximations are given p.1415 (p.10821083 in journal); see the extract 1 and extract 2.
I realize this is an old question, but it seems worth noting that the requested hinge function is probably the Huber loss. This is different from the ones discussed in other answers, and actually has a parameter $\rho \geq 0$ that can be made arbitrarily small. It can be defined as
$$ h(x ; \rho) = \begin{cases} 1  x & \text{ if } x \leq 1  \rho \\ \frac{1}{4\rho} (1  x + \rho)^2 & \text{ if } 1  \rho < x \leq 1 + \rho \\ 0 & \text{ if } x > 1 + \rho \end{cases} $$
As in the other answers, this is not "smooth" in the infinitelydifferentiable sense, but it is in $C^1$. It is straightforward to show that $\lim_{\rho \rightarrow 0} h(x ; \rho) = \max(1  x, 0)$ and it is exact for $x  1 \geq \rho$. This hinge function is sometimes used in SVMs [e.g., 1,2]. Here's a quick plot: