Search

This paper presents an extensive study of linear and logistic regression algorithms implemented with 1T1R memristor crossbars arrays. Using a sophisticated simulation platform that wraps circuit-level simulations of 1T1R crossbars and physics-based models of RRAM (memristors), we elucidate the impact of device variability on algorithm accuracy, convergence rate and precision. Moreover, a smart pulsing strategy is proposed for practical implementation of synaptic weight updates that can accelerate training in real crossbar architectures. Stochastic multi-variable linear regression shows robustness to memristor variability in terms of prediction accuracy but reveals impact on convergence rate and precision. Similarly, the stochastic logistic regression crossbar implementation reveals immunity to memristor variability as determined by negligible effects on image classification accuracy but indicates an impact on training performance manifested as reduced convergence rate and degraded precision. [ABSTRACT FROM AUTHOR]

In this paper, a unified framework is proposed to address the synchronization problem of memristor chaotic systems (MCSs) via the sliding-mode control method. By employing the presented unified framework, the finite-time and fixed-time synchronization of MCSs can be realized simultaneously. On the one hand, based on the Lyapunov stability and sliding-mode control theories, the finite-/fixed-time synchronization results are obtained. It is proved that the trajectories of error states come near and get to the designed sliding-mode surface, stay on it accordingly and approach the origin in a finite/fixed time. On the other hand, we develop an image encryption algorithm as well as its implementation process to show the application of the synchronization. Finally, the theoretical results and the corresponding image encryption application are carried out by numerical simulations and statistical performances. [ABSTRACT FROM AUTHOR]

Deep Neural Networks (DNNs) are increasingly being used in a variety of applications. However, DNNs have huge computational and memory requirements. One way to reduce these requirements is to sparsify DNNs by using smoothed LASSO (Least Absolute Shrinkage and Selection Operator) functions. In this paper, we show that irrespective of error profile, the sparsity values obtained using various smoothed LASSO functions are similar, provided the maximum error of these functions with respect to the LASSO function is the same. We also propose a layer-wise DNN pruning algorithm, where the layers are pruned based on their individual allocated accuracy loss budget, determined by estimates of the reduction in number of multiply-accumulate operations (in convolutional layers) and weights (in fully connected layers). Further, the structured LASSO variants in both convolutional and fully connected layers are explored within the smoothed LASSO framework and the tradeoffs involved are discussed. The efficacy of proposed algorithm in enhancing the sparsity within the allowed degradation in DNN accuracy and results obtained on structured LASSO variants are shown on MNIST, SVHN, CIFAR-10, and Imagenette datasets and on larger networks such as ResNet-50 and Mobilenet. [ABSTRACT FROM AUTHOR]

This paper addresses the finite-time and fixed-time bipartite average tracking (BAT) problems in multi-agent systems (MASs) subject to bounded disturbances. A novel non-smooth protocol is first constructed on the basis of utilizing the finite-time control method, which can realize the finite-time BAT with structurally balanced graph. Then, the fixed-time BAT problem is dealt with nonlinear fixed-time algorithm, the setting time of which is obtained without depending on initial states. By employing Lyapunov stability theory, some sufficient criteria are obtained to achieve the finite-time and fixed-time BAT for MASs with disturbances. Numerical examples are finally developed for illustration. [ABSTRACT FROM AUTHOR]

Piecewise affine (PWA) systems are attractive models that can represent various hybrid systems with local affine subsystems and polyhedral regions due to their universal approximation properties. The identification problem of PWA systems amounts to estimating the number of subsystems, parameters of each subsystem, and the corresponding polyhedral partitions via state-input vectors. In this paper, we propose a novel approach to address the online identification problem of continuous-time PWA systems in state-space form. Specifically, an online active mode recognition algorithm and a generalized integral concurrent learning identifier are presented to acquire the number of subsystems, the switching sequence, and the parameter of each subsystem. In addition, we develop the optimization problem for the polyhedral partition estimation, which is solved by using the estimated switching sequence and subsystem parameters. The effectiveness of the proposed identification approach is demonstrated via simulation results. [ABSTRACT FROM AUTHOR]

This paper presents a COordinate Rotation Digital Computer (CORDIC)-based architecture for the computation of Nth root and proves its feasibility by hardware implementation. The proposed architecture performs the task of Nth root simply by shift-add operations and enables easy tradeoff between the speed (or precision) and the area. Technically, we divide the Nth root computation into three different subtasks, and map them onto three different classes of the CORDIC accordingly. To overcome the drawback of narrow convergence range of the CORDIC algorithm, we adopt several innovative methods to yield a much improved convergence range. Subsequently, in terms of convergence range and precision, a flexible architecture is developed. The architecture is validated using MATLAB with extensive vector matching. Finally, using a pipelined structure with fixed-point input data, we implement the example circuits of the proposed architecture with radicand ranging from zero to one million, and achieve an average mean of approximately 10−7 for the relative error. The design is modeled using Verilog HDL and synthesized under the TSMC 40-nm CMOS technology. The report shows a maximum frequency of 2.083 GHz with $197421.00~{\mu }\text{m}^{2}$ area. The area decreases to $169689.98~{\mu }\text{m}^{2}$ when the frequency lowers to 1.00 GHz. [ABSTRACT FROM AUTHOR]

This article proposes a robust method for the synthesis and design of optimal linear group delay filters with prescribed bandwidth and dispersion properties. The proposed filters are based on a cascade of second-order all-pass filter cells, for which all the parameters are optimized in order to reach the desired wideband linear group delay characteristic with positive slope. Compared to the previously published synthesis method, the proposed approach offers appropriate initialization enabling convergence and aiming for the optimal solution. The method’s convergence and robustness are proved through a 21-cells synthesis, which is the highest number of cascaded cells reported to date, due to the usual convergence problem. Then the electronic feasibility is illustrated through the measurement results of a lumped-elements linear group-delay filter prototype dimensioned with this method. The measured group delay presents a positive slope of 8 ns GHz−1 in the frequency range [100–725] MHz. It is, to the best of our knowledge, the highest positive slope reported to date with an electronic implementation (i.e except SAW and waveguide devices). [ABSTRACT FROM AUTHOR]

This paper studies consensus problems of multi-agent systems with binary-valued communications. Different from most existing works, the agents considered in this paper can only get binary-valued observations of its neighbors’ states with random noises. A consensus algorithm is proposed: first, each agent estimates its neighbors’ states by the recursive projection algorithm; then, each agent designs the control timely based on the estimates. It is proved that the estimates of the states can converge to the true states with a faster convergence rate than that in the parameter estimation. Moreover, the states of the agents can achieve mean-square consensus, and the corresponding consensus speed can achieve $O(1/t)$ under certain conditions. Finally, simulations are given to demonstrate the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we consider the composition optimization with two expected-value functions in the form of $({1}/{n})\sum _{i = 1}^{n} F_{i}\left({({1}/{m})\sum _{j = 1}^{m} G_{j}(x)}\right)+R(x)$ , which formulates many important problems in statistical learning and machine learning such as solving Bellman equations in reinforcement learning and nonlinear embedding. Full gradient- or classical stochastic gradient descent-based optimization algorithms are unsuitable or computationally expensive to solve this problem due to the inner expectation $({1}/{m})\sum _{j = 1}^{m} G_{j}(x)$. We propose a dualityfree-based stochastic composition method that combines the variance reduction methods to address the stochastic composition problem. We apply the stochastic variance reduction gradient- and stochastic average gradient algorithm-based methods to estimate the inner function and the dualityfree method to estimate the outer function. We prove the linear convergence rate not only for the convex composition problem but also for the case that the individual outer functions are nonconvex, while the objective function is strongly convex. We also provide the results of experiments that show the effectiveness of our proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the proper orthogonal decomposition (POD) method to numerically solve the forward Kolmogorov equation (FKE). Our method aims to explore the low-dimensional structures in the solution space of the FKE and to develop efficient numerical methods. As an important application and our primary motivation to study the POD method to FKE, we solve the nonlinear filtering (NLF) problems with a real-time algorithm proposed by Yau and Yau combined with the POD method. This algorithm is referred as POD algorithm in this paper. Our POD algorithm consists of offline and online stages. In the offline stage, we construct a small number of POD basis functions that capture the dynamics of the system and compute propagation of the POD basis functions under the FKE operator. In the online stage, we synchronize the coming observations in a real-time manner. Its convergence analysis has also been discussed. Some numerical experiments of the NLF problems are performed to illustrate the feasibility of our algorithm and to verify the convergence rate. Our numerical results show that the POD algorithm provides considerable computational savings over existing numerical methods. [ABSTRACT FROM AUTHOR]

The limited memory version of the Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) algorithm is the most popular quasi-Newton algorithm in machine learning and optimization. Recently, it was shown that the stochastic L-BFGS (sL-BFGS) algorithm with the variance-reduced stochastic gradient converges linearly. In this paper, we propose a new sL-BFGS algorithm by importing a proper momentum. We prove an accelerated linear convergence rate under mild conditions. The experimental results on different data sets also verify this acceleration advantage. [ABSTRACT FROM AUTHOR]

Sparsified kernel adaptive filters (SKAFs) is an attractive filtering solution with low memory and computational complexity. Most of existing SKAFs are based on the mean square error (MSE) criterion under Gaussian noise assumption for its simplicity and convenience. When the assumption deviates largely from the underlying truth, the performance of these methods could degrade significantly. In this paper, we propose a novel SKAF, named as projected kernel least mean p-power algorithm (PKLMP), based on the mean p-power error (MPE) criterion and vector projection (VP) method. We provide convergence analyses in terms of the stead-state MSE, based on a Taylor expansion method, and derive the lower and upper bounds for the steady-state excess MSE. We also conduct mean convergence analysis for PKLMP, and derive convergence conditions. To exploit the information in the desired outputs, we further derive a modified PKLMP by smoothing the desired signal. Finally, a simple and effective online variable kernel centers strategy is proposed to improve the filtering performance of the proposed KAFs. Simulation results under a static function estimation, a chaotic time-series prediction, and two real-world time-series predictions are conducted and validate the effectiveness of the proposed PKLMP algorithms. [ABSTRACT FROM AUTHOR]

Predefined mymargin finite-time output containment control problem for nonlinear multi-agent systems with multiple dynamical leaders under directed topology is investigated, where the outputs of followers can converge to the predefined convex hull formed by the multiple leaders within a finite time, and the leaders can have unknown control inputs. Firstly, for the directed topological structure among the followers, a distributed adaptive observer is designed to estimate the whole states of all the leaders under the influences of the leaders’ unknown inputs. By utilizing Hardy’s inequality and common Lyapunov theory, the finite-time convergence of the proposed observer is proved. On the basis of this conclusion, a predefined distributed containment control protocol including the desired convex combinations of the leaders is developed for each follower by using the given weights. Then an algorithm is proposed to design the control parameters in the proposed containment control protocol. With the help of the output regulation theory, the finite-time output containment criterion for nonlinear multi-agent systems in the presence of the leaders’ unknown inputs is derived. Finally, a numerical simulation example is presented to demonstrate the effectiveness of the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, two control schemes producing a continuous control signal are presented for a perturbed triple integrator: The continuous twisting algorithm (3-CTA) and the output feedback continuous twisting algorithm (3-OFCTA). The first one is a state feedback controller that ensures global finite-time stability of the origin, despite of Lipschitz, nonvanishing, and matched disturbances. It provides steady-state precision of fourth order of the output w.r.t. sampling step. The second one is an output feedback controller, which uses a third-order robust and exact differentiator as an observer. By requiring only information of the measurable output, the 3-OFCTA preserves all features of robustness, convergence, and precision of the state feedback 3-CTA. Moreover, it is proven that a separation principle applies, so that the gains of the controller and of the observer can be selected independently to assure stability. [ABSTRACT FROM AUTHOR]

Growth transformations constitute a class of fixed-point multiplicative update algorithms that were originally proposed for optimizing polynomial and rational functions over a domain of probability measures. In this paper, we extend this framework to the domain of bounded real variables which can be applied towards optimizing the dual cost function of a generic support vector machine (SVM). The approach can, therefore, not only be used to train traditional soft-margin binary SVMs, one-class SVMs, and probabilistic SVMs but can also be used to design novel variants of SVMs with different types of convex and quasi-convex loss functions. In this paper, we propose an efficient training algorithm based on polynomial growth transforms, and compare and contrast the properties of different SVM variants using several synthetic and benchmark data sets. The preliminary experiments show that the proposed multiplicative update algorithm is more scalable and yields better convergence compared to standard quadratic and nonlinear programming solvers. While the formulation and the underlying algorithms have been validated in this paper only for SVM-based learning, the proposed approach is general and can be applied to a wide variety of optimization problems and statistical learning models. [ABSTRACT FROM AUTHOR]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an iterative learning control (ILC) algorithm with gain adaptation for discrete-time stochastic systems. The algorithm is based on Kesten's accelerated stochastic approximation (SA) algorithm. The gain adaptation uses only tracking error information, and, hence, is a data-driven adaptation approach. If stochastic noises account for a small proportion of the tracking error, the learning gain matrix remains constant with a high probability. If stochastic noises dominate the tracking error, the learning gain matrix is decreasing. Therefore, the new ILC algorithm converges more quickly than existing SA-based algorithms. In addition, the classic P-type ILC law for noise-free systems is a special case of the new ILC algorithm. The behaviors of the proposed ILC algorithm are demonstrated through examples. [ABSTRACT FROM AUTHOR]

In this paper, a numerically robust solver for least-square problems with bounded variables (BVLS) is presented for applications including, but not limited to, model predictive control (MPC). The proposed BVLS algorithm solves the problem efficiently by employing a recursive QR factorization method based on Gram–Schmidt orthogonalization. A reorthogonalization procedure that iteratively refines the QR factors provides numerical robustness for the described primal active-set method, which solves a system of linear equations in each of its iterations via recursive updates. The performance of the proposed BVLS solver, which is implemented in C without external software libraries, is compared in terms of computational efficiency against state-of-the-art quadratic programming solvers for small- to medium-sized random BVLS problems and a typical example of embedded linear MPC application. The numerical tests demonstrate that the solver performs very well even when solving ill-conditioned problems in single-precision floating-point arithmetic. [ABSTRACT FROM AUTHOR]

This paper studies linear stochastic approximation (SA) algorithms and their application to multiagent systems in engineering and sociology. As main contribution, we provide necessary and sufficient conditions for convergence of linear SA algorithms to a deterministic or random final vector. We also characterize the system convergence rate, when the system is convergent. Moreover, differing from non-negative gain functions in traditional SA algorithms, this paper considers also the case when the gain functions are allowed to take arbitrary real numbers. Using our general treatment, we provide necessary and sufficient conditions to reach consensus and group consensus for first-order discrete-time multiagent system over random signed networks and with state-dependent noise. Finally, we extend our results to the setting of multidimensional linear SA algorithms and characterize the behavior of the multidimensional Friedkin–Johnsen model over random interaction networks. [ABSTRACT FROM AUTHOR]

The convergence of the waveform relaxation (WR) method is demonstrated for a class of circuits: Chains of identical and symmetrical passive subcircuits. The WR algorithm uses resistive coupling to implement the iteration. Every part is modeled as a symmetric and reciprocal linear two-port network. The iteration matrices of the WR operator are constructed for the Gauss-Jacobi and Gauss-Seidel relaxations in the Fourier domain. An upperbound estimate of the spectral radius of the WR operator is presented. It demonstrates the convergence of the method independently of the number of cascaded parts in the chain and the coupling resistance. [ABSTRACT FROM AUTHOR]

Memory is one of the most important mechanisms in recurrent neural networks (RNNs) learning. It plays a crucial role in practical applications, such as sequence learning. With a good memory mechanism, long term history can be fused with current information, and can thus improve RNNs learning. Developing a suitable memory mechanism is always desirable in the field of RNNs. This paper proposes a novel memory mechanism for RNNs. The main contributions of this paper are: 1) an auxiliary memory unit (AMU) is proposed, which results in a new special RNN model (AMU-RNN), separating the memory and output explicitly and 2) an efficient learning algorithm is developed by employing the technique of error flow truncation. The proposed AMU-RNN model, together with the developed learning algorithm, can learn and maintain stable memory over a long time range. This method overcomes both the learning conflict problem and gradient vanishing problem. Unlike the traditional method, which mixes the memory and output with a single neuron in a recurrent unit, the AMU provides an auxiliary memory neuron to maintain memory in particular. By separating the memory and output in a recurrent unit, the problem of learning conflicts can be eliminated easily. Moreover, by using the technique of error flow truncation, each auxiliary memory neuron ensures constant error flow during the learning process. The experiments demonstrate good performance of the proposed AMU-RNNs and the developed learning algorithm. The method exhibits quite efficient learning performance with stable convergence in the AMU-RNN learning and outperforms the state-of-the-art RNN models in sequence generation and sequence classification tasks. [ABSTRACT FROM AUTHOR]

Conjugate gradient (CG) methods are a class of important methods for solving linear equations and nonlinear optimization problems. In this paper, we propose a new stochastic CG algorithm with variance reduction and we prove its linear convergence with the Fletcher and Reeves method for strongly convex and smooth functions. We experimentally demonstrate that the CG with variance reduction algorithm converges faster than its counterparts for four learning models, which may be convex, nonconvex or nonsmooth. In addition, its area under the curve performance on six large-scale data sets is comparable to that of the LIBLINEAR solver for the $L2$ -regularized $L2$ -loss but with a significant improvement in computational efficiency. 1 CGVR algorithm is available on github: https://github.com/xbjin/cgvr [ABSTRACT FROM AUTHOR]

This paper presents a discrete-time distributed and noncooperative routing algorithm, which is proved, via Lyapunov arguments, to asymptotically converge to a specific equilibrium condition among the traffic flows over the network paths, known as Wardrop equilibrium. This convergence result improves the discrete-time algorithms in the literature, which achieve approximate convergence to the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents a bounded confidence gossip algorithm for describing the process of opinion formation over a communication network. Each agent in the network keeps a time-varying opinion vector (or state), which represents its opinion about a set of matters. A common confidence threshold is set for all of the agents. The states of agents in the network will be updated time by time according to an iterative procedure: At each time, 1) one agent is chosen randomly, then it chooses one of its neighbors on the communication graph to contact with; 2) they exchange their states; and 3) if they have different states and the distance between their states is strictly smaller than the confidence threshold, they update their states as the average of the two. This algorithm converges almost surely to some equilibrium point such that any two adjacent agents either have the same state or have distinct states whose distance is no less than the confidence threshold. This is called the constant confidence threshold algorithm. An increasing confidence threshold algorithm, which repeats the constant confidence threshold algorithm several times with increasing confidence threshold, is also proposed. The algorithm is also convergent almost surely to some equilibrium point. Applicability of the method to clustering problems is shown through numerical examples. [ABSTRACT FROM AUTHOR]

This paper presents a family of robust set-membership normalized subband adaptive filtering (RSM-NSAF) algorithms for acoustic echo cancellation (AEC). By using a new robust set-membership error bound, the RSM-NSAF algorithm obtains improved robustness against impulsive noises and decreased steady-state misalignment relative to the conventional set-membership NSAF (SM-NSAF) algorithm. To exploit the sparsity of the impulse response, the L0 norm constraint robust set-membership NSAF ( L0 -RSM-NSAF), robust set-membership improved proportionate NSAF (RSM-IPNSAF), and L0 norm constraint robust set-membership improved proportionate NSAF ( L0 -RSM-IPNSAF) algorithms are derived by minimizing a differentiable cost function that utilizes the Riemannian distance between the updated and previous weight vectors as well as the L0 norm of the weighted updated weight vector. Simulations in AEC application confirm the improvements of the proposed algorithms in performance. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a distance-based formation control strategy for a group of mobile agents to achieve almost global convergence to a target formation shape provided that the formation is represented by a complete graph, and each agent is governed by a single-integrator model. The fundamental idea of achieving almost global convergence is to use a virtual formation of which the dimension is augmented with some virtual coordinates. We define a cost function associated with the virtual formation and apply the gradient-descent algorithm to the cost function so that the function has a global minimum at the target formation shape. We show that all agents finally achieve the target formation shape for almost all initial conditions under the proposed control law. [ABSTRACT FROM AUTHOR]

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods. [ABSTRACT FROM PUBLISHER]

Consider a connected network of agents endowed with local cost functions representing private objectives. Agents seek to find an agreement on some minimizer of the aggregate cost, by means of repeated communications between neighbors. Consensus on the average over the network, usually addressed by gossip algorithms, is a special instance of this problem, corresponding to quadratic private objectives. Consensus on the median, or more generally, consensus on a given quantile, is also a special instance of this problem. In this paper we show that optimizing the aggregate cost function regularized by a total variation (TV) term has appealing properties. First, it can be done very naturally in a distributed way, yielding algorithms that are efficient on numerical simulations. Secondly, the optimum for the regularized cost is shown to be also the optimum for the initial aggregate cost function under assumptions that are simple to state. Finally, these algorithms are robust to unreliable agents that keep injecting some false value in the network. This is remarkable enough, and is not the case, for instance, of gossip algorithms that are entirely ruled by unreliable agents as detailed in the paper. [ABSTRACT FROM PUBLISHER]

This paper proposes a continuous-time distributed algorithm for multiagent networks to achieve a solution with the minimum $l_1$ -norm to underdetermined linear equations. The proposed algorithm comes from a combination of the Filippov set-valued map with the projection-consensus flow. Given the underlying network is undirected and fixed, it is shown that the proposed algorithm drives all agents’ individual states to converge in finite time to a common value, which is the minimum $l_1$ -norm solution. [ABSTRACT FROM AUTHOR]

We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents’ decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators. [ABSTRACT FROM AUTHOR]

Many problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm. [ABSTRACT FROM AUTHOR]

This paper concerns a spectral estimation problem in which we want to find a spectral density function that is consistent with estimated second-order statistics. It is an inverse problem admitting multiple solutions, and selection of a solution can be based on prior functions. We show that the problem is well-posed when formulated in a parametric fashion, and that the solution parameter depends continuously on the prior function. In this way, we are able to obtain a smooth parametrization of admissible spectral densities. Based on this result, the problem is reparametrized via a bijective change of variables out of a numerical consideration, and then a continuation method is used to compute the unique solution parameter. Numerical aspects, such as convergence of the proposed algorithm and certain computational procedures are addressed. A simple example is provided to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distributed Newton method for decenteralized optimization of large sums of convex functions. Our proposed method is based on creating a set of separable finite sum minimization problems by utilizing a decomposition technique known as Global Consensus that distributes the computation across nodes of a graph and enforces a consensus constraint among the separated variables. The key idea is to exploit the sparsity of the dual Hessian and recast the computation of the Newton step as one of the efficiently solving symmetric diagonally dominant linear equations. We show that our method outperforms the state-of-the-art algorithms, including ADMM. We validate our algorithm both theoretically and empirically. On the theory side, we demonstrate that our algorithm exhibits superlinear convergence within a neighborhood of optimality. Empirically, we show the superiority of this new method on a variety of large-scale optimization problems. The proposed approach is scalable to large problems and has a low communication overhead. [ABSTRACT FROM AUTHOR]

This article develops a communication-efficient algorithm to solve the stochastic optimization problem defined over a distributed network, aiming at reducing the burdensome communication in applications, such as distributed machine learning. Different from the existing works based on quantization and sparsification, we introduce a communication-censoring technique to reduce the transmissions of variables, which leads to our communication-censored distributed stochastic gradient descent (CSGD) algorithm. Specifically, in CSGD, the latest minibatch stochastic gradient at a worker will be transmitted to the server if and only if it is sufficiently informative. When the latest gradient is not available, the stale one will be reused at the server. To implement this communication-censoring strategy, the batch size is increasing in order to alleviate the effect of stochastic gradient noise. Theoretically, CSGD enjoys the same order of convergence rate as that of SGD but effectively reduces communication. Numerical experiments demonstrate the sizable communication saving of CSGD. [ABSTRACT FROM AUTHOR]

In this article, distributed algorithms are proposed for training a group of neural networks with private data sets. Stochastic gradients are utilized in order to eliminate the requirement for true gradients. To obtain a universal model of the distributed neural networks trained using local data sets only, consensus tools are introduced to derive the model toward the optimum. Most of the existing works employ diminishing learning rates, which are often slow and impracticable for online learning, while constant learning rates are studied in some recent works, but the principle for choosing the rates is not well established. In this article, constant learning rates are adopted to empower the proposed algorithms with tracking ability. Under mild conditions, the convergence of the proposed algorithms is established by exploring the error dynamics of the connected agents, which provides an upper bound for selecting the constant learning rates. Performances of the proposed algorithms are analyzed with and without gradient noises, in the sense of mean square error (MSE). It is proved that the MSE converges with bounded errors determined by the gradient noises, and the MSE converges to zero if the gradient noises are absent. Simulation results are provided to validate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider the problem of two-player zero-sum games. This problem is formulated as a min–max Markov game in this article. The solution of this game, which is the min–max payoff, starting from a given state is called the min–max value of the state. In this article, we compute the solution of the two-player zero-sum game, utilizing the technique of successive relaxation that has been successfully applied in this article to compute a faster value iteration algorithm in the context of Markov decision processes. We extend the concept of successive relaxation to the setting of two-player zero-sum games. We show that, under a special structure on the game, this technique facilitates faster computation of the min–max value of the states. We then derive a generalized minimax Q-learning algorithm, which computes the optimal policy when the model information is not known. Finally, we prove the convergence of the proposed generalized minimax Q-learning algorithm utilizing stochastic approximation techniques, under an assumption on the boundedness of iterates. Through experiments, we demonstrate the [ABSTRACT FROM AUTHOR]

Focal underdetermined system solver (FOCUSS) is a powerful method for basis selection and sparse representation, where it employs the \ell \vphantom {Rjlp} -norm with $p\in (0,2)$ to measure the sparsity of solutions. In this paper, we give a systematical analysis on the rate of convergence of the FOCUSS algorithm with respect to $p\in (0,2)$ . We prove that the FOCUSS algorithm converges superlinearly for $0

This paper considers the problem of a leader that seeks to optimally influence the opinions of agents in a directed network through connecting with a limited number of the agents (“direct followers”), possibly in the presence of a fixed competing leader. The settings involving a single leader and two competing leaders are unified into a general combinatoric optimization problem, for which two heuristic approaches are developed. The first approach is based on a convex relaxation scheme, possibly in combination with the $\ell _1$ -norm regularization technique, and the second is based on a greedy selection strategy. The main technical novelties of this work are in the establishment of supermodularity of the objective function and convexity of its continuous relaxation. The greedy approach is guaranteed to have a lower bound on the approximation ratio sharper than $(1-1/e)$ , while the convex approach can benefit from efficient (customized) numerical solvers to have practically comparable solutions possibly with faster computation times. The two approaches can be combined to provide improved results. In numerical examples, the approximation ratio can be made to reach ${\text{90}\%}$ or higher depending on the number of direct followers. [ABSTRACT FROM AUTHOR]

In this paper, we study the interacting multiple model (IMM) estimator for networked control systems with packet loss but without packet acknowledgment (ACK). The ACK is a signal sent by the actuator to inform the estimator of whether control packets are lost or not. A system with ACK is usually called a transmission control protocol (TCP) like system; otherwise, it is called a user datagram protocol (UDP) like system. We show that the stability of the IMM estimator for UDP-like systems is determined by the observation packet arrival rate (p.a.r.) and is independent of the control p.a.r. and control inputs. The IMM estimator is stable if the observation p.a.r. is greater than a critical value. We show that this critical value is the same as the critical value for the stability of the optimal estimator for its corresponding TCP-like system. If control inputs eventually tend to zero, the error covariance of the IMM estimator converges to that of the optimal estimator for TCP-like systems. We characterize the impact of the control/observation p.a.r. and the control input on estimation performance. Finally, we prove that the average estimation performance of the IMM estimator approximates that of the optimal estimator within a finite bound, and is superior to that of the linear minimum mean square error estimator. [ABSTRACT FROM AUTHOR]

This paper proposes a distributed model predictive control (MPC) approach for a family of discrete-time linear systems with local (uncoupled) and global (coupled) constraints. The proposed approach is based on the dual problem of an overall MPC optimization problem involving all systems, which is then solved distributively using a modified distributed Nesterov-accelerated-gradient algorithm. To further reduce the computational requirement, this approach allows for early termination of the distributed gradient algorithm. This is made possible via a consensus algorithm that determines the satisfaction of the termination condition and by appropriate tightening of the coupled constraints. Under reasonable assumptions, the approach is able to produce a suboptimal solution as long as the network of the systems is connected while ensuring recursive feasibility and exponential stability of the closed-loop system. The performance of the proposed approach is demonstrated by a numerical example. [ABSTRACT FROM AUTHOR]

The problems discussed in this article are motivated by general ratio consensus algorithms, introduced by Kempe et al. in 2003 in a simple form as the push-sum algorithm, later extended by Bénézit et al. in 2010 under the name weighted gossip algorithm. We consider a communication protocol described by a strictly stationary, ergodic, sequentially primitive sequence of nonnegative matrices, applied iteratively to a pair of fixed initial vectors, the components of which are called values and weights defined at the nodes of a network. The subject of ratio consensus problems is to study the asymptotic properties of ratios of values and weights at each node, expecting convergence to the same limit for all nodes. The main results of this article provide upper bounds for the rate of the almost sure exponential convergence in terms of the spectral gap associated with the given sequence of random matrices. It will be shown that these upper bounds are sharp. Our results complement previous results of Picci and Taylor in 2013 and Iutzeler et al. in 2013. [ABSTRACT FROM AUTHOR]

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithms are decentralized in that each decision maker has access only to its own decisions and cost realizations as well as the state transitions; in particular, each decision maker is completely oblivious to the presence of the other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games. [ABSTRACT FROM AUTHOR]

This paper proposes a control algorithm based on adaptive dynamic programming to solve the infinite-horizon optimal control problem for known deterministic nonlinear systems with saturating actuators and nonquadratic cost functionals. The algorithm is based on an actor/critic framework, where a critic neural network (NN) is used to learn the optimal cost, and an actor NN is used to learn the optimal control policy. The adaptive control nature of the algorithm requires a persistence of excitation condition to be a priori validated, but this can be relaxed using previously stored data concurrently with current data in the update of the critic NN. A robustifying control term is added to the controller to eliminate the effect of residual errors, leading to the asymptotically stability of the closed-loop system. Simulation results show the effectiveness of the proposed approach for a controlled Van der Pol oscillator and also for a power system plant. [ABSTRACT FROM AUTHOR]

In this paper, we consider the learning problem of multilayer perceptrons (MLPs) formulated as the problem of minimizing a smooth error function. As well known, the learning problem of MLPs can be a difficult nonlinear nonconvex optimization problem. Typical difficulties can be the presence of extensive flat regions and steep sided valleys in the error surface, and the possible large number of training data and of free network parameters. We define a wide class of batch learning algorithms for MLP, based on the use of block decomposition techniques in the minimization of the error function. The learning problem is decomposed into a sequence of smaller and structured minimization problems in order to advantageously exploit the structure of the objective function. Theoretical convergence results are established, and a specific algorithm is constructed and evaluated through an extensive numerical experimentation. The comparisons with the state-of-the-art learning algorithms show the effectiveness of the proposed techniques. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) and symmetric NMF (SymNMF) have been shown to be effective for clustering linearly separable data and nonlinearly separable data, respectively. Nevertheless, many practical applications demand constrained algorithms in which a small number of constraints in the form of must-link and cannot-link are available. In this paper, we propose an NMF-based constrained clustering framework in which the similarity between two points on a must-link is enforced to approximate 1 and the similarity between two points on a cannot-link is enforced to approximate 0. We then formulate the framework using NMF and SymNMF to deal with clustering of linearly separable data and nonlinearly separable data, respectively. Furthermore, we present multiplicative update rules to solve them and show the correctness and convergence. Experimental results on various text data sets, University of California, Irvine (UCI) data sets, and gene expression data sets demonstrate the superiority of our algorithms over existing constrained clustering algorithms. [ABSTRACT FROM AUTHOR]

In many real-world applications, data are represented by matrices or high-order tensors. Despite the promising performance, the existing 2-D discriminant analysis algorithms employ a single projection model to exploit the discriminant information for projection, making the model less flexible. In this paper, we propose a novel compound rank- $k$ projection (CRP) algorithm for bilinear analysis. The CRP deals with matrices directly without transforming them into vectors, and it, therefore, preserves the correlations within the matrix and decreases the computation complexity. Different from the existing 2-D discriminant analysis algorithms, objective function values of CRP increase monotonically. In addition, the CRP utilizes multiple rank- $k$ projection models to enable a larger search space in which the optimal solution can be found. In this way, the discriminant ability is enhanced. We have tested our approach on five data sets, including UUIm, CVL, Pointing’04, USPS, and Coil20. Experimental results show that the performance of our proposed CRP performs better than other algorithms in terms of classification accuracy. [ABSTRACT FROM PUBLISHER]

An accelerated algorithm is proposed in this article for solving the linear quadratic optimal consensus problem of multiagent systems. To optimize the linear quadratic response and the final consensus state simultaneously, a nonseparable multiobjective optimization problem with coupled constraints on decision variables is formulated. The main difficulty in solving the optimization problem lies in the nonlinear coupling of objectives, which is overcome by separating the problem into two independent and solvable single-objective optimization subproblems using the alternating direction method of multipliers. The proximal gradient decent scheme is then introduced to approximate the precise optimal solutions of the subproblems so as to improve the computing efficiency. Convergence analysis is performed to estimate the convergence rate and derive the convergence condition, which is independent of any global information of the system and, therefore, is fully distributed. Furthermore, the solution of each subproblem is obtained in a distributed form, allowing the multiagent system to achieve optimal consensus. Numerical examples show the effectiveness of the accelerated algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present complexity certification results for a distributed augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the accelerated distributed AL (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $\epsilon$-optimal solution both in terms of suboptimality and infeasibility is O(\frac{1}{\epsilon }) iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier, which enables us to explicitly specify these complexity bounds. We also show how to choose the step-size parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control problem, involving a finite number of subsystems, which interact with each other via a general network. [ABSTRACT FROM PUBLISHER]

In this paper, source localization by a network of primitive binary sensors under various imperfections are studied. Detailed analysis and mathematical modeling of imperfect binary sensors are presented. Imperfections include sensor failures of two types, drifting, uncertainty, and heterogeneity in binary sensor trigger thresholds, presence of noise, and nonradial symmetry of sensing ranges. Theoretical results, including asymptotical convergence, are established, in particular in the presence of substantial outliers due to sensor failure and large noise. Efficient numerical algorithms are proposed and simulated supporting the theoretical analysis. [ABSTRACT FROM PUBLISHER]