Global ETD Search

1	DISTRIBUTED OPTIMIZATION FOR MACHINE LEARNING: GUARANTEES AND TRADEOFFS Ye Tian (11166960) 01 September 2021 (has links) <div>In the era of big data, the sheer volume and widespread spatial distribution of information has been promoting extensive research on distributed optimization over networks. Each computing unit has access only to a relatively small portion of the entire data and can only communicate with a relatively small number of neighbors. The goal of the system is to reach consensus on the optimal parametric model with respect to the entire data among all computing units. Existing work has provided various decentralized optimization algorithms for the purpose. However, some important questions remain unclear: (I) what is the intrinsic connection among different existing algorithms? (II) what is the min-max lower complexity bound for decentralized algorithms? Can one design an optimal decentralized algorithm in the sense that it achieves the lower complexity bound? and (III) in the presence of asynchrony and imperfect communications, can one design linearly convergent decentralized algorithms?</div><div><br></div><div> This thesis aims at addressing the above questions. (I) Abstracting from ad-hoc, specific solution methods, we propose a unified distributed algorithmic framework and analysis for a general class of optimization problems over networks. Our method encapsulates several existing first-order distributed algorithms. Distinguishing features of our scheme are: (a) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (b) When the objective function is convex, but not strongly convex, similar decoupling as in (a) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate; (c) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (d) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms, yielding provably faster (worst-case) convergence rate for the class of problems under consideration. (II) Referring to lower complexity bounds, the proposed novel family of algorithms, when equipped with acceleration, are proved to be optimal, that is, they achieve convergence rate lower bounds. (III) Finally, to make the proposed algorithms practical, we break the synchronism in the agents’ updates: agents wake up and update without any coordination, using information only from immediate neighbors with unknown, arbitrary but bounded delays. Quite remarkably, even in the presence of asynchrony, the proposed algorithmic framework is proved to converge at a linear rate (resp. sublinear rate) when applied to strongly convex (resp. non strongly convex) optimization problems.</div> Operations Research decentralized computation asynchronous updates optimal algorithms unified framework distributed optimization
2	Optimal Control Of Voltage And Power In Mvdc Multi-Zonal Shipboard Power System Kankanala, Padmavathy 11 December 2009 (has links) Recent advancements in Voltage Source Converters (VSCs) of high-voltage and high-power rating had a significant impact on the development of Multi-Terminal HVDC (MTDC) power transmission systems. The U.S. Navy has proposed Multi-Zonal Medium Voltage DC (MVDC) Shipboard Power System (SPS) architecture for the next generation of their surface combatant. A Multi-Zonal MVDC SPS consists of several VSCs exchanging power through a DC network. Following a system fault or damage, the current flow pattern in the DC distribution grid will change and the DC voltages across the VSCs will assume new values. DC voltage reference or power reference settings of VSCs have to be determined, in advance, which can maintain the DC voltage within desired margins (usually 5% around the nominal value) in steady state, under the prefault as well as the postault conditions. In this work, the reference settings have been pre-determined by: (1) Development of a sensitivity based algorithm for voltage control of VSCs of the DC system and (2) Development of an optimal algorithm for voltage and power control of the VSCs. The algorithms have been tested on a simplified representation of the MVDC SPS architecture. MVDC shipboard power system biogeography based optimization genetic algorithm Voltage sensitivity method Optimal Algorithms
3	Optimal Algorithms for Affinely Constrained, Distributed, Decentralized, Minimax, and High-Order Optimization Problems Kovalev, Dmitry 09 1900 (has links) Optimization problems are ubiquitous in all quantitative scientific disciplines, from computer science and engineering to operations research and economics. Developing algorithms for solving various optimization problems has been the focus of mathematical research for years. In the last decade, optimization research has become even more popular due to its applications in the rapidly developing field of machine learning. In this thesis, we discuss a few fundamental and well-studied optimization problem classes: decentralized distributed optimization (Chapters 2 to 4), distributed optimization under similarity (Chapter 5), affinely constrained optimization (Chapter 6), minimax optimization (Chapter 7), and high-order optimization (Chapter 8). For each problem class, we develop the first provably optimal algorithm: the complexity of such an algorithm cannot be improved for the problem class given. The proposed algorithms show state-of-the-art performance in practical applications, which makes them highly attractive for potential generalizations and extensions in the future. Optimization Convex Optimization Distributed Optimization High-Order Optimization Saddle-Point Problems Minimax Optimization Tensor Methods Optimal Algorithms
4	Energy-aware scheduling : complexity and algorithms Renaud-Goud, Paul 05 July 2012 (has links) (PDF) In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption. [INFO:INFO_OH] Computer Science/Other Energy minimization Power Scheduling Complexity Makespan Heuristics Optimal algorithms Greedy algorithm Independent jobs Parallel processors Mapping Concurrent streaming applications Heterogeneous platforms Resource sharing Energy Latency Period Workflow Replica placement Tree networks Update strategies Dynamic programming algorithms Series-parallel graph Routing Chip multiprocesseur Manhattan Single path Multiple paths Slack reclamation DAG
5	Energy-aware scheduling : complexity and algorithms / Ordonnancement sous contrainte d'énergie : complexité et algorithmes Renaud-Goud, Paul 05 July 2012 (has links) Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles. / In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption. Minimisation d'énergie Puissance Ordonnancement Complexité Heuristique Algorithmes optimaux Algorithme glouton Travaux indépendants Processeurs parallèles Placement Applications concurrentes Plate-forme hétérogène Partage de ressources Énergie Latence Période Placement de répliques Réseau arborescent Stratégies de mise à jour Algorithme de programmation dynamique Graphe série-parallèle Routage Multiprocesseur Manhattan Chemin unique Chemin multiples DAG Energy minimization Power Scheduling Complexity Makespan Heuristics Optimal algorithms Greedy algorithm Independent jobs Parallel processors Mapping Concurrent streaming applications Heterogeneous platforms Resource sharing Energy Latency Period Workflow Replica placement Tree networks Update strategies Dynamic programming algorithms Series-parallel graph Routing Chip multiprocesseur Manhattan Single path Multiple paths Slack reclamation DAG

1

Page generated in 0.0653 seconds