Implementation and Analysis of Gradient-Based Algorithms for Synthetic and Real Datasets
This project focuses on the implementation and experimental evaluation of optimization algorithms based on gradient methods, in the context of data science applications. The goal is to study their behavior and performance on both synthetic and real datasets.
We will implement three core optimization algorithms:
-
Gradient Descent (GD)
The classic gradient-based method used to minimize differentiable objective functions, updating all coordinates simultaneously in the direction of the negative gradient. -
Block Coordinate Gradient Descent with Gauss-Southwell Rule
A variant of coordinate descent where, at each step, only a subset (or block) of variables is updated. The Gauss-Southwell rule selects the most "promising" coordinates based on gradient magnitude, aiming for more efficient convergence. -
Coordinate Minimization
An iterative method where, at each iteration, a single coordinate is selected and minimized exactly, holding the others fixed. This is especially useful when the objective function is partially separable or when full gradient updates are computationally expensive.
The project is structured in two main phases. In the first phase, we will test and compare these algorithms on synthetic datasets. These datasets will allow us to clearly visualize and interpret convergence patterns, optimization paths, and algorithm behavior under controlled conditions.
In the second phase, we will apply the algorithms to real-world data from a selected dataset, focusing on a practical problem (e.g., regression or classification). This will help us evaluate robustness, scalability, and performance in realistic scenarios.
Throughout the project, we will include visualizations such as loss curves, decision boundaries, and coordinate updates to better understand and communicate the effectiveness of each method.
Implementazione e Analisi di Algoritmi Basati sul Gradiente per Dataset Sintetici e Reali
Il progetto ha l'obiettivo di implementare e analizzare algoritmi di ottimizzazione basati sul gradiente, nel contesto di applicazioni di data science. L'obiettivo principale è studiarne il comportamento e le prestazioni sia su dati sintetici che su dati reali.
Gli algoritmi che verranno sviluppati sono i seguenti:
-
Gradient Descent (GD)
Il metodo classico basato sul gradiente, utilizzato per minimizzare funzioni obiettivo differenziabili aggiornando tutte le coordinate contemporaneamente nella direzione del gradiente negativo. -
Block Coordinate Gradient Descent con Gauss-Southwell Rule
Una variante del metodo di coordinate in cui, a ogni iterazione, si aggiorna solo un blocco di variabili. L’uso della regola di Gauss-Southwell permette di selezionare le coordinate con il gradiente più rilevante, cercando di migliorare la velocità e l’efficienza della convergenza. -
Coordinate Minimization
Un metodo iterativo in cui, ad ogni passo, si seleziona una singola coordinata e si minimizza esattamente la funzione rispetto a essa, mantenendo fisse le altre. È particolarmente utile quando la funzione è parzialmente separabile o il calcolo del gradiente completo è troppo costoso.
Il progetto si articola in due fasi principali. Nella prima fase, testeremo e confronteremo gli algoritmi su dataset sintetici. Questo ci permetterà di visualizzare e comprendere meglio i percorsi di ottimizzazione e il comportamento degli algoritmi in condizioni controllate.
Nella seconda fase, applicheremo gli algoritmi a un dataset reale scelto, affrontando un problema pratico (come una regressione o classificazione), per valutarne la robustezza e le prestazioni in scenari più complessi.
Durante tutto il progetto, verranno realizzate visualizzazioni grafiche (curve di errore, traiettorie dei parametri, aggiornamenti delle coordinate) per facilitare la comprensione e la presentazione dei risultati ottenuti.