Square Root Regularization and High Loss
The problem with using $L_p$ norm with $p &lt; 1$ for regularization is the gradient. 

Regularization term is used to force the parameters to be closer to zero. For this to work, when a parameter goes closer to zero, the gradient of regularization term, i.e. its contribution in updating the parameter, should decrease as well or at least remain constant. 

However, by going closer to zero, the gradient increases unboundedly for $p &lt; 1$, which causes radical changes in parameters, leading to your observations. Here is a visual plot for root $r$, absolute $a$, and squared $s$ regularization terms in one dimension (drawn here):



As you can see, for root regularization, the gradient explodes to infinity as we get closer to zero which is in conflict with our intention to bring the parameters close to zero. 

For the sake of completeness, here is what a 1D parameter update with root regularization looks like:
$$\theta_{n+1} = \theta_n + \alpha \frac{d L(\theta)}{d \theta}\Bigr|_{\theta=\theta_n} = \theta_n + \alpha \left(\frac{d l(\theta)}{d \theta}\Bigr|_{\theta=\theta_n} \pm \lambda \frac{1}{\color{red}{\sqrt{|\theta_n|}}}\right)$$
where $L(\theta) = l(\theta) + \lambda \sqrt{|\theta|}$. 

You can spot the trouble! The more we get close to zero, the less we get close to zero!