Calculating gradient for regression methods

Question

I have the lasso regression formula: $\left \| y-X\beta \right \|_2^2 st. \left \| \beta \right \|_1$ in a loop I am computing the value of $\beta$ until the algorithm stops.

Sometimes the algorithm is not stopping because it is reaching a local minimum and is computing the same values of $\beta$.

At that moment I want to say if the gradient is smaller than a value e.g. $10^-3$ the algorithm should stop.

The problem is I computed the gradient for the Loss so: $\Delta L(\beta;X,y)=2X^t(y-X\beta)$ which gives me a vector, that I cannot compare with the value $10^-3$

Is there any other formula that I could use to calculate the gradient, that would return a value?

Answer 1

The usual thing to do when evaluating nearness of a gradient to zero is to use the infinity norm of the gradient. I.e., terminate if the largest magnitude of any element is less than or equal to the specified threshold, such as 1e-3.

$\left\|gradient\right\|_{inf} \le$ 1e-3

That said, either you should be solving an unconstrained problem with another term $\lambda\beta$ in the objective, also contributing to the gradient. Or you should be solving a constrained problem with constraint $\left \| \beta \right \|_1 \le \lambda$, in which case your optimality condition is wrong - see https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

However, presuming $\lambda \ge 0$, both formulations are convex optimization problems, and therefore, there should be no local minimum which is not a global minimum. Presumably your algorithm is wrong and maybe you are just doing ordinary least squares. But that matter is out of scope of this question.