On the geometry of optimization based on the exponential family relaxation

In this thesis, we present a geometric perspective on the study of meta-heuristics in optimization that belong to the paradigm of Model-based Search (MBS). We describe a geometric framework for the study of the behavior of model-based algorithms, based on notions of Information Geometry (IG). In particular, we focus on the optimization of pseudo-Boolean functions, i.e., real-valued functions defined over a vector of binary variables, in the black-box context when the analytic formula of the function to be minimized is unknown. The algorithms that belong to MBS introduce a statistical model over the original search space associated to the optimization problem, and exploit it, in order to guide the search for the optimum towards regions that with higher probability could include the global optimum. Such paradigm can be applied in both the discrete and the continuous domain, and it provides a unifying view over many algorithms and techniques in different communities, in particular in Evolutionary Computation (EC), and in Stochastic Optimization (SO), as well as other approaches in optimization, such as the Method of Moments (MoM), and Linear Programming (LP) and Semi-definite Programming (SDP) relaxations, among the others. In order to study the behavior of model-based algorithms, we introduce the optimization problem of the stochastic relaxation, i.e., the minimization of the expected value of the original function with respect to a density in a given statistical model. The stochastic relaxation is a function defined over a statistical model for the original search space, and its variables are the parameters that identify a density in the model. By solving the new optimization problem, and by sampling its solution, we can obtain points that are feasible for the original problem, and under some conditions, correspond to global optima. At different extents, MBS algorithms search for the optimum of a function by minimizing the stochastic relaxation, often with iterative approaches that generate a sequence of densities in the statistical model. Such sequences can be produced in different ways, for instance by following the direction of the gradient of the stochastic relaxation, as in gradient descent algorithms; by employing techniques based on selection of the sample, estimation of the correlations, and then sampling, as in Estimation of Distribution Algorithms (EDAs); or by estimating and sampling a probabilistic model of the function to be minimized, as in the Distribution Estimation using Markov Random Fields (DEUM) framework, a relatively new family of algorithms in EC. In our research, we focus on statistical models that belong to the exponential family of probability distributions, a class of statistical models well known and used in statistics, which includes many common distributions, both in the continuous and in the discrete case. We introduce a geometric framework, based on IG, for the study of the exponential family, which allows us to describe properties of the model and of the stochastic relaxation, independently of the specific parametrization. Such approach provides a unifying perspective on different techniques and heuristics in MBS, and allows the comparison of algorithms that at first sight appear different and incomparable. The theoretical analysis we develop in the thesis focus on the characterization of the tangent space at each point of the exponential family, in order to the study the direction of maximum decrement of the stochastic relaxation, and on the description of the topological closure of the exponential family, to identify limits of sequences of densities in the model. In particular, we derive the formula for the natural gradient of the stochastic relaxation, that is, the gradient evaluated with respect to the Fisher information metric. Differently from the regular gradient with respect to the natural parameters of the exponential family, the natural gradient has the intrinsic property of being invariant with respect to the parametrization for the model, and is known to suffer less from premature convergence in case of large plateaus. For these reasons, the natural gradient identifies a better candidate direction for gradient descent algorithms in MBS compared to the regular gradient. Moreover, the geometrical framework we introduce allows to compare gradient-based methods and function modeling techniques, where probabilities of a point in the search space are estimated according to the value of the function. Indeed, under some hypotheses, we show how a step in the direction of the gradient is equivalent to an estimation of a distribution where probabilities are proportional to the value of the function. This provides a new perspective on the behavior of many existing algorithms in the MBS literature, in particular in the DEUM framework. In a single generation approach, an EDA learns a model for the variables of the function and estimates the parameters of a distribution from a subset of the initial sample only once. Then, the estimated distribution is sampled, in order to look for the minimum of the function. In such a scenario, the probability of a model-based algorithm to consistently identify the global optimum of a function, strongly depends on the ability to correctly identify the relevant interactions that appear among the variables of the function. Our analysis proves how the landscape of the stochastic relaxation of a given function depends on the choice of the statistical model, and how the presence of local minima is determined by some missing interactions among the sufficient statistics of the exponential family. Follows that, in black-box contexts, model selection is crucial in order to identify the relevant interactions among the variables of a function, and thus obtain a good model for the stochastic relaxation. For this reason, many model-based algorithms rely on efficient model selection techniques from statistics and machine learning, able to estimate statistical models in the high-dimensional setting. In the thesis, we see how model selection in MBS can be formalized as a sparse linear regression problem, which in turn, under some assumptions, corresponds to an estimation of the gradient of the function evaluated with respect to the uniform distribution. We exploit such relationship between gradient estimation and linear regression, and we present a novel algorithm for model selection based on $\ell_1$-norm penalization. In this thesis we focus on gradient descent techniques, based on the natural gradient, and we present efficient algorithms in the Stochastic Natural Gradient Descent (SNGD) framework able to find the global minimum of well known benchmarks in pseudo-Boolean optimization. Due to the properties of the exponential family we estimate the natural gradient by evaluating empirical covariances, and as a consequence of the robustness of natural gradient, we show how SNGD requires a sample of smaller size, and thus a reduced number of functions evaluations, compared to other techniques in EC. In the last part of the thesis, we present an alternative approach to model selection in MBS, which we called Function Composition Algorithm (FCA). The idea is that of applying a transformation to the original variables in the function to obtain a new set of variables, by the choice of a proper one-to-one mapping. Next, a low dimensional statistical model is employed in the new space, and once the population has been transformed, estimation and sampling are performed as in a regular EDA. The choice of the model corresponds implicitly to the choice of a different model in the original space, which in turn depends on the specific transformation among the variables. By iteratively choosing different transformations, estimating a distribution and sampling, we identify a sequence of densities each belonging to a low dimensional exponential family, able to capture higher order interactions among the variables. All algorithms we propose in the thesis have been evaluated with respect to a set of benchmarks of increasing difficulty, and their performance have been compared with other algorithms in the literature of MBS, and in particular EDAs. This thesis provides contributes at different levels. In particular, it goes into the direction of linking theory and practice in MBS, by introducing a theoretical framework based on a geometric perspective for a rigorous analysis of different model-based algorithms. The theoretical analysis not only provides a novel and unifying perspective on the subject, but also it serves as a motivation for the proposal and definition of new and efficient algorithms for black-box pseudo-Boolean optimization.

Questa tesi propone una prospettiva di tipo geometrico, per lo studio di meta-euristiche all'interno del paradigma di ottimizzazione basata su modello (MBS). In particolare, si presenta un framework geometrico per l'analisi del comportamento di algoritmi basati su modello, che trae fondamento da nozioni di geometria dell'informazione (IG). L'analisi si concentra sull'ottimizzazione di funzioni pseudo-Booleane, ovvero funzioni a valori reali definite su un vettore di variabili binarie, in particolare nel contesto black-box, dove la formula analitica della funzione da minimizzare non è nota. Gli algoritmi che appartengono alla MBS introducono un modello statistico sullo spazio di ricerca associato al problema di ottimizzazione e lo sfruttano con lo scopo di guidare la ricerca per l'ottimo globale verso regioni dello spazio che, con maggiore probabilità, potrebbero contenere l'ottimo globale. Tale paradigma può essere applicato tanto nel caso discreto quanto nel caso continuo, e fornisce un punto di vista comune rispetto ad algoritmi e tecniche applicate in diverse comunità scientifiche, in particolare in computazione evolutiva (EC) e in ottimizzazione stocastica (SO). La MBS fornisce altresì una chiave di lettura per altri paradigmi, quali il metodo dei momenti (MoM), e i rilassamenti in programmazione lineare (LP) e in programmazione semidefinita (SDP). Al fine di analizzare il comportamento degli algoritmi basati su modello, si introduce il problema di ottimizzazione del rilassamento stocastico, ovvero la minimizzazione del valore atteso della funzione originale rispetto ad una densità in un dato modello statistico. Il rilassamento stocastico è una funzione definita su un modello statistico per lo spazio originale di ricerca, e le sue variabili sono costituite dai parametri che identificano le diverse densità nel modello. Risolvendo il nuovo problema di ottimizzazione e campionando è possibile ottenere soluzioni ammissibili per il problema originale che, sotto certe condizioni, corrispondono all'ottimo globale. Sotto diversi aspetti, gli algoritmi basati su modello ricercano l'ottimo della funzione minimizzando il rilassamento stocastico, spesso impiegando metodi iterativi che generano successioni di densità nel modello statistico. Tali successioni possono essere prodotte con diversi criteri, ad esempio seguendo la direzione del gradiente del rilassamento stocastico, come negli algoritmi di discesa del gradiente, oppure impiegando tecniche basate su selezione del campione, stima della correlazioni tra le variabili, e campionamento, come negli algoritmi di stima della distribuzione (EDA). Altre tecniche che rientrano nel paradigma della MBS ricercano l'ottimo stimando e successivamente campionando un modello probabilistico della funzione originale, come ad esempio gli algoritmi che appartengono al framework chiamato DEUM, introdotto recentemente nella letteratura di EC. La ricerca in questa tesi si concenta su modelli statistici che appartengono alla famiglia esponenziale, una classe che include un diversi modelli molto utilizzati in statistica, sia nel caso continuo che nel caso discreto. Per un'analisi formale della MBS introduciamo un framework geometrico basato su IG, che ci consente di studiare le proprietà del modello e del rilassamento stocastico indipendentemente dalla specifica parametrizzazione. Tale approccio ci fornisce una prospettiva comune su diverse tecniche ed meta-euristiche, che a prima vista appaiono diverse e non confrontabili. L'analisi teorica che abbiamo sviluppato nella tesi si concentra sulla caratterizzazione dello spazio tangente della famiglia esponenziale, col fine di studiare la direzione di massima decrescita del rilassamento stocastico, e sulla descrizione della chiusura topologica del modello statistico, con l'obiettivo di identificare i limiti di successioni prodotte da algoritmi basati su modello. In particolare, abbiamo derivato le formule per il gradiente naturale del rilassamento stocastico, ovvero il gradiente valutato rispetto alla metrica dell'informazione di Fisher. A differenza del gradiente naturale, calcolato rispetto ai parametri naturali della famiglia esponenziale, il gradiente naturale ha la proprietà intrinseca di essere invariante rispetto alla parametrizzazione del modello, e di soffrire meno di problemi di convergenza prematura, in presenza di plateau. Per queste ragioni, per gli algoritmi di discesa del gradiente, il gradiente naturale identifica una miglior direzione di ricerca rispetto al gradiente regolare. Il framework geometrico introdotto ci consente di confrontare direttamente metodi basati sul gradiente, con tecniche che stimano modelli probabilistici per la funzione da minimizzare, dove le probabilità di un punto nello spazio di ricerca dipendono dal valore della funzione. Infatti, sotto certe ipotesi, è possibile dimostrare come un passo nella direzione del gradiente equivale ad una stima delle probabilità proporzionali al valore della funzione. Ciò fornisce una nuova prospettiva sul comportamento di diversi algoritmi esistenti nella letteratura MBS, in particolare per il framework DEUM. Negli approcci black-box basati su singola generazione, un EDA apprende un solo modello statistico e stima i parametri della distribuzione partendo da un sottoinsieme della campione iniziale. Successivamente, la distribuzione stimata viene campionata, per cercare il minimo della funzione. In tale scenario, la probabilità di un algoritmo di identificare in modo sistematico l'ottimo globale di una funzione dipende fortemente dalla capacità di identificare le interazioni rilevanti tra le variabili. La nostra analisi dimostra come la presenza di punti critici per il gradiente del rilassamento stocastico di una funzione dipende dalla scelta del modello statistico, e che la presenza di minimi locali è determinata dalla mancanza tra le statistiche sufficienti della famiglia esponenziale di monomi che rappresentano interazioni della funzione. Come conseguenza, nel contesto black-box, la selezione del modello diventa cruciale per poter identificare le interazioni rilevanti in una funzione, e quindi ottenere un buon modello per il rilassamento stocastico. Per questa ragione, molto algoritmi in MBS si affidano ad efficienti tecniche di selezione del modello presenti in statistica e in machine learning, capaci di effettuare stime robuste quando il numero di variabili è elevato. Inoltre, in questa tesi, dimostriamo come la selezione del modello nella MBS possa essere formalizzata come un problema di regressione lineare sparso, che a sua volta, sotto certe ipotesi, corrisponde ad una stima del gradiente della funzione valutata rispetto alla distribuzione uniforme. La corrispondenza tra stima del gradiente e la regressione lineare, fornisce le basi per nuovi algoritmi per la selezione del modello basato su penalizzazione in norma l1. Gli algoritmi studiati in questa tesi implementano una discesa del gradiente stocastica, basata sul gradiente naturale. In particolare viene presentata una famiglia di algoritmi chiamata SNGD, capace di identificare l'ottimo globale di una serie di benchmark ben noti in ottimizzazione pseudo-Booleana. Come conseguenza delle proprietà della famiglia esponenziale, il gradiente naturale viene stimato mediante covarianze empiriche, ottenendo delle stime robuste della direzione di massimo decremento del rilassamento stocastico. Inoltre, rispetto al gradiente regolare, ed ad altre tecniche in EC, il numero di campioni è ridotto, e di conseguenza anche il numero di valutazioni della funzione. Nell'ultima parte della tesi, viene presentato un approccio alternativo alla selezione del modello in MBS, chiamato FCA. L'idea alla base di questo approccio consiste nell'applicare una trasformazione delle variabili originali della funzione, al fine di ottenere un nuovo insieme di variabili. Successivamente, un modello statistico con un numero ridotto di parametri viene scelto nel nuovo spazio, e una volta che la popolazione è stata trasformata, la stima e il campionamento avvengono come in un EDA. La scelta di un modello nello spazio trasformato corrisponde implicitamente alla scelta di una diversa famiglia esponenziale nello spazio originale, che a sua volta dipende dalla specifica trasformazione scelta per le variabili. Ripetendo in modo iterativo la scelta della trasformazione, la stima e il campionamento, è possibile identificare una sequenza di densità ognuna delle quali appartiene ad una famiglia esponenziale di dimensione ridotta, capace di catturare interazioni di ordine elevato tra le variabili. Tutti gli algoritmi proposti nella tesi sono stati valutati rispetto ad un set di benchmark di difficoltà crescente, e le loro performance sono state confrontate con quelle di altri algoritmi nella letteratura MBS, e in particolare con altri EDA. I contributi di questa tesi si collocano a diversi livelli. Da un lato si fornisce un collegamento tra la teoria e la pratica nella MBS, introducendo un framework teorico basato su una prospettiva geometrica, che consente una rigorosa analisi di diversi algoritmi basati su modello. Dall'altro lato, l'analisi teorica non solo consente una nuova prospettiva su algoritmi esistenti, ma anche fornisce la motivazione per la definizione di nuovi ed efficienti algoritmi per l'ottimizzazione black-box di funzioni pseudo-Booleane.