Ph.D. Defence

Hello everyone,

On Tuesday, $3^{\text{rd}}$ November my Ph.D. defence took place.

Title: Proximal Optimization with Automatic Dimension Reduction for Large Scale Learning.

Abstract: In this thesis, we develop a framework to reduce the dimensionality of composite optimization problems with sparsity inducing regularizers. Based on the identification property of proximal methods, we first develop a ``sketch-and-project” method that uses projections based on the structure of the correct point. This method allows to work with random low-dimensional subspaces instead of considering the full space in the cases when the final solution is sparse. Second, we place ourselves in the context of the delay-tolerant asynchronous proximal methods and use our dimension reduction technique to decrease the total size of communications. However, this technique is proven to converge only for well-conditioned problems both in theory in practice. Thus, we investigate wrapping it up into a proximal reconditioning framework. This leads to a theoretically backed algorithm that is guaranteed to cost less in terms of communications compared with a non-sparsified version; we show in practice that it implies faster runtime convergence when the sparsity of the problem is suficiently big.

Jury committee:

  • Jérôme Malick, CNRS, LJK, Thesis director.

  • Pascal Bianchi, Professor, Télécom ParisTech, Referee.

  • Peter Richtárik, Professor, KAUST, Referee.

  • Julien Mairal, Research Scientist, Inria Grenoble, Examiner.

  • Massih-Reza Amini, Professor, Université Grenoble Alpes, Thesis co-director.

  • Aleksander Gasnikov, Associate Professor, MIPT, Examiner.

  • Samuel Vaiter, CNRS, Délégation Centre-Est, Examiner.

  • Frank Iutzeler, Maître de Conférences, Université Grenoble Alpes, Thesis co-director.


First of all, I would like to thank my supervisors Frank Iutzeler, Massih-Reza Amini, and Jérôme Malick for their support during these three years. I have learned a lot from their advises and I am happy that I have been immersed in the hot research topic and had a chance to develop interesting ideas.

I would like to thank Pascal Bianchi and Peter Richtárik for accepting to review my thesis and sharing their suggestions about improvements both from the mathematical point of view and from the writing one. I am grateful to Julien Mairal, Aleksander Gasnikov, and Samuel Vaiter for accepting to be a part of the jury and for the interesting questions during the Q&A session.

Furthermore, I would like to thank all my friends who helped me a lot to stay on track, to have a lot of fun during the Ph.D., and to solve all the administrative issues. I am grateful to Anatoli Iouditski, Roland Hildebrand, and Panayotis Mertikopoulos for their very useful comments during the rehearsal that helps me to improve a lot. Also, I would like to thank all my math teachers from the school and universities and to the members of LJK/LIG.

Last but not least, I can not describe in words how I am grateful to my family. Their support and belief in me gave me the strength that was very important in these challenging times. Finally, I want to dedicate this thesis to my parents, who pushed me forward starting from the elementary school.

Dmitry Grishchenko
Senior Engineer