Optimization is an important tool in many science and engineering applications, ranging from machine learning to control, from signal processing to power systems management, to name a few. The relevance of optimization in this wide range of applications requires the design of algorithms that can overcome different challenges. Indeed, depending on the application, optimization algorithms may have access to limited computational power, or have hard constraints on the time available for computations. To address these challenges, optimization research in recent years has increasingly relied on operator theory, with its powerful tools and results. Importantly, this is allowed by the fact that optimization algorithms can be interpreted as the recursive application of an operator, thus translating a minimization problem into a fixed point problem. The central theme of this thesis is therefore the intersection of optimization and operator theory, and how we can leverage their interplay to solve different challenges and design novel algorithms. We focus in particular on two broad areas of research: stochastic optimization and online optimization. Stochastic optimization groups all problems in which an algorithms is constrained by the presence of randomness during its execution, e.g. because of additive noise perturbing the computation. In this context, the thesis proposes two contribution. The first is the study of the alternating direction method of multipliers (ADMM) applied to distributed optimization problems when the network is asynchronous and peertopeer communications may randomly fail. The second contribution is a framework for stochastic operator theory that allows us to analyze the convergence of a large number of stochastic optimization algorithms in a unified way, with applications in e.g. machine learning. In this framework we derive both mean and high probability convergence guarantees, the latter leveraging the powerful formalism of subWeibull random variables. In online optimization we are faced with the challenge of solving a problem whose cost and constraints change over time, and thus the goal is to track a sequence of optimizers. The first contribution we propose is a general predictioncorrection method, which abstracts many online algorithms and can be used to study their convergence. The predictioncorrection method is characterized by the fact that past information is used to warmstart the solution of future problems, and we propose a novel polynomial extrapolationbased strategy to do so. Secondly, in the area of learning to optimize we propose a novel approach to accelerate online algorithms for weakly convex problems. The method is based on the concept of operator regression, which learns a faster algorithm from samples of the original one. Finally, the thesis reports numerical results that showcase the practical applications of the theoretical contributions, and discusses the tvopt Python module implemented for the purpose of prototyping and benchmarking optimization algorithms.
Optimization is an important tool in many science and engineering applications, ranging from machine learning to control, from signal processing to power systems management, to name a few. The relevance of optimization in this wide range of applications requires the design of algorithms that can overcome different challenges. Indeed, depending on the application, optimization algorithms may have access to limited computational power, or have hard constraints on the time available for computations. To address these challenges, optimization research in recent years has increasingly relied on operator theory, with its powerful tools and results. Importantly, this is allowed by the fact that optimization algorithms can be interpreted as the recursive application of an operator, thus translating a minimization problem into a fixed point problem. The central theme of this thesis is therefore the intersection of optimization and operator theory, and how we can leverage their interplay to solve different challenges and design novel algorithms. We focus in particular on two broad areas of research: stochastic optimization and online optimization. Stochastic optimization groups all problems in which an algorithms is constrained by the presence of randomness during its execution, e.g. because of additive noise perturbing the computation. In this context, the thesis proposes two contribution. The first is the study of the alternating direction method of multipliers (ADMM) applied to distributed optimization problems when the network is asynchronous and peertopeer communications may randomly fail. The second contribution is a framework for stochastic operator theory that allows us to analyze the convergence of a large number of stochastic optimization algorithms in a unified way, with applications in e.g. machine learning. In this framework we derive both mean and high probability convergence guarantees, the latter leveraging the powerful formalism of subWeibull random variables. In online optimization we are faced with the challenge of solving a problem whose cost and constraints change over time, and thus the goal is to track a sequence of optimizers. The first contribution we propose is a general predictioncorrection method, which abstracts many online algorithms and can be used to study their convergence. The predictioncorrection method is characterized by the fact that past information is used to warmstart the solution of future problems, and we propose a novel polynomial extrapolationbased strategy to do so. Secondly, in the area of learning to optimize we propose a novel approach to accelerate online algorithms for weakly convex problems. The method is based on the concept of operator regression, which learns a faster algorithm from samples of the original one. Finally, the thesis reports numerical results that showcase the practical applications of the theoretical contributions, and discusses the tvopt Python module implemented for the purpose of prototyping and benchmarking optimization algorithms.
Teoria degli operatori per ottimizzazione e learning / Bastianello, Nicola.  (2022 Feb 14).
Teoria degli operatori per ottimizzazione e learning
BASTIANELLO, NICOLA
2022
Abstract
Optimization is an important tool in many science and engineering applications, ranging from machine learning to control, from signal processing to power systems management, to name a few. The relevance of optimization in this wide range of applications requires the design of algorithms that can overcome different challenges. Indeed, depending on the application, optimization algorithms may have access to limited computational power, or have hard constraints on the time available for computations. To address these challenges, optimization research in recent years has increasingly relied on operator theory, with its powerful tools and results. Importantly, this is allowed by the fact that optimization algorithms can be interpreted as the recursive application of an operator, thus translating a minimization problem into a fixed point problem. The central theme of this thesis is therefore the intersection of optimization and operator theory, and how we can leverage their interplay to solve different challenges and design novel algorithms. We focus in particular on two broad areas of research: stochastic optimization and online optimization. Stochastic optimization groups all problems in which an algorithms is constrained by the presence of randomness during its execution, e.g. because of additive noise perturbing the computation. In this context, the thesis proposes two contribution. The first is the study of the alternating direction method of multipliers (ADMM) applied to distributed optimization problems when the network is asynchronous and peertopeer communications may randomly fail. The second contribution is a framework for stochastic operator theory that allows us to analyze the convergence of a large number of stochastic optimization algorithms in a unified way, with applications in e.g. machine learning. In this framework we derive both mean and high probability convergence guarantees, the latter leveraging the powerful formalism of subWeibull random variables. In online optimization we are faced with the challenge of solving a problem whose cost and constraints change over time, and thus the goal is to track a sequence of optimizers. The first contribution we propose is a general predictioncorrection method, which abstracts many online algorithms and can be used to study their convergence. The predictioncorrection method is characterized by the fact that past information is used to warmstart the solution of future problems, and we propose a novel polynomial extrapolationbased strategy to do so. Secondly, in the area of learning to optimize we propose a novel approach to accelerate online algorithms for weakly convex problems. The method is based on the concept of operator regression, which learns a faster algorithm from samples of the original one. Finally, the thesis reports numerical results that showcase the practical applications of the theoretical contributions, and discusses the tvopt Python module implemented for the purpose of prototyping and benchmarking optimization algorithms.File  Dimensione  Formato  

main.pdf
accesso aperto
Descrizione: tesi_Nicola_Bastianello
Tipologia:
Tesi di dottorato
Dimensione
7.25 MB
Formato
Adobe PDF

7.25 MB  Adobe PDF  Visualizza/Apri 
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.