Search

Dropout and DropConnect are two techniques to facilitate the regularization of neural network models, having achieved the state-of-the-art results in several benchmarks. In this paper, to improve the generalization capability of spiking neural networks (SNNs), the two drop techniques are first applied to the state-of-the-art SpikeProp learning algorithm resulting in two improved learning algorithms called SPDO (SpikeProp with Dropout) and SPDC (SpikeProp with DropConnect). In view that a higher membrane potential of a biological neuron implies a higher probability of neural activation, three adaptive drop algorithms, SpikeProp with Adaptive Dropout (SPADO), SpikeProp with Adaptive DropConnect (SPADC), and SpikeProp with Group Adaptive Drop (SPGAD), are proposed by adaptively adjusting the keep probability for training SNNs. A convergence theorem for SPDC is proven under the assumptions of the bounded norm of connection weights and a finite number of equilibria. In addition, the five proposed algorithms are carried out in a collaborative neurodynamic optimization framework to improve the learning performance of SNNs. The experimental results on the four benchmark data sets demonstrate that the three adaptive algorithms converge faster than SpikeProp, SPDO, and SPDC, and the generalization errors of the five proposed algorithms are significantly smaller than that of SpikeProp. Furthermore, the experimental results also show that the five algorithms based on collaborative neurodynamic optimization can be improved in terms of several measures. [ABSTRACT FROM AUTHOR]

The paper considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. It is shown that, contrary to GD, NGD escapes saddle points “quickly.” A serious shortcoming of GD in nonconvex problems is that it can take arbitrarily long to escape from the neighborhood of a saddle point. In practice, this issue can significantly slow the convergence of GD, particularly in high-dimensional nonconvex problems. The paper focuses on continuous-time dynamics. It is shown that 1) NGD “almost never” converges to saddle points and 2) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa }r$ , where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As a simple application of these results, a global convergence-time bound is established for NGD under mild assumptions. [ABSTRACT FROM AUTHOR]

Recently, Thompson sampling has been shown to achieve good theoretical performance guarantees for stochastic control problems with parameter uncertainty when the state, control, and parameter spaces are all finite. Much less is known however about the performance of Thompson sampling when applied to continuous or more general spaces, which constitutes an important class of problems in practice. In this paper, we study Thompson sampling when applied to a broad class of average cost stochastic control problems where the state, control, and parameter spaces are all general measurable spaces. The main contributions of our paper are establishing theoretical performance guarantees for Thompson sampling as measured by: first, expected posterior sampling error; and second, average per period regret. [ABSTRACT FROM AUTHOR]

This paper deals with the estimation of convergence rate and domain of attraction of control-Lyapunov functions in Lyapunov-based control. This pair of estimation problems has been considered only for input-affine systems with constraints on the input norm. In this paper, we propose a novel optimization framework to address the estimation of convergence rate and domain of attraction. Specifically, we formulate the estimation problems as min–max bilevel programs for the decay rate of the Lyapunov function, where the inner problem can be resolved using Karush–Kuhn–Tucker optimality conditions, and the resulting single-level programs can be transformed into and solved as mixed-integer nonlinear programs. The proposed approach is applicable to systems with input-nonaffinity or more general forms of input constraints under an input-convexity assumption. [ABSTRACT FROM AUTHOR]

This paper investigates the distributed computation of the well-known linear matrix equation in the form of ${{AXB}} = F$ , with the matrices $A$ , $B$ , $X$ , and $F$ of appropriate dimensions, over multiagent networks from an optimization perspective. In this paper, we consider the standard distributed matrix-information structures, where each agent of the considered multiagent network has access to one of the subblock matrices of $A$ , $B$ , and $F$. To be specific, we first propose different decomposition methods to reformulate the matrix equations in standard structures as distributed constrained optimization problems by introducing substitutional variables; we show that the solutions of the reformulated distributed optimization problems are equivalent to least squares solutions to original matrix equations; and we design distributed continuous-time algorithms for the constrained optimization problems, even by using augmented matrices and a derivative feedback technique. Moreover, we prove the exponential convergence of the algorithms to a least squares solution to the matrix equation for any initial condition. [ABSTRACT FROM AUTHOR]

In this paper, we consider the regularized version of the Jacobi algorithm, a block coordinate descent method for convex optimization with an objective function consisting of the sum of a differentiable function and a block-separable function. Under certain regularity assumptions on the objective function, this algorithm has been shown to satisfy the so-called sufficient decrease condition, and consequently, to converge in objective function value. In this paper, we revisit the convergence analysis of the regularized Jacobi algorithm and show that it also converges in iterates under very mild conditions on the objective function. Moreover, we establish conditions under which the algorithm achieves a linear convergence rate. [ABSTRACT FROM PUBLISHER]

This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)—A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples. [ABSTRACT FROM PUBLISHER]

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]

One of the most important problems in the field of distributed optimization is the problem of minimizing a sum of local convex objective functions over a networked system. Most of the existing work in this area focuses on developing distributed algorithms in a synchronous setting under the presence of a central clock, where the agents need to wait for the slowest one to finish the update, before proceeding to the next iterate. Asynchronous distributed algorithms remove the need for a central coordinator, reduce the synchronization wait, and allow some agents to compute faster and execute more iterations. In the asynchronous setting, the only known algorithms for solving this problem could achieve an either linear or sublinear rate of convergence. In this paper, we build upon the existing literature to develop and analyze an asynchronous Newton-based method to solve a penalized version of the problem. We show that this algorithm guarantees almost sure convergence with a global linear and local quadratic rate in expectation. Numerical studies confirm the superior performance of our algorithm against other asynchronous methods. [ABSTRACT FROM AUTHOR]

We study distributed optimization to minimize a sum of smooth and strongly-convex functions. Recent work on this problem uses gradient tracking to achieve linear convergence to the exact global minimizer. However, a connection among different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are related with a simple state transformation, at the heart of which lies a recently introduced algorithm known as  $\mathcal {AB}$. We then present distributed heavy-ball, denoted as  $\mathcal {AB}m$ , that combines  $\mathcal {AB}$ with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights,  $\mathcal {AB}m$ removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation.  $\mathcal {AB}m$ thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that  $\mathcal {AB}m$ has a global $R$ -linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that  $\mathcal {AB}m$ achieves acceleration, particularly when the objective functions are ill-conditioned. [ABSTRACT FROM AUTHOR]

This paper proposes a novel exact asynchronous subgradient-push algorithm (AsySPA) to solve an additive cost optimization problem over digraphs where each node only has access to a local convex function and updates asynchronously with an arbitrary rate. Specifically, each node of a strongly connected digraph does not wait for updates from other nodes but simply starts a new update within any bounded time interval by using local information available from its in-neighbors. “Exact” means that every node of the AsySPA can asymptotically converge to the same optimal solution, even under different update rates among nodes and bounded communication delays. To address uneven update rates, we design a simple mechanism to adaptively adjust stepsizes per update in each node, which is substantially different from the existing works. Then, we construct a delay-free augmented system to address asynchrony and delays, and study its convergence by proposing a generalized subgradient algorithm, which clearly has its own significance and helps us to explicitly evaluate the convergence rate of the AsySPA. Finally, we demonstrate advantages of the AsySPA in both theory and simulation. [ABSTRACT FROM AUTHOR]

This paper investigates distributed control and incentive mechanisms to coordinate distributed energy resources (DERs) with both continuous and discrete decision variables as well as device dynamics in distribution grids. We formulate a multiperiod social welfare maximization problem, and based on its convex relaxation propose a distributed stochastic dual gradient algorithm for managing DERs. We further extend it to an online real-time setting with time-varying operating conditions, asynchronous updates by devices, and feedback being leveraged to account for nonlinear power flows as well as reduce communication overhead. The resulting algorithm provides a general online stochastic optimization algorithm for coordinating networked DERs with discrete power setpoints and dynamics to meet operational and economic objectives and constraints. We characterize the convergence of the algorithm analytically and evaluate its performance numerically. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel strategy to combine a set of compact descriptors to leverage an associated recognition task. We formulate the problem from a multiple kernel learning (MKL) perspective and solve it following a stochastic variance reduced gradient (SVRG) approach to address its scalability, currently an open issue. MKL models are ideal candidates to jointly learn the optimal combination of features along with its associated predictor. However, they are unable to scale beyond a dozen thousand of samples due to high computational and memory requirements, which severely limits their applicability. We propose SVRG-MKL, an MKL solution with inherent scalability properties that can optimally combine multiple descriptors involving millions of samples. Our solution takes place directly in the primal to avoid Gram matrices computation and memory allocation, whereas the optimization is performed with a proposed algorithm of linear complexity and hence computationally efficient. Our proposition builds upon recent progress in SVRG with the distinction that each kernel is treated differently during optimization, which results in a faster convergence than applying off-the-shelf SVRG into MKL. Extensive experimental validation conducted on several benchmarking data sets confirms a higher accuracy and a significant speedup of our solution. Our technique can be extended to other MKL problems, including visual search and transfer learning, as well as other formulations, such as group-sensitive (GMKL) and localized MKL (LMKL) in convex settings. [ABSTRACT FROM AUTHOR]

This paper deals with iterative Jacobian-based recursion technique for the root-finding problem of the vector-valued function, whose evaluations are contaminated by noise. Instead of a scalar step size, we use an iterate-dependent matrix gain to effectively weigh the different elements associated with the noisy observations. The analytical development of the matrix gain is built on an iterative-dependent linear function interfered by additive zero-mean white noise, where the dimension of the function is $ {M\ge 1}$ and the dimension of the unknown variable is $ {N\ge 1}$. Necessary and sufficient conditions for $ {M\ge N}$ algorithms are presented pertaining to algorithm stability and convergence of the estimate error covariance matrix. Two algorithms are proposed: one for the case where $ {M\ge N}$ and the second one for the antithesis. The two algorithms assume full knowledge of the Jacobian. The recursive algorithms are proposed for generating the optimal iterative-dependent matrix gain. The proposed algorithms here aim for per-iteration minimization of the mean square estimate error. We show that the proposed algorithm satisfies the presented conditions for stability and convergence of the covariance. In addition, the convergence rate of the estimation error covariance is shown to be inversely proportional to the number of iterations. For the antithesis $ {M< N}$ , contraction of the error covariance is guaranteed. This underdetermined system of equations can be helpful in training neural networks. Numerical examples are presented to illustrate the performance capabilities of the proposed multidimensional gain while considering nonlinear functions. [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]

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]

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, a novel distributed stochastic approximation algorithm (DSAA) is proposed to seek roots of the sum of local functions, each of which is associated with an agent from multiple agents connected over a network. At each iteration, each agent updates its estimate for the root utilizing the noisy observations of its local function and the information derived from the neighboring agents. The key difference of the proposed algorithm from the existing ones consists in the expanding truncations (so it is called the DSAAWET), by which the boundedness of the estimates can be guaranteed without imposing the growth-rate constraints on the local functions. The estimates generated by the DSAAWET are shown to converge almost surely to a consensus set, which belongs to a connected subset of the root set of the sum function. In comparison with the existing results, we impose weaker conditions on the local functions and on the observation noise. We then apply the proposed algorithm to two applications, one from signal processing and the other one from distributed optimization, and establish the almost sure convergence. Numerical simulation results are also included. [ABSTRACT FROM AUTHOR]

Convolutional sparse coding (CSC) is a useful tool in many image and audio applications. Maximizing the performance of CSC requires that the dictionary used to store the features of signals can be learned from real data. The so-called convolutional dictionary learning (CDL) problem is formulated within a nonconvex, nonsmooth optimization framework. Most existing CDL solvers alternately update the coefficients and dictionary in an iterative manner. However, these approaches are prone to running redundant iterations, and their convergence properties are difficult to analyze. Moreover, most of those methods approximate the original nonconvex sparse inducing function using a convex regularizer to promote computational efficiency. This approach to approximation may result in nonsparse representations and, thereby, hinder the performance of the applications. In this paper, we deal with the nonconvex, nonsmooth constraints of the original CDL directly using the modified forward–backward splitting approach, in which the coefficients and dictionary are simultaneously updated in each iteration. We also propose a novel parameter adaption scheme to increase the speed of the algorithm used to obtain a usable dictionary and in so doing prove convergence. We also show that the proposed approach is applicable to parallel processing to reduce the computing time required by the algorithm to achieve convergence. The experimental results demonstrate that our method requires less time than the existing methods to achieve the convergence point while using a smaller final functional value. We also applied the dictionaries learned using the proposed and existing methods to an application involving signal separation. The dictionary learned using the proposed approach provides performance superior to that of comparable methods. [ABSTRACT FROM AUTHOR]

This paper is devoted to distributed continuous-time and discrete-time optimization problems with nonuniform convex constraint sets and nonuniform stepsizes for general differentiable convex objective functions. The communication graphs are not required to be strongly connected at any time, the gradients of the local objective functions are not required to be bounded when their independent variables tend to infinity, and the constraint sets are not required to be bounded. For continuous-time multiagent systems, a distributed continuous algorithm is first introduced where the stepsizes and the convex constraint sets are both nonuniform. It is shown that all agents reach a consensus while minimizing the team objective function even when the constraint sets are unbounded. After that, the obtained results are extended to discrete-time multiagent systems and then the case where each agent remains in a corresponding convex constraint set is studied. To ensure all agents to remain in a bounded region, a switching mechanism is introduced in the algorithms. It is shown that the distributed optimization problems can be solved, even though the discretization of the algorithms might deviate the convergence of the agents from the minimum of the objective functions. [ABSTRACT FROM AUTHOR]

This paper studies analysis and synthesis problems for diffusively coupled multi-agent systems. We focus on networks comprised of multi-input multi-output nonlinear systems that possess a property we term maximal equilibrium-independent cyclically monotone passivity (MEICMP), which is an extension of recent passivity results. We demonstrate that networks comprised of MEICMP systems are related to a pair of dual network optimization problems. In particular, we show that the steady-state behavior of the multi-agent system correspond to the minimizers of appropriately defined network optimization problems. This optimization perspective leads to a synthesis procedure for designing the network controllers to achieve a desired output. We provide detailed examples of networked systems satisfying these properties and demonstrate the results for a network of damped planar oscillators. [ABSTRACT FROM AUTHOR]

Average consensus underpins key functionalities of distributed systems ranging from distributed information fusion, decision-making, distributed optimization, to load balancing and decentralized control. Existing distributed average consensus algorithms require each node to exchange and disclose state information to its neighbors, which is undesirable in cases where the state is private or contains sensitive information. In this paper, we propose a novel approach that avoids disclosing individual state information in average consensus by letting each node decompose its state into 2 substates. For each node, one of the two substates involves in computation and internode interactions as if it were the original state, while the other substate interacts only with the first substate of the same node, being completely invisible to other nodes. The initial values of the two substates are chosen randomly but with their mean fixed to the initial value of the original state, which is key to guarantee convergence to the desired consensus value. In direct contrast to differential-privacy based privacy-preserving average-consensus approaches, which enable privacy by compromising accuracy in the consensus value, the proposed approach can guarantee convergence to the exact desired value without any error. Not only is the proposed approach able to prevent the disclosure of a node's initial state to honest-but-curious neighbors, it can also provide protection against inference by external eavesdroppers able to wiretap communication links. Numerical simulations demonstrate the effectiveness of the approach and its advantages over state-of-the-art counterparts. [ABSTRACT FROM AUTHOR]

This paper focuses on a distributed convex optimization problem with set constraints, where the local objective functions are convex but not necessarily differentiable. We employ an exact penalty method for the constrained optimization problem to avoid the projection of subgradients to convex sets, which may result in problems about algorithm trajectories caused by maybe nonconvex differential inclusions and quite high computational cost. To effectively find a suitable gain of the penalty function online, we propose an adaptive distributed algorithm with the help of the adaptive control idea in order to achieve an exact solution without any a priori computation or knowledge of the objective functions. By virtue of convex and nonsmooth analysis, we give a rigorous proof for the convergence of the proposed continuous-time algorithm. [ABSTRACT FROM AUTHOR]

Many machine learning problems involve learning a low-rank positive semidefinite matrix. However, existing solvers for this low-rank semidefinite program (SDP) are often expensive. In this paper, by factorizing the target matrix as a product of two matrices and using a Courant penalty to penalize for their difference, we reformulate the SDP as a biconvex optimization problem. This allows the use of multiconvex optimization techniques to define simple surrogates, which can be minimized easily by block coordinate descent. Moreover, while traditionally this biconvex problem approaches the original problem only when the penalty parameter is infinite, we show that the two problems are equivalent when the penalty parameter is sufficiently large. Experiments on a number of SDP applications in machine learning show that the proposed algorithm is as accurate as other state-of-the-art algorithms, but is much faster, especially on large data sets. [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]

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]

In this paper, we consider distributed optimization problems over a multiagent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimizing a class of nonconvex problems and under the challenging setting, where each agent can only access the zeroth-order information (i.e., the functional values) of its local functions. For different types of network topologies, such as undirected connected networks or star networks, we develop efficient distributed algorithms and rigorously analyze their convergence and rate of convergence (to the set of stationary solutions). Numerical results are provided to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes Triangularly Preconditioned Primal- Dual algorithm, a new primal-dual algorithm for minimizing the sum of a Lipschitz-differentiable convex function and two possibly nonsmooth convex functions, one of which is composed with a linear mapping. We devise a randomized block-coordinate (BC) version of the algorithm which converges under the same stepsize conditions as the full algorithm. It is shown that both the original as well as the BC scheme feature linear convergence rate when the functions involved are either piecewise linear-quadratic, or when they satisfy a certain quadratic growth condition (which is weaker than strong convexity). Moreover, we apply the developed algorithms to the problem of multiagent optimization on a graph, thus obtaining novel synchronous and asynchronous distributed methods. The proposed algorithms are fully distributed in the sense that the updates and the stepsizes of each agent only depend on local information. In fact, no prior global coordination is required. Finally, we showcase an application of our algorithm in distributed formation control. [ABSTRACT FROM AUTHOR]

Recently, there is a rapidly increasing attraction for the efficient recovery of low-rank matrix in computer vision and machine learning. The popular convex solution of rank minimization is nuclear norm-based minimization (NNM), which usually leads to a biased solution since NNM tends to overshrink the rank components and treats each rank component equally. To address this issue, some nonconvex nonsmooth rank (NNR) relaxations have been exploited widely. Different from these convex and nonconvex rank substitutes, this paper first introduces a general and flexible rank relaxation function named weighted NNR relaxation function, which is actually derived from the initial double NNR (DNNR) relaxations, i.e., DNNR relaxation function acts on the nonconvex singular values function (SVF). An iteratively reweighted SVF optimization algorithm with continuation technology through computing the supergradient values to define the weighting vector is devised to solve the DNNR minimization problem, and the closed-form solution of the subproblem can be efficiently obtained by a general proximal operator, in which each element of the desired weighting vector usually satisfies the nondecreasing order. We next prove that the objective function values decrease monotonically, and any limit point of the generated subsequence is a critical point. Combining the Kurdyka–Łojasiewicz property with some milder assumptions, we further give its global convergence guarantee. As an application in the matrix completion problem, experimental results on both synthetic data and real-world data can show that our methods are competitive with several state-of-the-art convex and nonconvex matrix completion methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider Newton–Kantorovich type methods for solving control-constrained optimal control problems that appear in model predictive control. Conditions for convergence are established for an inexact version of the Newton–Kantorovich method applied to variational inequalities. Based on these results, two groups of algorithms are proposed to solve the optimality system. The first group includes exact and inexact Newton and Newton–Kantorovich implementations of the sequential quadratic programming. In the second group, exact and inexact Newton and Newton–Kantorovich methods are developed for solving a nonsmooth normal map equation equivalent to the optimality system. Numerical simulations featuring examples from the aerospace and automotive domain are presented, which show that inexact Newton–Kantorovich type methods can achieve significant reduction of the computational time. [ABSTRACT FROM AUTHOR]

The flow network balancing problem, i.e., the problem of balancing the incoming and outgoing flows for each vertex of a directed graph, has been widely investigated with several distributed solutions being proposed in recent years. Flow balancing is crucial in several application domains, ranging from water and traffic networks to complex network synchronization and distributed adaptive networked control. In this paper, we focus on finding the solution for the flow network balancing problem that is optimal in a minimal effort sense. More specifically, we aim at modifying a given set of (unbalanced) flows so that we obtain a balanced solution. We assume that there is a (possibly heterogenous) cost associated to the unit variation of each flow, as well as lower and upper bounds on the peredge flows. More in detail, we first establish a necessary and sufficient optimality condition for network balancing and then propose a distributed protocol, demonstrating its convergence toward the global optimal solution. Simulation results are provided to corroborate the effectiveness of the proposed distributed algorithm. [ABSTRACT FROM AUTHOR]

The recent studies have found that the nonconvex relaxation functions usually perform better than the convex counterparts in the $l_{0}$ -norm and rank function minimization problems. However, due to the absence of convexity in these nonconvex problems, developing efficient algorithms with convergence guarantee becomes very challenging. Inspired by the basic ideas of both the Jacobian alternating direction method of multipliers (JADMMs) for solving linearly constrained problems with separable objectives and the proximal gradient methods (PGMs) for optimizing the unconstrained problems with one variable, this paper focuses on extending the PGMs to the proximal Jacobian iteration methods (PJIMs) for handling with a family of nonconvex composite optimization problems with two splitting variables. To reduce the total computational complexity by decreasing the number of iterations, we devise the accelerated version of PJIMs through the well-known Nesterov’s acceleration strategy and further extend both to solve the multivariable cases. Most importantly, we provide a rigorous convergence analysis, in theory, to show that the generated variable sequence globally converges to a critical point by exploiting the Kurdyka–Łojasiewica (KŁ) property for a broad class of functions. Furthermore, we also establish the linear and sublinear convergence rates of the obtained variable sequence in the objective function. As the specific application to the nonconvex sparse and low-rank recovery problems, several numerical experiments can verify that the newly proposed algorithms not only keep fast convergence speed but also have high precision. [ABSTRACT FROM AUTHOR]

Boosting is a learning scheme that combines weak learners to produce a strong composite learner, with the underlying intuition that one can obtain accurate learner by combining “rough” ones. This paper aims at developing a new boosting strategy, called rescaled boosting (RBoosting), to accelerate the numerical convergence rate and, consequently, improve learning performances of the original boosting. Our studies show that RBoosting possesses the almost optimal numerical convergence rate in the sense that, up to a logarithmic factor, it can reach the minimax nonlinear approximation rate. We then use RBoosting to tackle classification problems and deduce corresponding statistical consistency and tight generalization error estimates. A series of theoretical and experimental results shows that RBoosting outperforms boosting in terms of generalization. [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 considers solving convex quadratic programs in a real-time setting using a regularized and smoothed Fischer–Burmeister method (FBRS). The Fischer–Burmeister function is used to map the optimality conditions of a quadratic program to a nonlinear system of equations which is solved using Newton's method. Regularization and smoothing are applied to improve the practical performance of the algorithm and a merit function is used to globalize convergence. FBRS is simple to code, easy to warmstart, robust to early termination, and has attractive theoretical properties, making it appealing for real time and embedded applications. Numerical experiments using several predictive control examples show that the proposed method is competitive with other state-of-the-art solvers. [ABSTRACT FROM AUTHOR]

In recent years, efficient optimization algorithms for nonlinear model predictive control (NMPC) have been proposed, that significantly reduce the online computational time. In particular, the direct multiple shooting and the sequential quadratic programming (SQP) are used to efficiently solve nonlinear programming (NLP) problems arising from continuous-time NMPC applications. One of the computationally demanding steps for the online optimization is the computation of sensitivities of the nonlinear dynamics at every sampling instant, especially for systems of large dimensions, strong stiffness, and when using long prediction horizons. In this paper, within the algorithmic framework of the real-time iteration scheme based on multiple shooting, an inexact sensitivity updating scheme is proposed, that performs a partial update of the Jacobian of the constraints in the NLP. Such update is triggered by using a curvature-like measure of nonlinearity, so that only sensitivities exhibiting highly nonlinear behavior are updated, thus adapting to system operating conditions and possibly reducing the computational burden. An advanced tuning strategy for the updating scheme is provided to automatically determine the number of sensitivities being updated, with a guaranteed bounded error on the quadratic programming solution. Numerical and control performance of the scheme is evaluated by means of two simulation examples performed on a dedicated implementation. Local convergence analysis is also presented and a tunable convergence rate is proven, when applied to the SQP method. [ABSTRACT FROM AUTHOR]

This paper proposes distributed discrete-time algorithms to cooperatively solve an additive cost optimization problem in multiagent networks. The striking feature lies in the use of only the sign of relative state information between neighbors, which substantially differentiates our algorithms from others in the existing literature. We first interpret the proposed algorithms in terms of the penalty method in optimization theory and then perform nonasymptotic analysis to study convergence for static network graphs. Compared with the celebrated distributed subgradient algorithms, which, however, use the exact relative state information, the convergence speed is essentially not affected by the loss of information. We also study how introducing noise into the relative state information and randomly activated graphs affect the performance of our algorithms. Finally, we validate the theoretical results on a class of distributed quantile regression problems. [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 continuous-time multiagent systems for distributed minimax optimization subject to bounded constraints. All agents in the system are divided into two groups for minimization and maximization. The multiagent system features competitive intergroup interactions and cooperative intragroup interactions, both of which are based on the output information of agents. First, a proportional-integral (PI) intragroup interaction rule is utilized for consensus within each group in the system. With this interaction rule, the system is proved to be convergent to an optimal solution to the problem, under a certain requirement on the intergroup interactions. Second, another discontinuous intragroup interaction rule is introduced. It is proved that the system with such an interaction is still convergent to an optimal solution if the proportional gain exceeds a derived lower bound, without the previous requirement on the intergroup interactions. As a special case, the systems are further applied for distributed optimization. Finally, simulation results are presented to substantiate the theoretical results. [ABSTRACT FROM AUTHOR]

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 kernel methods, the kernels are often required to be positive definitethat restricts the use of many indefinite kernels. To consider those nonpositive definite kernels, in this paper, we aim to build an indefinite kernel learning framework for kernel logistic regression (KLR). The proposed indefinite KLR (IKLR) model is analyzed in the reproducing kernel Kreĭn spaces and then becomes nonconvex. Using the positive decomposition of a nonpositive definite kernel, the derived IKLR model can be decomposed into the difference of two convex functions. Accordingly, a concave-convex procedure (CCCP) is introduced to solve the nonconvex optimization problem. Since the CCCP has to solve a subproblem in each iteration, we propose a concave-inexact-convex procedure (CCICP) algorithm with an inexact solving scheme to accelerate the solving process. Besides, we propose a stochastic variant of CCICP to efficiently obtain a proximal solution, which achieves the similar purpose with the inexact solving scheme in CCICP. The convergence analyses of the above-mentioned two variants of CCCP are conducted. By doing so, our method works effectively not only in a deterministic setting but also in a stochastic setting. Experimental results on several benchmarks suggest that the proposed IKLR model performs favorably against the standard (positive definite) KLR and other competitive indefinite learning-based algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we bring the celebrated max-weight features (myopic and discrete actions) to mainstream convex optimization. Myopic actions are important in control because decisions need to be made in an online manner and without knowledge of future events and discrete actions, because many systems have a finite (so nonconvex) number of control decisions. For example, whether to transmit a packet or not in communication networks. Our results show that these two features can be encompassed in the subgradient method for the Lagrange dual problem by the use of stochastic and $\epsilon$ -subgradients. One of the appealing features of our approach is that it decouples the choice of a control action from a specific choice of subgradient, which allows us to design control policies without changing the underlying convex updates. Two classes of discrete control policies are presented: one that can make discrete actions by looking only at the system's current state, and another that selects actions using blocks. The latter class is useful for handling systems that have constraints on the order in which actions are selected. [ABSTRACT FROM AUTHOR]

This paper is concerned with variational optimal control constructions whose solution yields a sampling algorithm. The particular form of the sampling algorithm considered here is a particle filter, designed to numerically approximate the solution to the global optimization problem. The theoretical significance of this study comes from its variational aspects. Specifically, the control input represents the solution of a mean-field-type optimal control problem. Its parametric counterpart, obtained when a parametric form of density is known a priori, is shown to be equivalent to the natural gradient algorithm. Explicit formulae for the filter are derived when the objective function is quadratic and the density is Gaussian. The optimal control construction of the particle filter is a significant departure from the classical importance sampling–resampling-based approaches. [ABSTRACT FROM AUTHOR]

We consider networks the nodes of which are interconnected via directed edges, each able to admit a flow (or weight) within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. This paper proposes and analyzes a distributed algorithm for obtaining admissible and balanced flows, i.e., flows that are within the given intervals at each edge and are balanced (the total in-flow equals the total out-flow) at each node. The algorithm can also be viewed as a distributed method for obtaining a set of weights that balance a weighted digraph for the case when there are lower and upper limit constraints on the edge weights. The proposed iterative algorithm assumes that communication among pairs of nodes that are interconnected is bidirectional (i.e., the communication topology is captured by the undirected graph that corresponds to the network digraph), and allows the nodes to asymptotically (with geometric rate) reach a set of balanced feasible flows, as long as the (necessary and sufficient) circulation conditions on the given digraph, with the given flow/weight interval constraints on each edge, are satisfied. We also provide a methodology that can be used by the nodes to asymptotically determine, in a distributed manner, when the circulation conditions are not satisfied (thus, making the problem infeasible). Finally, we provide several examples and simulation studies to highlight the role of various parameters involved in the proposed distributed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we address a class of distributed optimization problems in the presence of interagent communication delays based on passivity. We first focus on unconstrained distributed optimization and provide a passivity-based perspective for distributed optimization algorithms. With the help of the scattering transformation, this perspective allows us to handle arbitrary and unknown constant communication delays in the distributed optimization problem. Then, we extend the results to constrained distributed optimization. Finally, the algorithm is applied to a visual human localization problem. [ABSTRACT FROM AUTHOR]

In this paper, we establish necessary and sufficient conditions for global linear convergence rate bounds in operator splitting methods for a general class of convex optimization problems, where the associated fixed-point operator is strongly quasi-nonexpansive. We also provide a tight bound on the achievable convergence rate. Most existing results establishing global linear convergence in such methods require restrictive assumptions regarding strong convexity and smoothness of the constituent functions in the optimization problem. However, there are several examples in the literature showing that linear convergence is possible even when these properties do not hold. We provide a unifying analysis method for establishing global linear convergence based on linear regularity and show that many existing results are special cases of our approach. Moreover, we propose a novel linearly convergent splitting method for linear programming. [ABSTRACT FROM AUTHOR]

As a variant of nonnegative matrix factorization (NMF), symmetric NMF (SNMF) has shown to be effective for capturing the cluster structure embedded in the graph representation. In contrast to the existing SNMF-based clustering methods that empirically construct the similarity matrix and rigidly introduce the supervisory information to the assignment matrix, in this paper, we propose a novel SNMF-based semisupervised clustering method, namely, pairwise constraint propagation-induced SNMF (PCPSNMF). By formulating a single-constrained optimization problem, PCPSNMF is capable of learning the similarity and assignment matricesadaptively and simultaneously, in which a small amount of supervisory information in the form of pairwise constraints is introduced in a flexible way to guide the construction of the similarity matrix, and the two matrices communicate with each other to achieve mutual refinement until convergence. In addition, we propose an efficient alternating iterative algorithm to solve the optimization problem, whose convergence is theoretically proven. Experimental results over several benchmark image data sets demonstrate that PCPSNMF is less sensitive to initialization and produces higher clustering performance, compared with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Mean square error (MSE) is the most prominent criterion in training neural networks and has been employed in numerous learning problems. In this paper, we suggest a group of novel robust information theoretic backpropagation (BP) methods, as correntropy-based conjugate gradient BP (CCG-BP). CCG-BP algorithms converge faster than the common correntropy-based BP algorithms and have better performance than the common CG-BP algorithms based on MSE, especially in nonGaussian environments and in cases with impulsive noise or heavy-tailed distributions noise. In addition, a convergence analysis of this new type of method is particularly considered. Numerical results for several samples of function approximation, synthetic function estimation, and chaotic time series prediction illustrate that our new BP method is more robust than the MSE-based method in the sense of impulsive noise, especially when SNR is low. [ABSTRACT FROM AUTHOR]

Many practical applications such as gene expression analysis, multitask learning, image recognition, signal processing, and medical data analysis pursue a sparse solution for the feature selection purpose and particularly favor the nonzeros evenly distributed in different groups. The exclusive sparsity norm has been widely used to serve to this purpose. However, it still lacks systematical studies for exclusive sparsity norm optimization. This paper offers two main contributions from the optimization perspective: 1) we provide several efficient algorithms to solve exclusive sparsity norm minimization with either smooth loss or hinge loss (nonsmooth loss). All algorithms achieve the optimal convergence rate $O(1/k^{2})$. ($k$ is the iteration number.) To the best of our knowledge, this is the first time to guarantee such convergence rate for the general exclusive sparsity norm minimization and 2) when the group information is unavailable to define the exclusive sparsity norm, we propose to use the random grouping scheme to construct groups and prove that if the number of groups is appropriately chosen, the nonzeros (true features) would be grouped in the ideal way with high probability. Empirical studies validate the efficiency of the proposed algorithms, and the effectiveness of random grouping scheme on the proposed exclusive support vector machine formulation. [ABSTRACT FROM AUTHOR]