The Frank-Wolfe (FW) optimization algorithm, due to its projection free property, has gained popularity in recent years with typical application within the field of machine learning. In the stochastic setting, it is still relatively understudied in comparison to the more expensive projected method of Stochastic Gradient Descent (SGD). We propose a novel Stochastic Frank-Wolfe (SFW) algorithm, inspired by SGDo where random sampling is considered without replacement. In analogy to this abbreviation, we call the proposed algorithm SFWo. We consider a convex setting of gradient Lipschitz (smooth) functions over compact domains. Depending on experiment design (LASSO, Matrix Sensing, Matrix Completion), the SFWo algorithm, exhibits a faster or matching empirical convergence, and a tendency of bounded suboptimality by the precursor SFW. Benchmarks on both synthetic and real world data display that SFWo improves on the number of stochastic gradient evaluations needed to achieve the same guarantee as SFW. / Intresset för Frank-Wolfes (FW) optimeringsalgoritm har tack vare dess projektionsfria egenskap ökat de senaste åren med typisk tillämpning inom området maskininlärning. I sitt stokastiska uförande är den fortfarande relativt understuderad i jämförelse med den dyrare projicerande metoden Stochastic Gradient Descent (SGD). Vi föreslår en ny Stochastic Frank-Wolfe(SFW) algoritm, inspirerad av SGDo där slumpmässigt urval görs utan återläggning. I analogi med denna förkortning så kallar vi den föreslagna algoritmen SFWo. Vi betraktar en konvex miljö och gradient Lipschitz kontinuerliga (släta) funktioner över kompakta definitionsmängder. Beroende på experimentdesign (LASSO, Matrix Sensing, Matrix Completion) så visar den föreslagna algoritmen SFWo på en snabbare eller matchande empirisk konvergens och tenderar vara begränsad i suboptimalitet av föregångaren SFW. Prestandajämförelser på både syntetisk och verklig data visar att SFWo förbättrarantalet stokastiska gradientevalueringar som behövs för att uppnå samma garanti som för SFW.

La phase d’apprentissage des méthodes d’apprentissage statistique automatique correspondent à la résolution d’un problème d’optimisation mathématique dont la fonction objectif se décompose en deux parties: a) le risque empirique, construit à partir d’une fonction de perte, dont la forme est déterminée par la métrique de performance et les hypothèses sur le bruit; b) la pénalité de régularisation, construite a partir d’une norme ou fonction jauge, dont la structure est déterminée par l’information à priori disponible sur le problème a résoudre.Les fonctions de perte usuelles, comme la fonction de perte charnière pour la classification supervisée binaire, ainsi que les fonctions de perte plus avancées comme celle pour la classification supervisée avec possibilité d’abstention, sont non-différentiables. Les pénalités de régularisation comme la norme l1 (vectorielle), ainsi que la norme nucléaire (matricielle), sont également non- différentiables. Cependant, les algorithmes d’optimisation numériques les plus simples, comme l’algorithme de sous-gradient ou les méthodes de faisceaux, ne tirent pas profit de la structure composite de l’objectif. Le but de cette thèse est d’étudier les problèmes d’apprentissage doublement non-différentiables (perte non- différentiable et régularisation non-différentiable), ainsi que les algorithmes d’optimisation numérique qui sont en mesure de bénéficier de cette structure composite.Dans le premier chapitre, nous présentons une nouvelle famille de pénalité de régularisation, les normes de Schatten par blocs, qui généralisent les normes de Schatten classiques. Nous démontrons les principales propriétés des normes de Schatten par blocs en faisant appel à des outils d’analyse convexe et d’algèbre linéaire; nous retrouvons en particulier des propriétés caractérisant les normes proposées en termes d’enveloppe convexes. Nous discutons plusieurs applications potentielles de la norme nucléaire par blocs, pour le filtrage collaboratif, la compression de bases de données, et l’annotation multi-étiquettes d’images.Dans le deuxième chapitre, nous présentons une synthèse de différentes tech- niques de lissage qui permettent d’utiliser des algorithmes de premier ordre adaptes aux objectifs composites qui de décomposent en un terme différentiable et un terme non-différentiable. Nous montrons comment le lissage peut être utilisé pour lisser la fonction de perte correspondant à la précision au rang k, populaire pour le classement et la classification supervises d’images. Nous décrivons dans les grandes lignes plusieurs familles d’algorithmes de premier ordre qui peuvent bénéficier du lissage: i) les algorithmes de gradient conditionnel; ii) les algorithmes de gradient proximal; iii) les algorithmes de gradient incrémental.Dans le troisième chapitre, nous étudions en profondeur les algorithmes de gradient conditionnel pour les problèmes d’optimisation non-différentiables d’apprentissage statistique automatique. Nous montrons qu’une stratégie de lis- sage adaptative associée à un algorithme de gradient conditionnel donne lieu à de nouveaux algorithmes de gradient conditionnel qui satisfont des garanties de convergence théoriques. Nous présentons des résultats expérimentaux prometteurs des problèmes de filtrage collaboratif pour la recommandation de films et de catégorisation d’images. / Training machine learning methods boils down to solving optimization problems whose objective functions often decomposes into two parts: a) the empirical risk, built upon the loss function, whose shape is determined by the performance metric and the noise assumptions; b) the regularization penalty, built upon a norm, or a gauge function, whose structure is determined by the prior information available for the problem at hand.Common loss functions, such as the hinge loss for binary classification, or more advanced loss functions, such as the one arising in classification with reject option, are non-smooth. Sparse regularization penalties such as the (vector) l1- penalty, or the (matrix) nuclear-norm penalty, are also non-smooth. However, basic non-smooth optimization algorithms, such as subgradient optimization or bundle-type methods, do not leverage the composite structure of the objective. The goal of this thesis is to study doubly non-smooth learning problems (with non-smooth loss functions and non-smooth regularization penalties) and first- order optimization algorithms that leverage composite structure of non-smooth objectives.In the first chapter, we introduce new regularization penalties, called the group Schatten norms, to generalize the standard Schatten norms to block- structured matrices. We establish the main properties of the group Schatten norms using tools from convex analysis and linear algebra; we retrieve in particular some convex envelope properties. We discuss several potential applications of the group nuclear-norm, in collaborative filtering, database compression, multi-label image tagging.In the second chapter, we present a survey of smoothing techniques that allow us to use first-order optimization algorithms designed for composite objectives decomposing into a smooth part and a non-smooth part. We also show how smoothing can be used on the loss function corresponding to the top-k accuracy, used for ranking and multi-class classification problems. We outline some first-order algorithms that can be used in combination with the smoothing technique: i) conditional gradient algorithms; ii) proximal gradient algorithms; iii) incremental gradient algorithms.In the third chapter, we study further conditional gradient algorithms for solving doubly non-smooth optimization problems. We show that an adaptive smoothing combined with the standard conditional gradient algorithm gives birth to new conditional gradient algorithms having the expected theoretical convergence guarantees. We present promising experimental results in collaborative filtering for movie recommendation and image categorization.

L'apprentissage des matrices de rang faible est un problème de grande importance dans les statistiques, l'apprentissage automatique, la vision par ordinateur et les systèmes de recommandation. En raison de sa nature NP-difficile, une des approches principales consiste à résoudre sa relaxation convexe la plus étroite : la minimisation de la norme de trace. Parmi les différents algorithmes capables de résoudre cette optimisation, on peut citer la méthode de Frank-Wolfe, particulièrement adaptée aux matrices de grande dimension. En préparation à l'utilisation d'infrastructures distribuées pour accélérer le calcul, cette étude vise à explorer la possibilité d'exécuter l'algorithme de Frank-Wolfe dans un réseau en étoile avec le modèle BSP (Bulk Synchronous Parallel) et à étudier son efficacité théorique et empirique. Concernant l'aspect théorique, cette étude revisite le taux de convergence déterministe de Frank-Wolfe et l'étend à des cas non déterministes. En particulier, il montre qu'avec le sous-problème linéaire résolu de manière appropriée, Frank-Wolfe peut atteindre un taux de convergence sous-linéaire à la fois en espérance et avec une probabilité élevée. Cette contribution pose la fondation théorique de l'utilisation de la méthode de la puissance itérée ou de l'algorithme de Lanczos pour résoudre le sous-problème linéaire de Frank-Wolfe associé à la minimisation de la norme de trace. Concernant l'aspect algorithmique, dans le cadre de BSP, cette étude propose et analyse quatre stratégies pour le sous-problème linéaire ainsi que des méthodes pour la recherche linéaire. En outre, remarquant la propriété de mise à jour de rang-1 de Frank-Wolfe, il met à jour le gradient de manière récursive, avec une représentation dense ou de rang faible, au lieu de le recalculer de manière répétée à partir de zéro. Toutes ces conceptions sont génériques et s'appliquent à toutes les infrastructures distribuées compatibles avec le modèle BSP. Concernant l'aspect empirique, cette étude teste les conceptions algorithmiques proposées dans un cluster Apache SPARK. Selon les résultats des expériences, pour le sous-problème linéaire, la centralisation des gradients ou la moyenne des vecteurs singuliers est suffisante dans le cas de faible dimension, alors que la méthode de la puissance itérée distribuée, avec aussi peu qu'une ou deux itérations par époque, excelle dans le cas de grande dimension. La librairie Python développée pour les expériences est modulaire, extensible et prête à être déployée dans un contexte industriel. Cette étude a rempli sa fonction de preuve de concept. Suivant le chemin qu'il met en place, des solveurs peuvent être implémentés pour différentes infrastructures, parmi lesquelles des clusters GPU, pour résoudre des problèmes pratiques dans des contextes spécifiques. En outre, ses excellentes performances dans le jeu de données ImageNet le rendent prometteur pour l'apprentissage en profondeur. / Learning low-rank matrices is a problem of great importance in statistics, machine learning, computer vision, recommender systems, etc. Because of its NP-hard nature, a principled approach is to solve its tightest convex relaxation : trace norm minimization. Among various algorithms capable of solving this optimization is the Frank-Wolfe method, which is particularly suitable for high-dimensional matrices. In preparation for the usage of distributed infrastructures to further accelerate the computation, this study aims at exploring the possibility of executing the Frank-Wolfe algorithm in a star network with the Bulk Synchronous Parallel (BSP) model and investigating its efficiency both theoretically and empirically. In the theoretical aspect, this study revisits Frank-Wolfe's fundamental deterministic sublinear convergence rate and extends it to nondeterministic cases. In particular, it shows that with the linear subproblem appropriately solved, Frank-Wolfe can achieve a sublinear convergence rate both in expectation and with high probability. This contribution lays the theoretical foundation of using power iteration or Lanczos iteration to solve the linear subproblem for trace norm minimization. In the algorithmic aspect, within the BSP model, this study proposes and analyzes four strategies for the linear subproblem as well as methods for the line search. Moreover, noticing Frank-Wolfe's rank-1 update property, it updates the gradient recursively, with either a dense or a low-rank representation, instead of repeatedly recalculating it from scratch. All of these designs are generic and apply to any distributed infrastructures compatible with the BSP model. In the empirical aspect, this study tests the proposed algorithmic designs in an Apache SPARK cluster. According to the experiment results, for the linear subproblem, centralizing the gradient or averaging the singular vectors is sufficient in the low-dimensional case, whereas distributed power iteration, with as few as one or two iterations per epoch, excels in the high-dimensional case. The Python package developed for the experiments is modular, extensible and ready to deploy in an industrial context. This study has achieved its function as proof of concept. Following the path it sets up, solvers can be implemented for various infrastructures, among which GPU clusters, to solve practical problems in specific contexts. Besides, its excellent performance in the ImageNet dataset makes it promising for deep learning.

We derive a technique for scaling the search directions of feasible direction methods when applied to optimization problems over Cartesian product sets. It is proved that when the scaling is included in a convergent feasible direction method, also the new method will be convergent. The scaling technique is applied to the Frank-Wolfe method, the partanized Frank-Wolfe method and a heuristic Frank-Wolfe method. The performance of  these algorithms with and without scaling is evaluated on the stochastic transportation problem. It is found that the scaling technique has the ability to improve the performance of some methods. In particular we observed a huge improvement in the performance of the partanized Frank-Wolfe method, especially when the scaling is used together with an exact line search and when the number of sets in the Cartesian product is large.

Modern large data sets inevitably contain outliers that deviate from the model assumptions. However, many widely used estimators, such as maximum likelihood estimators and least squared estimators, perform weakly with the existence of outliers. Alternatively, many statistical modeling approaches have matrices as the parameters. We consider penalized estimators for matrix-valued parameters with a focus on their robustness properties in the presence of outliers. We propose a general framework for robust modeling with matrix-valued parameters by minimizing robust loss functions with penalization. However, there are challenges to this approach in both computation and theoretical analysis. To tackle the computational challenges from the large size of the data, non-smoothness of robust loss functions, and the slow speed of matrix operations, we propose to apply the Frank-Wolfe algorithm, a first-order algorithm for optimization on a restricted region with low computation burden per iteration. Theoretically, we establish finite-sample error bounds under high-dimensional settings. We show that the estimation errors are bounded by small terms and converge in probability to zero under mild conditions in a neighborhood of the true model. Our method accommodates a broad classes of modeling problems using robust loss functions with penalization. Concretely, we study three cases: matrix completion, multivariate regression, and network estimation. For all cases, we illustrate the robustness of the proposed method both theoretically and numerically. / Statistics

<p>Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. </p><p>This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. </p><p>These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.</p>

Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.