Nonlinear Perturbation-based Non-Convex Optimization over Time-Varying Networks
Decentralized optimization strategies are helpful for various applications, from networked estimation to distributed machine learning. This paper studies finite-sum minimization problems described over a network of nodes and proposes a computationally efficient algorithm that solves distributed convex problems and optimally finds the solution to locally non-convex objective functions. In contrast to batch gradient optimization in some literature, our algorithm is on a single-time scale with no extra inner consensus loop. It evaluates one gradient entry per node per time. Further, the algorithm addresses link-level nonlinearity representing, for example, logarithmic quantization of the exchanged data or clipping of the exchanged data bits. Leveraging perturbation-based theory and algebraic Laplacian network analysis proves optimal convergence and dynamics stability over time-varying and switching networks. The time-varying network setup might be due to packet drops or link failures. Despite the nonlinear nature of the dynamics, we prove exact convergence in the face of odd sign-preserving sector-bound nonlinear data transmission over the links. Illustrative numerical simulations further highlight our contributions.
Code (0)
등록된 구현이 없습니다.
Tasks
QuantizationSimilar Papers 제목 키워드 기반
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of…
Online convex optimization for constrained control of nonlinear systems
This paper investigates the problem of controlling nonlinear dynamical systems subject to state and input constraints while minimizing time-varying and a priori unknown cost functions. We propose a modular approach that …
Sensitivity Analysis for Piecewise-Affine Approximations of Nonlinear Programs with Polytopic Constraints
Nonlinear Programs (NLPs) are prevalent in optimization-based control of nonlinear systems. Solving general NLPs is computationally expensive, necessitating the development of fast hardware or tractable suboptimal approx…
Model Predictive ControlSensitivityMotion Planning for Autonomous Vehicles using Optimization over Graphs of Convex Sets
Motion planning for autonomous vehicles requires generating collision-free and dynamically feasible trajectories in complex environments under real-time constraints. While nonlinear optimal control formulations provide h…
Computational EfficiencyAutonomous VehiclesAutonomous DrivingMotion PlanningContracting Nonlinear Observers: Convex Optimization and Learning from Data
A new approach to design of nonlinear observers (state estimators) is proposed. The main idea is to (i) construct a convex set of dynamical systems which are contracting observers for a particular system, and (ii) optimi…
State Estimation