Performance Limits of Stochastic Sub-Gradient Learning, Part II: Multi-Agent Case

The analysis in Part I revealed interesting properties for subgradient learning algorithms in the context of stochastic optimization when gradient noise is present. These algorithms are used when the risk functions are non-smooth and involve non-differentiable components. They have been long recognized as being slow converging methods. However, it was revealed in Part I that the rate of convergence becomes linear for stochastic optimization problems, with the error iterate converging at an exponential rate $\alpha^i$ to within an $O(\mu)-$neighborhood of the optimizer, for some $\alpha \in (0,1)$ and small step-size $\mu$. The conclusion was established under weaker assumptions than the prior literature and, moreover, several important problems (such as LASSO, SVM, and Total Variation) were shown to satisfy these weaker assumptions automatically (but not the previously used conditions from the literature). These results revealed that sub-gradient learning methods have more favorable behavior than originally thought when used to enable continuous adaptation and learning. The results of Part I were exclusive to single-agent adaptation. The purpose of the current Part II is to examine the implications of these discoveries when a collection of networked agents employs subgradient learning as their cooperative mechanism. The analysis will show that, despite the coupled dynamics that arises in a networked scenario, the agents are still able to attain linear convergence in the stochastic case; they are also able to reach agreement within $O(\mu)$ of the optimizer.


Similar Publications

Scalarization in vector optimization is essentially based on the minimization of Gerstewitz functionals. In this paper, the minimizer sets of Gerstewitz functionals are investigated. Conditions are given under which such a set is nonempty and compact. Read More


We develop an asymptotical control theory for one of the simplest distributed oscillating system --- the closed string under a bounded load applied to a single distinguished point. We find exact classes of the string states that allows complete damping, and asymptotically exact value of the required time. By using approximate reachable sets instead of exact ones we design a dry-friction like feedback control, which turns to be asymptotically optimal. Read More


Through the development of efficient algorithms, data structures and preprocessing techniques, real-world shortest path problems in street networks are now very fast to solve. But in reality, the exact travel times along each arc in the network may not be known. This lead to the development of robust shortest path problems, where all possible arc travel times are contained in a so-called uncertainty set of possible outcomes. Read More


The multidimensional ($n$-D) systems described by Roesser model are presented in this paper. These $n$-D systems consist of discrete systems and continuous fractional order systems with fractional order $\nu$, $0<\nu<1$. The stability and Robust stability of such $n$-D systems are investigated. Read More


The celebrated GKYP is widely used in integer-order control system. However, when it comes to the fractional order system, there exists no such tool to solve problems. This paper prove the FGKYP which can be used in the analysis of problems in fractional order system. Read More


This paper focuses on some properties, which include regularity, impulse, stability, admissibility and robust admissibility, of singular fractional order system (SFOS) with fractional order $1<\alpha<2$. The finitions of regularity, impulse-free, stability and admissibility are given in the paper. Regularity is analysed in time domain and the analysis of impulse-free is based on state response. Read More


This paper introduces a new method of partitioning the solution space of a multi-objective optimisation problem for parallel processing, called Efficient Projection Partitioning. This method projects solutions down into a single dimension, greatly reducing the cost of partitioning the search space. We test EPP on a variety of randomly generated multi-objective combinatorial optimisation problems. Read More


Estimation of the operational topology of the power grid is necessary for optimal market settlement and reliable dynamic operation of the grid. This paper presents a novel framework for topology estimation for general power grids (loopy or radial) using time-series measurements of nodal voltage phase angles that arise from the swing dynamics. Our learning framework utilizes multivariate Wiener filtering to unravel the interaction between fluctuations in voltage angles at different nodes and identifies operational edges by considering the phase response of the elements of the multivariate Wiener filter. Read More


In our companion paper "Multidimensional rational covariance extension with applications to spectral estimation and image compression" we discussed the multidimensional rational covariance extension problem (RCEP), which has important applications in image processing, and spectral estimation in radar, sonar, and medical imaging. This is an inverse problem where a power spectrum with a rational absolutely continuous part is reconstructed from a finite set of moments. However, in most applications these moments are determined from observed data and are therefore only approximate, and RCEP may not have a solution. Read More


Distributed averaging of agent initial conditions is a well-studied problem in context of networked systems where coordination amongst the agents is of paramount importance. The asymptotic nature of convergence of distributed averaging protocols and presence of communication delays, however, makes it challenging to implement in practical settings. It is important that agents develop the ability to detect on their own when average of the initial conditions of the agents is achieved within some pre-specified tolerance and stop further computations to avoid overhead expenses in the presence of delays. Read More