Enhancing safe screening rules using adaptive thresholding for regularized optimization problems

Abstract

La esparsidad es una propiedad ampliamente valorada en diversas aplicaciones de aprendizaje automático y procesamiento de se ́ nales pues permite una representación eficiente de datos y previene el sobreajuste en modelos de aprendizaje. A pesar de su amplia utilidad, el uso de la esparsidad para reducir las demandas computacionales sigue siendo un área activa de investigación. En optimización matemática, la esparsidad puede promoverse en las soluciones mediante técnicas de regularización o imponiendo restricciones explícitas. Recientemente se han propuesto técnicas como las reglas de cribado para explotar la esparsidad y disminuir los requerimientos computacionales de problemas de optimización a gran escala. Sin embargo, los métodos de cribado más avanzados actualmente disponibles proporcionan solo aproximaciones inexactas del soporte de la solución, descartando pocos elementos y, por lo tanto, ofreciendo ahorros computacionales limitados. Esta tesis contribuye con una extensión de las reglas de cribado seguro basada en umbralización adaptativa orientada a problemas de optimización regularizada. La regla de umbralización propuesta se fundamenta en la observación de que la métrica utilizada para identificar características no contribuyentes puede considerarse que presenta una distribución aproximadamente unimodal para fines prácticos. El enfoque propuesto fue incorporado en el algoritmo gradiente proximal acelerado (APG) / algoritmo de contracción iterativa rápida (FISTA), un optimizador que recientemente ha atraído atención debido a su tasa de convergencia teórica ́O (k−2). Para validar la técnica propuesta, se llevaron a cabo experimentos computacionales en múltiples contextos. Los resultados experimentales indican que el método propuesto proporciona mejoras de velocidad superiores tanto a las reglas de cribado seguro como a las de cribado fuerte en sus versiones estáticas (como etapa de preprocesamiento), tanto en conjuntos de datos sintéticos como reales, con una aceleración de hasta aproximadamente 33.9 veces. El método desarrollado en esta tesis fue presentado en un artículo de conferencia en la 2023 24th International Conference on Digital Signal Processing (DSP).

Sparsity is a widely valued property in several machine learning and signal processing applications as it enables efficient data representation and prevents overfitting in learning models. Despite its broad utility, the use of sparsity to reduce computational demands re- mains an active research area. In mathematical optimization, sparsity can be promoted in solutions through regularization techniques or by imposing explicit constraints. Recently, techniques such as screening rules have been proposed to exploit sparsity to diminish the computational requirements of large and huge-scale optimization problems. Nevertheless, current state-of-the-art screening methods provide only rough approximations of the solu- tion support, discarding few elements and thus yielding limited computational savings. This thesis contributes with an extension of safe screening rules based on adaptive thresholding aimed at regularized optimization problems. The proposed thresholding rule is based on the observation that the metric used to identify non-contributing features can be considered to have an approximate unimodal distribution for practical purposes. The proposed approach was embedded into the accelerated proximal gradient (APG) / fast it- erative shrinkage thresholding algorithm (FISTA), an optimizer that has recently attracted attention due to its theoretical convergence rate O (k−2). To validate the proposed technique, computational experiments were conducted across multiple contexts. Experimental results indicate that the proposed method provides greater speedups than both safe and strong screening rules in their static version (each implemented as a preprocessing stage) across synthetic and real datasets with a speedup of up to 33.9, approximately. The method developed in this thesis was presented in a conference article at the 2023 24th International Conference on Digital Signal Processing (DSP).