Scalable Gradient-Based Optimization Methods with Application to Supervised Learning

L’apprendimento supervisionato è una delle tecniche più ampiamente utilizzate nell’ambito del machine learning e, da un punto di vista matematico, può essere formulato come un problema di ottimizzazione a somma finita. Con la crescente disponibilità di dati e l’aumento della complessità dei modelli, negli ultimi decenni sono stati compiuti notevoli sforzi nello sviluppo di algoritmi di ottimizzazione che siano al tempo stesso scalabili ed efficienti. Tra gli approcci più comuni figurano quelli derivati dal metodo classico del gradient descent, basati sul calcolo del gradiente della funzione obiettivo. Tuttavia, in un contesto di apprendimento supervisionato, il calcolo esatto del gradiente risulta spesso costoso o persino irrealizzabile. Per questo motivo, due delle strategie più diffuse sono il metodo del gradiente incrementale (IG) e il gradiente stocastico (SGD), che si basano su approssimazioni del gradiente esatto. Questa tesi contribuisce alla linea di ricerca che mira a superare diversi limiti teorici e pratici delle versioni standard di tali metodi. In particolare, presentiamo tre contributi principali. Il primo riguarda il metodo IG, per il quale proponiamo un algoritmo che impiega una matrice di scaling al fine di accelerare la convergenza. Questo approccio viene applicato all’addestramento di un classificatore lineare multiclasse basato sul framework delle Support Vector Machine (SVM). Inoltre, introduciamo tecniche di preprocessing volte a migliorare l’accuratezza di classificazione di tale modello, ottenendo in alcuni casi prestazioni paragonabili a quelle dei modelli di deep learning. I restanti due contributi sono invece relativi al metodo SGD. Nel primo caso, proponiamo una strategia di line-search per la selezione automatica dello step-size, integrata nell’algoritmo SGD-AIS, un metodo basato su SGD che sfrutta l’importance sampling come tecnica di riduzione della varianza. Tale strategia affronta la problematica della scelta dello step-size, iperparametro che ha un impatto sostanziale sulle prestazioni dell’algoritmo ed è tipicamente oneroso da selezionare. Il secondo contributo consiste in un’estensione dell’algoritmo LISA (Line search based Stochastic first order Algorithm), un metodo SGD che combina tecniche di dynamic sampling e una procedura di line-search per la selezione dello step-size. In particolare, introduciamo un termine di momentum nella direzione di discesa, con l’obiettivo di accelerare la convergenza e aumentare la robustezza dell’algoritmo, soprattutto nel caso di funzioni obiettivo non convesse. Per ciascuno dei tre algoritmi proposti forniamo un’analisi teorica di convergenza, supportata da esperimenti numerici. In tutti i casi, il problema di test è un task di classificazione. Nel contesto IG ci concentriamo sull’addestramento del classificatore lineare multiclasse basato su SVM, mentre per i due metodi SGD valutiamo le prestazioni sia su un classificatore lineare binario sia su una rete di tipo CNN applicata a un problema di classificazione multiclasse.

Supervised learning is one of the most widely used techniques in machine learning and, from a mathematical perspective, it can be formulated as a finite-sum optimization problem. With the increasing availability of data and the growing complexity of models, significant efforts have been devoted in recent decades to the development of optimization algorithms that are both scalable and efficient. Among the most common approaches are those derived from the classical gradient descent algorithm, which is based on the computation of the gradient of the objective function. However, in a supervised learning setting, computing the exact gradient is often computationally expensive or even infeasible. For this reason, two of the most widely adopted strategies are incremental gradient (IG) and stochastic gradient descent (SGD), both of which rely on approximations of the true gradient. This thesis contributes to the research area that focuses on addressing several theoretical and practical limitations of the standard versions of these methods. Specifically, we present three main contributions. The first pertains to the IG method, for which we propose an algorithm that employs a scaling matrix to accelerate convergence. This approach is applied to the training of a multiclass linear classifier based on the Support Vector Machine (SVM) framework. Furthermore, we introduce preprocessing techniques aimed at improving the classification accuracy of this model, in some cases achieving performance comparable to those of deep learning models. The remaining two contributions are related to the SGD method. In the first case, we propose a line-search strategy for the automatic selection of the step-size, integrated into the SGD-AIS algorithm, an SGD-based method that leverages importance sampling as a variance reduction technique. This addresses the critical issue of step-size selection, which has a substantial impact on algorithm performance and is typically expensive to tune. The second contribution involves an extension of the Line search based Stochastic first order Algorithm (LISA) algorithm, an SGD-based method that combines dynamic sampling with a line-search procedure for step-size selection. In particular, we introduce a momentum term in the descent direction, aiming to accelerate convergence and improve the robustness of the algorithm, especially when dealing with non-convex objective functions. For each of the three proposed algorithms, we provide a theoretical convergence analysis, supported by numerical experiments. In all cases, the test problem is a classification task. In the IG setting, we focus on training the SVM-based multiclass linear classifier, while for the two SGD methods, we evaluate performance on both a binary linear classifier and a convolutional neural network applied to a multiclass classification task.