OML
Optimization for machine learning II

Invited Session

Time Slot: Friday Morning

Room: 003

Chair: Vassilis Apidopoulos

Faster Randomized Block Sparse Kaczmarz by Averaging

Time: 9:00

Lionel Tondji (TU Braunschweig), Dirk Lorenz

The standard randomized sparse Kaczmarz (RSK) method is an algorithm to compute sparse solutions of linear systems of equations and uses sequential updates, and thus, does not take advantage of parallel computations. In this work, we introduce a parallel (mini batch) version of RSK based on averaging several Kaczmarz steps. Naturally, this method allows for parallelization and we show that it can also leverage large over-relaxation. We prove linear expected convergence and show that, given that parallel computations can be exploited, the method provably provides faster convergence than the standard method. This method can also be viewed as a variant of the linearized Bregman algorithm, a randomized dual block coordinate descent update, a stochastic mirror descent update, or a relaxed version of RSK and we recover the standard RSK method when the batch size is equal to one. We also provide estimates for inconsistent systems and show that the iterates convergence to an error in the order of the noise level. Finally, numerical examples illustrate the benefits of the new algorithm.

Asynchronous parallel block-coordinate forward-backward algorithm

Time: 9:20

Cheik Traoré (Università di Genova)

We are going to present our work on the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block- coordinates are updated in parallel, asynchronously and randomly according to an arbitrary probability distribution. In that work, we prove that the iterates generated by the algorithm form a stochastic quasi-Fejér sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.

Iterative regularization for convex regularizers with activation onto a priori information

Time: 9:40

Cristian Vega (University of Genoa), Cesare Molinari, Lorenzo Rosasco, Silvia Villa

Inverse problems are often reduced to solve a system of equationsin a stable way with respect to noise in the data. A typical approach to en-force stability and select a meaningful solution is to introduce a regularizer,which is minimized under the constraint given by the system of equations. Theregularization function is supposed to be convex, but not necessarily smoothneither strongly convex. In this paper, we propose and study two new iter-ative regularization methods, based on primal-dual algorithm, to solve theproblem above. Our analysis, in the noise free case, provides convergence ratesfor the Lagrangian and the feasibility gap. In the noisy case, it provides stabil-ity bounds and practical early-stopping rules with theoretical guarantees. Themain novelty is the exploitation of some a priori knowledge about the solutionset, i.e. redundant information. We discuss various approaches to take advan-tage of the redundant information, that are at the same time consistent withour assumptions and flexible in the implementation. Finally, we illustrate ourtheoretical findings with numerical simulations for robust sparse recovery and image reconstruction through total variation. We confirm the efficiency of theproposed procedures, comparing the results with state-of-the-art methods.Optimization for machine learning

GPU-based Implementations of MM Algorithms. Application to Spectroscopy Signal Restoration

Time: 10:00

Mouna Gharbi (Universite Paris-Saclay, Inria, CentraleSupelec, CVN, France), Emilie Chouzenoux, Jean-Christophe Pesquet, Laurent Duval

Restoration of analytical chemistry data from degraded physical acquisitions is an important task for chemists to obtain accurate component analysis and sound interpretation. The high-dimensional nature of these signals and the large amount of data to be processed call for fast and efficient reconstruction methods. Existing works have primarily relied on optimization algorithms to solve a penalized formulation. Although very powerful, such methods can be computationally heavy, and hyperparameter tuning can be a tedious task for non-experts. Another family of approaches explored recently consists in adopting deep learning to perform the signal recovery task in a supervised fashion. Although fast, thanks to their formulations amenable to GPU implementations, these methods usually need large annotated databases and are not explainable. In this work, we propose to combine the best of both worlds, by proposing unfolded Majorization-Minimization (MM) algorithms with the aim to reach fast and accurate methods for sparse spectroscopy signal restoration. Two state-of-the-art iterative MM algorithms are unfolded onto deep network architectures. This allows both the deployment of GPU-friendly tools for accelerated implementation, as well as the introduction of a supervised learning strategy for tuning automatically the regularization parameter. The effectiveness of our approach is demonstrated on the restoration of a large dataset of realistic mass spectrometry data.

Iterative regularization in classification via hinge loss diagonal methods

Time: 10:20

Vassilis Apidopoulos (Università di Genova)

Iterative (implicit) regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks.In this talk, we focus on iterative regularization in the context of classification. After contrasting this setting with that of inverse problems, we develop an iterative regularization approach based on using the hinge loss function. More precisely we present an inertial diagonal approach for which we show convergence as also rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.