Proximal Gradient methods with Adaptive Subspace Sampling

Dmitry Grishchenko (1, 2) , Franck Iutzeler (1) , Jérôme Malick (1)

1 DAO - Données, Apprentissage et Optimisation
2 AMA - Analyse de données, Modélisation et Apprentissage automatique [Grenoble]

Many applications in machine learning or signal processing involve nonsmooth optimization problems. This nonsmoothness brings a low-dimensional structure to the optimal solutions. In this paper, we propose a randomized proximal gradient method harnessing this underlying structure. We introduce two key components: i) a random subspace proximal gradient algorithm; ii) an identification-based sampling of the subspaces. Their interplay brings a significant performance improvement on typical learning problems in terms of dimensions explored.

Domaines: Optimisation et contrôle [math.OC]

Dmitry Grishchenko, Franck Iutzeler, Jérôme Malick. Proximal Gradient methods with Adaptive Subspace Sampling. Mathematics of Operations Research, In press. ⟨hal-02555292v1⟩