Let $X \subseteq \mathbb{R}^{d}$ be set of $n$ points and let $y : X \to \left\lbrace -1, 1\right\rbrace$ be a labeling function. Let $C \geq 0$ be a regularization parameter and let the following denote the SVM formulation:
$$ \min\limits_{\substack{w \in \mathbb{R}^d \\ b \in \mathbb{R}}} \frac{ \left\| w \right\|_2^2}{2} + C \sum\limits_{x \in X} max\left\lbrace 0, 1-y(x) \left( x^Tw + b \right) \right\rbrace.$$
It was stated at Pegasos's Paper that when $b = 0$ then the problem is strongly convex yet when otherwise, this property of SVMs cease to exist.
Why the function above when the bias is incorporated into the problem's formulation, is not strongly convex? Can anyone explain this?
According to Page 16 of the paper (around Equation 23), there is no regularization term for $b$, thus it is not strongly convex. In order to see this easily, you can fix $w$, then there is no quadratic term for $b$, which implies the function is not strongly convex over the variable $b$.
If $b$ is fixed or set to $0$, then the optimization takes place over only $w$, then the function is strongly convex, due to the quadratic term.