Optimization and Control (math.OC)
Thu, 08 Jun 2023
1.Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates
Authors:Siqi Zhang, Sayantan Choudhury, Sebastian U Stich, Nicolas Loizou
Abstract: Distributed and federated learning algorithms and techniques associated primarily with minimization problems. However, with the increase of minimax optimization and variational inequality problems in machine learning, the necessity of designing efficient distributed/federated learning approaches for these problems is becoming more apparent. In this paper, we provide a unified convergence analysis of communication-efficient local training methods for distributed variational inequality problems (VIPs). Our approach is based on a general key assumption on the stochastic estimates that allows us to propose and analyze several novel local training algorithms under a single framework for solving a class of structured non-monotone VIPs. We present the first local gradient descent-accent algorithms with provable improved communication complexity for solving distributed variational inequalities on heterogeneous data. The general algorithmic framework recovers state-of-the-art algorithms and their sharp convergence guarantees when the setting is specialized to minimization or minimax optimization problems. Finally, we demonstrate the strong performance of the proposed algorithms compared to state-of-the-art methods when solving federated minimax optimization problems.
2.Zero-sum stopper vs. singular-controller games with constrained control directions
Authors:Andrea Bovo, Tiziano De Angelis, Jan Palczewski
Abstract: We consider a class of zero-sum stopper vs.\ singular-controller games in which the controller can only act on a subset $d_0<d$ of the $d$ coordinates of a controlled diffusion. Due to the constraint on the control directions these games fall outside the framework of recently studied variational methods. In this paper we develop an approximation procedure, based on $L^1$-stability estimates for the controlled diffusion process and almost sure convergence of suitable stopping times. That allows us to prove existence of the game's value and to obtain an optimal strategy for the stopper, under continuity and growth conditions on the payoff functions. This class of games is a natural extension of (single-agent) singular control problems, studied in the literature, with similar constraints on the admissible controls.
3.On the Identification and Optimization of Nonsmooth Superposition Operators in Semilinear Elliptic PDEs
Authors:Constantin Christof, Julia Kowalczyk
Abstract: We study an infinite-dimensional optimization problem that aims to identify the Nemytskii operator in the nonlinear part of a prototypical semilinear elliptic partial differential equation (PDE) which minimizes the distance between the PDE-solution and a given desired state. In contrast to previous works, we consider this identification problem in a low-regularity regime in which the function inducing the Nemytskii operator is a-priori only known to be an element of $H^1_{loc}(\mathbb{R})$. This makes the studied problem class a suitable point of departure for the rigorous analysis of training problems for learning-informed PDEs in which an unknown superposition operator is approximated by means of a neural network with nonsmooth activation functions (ReLU, leaky-ReLU, etc.). We establish that, despite the low regularity of the controls, it is possible to derive a classical stationarity system for local minimizers and to solve the considered problem by means of a gradient projection method. The convergence of the resulting algorithm is proven in the function space setting. It is also shown that the established first-order necessary optimality conditions imply that locally optimal superposition operators share various characteristic properties with commonly used activation functions: They are always sigmoidal, continuously differentiable away from the origin, and typically possess a distinct kink at zero. The paper concludes with numerical experiments which confirm the theoretical findings.
4.Safe Adaptive Multi-Agent Coverage Control
Authors:Yang Bai, Yujie Wang, Xiaogang Xiong, Mikhail Svinin
Abstract: This paper presents a safe adaptive coverage controller for multi-agent systems with actuator faults and time-varying uncertainties. The centroidal Voronoi tessellation (CVT) is applied to generate an optimal configuration of multi-agent systems for covering an area of interest. As a conventional CVT-based controller cannot prevent collisions between agents with non-zero size, a control barrier function (CBF) based controller is developed to ensure collision avoidance with a function approximation technique (FAT) based design to deal with system uncertainties. The proposed controller is verified under simulations.