¿Tasa de convergencia al resolver la optimización regularizada L1 mediante el descenso de coordenadas con un paso diminuto?

Question

Me pregunto si existe un resultado establecido para la tasa de convergencia cuando se resuelve la optimización regularizada L1 mediante el descenso de coordenadas con un paso diminuto. Por "paso minúsculo" me refiero a que el paso se fija siempre en una constante positiva muy pequeña, sin que intervenga ninguna de esas técnicas de selección de pasos.

Answer 1

Un resultado débil derivado de Boyd & Vandenberge "Convex Optimization" p. 479 es que para $l_1$ -(descenso por coordenadas), con un tamaño de paso de $t=\frac{1}{M}$ tenemos que $$ f(x^{(k)}) - p^* \leq c^k(f(x^{(0)})-p^*)\\ c = \left(1-\frac{m}{Mn}\right) < 1 $$ donde el hessiano de $f$ está limitada por $MI\succeq \nabla^2 f(x) \succeq mI$ . Te aconsejo que mires esa sección para ver si puedes conseguir algo mejor.

EDIT: Esto no responde al 100% a la pregunta original, mis disculpas. Sin embargo, $l_1$ -Los programas regularizados pueden ser refundidos como SOCP. En las páginas 599 y 601 de la citada referencia se enumeran algunas técnicas de optimización.