Search

In this paper, we propose a variance reduction approach for Markov chains based on additive control variates and the minimization of an appropriate estimate for the asymptotic variance. We focus on the particular case when control variates are represented as deep neural networks. We derive the optimal convergence rate of the asymptotic variance under various ergodicity assumptions on the underlying Markov chain. The proposed approach relies upon recent results on the stochastic errors of variance reduction algorithms and function approximation theory. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of secure event-triggered control is to guarantee the stability and security of a general class of industrial cyber-physical systems (CPSs) under limited resource budget and deception attacks. Note that the coupled data and the complicated structure of the CPS make it hard for the traditional control algorithms to fulfill the stability and security requirements. To this end, a neural network learning-based approximation algorithm is first proposed to separate the coupling influence, and then estimate the lumped uncertain nonlinearities. This is done by using the separated data as the input of the neural networks. Second, Nussbaum-type functions are presented to settle the unknown sign of the time-varying attack injection signal. Third, an event triggering mechanism is developed to reduce the communication load. Under the developed secure control laws, all the signals of the resulted closed-loop CPS are bounded. Finally, to validate the effectiveness of the proposed secure event-triggered control method, a benchmark control example for the one-link manipulator actuated by a DC motor is exploited. • Secure event-triggered control is proposed to ensure the security of industrial CPSs. • Neural network learning algorithm is used to estimate the uncertain nonlinearities. • Nussbaum-type functions are presented to handle the unknown sign of the time-varying attack injection signal. • Event triggering mechanism is developed to reduce the communication. [ABSTRACT FROM AUTHOR]

THE GENERAL SETTING for worst-case execution time (WCET) analysis is that a set of hard real-time tasks is to be executed on a given hardware platform. Hard real-time tasks have associated deadlines within which they must finish their execution. The deadlines may be given by periods. Timing verification must verify these timing constraints are satisfied. Traditionally, timing verification is split into a WCET analysis, which determines upper bounds on the execution times of all tasks, and a schedulability analysis, which takes these upper bounds and attempts to verify the given set of tasks when executed on the given platform will all respect their deadlines. The problem to determine upper (and potentially also) lower bounds on execution times underwent a transition in the 1990s: [ABSTRACT FROM AUTHOR]

The article offers derivation of Kalman filtering, a state estimation technique used in computer programming. Topics covered include computer system control, the use of Kalman filtering as a black box, and how Kalman filtering can improve approximation.

• We propose a novel framework of measures to evaluate soft clustering. • Our methods allow to generalize every hard clustering measure using optimal transport. • We study the metric and computational properties of the proposed methods. • We also propose computationally efficient approximation and sampling algorithms. • Our methods allow better quantification of uncertainty than previous proposals. In this article, we propose a general framework for the development of external evaluation measures for soft clustering. Our proposal is based on the interpretation of soft clustering as representing uncertain information about an underlying, unknown hard clustering. We present a general construction, based on optimal transport theory, by which any evaluation measure can be naturally extended to soft clustering. The proposed "transport-based measure" provides an objective, interval-valued comparison index that represents the range of compatibility between two soft clusterings. We study the metric and complexity properties of the proposed approach, as well as its relationship with other existing proposals. We also propose approximation and bounding algorithms that make the approach practical for large datasets. Finally, we illustrate the application of the proposed method through two computational experiments. [ABSTRACT FROM AUTHOR]

Reinforcement learning algorithms, such as hindsight experience replay (HER) and hindsight goal generation (HGG), have been able to solve challenging robotic manipulation tasks in multigoal settings with sparse rewards. HER achieves its training success through hindsight replays of past experience with heuristic goals but underperforms in challenging tasks in which goals are difficult to explore. HGG enhances HER by selecting intermediate goals that are easy to achieve in the short term and promising to lead to target goals in the long term. This guided exploration makes HGG applicable to tasks in which target goals are far away from the object’s initial position. However, the vanilla HGG is not applicable to manipulation tasks with obstacles because the Euclidean metric used for HGG is not an accurate distance metric in such an environment. Although, with the guidance of a handcrafted distance grid, grid-based HGG can solve manipulation tasks with obstacles, a more feasible method that can solve such tasks automatically is still in demand. In this article, we propose graph-based hindsight goal generation (G-HGG), an extension of HGG selecting hindsight goals based on shortest distances in an obstacle-avoiding graph, which is a discrete representation of the environment. We evaluated G-HGG on four challenging manipulation tasks with obstacles, where significant enhancements in both sample efficiency and overall success rate are shown over HGG and HER. Videos can be viewed at https://videoviewsite.wixsite.com/ghgg. [ABSTRACT FROM AUTHOR]

Model compression is crucial for the deployment of neural networks on devices with limited computational and memory resources. Many different methods show comparable accuracy of the compressed model and similar compression rates. However, the majority of the compression methods are based on heuristics and offer no worst case guarantees on the tradeoff between the compression rate and the approximation error for an arbitrarily new sample. We propose the first efficient structured pruning algorithm with a provable tradeoff between its compression rate and the approximation error for any future test sample. Our method is based on the coreset framework, and it approximates the output of a layer of neurons/filters by a coreset of neurons/filters in the previous layer and discards the rest. We apply this framework in a layer-by-layer fashion from the bottom to the top. Unlike previous works, our coreset is data-independent, meaning that it provably guarantees the accuracy of the function for any input $x\in \mathbb {R}^{d}$ , including an adversarial one. [ABSTRACT FROM AUTHOR]

Recently, stochastic hard thresholding (HT) optimization methods [e.g., stochastic variance reduced gradient hard thresholding (SVRGHT)] are becoming more attractive for solving large-scale sparsity/rank-constrained problems. However, they have much higher HT oracle complexities, especially for high-dimensional data or large-scale matrices. To address this issue and inspired by the well-known Gradient Support Pursuit (GraSP) method, this article proposes a new Relaxed Gradient Support Pursuit (RGraSP) framework. Unlike GraSP, RGraSP only requires to yield an approximation solution at each iteration. Based on the property of RGraSP, we also present an efficient stochastic variance reduction-gradient support pursuit algorithm and its fast version (called stochastic variance reduced gradient support pursuit (SVRGSP+). We prove that the gradient oracle complexity of both our algorithms is two times less than that of SVRGHT. In particular, their HT complexity is about $\kappa _{\widehat {s}}$ times less than that of SVRGHT, where $\kappa _{\widehat {s}}$ is the restricted condition number. Moreover, we prove that our algorithms enjoy fast linear convergence to an approximately global optimum, and also present an asynchronous parallel variant to deal with very high-dimensional and sparse data. Experimental results on both synthetic and real-world datasets show that our algorithms yield superior results than the state-of-the-art gradient HT methods. [ABSTRACT FROM AUTHOR]

Recurrent neural networks (RNNs) are widely used for online regression due to their ability to generalize nonlinear temporal dependencies. As an RNN model, long short-term memory networks (LSTMs) are commonly preferred in practice, as these networks are capable of learning long-term dependencies while avoiding the vanishing gradient problem. However, due to their large number of parameters, training LSTMs requires considerably longer training time compared to simple RNNs (SRNNs). In this article, we achieve the online regression performance of LSTMs with SRNNs efficiently. To this end, we introduce a first-order training algorithm with a linear time complexity in the number of parameters. We show that when SRNNs are trained with our algorithm, they provide very similar regression performance with the LSTMs in two to three times shorter training time. We provide strong theoretical analysis to support our experimental results by providing regret bounds on the convergence rate of our algorithm. Through an extensive set of experiments, we verify our theoretical work and demonstrate significant performance improvements of our algorithm with respect to LSTMs and the other state-of-the-art learning models. [ABSTRACT FROM AUTHOR]

This article concentrates on the design of a novel event-based adaptive neural network (NN) control algorithm for a class of multiple-input–multiple-output (MIMO) nonlinear discrete-time systems. A controller is designed through a novel recursive design procedure, under which the dependence on virtual controls is avoided and only system states are needed. The numbers of the event-triggered conditions and parameters updated online in each subsystem reduce to only one, which largely reduces the computation burden and simplifies the algorithm realization. In this case, radial basis function NNs (RBFNNs) are employed to approximate the control input. The semiglobal uniformly ultimate boundedness (SGUUB) of all the signals in the closed-loop system is guaranteed by the Lyapunov difference approach. The effectiveness of the proposed algorithm is validated by a simulation example. [ABSTRACT FROM AUTHOR]

Applications of Dempster-Shafer (D-S) belief functions to practical problems involve difficulties arising from their high computational complexity. One can use space-saving factored approximations such as graphical belief function models to solve them. Using an analogy with probability distributions, we represent these approximations in the form of compositional models. Since no theoretical apparatus similar to probabilistic information theory exists for D-S belief functions (e.g., dissimilarity measure analogous to the Kullback-Liebler divergence measure), the problems arise not only in connection with the design of algorithms seeking optimal approximations but also in connection with a criterion comparing two different approximations. In this respect, the application of the analogy with probability theory fails. Therefore, in this paper, we conduct some synthetic experiments and describe the results designed to reveal whether some belief function entropy definitions described in the literature can detect optimal approximations, i.e., that achieve their minimum for an optimal approximation. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive design space exploration for boosting energy efficiency of a fast Fourier transform (FFT) VLSI accelerator, exploiting several approximate multipliers (AxM) combined with approximate adder (AxA) circuits. The FFT hardware herein presented consists of a fixed-point sequential architecture using a radix-2 butterfly with decimation in time. We explore a set of AxMs – namely Dynamic Range Unbiased (DRUM), Rounding-based Approximate (RoBA), leading one Bit-based Approximate (LoBA), and Truncated approach – jointly with the LOA, ETA-I, CopyA, CopyB, Trunc0, Trunc1 approximate adders. The approximate arithmetic operators are used in the butterfly kernel with exploration of the approximation levels (for the ${L}$ and ${K}$ least-significant bits, respectively, for the AxM and AxA), aiming at discovering the most energy-efficient configuration under a design-time QoR constraint. The mean square error and peak signal-to-noise ratio metrics define which approximate levels combining ${L}$ and ${K}$ variations will enable the FFT to process signals to generate spectrograms without significant losses. Our results show that the LoBA multiplier with $L$ =8 together with the LOA, Trunc1 and Trunc0, at different approximation levels, provide most energy savings with controllable quality degradation, presenting a minimum decrease of 20.2% in power dissipation without degrading the spectrogram generation quality. [ABSTRACT FROM AUTHOR]

Sample complexity bounds are a common performance metric in the reinforcement learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilon-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent min–max lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Q-learning algorithm with an optimized step-size sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors. [ABSTRACT FROM AUTHOR]

Approximating model predictive control (MPC) policy using expert-based supervised learning techniques requires labeled training datasets sampled from the MPC policy. This is typically obtained by sampling the feasible state space and evaluating the control law by solving the numerical optimization problem offline for each sample. Although the resulting approximate policy can be cheaply evaluated online, generating large training samples to learn the MPC policy can be time-consuming and prohibitively expensive. This is one of the fundamental bottlenecks that limit the design and implementation of MPC policy approximation. This technical article aims to address this challenge, and proposes a novel sensitivity-based data augmentation scheme for direct policy approximation. The proposed approach is based on exploiting the parametric sensitivities to cheaply generate additional training samples in the neighborhood of the existing samples. [ABSTRACT FROM AUTHOR]

In reinforcement learning (RL), function approximation errors are known to easily lead to the $Q$ -value overestimations, thus greatly reducing policy performance. This article presents a distributional soft actor–critic (DSAC) algorithm, which is an off-policy RL method for continuous control setting, to improve the policy performance by mitigating $Q$ -value overestimations. We first discover in theory that learning a distribution function of state–action returns can effectively mitigate $Q$ -value overestimations because it is capable of adaptively adjusting the update step size of the $Q$ -value function. Then, a distributional soft policy iteration (DSPI) framework is developed by embedding the return distribution function into maximum entropy RL. Finally, we present a deep off-policy actor–critic variant of DSPI, called DSAC, which directly learns a continuous return distribution by keeping the variance of the state–action returns within a reasonable range to address exploding and vanishing gradient problems. We evaluate DSAC on the suite of MuJoCo continuous control tasks, achieving the state-of-the-art performance. [ABSTRACT FROM AUTHOR]

A Bayesian nonparametric approach for estimation of a Dirichlet process (DP) mixture of generalized inverted Dirichlet distributions [i.e., an infinite generalized inverted Dirichlet mixture model (InGIDMM)] has been proposed. The generalized inverted Dirichlet distribution has been proven to be efficient in modeling the vectors that contain only positive elements. Under the classical variational inference (VI) framework, the key challenge in the Bayesian estimation of InGIDMM is that the expectation of the joint distribution of data and variables cannot be explicitly calculated. Therefore, numerical methods are usually applied to simulate the optimal posterior distributions. With the recently proposed extended VI (EVI) framework, we introduce lower bound approximations to the original variational objective function in the VI framework such that an analytically tractable solution can be derived. Hence, the problem in numerical simulation has been overcome. By applying the DP mixture technique, an InGIDMM can automatically determine the number of mixture components from the observed data. Moreover, the DP mixture model with an infinite number of mixture components also avoids the problems of underfitting and overfitting. The performance of the proposed approach is demonstrated with both synthesized data and real-life data applications. [ABSTRACT FROM AUTHOR]

The neural-network (NN)-based control method is a new emerging promising technique for controller design in a power electronic circuit (PEC). However, the optimization of NN-based controllers (NNCs) has significant challenges in two aspects. The first challenge is that the search space of the NNC optimization problem is such complex that the global optimization ability of the existing algorithms still needs to be improved. The second challenge is that the training process of the NNC parameters is very computationally expensive and requires a long execution time. Thus, in this article, we develop a powerful evolutionary computation-based algorithm to find a high-quality solution and reduce computational time. First, the differential evolution (DE) algorithm is adopted because it is a powerful global optimizer in solving a complex optimization problem. This can help to overcome the premature convergence in local optima to train the NNC parameters well. Second, to reduce the computational time, the DE is extended to distribute DE (DDE) by dispatching all the individuals to different distributed computing resources for parallel computing. Moreover, a resource-aware strategy (RAS) is designed to further efficiently utilize the resources by adaptively dispatching individuals to resources according to the real-time performance of the resources, which can simultaneously concern the computing ability and load state of each resource. Experimental results show that, compared with some other typical evolutionary algorithms, the proposed algorithm can get significantly better solutions within a shorter computational time. [ABSTRACT FROM AUTHOR]

Singular value decomposition (SVD) is one of the most effective algorithms in recommender systems (RSs). Due to the iterative nature of SVD algorithms, one big challenge is initialization that has a major impact on the convergence and performance of RSs. Unfortunately, existing SVD algorithms in the literature typically initialize the user and item features in a random manner; thus, data information is not fully utilized. This work addresses the challenge of developing an efficient initialization method for SVD algorithms. We propose a general neural embedding initialization framework, where a low-complexity probabilistic autoencoder neural network initializes the features of user and item. This framework supports explicit and implicit feedback data sets. The design details of our proposed framework are elaborated and discussed. Experimental results show that RSs based on our proposed initialization framework outperform the state-of-the-art methods in rating prediction. Moreover, regarding item ranking, our proposed framework shows an improvement of at least 2.20% ~5.74% than existing SVD algorithms and other matrix factorization methods in the literature. [ABSTRACT FROM AUTHOR]

The Gaussian–Bernoulli restricted Boltzmann machine (GB-RBM) is a useful generative model that captures meaningful features from the given $n$ -dimensional continuous data. The difficulties associated with learning GB-RBM are reported extensively in earlier studies. They indicate that the training of the GB-RBM using the current standard algorithms, namely contrastive divergence (CD) and persistent contrastive divergence (PCD), needs a carefully chosen small learning rate to avoid divergence which, in turn, results in slow learning. In this work, we alleviate such difficulties by showing that the negative log-likelihood for a GB-RBM can be expressed as a difference of convex functions if we keep the variance of the conditional distribution of visible units (given hidden unit states) and the biases of the visible units, constant. Using this, we propose a stochastic difference of convex (DC) functions programming (S-DCP) algorithm for learning the GB-RBM. We present extensive empirical studies on several benchmark data sets to validate the performance of this S-DCP algorithm. It is seen that S-DCP is better than the CD and PCD algorithms in terms of speed of learning and the quality of the generative model learned. [ABSTRACT FROM AUTHOR]

CAE/CAD integration has always been the focus of competition among CAE software vendors. For decades, however, despite the large human resource and financial investment from some super international companies, CAE/CAD integration has not yet been fully realized. As we know, the boundary integral equation method has advantages of naturally seamless connection with CAD packages. Unfortunately, the conventional implementation of the boundary element method is unsuccessful in engineering application. In this paper, a new method to seamlessly integrate CAE/CAD based on boundary integral equations and nonconforming meshes is introduced. The nonconform mesh can effectively promote automatic CAE analysis development, while the dual interpolation boundary face method provides theoretical support for the above technologies. In addition, a spherical subdivision method is proposed to improve the accuracy and stability of singular and near-singular integrals in BIE. Adaptive cross approximation algorithm can reduce the storage of the dense coefficient matrix effectively and approximate the far-field matrix for large-scale computation. Based on the above theories, the "5aCAE simulation software" is developed. In this software, CAE analysis is performed directly on the CAD model using discontinuous mesh without geometric simplifying and repairing, which is impossible for existing commercial software. There is no need to select element types such as beams, shells elements, because any structure is treated as a complete entity. Automation is another feature of this software, which lowers the threshold for users. This paper presents a comprehensive overview of the dual interpolation boundary surface method and introduces the highlights of "5aCAE simulation software", which can provide technical support for boundary element CAE software development. [ABSTRACT FROM AUTHOR]

Explainable clustering provides human-understandable reasons for decisions in black-box learning models. In a previous work, a decision tree built on the set of dimensions was used to define ranges of values for k -means clusters. For explainable graph clustering, we use expander graphs instead of dense subgraphs since powering an expander graph is guaranteed to result in a clique after at most a logarithmic number of steps. Consider a set of multi-dimensional points labeled with k labels. We introduce the heat map sorting problem as reordering the rows and columns of an input matrix (each point is a column and each row is a dimension) such that the labels of the entries of the matrix form connected components (clusters). A cluster is preserved if it remains connected, i.e., if it is not split into several clusters and no two clusters are merged. In the massively parallel computation model (MPC), each machine has a sublinear memory and the total memory of the machines is linear. We prove the problem is NP-hard. We give a fixed-parameter algorithm in MPC and an approximation algorithm based on expander decomposition. We empirically compare our algorithm with explainable k-means on several graphs of email and computer networks. • A general method for explainable clustering of high-dimensional data. • A fixed-parameter algorithms for explainable graph clustering. • A Massively Parallel Computation (MPC) algorithm for explainable clustering. • An approximation algorithm for graph clustering on expander graphs. [ABSTRACT FROM AUTHOR]

Population diversity holds significant importance in determining the success of any evolutionary algorithm. It helps the algorithm in efficiently exploring the search space and identifying the promising region(s) containing global optimal solution(s). However, during the optimization procedure the population may lose its diversity, causing premature convergence in the algorithm and resulting in approximations to the sub-optimal solution(s). This paper proposes a Voronoi Tessellations based Simple Optimizer (VTSO) algorithm that utilizes a niche concept of Voronoi Tessellations (VTs) from the field of computational geometry to ensure a well-distributed population throughout the optimization procedure. It proposed an elite sampling mechanism that utilizes Lévy flights to aggressively explore the search space for locating potential optimal region(s), and the Differential Evolution (DE) algorithm to exploit these regions in order to approximate the global optimal solution(s). In addition, a population diameter-based switch is devised which activates itself when the algorithm detects premature convergence in the algorithm. Experiments are conducted on CEC14 and CEC17 benchmark test suit, and the proposed algorithm is compared with the existing state-of-the-art evolutionary algorithms. The results are competitive to recommend the VTSO algorithm as a new efficient and accurate optimizer for handling complex optimization problems. • This paper proposed a computational geometry approach for improving population diversity in evolutionary algorithms. • This includes a novel Voronoi Tessellations-based population generation method. • A levy flight and Differential Evolution assisted approach for updating population in the search space. • In addition, a population diameter-based switch is proposed to check the stagnation or premature convergence. [ABSTRACT FROM AUTHOR]

In this paper, for 3-DOF series elastic actuator (SEA)-based manipulators under partial state constraints, a prescribed performance model-free hybrid force/position controller (PPMHC) is designed. The PPMHC contains an outer force and an inner position control loop. The outer force control loop is designed by impedance control. Then, the inner position control loop is proposed according to the idea of model-free control. The inner position control loop consists of the prescribed performance control, integral-barrier Lyapunov function (IBLF), time-delay estimator, and neural approximation algorithm. It can be proven that the designed PPMHC can achieve stability of the closed-loop system under the partial state constraints by the Lyapunov function. Finally, the effectiveness of PPMHC is illustrated by the simulation results. [ABSTRACT FROM AUTHOR]

This article is concerned with the distributed Kalman filtering problem for discrete-time linear systems whose measurement information comes from a set of sensor nodes that can communicate with their direct neighbors. Two algorithms for distributed Kalman filtering are proposed, where the first algorithm is based on single-node measurement and the second algorithm is based on neighboring-node measurements. In order to improve the performance, a novel criterion is introduced to the algorithm design, where in the criterion, the proximity of matrix’s trace is used to determine the proximity of positive semidefinite matrix. We prove that all the proposed algorithms for distributed Kalman filtering are unbiased. Numerical examples are provided to demonstrate the correctness of the proposed theoretical method and the performance of the proposed new design technique. [ABSTRACT FROM AUTHOR]

This article is about the data-driven computation of optimal control for a class of control affine deterministic nonlinear systems. We assume that the control dynamical system model is not available, and the only information about the system dynamics is available in the form of time-series data. We provide a convex formulation for the optimal control problem (OCP) of the nonlinear system. The convex formulation relies on the duality result in the dynamical system’s stability theory involving density function and Perron–Frobenius operator. We formulate the OCP as an infinite-dimensional convex optimization program. The finite-dimensional approximation of the optimization problem relies on the recent advances made in the Koopman operator’s data-driven computation, which is dual to the Perron–Frobenius operator. Simulation results are presented to demonstrate the application of the developed framework. [ABSTRACT FROM AUTHOR]

Reinforcement learning aims to find policies that maximize an expected cumulative reward in Markov decision processes with unknown transition probabilities. Policy gradient (PG)-algorithms use stochastic gradients of the value function to update the policy. A major drawback of PG-algorithms is that they are limited to episodic tasks (multiple finite-horizon trajectories) unless stringent stationarity assumptions are imposed on the trajectories. Hence, they need restarts and cannot be fully implemented online, which is critical for systems need to adapt to new tasks and/or environments in deployment. Moreover, the standard stationary formulation ignores transient behaviors. This motivates our study of discounted MDPs of infinite horizon without restarts. However, it is unknown if in this case following stochastic PG-type estimates would improve the policy. The main result of this work is to establish that when policies belong to a reproducing kernel Hilbert space (RKHS), and the kernel is selected properly, then these PG-estimates are ascent directions for the value function conditioned to any arbitrary initial point. This allows us to prove convergence of our online algorithm to the local optima. A numerical example shows that an agent running our online algorithm learns to navigate and succeeds in a surveillance task that requires looping between two goal locations. This example corroborates our theoretical findings about the ascent directions of subsequent stochastic gradients. It also shows how our online algorithm guides the agent through a continuing cyclic trajectory that does not comply with the standard stationarity assumptions in the literature for non-episodic training. [ABSTRACT FROM AUTHOR]

For portable devices with limited resources, it is often difficult to deploy deep networks due to the prohibitive computational overhead. Numerous approaches have been proposed to quantize weights and/or activations to speed up the inference. Loss-aware quantization has been proposed to directly formulate the impact of weight quantization on the model’s final loss. However, we discover that, under certain circumstances, such a method may not converge and end up oscillating. To tackle this issue, we introduce a novel loss-aware quantization algorithm to efficiently compress deep networks with low bit-width model weights. We provide a more accurate estimation of gradients by leveraging the Taylor expansion to compensate for the quantization error, which leads to better convergence behavior. Our theoretical analysis indicates that the gradient mismatch issue can be fixed by the newly introduced quantization error compensation term. Experimental results for both linear models and convolutional networks verify the effectiveness of our proposed method. [ABSTRACT FROM AUTHOR]

With the advent of data science, the analysis of network or graph data has become a very timely research problem. A variety of recent works have been proposed to generalize neural networks to graphs, either from a spectral graph theory or a spatial perspective. The majority of these works, however, focus on adapting the convolution operator to graph representation. At the same time, the pooling operator also plays an important role in distilling multiscale and hierarchical representations, but it has been mostly overlooked so far. In this article, we propose a parameter-free pooling operator, called iPool, that permits to retain the most informative features in arbitrary graphs. With the argument that informative nodes dominantly characterize graph signals, we propose a criterion to evaluate the amount of information of each node given its neighbors and theoretically demonstrate its relationship to neighborhood conditional entropy. This new criterion determines how nodes are selected and coarsened graphs are constructed in the pooling layer. The resulting hierarchical structure yields an effective isomorphism-invariant representation of networked data on arbitrary topologies. The proposed strategy achieves superior or competitive performance in graph classification on a collection of public graph benchmark data sets and superpixel-induced image graph data sets. [ABSTRACT FROM AUTHOR]

Stochastic optimization methods have become a class of popular optimization tools in machine learning. Especially, stochastic gradient descent (SGD) has been widely used for machine learning problems, such as training neural networks, due to low per-iteration computational complexity. In fact, the Newton or quasi-newton (QN) methods leveraging the second-order information are able to achieve a better solution than the first-order methods. Thus, stochastic QN (SQN) methods have been developed to achieve a better solution efficiently than the stochastic first-order methods by utilizing approximate second-order information. However, the existing SQN methods still do not reach the best known stochastic first-order oracle (SFO) complexity. To fill this gap, we propose a novel faster stochastic QN method (SpiderSQN) based on the variance reduced technique of SIPDER. We prove that our SpiderSQN method reaches the best known SFO complexity of $\mathcal {O}(n+n^{1/2}\epsilon ^{-2})$ in the finite-sum setting to obtain an $\epsilon $ -first-order stationary point. To further improve its practical performance, we incorporate SpiderSQN with different momentum schemes. Moreover, the proposed algorithms are generalized to the online setting, and the corresponding SFO complexity of $\mathcal {O}(\epsilon ^{-3})$ is developed, which also matches the existing best result. Extensive experiments on benchmark data sets demonstrate that our new algorithms outperform state-of-the-art approaches for nonconvex optimization. [ABSTRACT FROM AUTHOR]

• An end-to-end framework to solve JSSPs by using graph neural networks and dueling double deep Q network. • This single policy model is suitable for solving instances that have similar size and is trained only by observing reward signals and following feasible rules. • The trained model behaves like a constructive heuristic algorithm that incrementally constructs a solution, and each action is determined by the output of a Graph Neural Network (GNN) which captures the current state of the partial solution. A key problem in traffic management is to schedule the movements of vehicles to reduce unnecessary costs; this issue has arisen in applications such as train schedule management, air-traffic control, and urban traffic management. This problem can be modeled as a job shop scheduling problem (JSSP), which is an important combinatorial optimization problem that is widely applied in real-world scenarios. However, designing good approximation algorithms for JSSPs often requires significant specialized knowledge and trial-and-error. In this paper, we present an end-to-end framework for solving JSSPs by using graph neural networks (GNNs) and deep Q-Learning. This single-policy model is suitable for solving instances that have similar sizes and is trained only by observing reward signals and following feasible rules. The trained model behaves like a constructive heuristic algorithm that incrementally constructs a solution, and each action is determined by the output of a GNN, which captures the current state of the partial solution. We test the proposed approach on JSSP instances with multiple sizes and demonstrate its competitive performance in all cases (after training). Our proposed framework also has the potential to be applied to other JSS subproblems. [ABSTRACT FROM AUTHOR]

Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov decision process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first-order method and, therefore, it may take a large number of iterations to converge to the optimal solution. Successive relaxation is a popular technique that can be applied to solve a fixed point equation. It has been shown in the literature that under a special structure of the MDP, successive overrelaxation technique computes the optimal value function faster than standard value iteration. In this article, we propose a second-order value iteration procedure that is obtained by applying the Newton–Raphson method to the successive relaxation value iteration scheme. We prove the global convergence of our algorithm to the optimal solution asymptotically and show the second-order convergence. Through experiments, we demonstrate the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

In this work, time-driven learning refers to the machine learning method that updates parameters in a prediction model continuously as new data arrives. Among existing approximate dynamic programming (ADP) and reinforcement learning (RL) algorithms, the direct heuristic dynamic programming (dHDP) has been shown an effective tool as demonstrated in solving several complex learning control problems. It continuously updates the control policy and the critic as system states continuously evolve. It is therefore desirable to prevent the time-driven dHDP from updating due to insignificant system event such as noise. Toward this goal, we propose a new event-driven dHDP. By constructing a Lyapunov function candidate, we prove the uniformly ultimately boundedness (UUB) of the system states and the weights in the critic and the control policy networks. Consequently, we show the approximate control and cost-to-go function approaching Bellman optimality within a finite bound. We also illustrate how the event-driven dHDP algorithm works in comparison to the original time-driven dHDP. [ABSTRACT FROM AUTHOR]

The maximum clique problem is an NP hard combinatorial optimization problem, which is widely used in industrial and management processes. In order to approach the solution of the maximum clique problem, a deterministic annealing algorithm is proposed. When the barrier parameter is reduced from a large positive number to zero, the algorithm can track the minimum path of the obstacle problem to obtain a high-quality solution, which is a continuous method. The global convergence iteration of the Lagrange multiplier can be performed to obtain the minimum point of the obstacle problem in the feasible descent direction for any given positive value of the barrier parameter and has a desired property that it automatically satisfies the upper and lower bounds of variables if the steplength is a number that is between 0 and 1. Numerical results are provided to illustrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A structural hole spanner in a social network is a user who bridges multiple communities, and he can benefit from acting the bridging role, such as arbitrating information across different communities or getting earlier access to valuable and diverse information. Existing studies of finding hole spanners either identified redundant hole spanners (i.e., communities bridged by different hole spanners are redundant) or found nonredundant hole spanners only by network structure. Unlike the existing studies, we not only study a problem of finding top- k hole spanners that connect nonredundant communities in the social network, but also consider the tie strengths between different pairs of users and the different information sharing rates of different users, so that after removing the found users, the number of blocked information diffusion is maximized. In addition, we devise a novel (1 - 1 e) -approximation algorithm for the problem, where e is the base of the natural logarithm. We further propose a fast randomized algorithm with a smaller time complexity. Our experiment results demonstrate that, after removing the nodes found by the proposed two algorithms, the numbers of blocked information diffusion can be up to 80% larger than those by existing algorithms. [ABSTRACT FROM AUTHOR]

In the open-world environment, the incremental updating approaches to attribute reduction based on rough sets are efficient and effective to evaluate and search an optimal subset of attributes from two-dimensionally time-evolving data, which can be interpreted as the complex changes of dynamic data, i.e., four types of combinations induced by the insertion/deletion of objects and the addition/remove of attributes. To avoid the time-consuming and repetitive computation from scratch in such dynamic data, this paper mainly focuses on constructing a unified incremental framework to attribute reduction by the matrix-based accelerated updating strategies. We systematically discuss and present a series of incremental updating mechanisms and algorithms of approximation quality in the neighborhood-based probabilistic rough sets. Besides, a unified framework of dynamic attribute reduction in four situations of changes is proposed to develop the performance of updating reduct. Finally, we report the comparative experiments between the non-incremental and incremental algorithms of reduct to demonstrate the feasibility and efficiency of proposed approaches. [ABSTRACT FROM AUTHOR]

Approximate computing (AC) has been considered as a promising paradigm to improve the energy-efficiency of computing hardware for error-tolerant applications, with negligible quality degradation to the output. Dividers frequently limit the performance of a computing system; however, they have not received as much attention as multipliers and adders in AC. In this paper, an energy-efficient and high-performance approximate divider is proposed based on logarithmic conversion and piecewise constant approximation. In this design, the range for the conversion between binary and logarithmic numbers is first expanded from $\mathbf {[{0,1}]}$ to $\mathbf {[-0.5,1]}$. A heuristic search algorithm is then devised to find the most accurate constant set to approximate the reciprocal of the divisor, by minimizing a statistical error. The hardware implementation is presented for both floating-point (FP) and integer dividers. With a high configurability, the proposed divider results in a mean relative error distance (MRED) from 2.78% to 0.046%, indicating a high accuracy among state-of-the-art approximate dividers. Compared to the half-precision FP divider, the proposed divider with a MRED of 0.74% can achieve nearly $\mathbf {90\times }$ improvement in PDP. Moreover, compared to state-of-the-art approximate dividers, the proposed design is in the Pareto Frontier in terms of power delay product (PDP) and MRED. The three image processing application results demonstrate that the proposed divider can result in the highest peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) even with truncation. [ABSTRACT FROM AUTHOR]

Timed extended reachability graphs (TERG) of time Petri nets abstract the temporal specifications and represent the feasible trajectories under the earliest firing policy. One drawback of such graphs is the rapid increase in the number of states with respect to time specifications. For this reason, approximations of TERG that remove some states have been studied in recent works. In this article, we improve the approximation of a TERG. New objects—called vertices—are defined to manipulate the time constraints and algorithms are proposed to cluster nearby vertices. A metric based on the time constraints is defined for this purpose and a cluster TERG of reduced size is obtained. [ABSTRACT FROM AUTHOR]

This article addresses the problem of learning the optimal control policy for a nonlinear stochastic dynamical. This problem is subject to the “curse of dimensionality” associated with the dynamic programming method. This article proposes a novel decoupled data-based control (D2C) algorithm that addresses this problem using a decoupled, “open-loop–closed-loop,” approach. First, an open-loop deterministic trajectory optimization problem is solved using a black-box simulation model of the dynamical system. Then, closed-loop control is developed around this open-loop trajectory by linearization of the dynamics about this nominal trajectory. By virtue of linearization, a linear quadratic regulator based algorithm can be used for this closed-loop control. We show that the performance of D2C algorithm is approximately optimal. Moreover, simulation performance suggests a significant reduction in training time compared to other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Sparse Bayesian learning (SBL) is a popular machine learning approach with a superior generalization capability due to the sparsity of its adopted model. However, it entails a matrix inversion at each iteration, hindering its practical applications with large-scale data sets. To overcome this bottleneck, we propose an efficient SBL algorithm with $\mathcal {O}(n^{2})$ computational complexity per iteration based on a Gaussian-scale mixture prior model. By specifying two different hyperpriors, the proposed efficient SBL algorithm can meet two different requirements, such as high efficiency and high sparsity. A surrogate function is introduced herein to approximate the posterior density of model parameters and thereby to avoid matrix inversions. Using a data-dependent term, a joint cost function with separate penalty terms is reformulated in a joint space of model parameters and hyperparameters. The resulting nonconvex optimization problem is solved using a block coordinate descent method in a majorization–minimization framework. Finally, the results of extensive experiments for sparse signal recovery and sparse image reconstruction on benchmark problems are elaborated to substantiate the effectiveness and superiority of the proposed approach in terms of computational time and estimation error. [ABSTRACT FROM AUTHOR]

Truncated Newton (TN) methods have been a useful technique for large-scale optimization. Instead of obtaining the full Newton direction, a truncated method approximately solves the Newton equation with an inner conjugate gradient (CG) procedure (TNCG for the whole method). These methods have been employed to efficiently solve linear classification problems. However, even in this deeply studied field, various theoretical and numerical aspects were not completely explored. The first contribution of this work is to comprehensively study the global and local convergence when TNCG is applied to linear classification. Because of the lack of twice differentiability under some losses, many past works cannot be applied here. We prove various missing pieces of theory from scratch and clarify many proper references. The second contribution is to study the termination of the CG method. For the first time when TNCG is applied to linear classification, we show that the inner stopping condition strongly affects the convergence speed. We propose using a quadratic stopping criterion to achieve both robustness and efficiency. The third contribution is that of combining the study on inner stopping criteria with that of preconditioning. We discuss how convergence theory is affected by preconditioning and finally propose an effective preconditioned TNCG. [ABSTRACT FROM AUTHOR]

Emerging advanced System-on-Chip (SoC) designs contain more and more complicated functions to be accelerated. This presents a challenge to conventional design approaches which use different hardware architectures or separate hardware accelerators to implement the various functions. To tackle this challenge, for the first time, we propose a generalized hardware accelerator called “Huicore” to speed up diverse functions on the same substrate. Through the analysis and transformation of mathematical characteristics, we reveal the commonality of many complicated functions using the CORDIC algorithm. Then we explore a reconfigurable architecture to implement them. The proposed reconfigurable accelerator can not only accelerate the implementation of many complicated functions, but also has small area, low power consumption and high precision. It is very suitable for integration in a SoC system to accelerate the implementation of various applications. [ABSTRACT FROM AUTHOR]

In this article, we propose a symplectic algorithm for the stable manifolds of the Hamilton–Jacobi equations combined with an iterative procedure in [N. Sakamoto and A. J. van der Schaft, “Analytical approximation methods for the stabilizing solution of the Hamilton–Jacobi equation,” IEEE Trans. Autom. Control, 2008]. Our algorithm includes two key aspects. The first one is to prove a precise estimate for radius of convergence and the errors of local approximate stable manifolds. The second one is to extend the local approximate stable manifolds to larger ones by symplectic algorithms, which have better long-time behaviors than general-purpose schemes. Our approach avoids the case of divergence of the iterative sequence of approximate stable manifolds and reduces the computation cost. We illustrate the effectiveness of the algorithm by an optimal control problem with exponential nonlinearity. [ABSTRACT FROM AUTHOR]

For nonzero-sum (NZS) games of nonlinear systems, reinforcement learning (RL) or adaptive dynamic programming (ADP) has shown its capability of approximating the desired index performance and the optimal input policy iteratively. In this article, an event-triggered ADP is proposed for NZS games of continuous-time nonlinear systems with completely unknown system dynamics. To achieve the Nash equilibrium solution approximately, the critic neural networks and actor neural networks are utilized to estimate the value functions and the control policies, respectively. Compared with the traditional time-triggered mechanism, the proposed algorithm updates the neural network weights as well as the inputs of players only when a state-based event-triggered condition is violated. It is shown that the system stability and the weights’ convergence are still guaranteed under mild assumptions, while occupation of communication and computation resources is considerably reduced. Meanwhile, the infamous Zeno behavior is excluded by proving the existence of a minimum inter-event time (MIET) to ensure the feasibility of the closed-loop event-triggered continuous-time system. Finally, a numerical example is simulated to illustrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Currently, numerical optimization methods are used to solve distributed optimal power allocation (OPA) problems for islanded microgrid (MG) systems. Most of them are developed based on rigorous mathematical derivation. However, the complexity of such optimization algorithms inevitably creates a gap between theoretical analysis and real-time implementation. In order to bridge such a gap, in this article we provide a new distributed learning-based framework to solve the real-time OPA problem. Specifically, inspired by the human-thinking scheme, distributed deep neural networks (DNNs) together with a dynamic average consensus algorithm are first employed to obtain an approximate OPA solution in a distributed manner. Then a distributed balance generation and demand algorithm is designed to fine-tune it to obtain the final optimal feasible solution. In addition, it is theoretically proved that the proposed DNN can well approximate one existing OPA algorithm (Guo et al. 2018), where quantitative numbers of at most how many hidden layers and neurons are provided. Several experimental case studies show that our proposed distributed learning framework can achieve similar optimal results to those obtained by using typical existing distributed numerical optimization methods while it is superior in terms of simplicity and real-time capability. [ABSTRACT FROM AUTHOR]

Recently, massive multiple-input multiple-output (MIMO) detection schemes based on message passing detection (MPD) have attracted extensive attention due to their good performance-complexity tradeoff. In this paper, to facilitate a high-throughput detector design, we introduce a layered updating schedule and propose an improved layered MPD (ILMPD) algorithm. In the new algorithm, several algorithmic transformations or approximations are derived for lower complexity. For instance, by exploiting the property of quadratic functions, the numbers of multiplications and additions in the constellation matching are both reduced by half; Through reasonable approximations, the multiplication, addition, and sorting operations in the initialization are all removed. Moreover, a lightweight early termination strategy is explored, reducing the number of detection iterations by nearly 20%. Based on the proposed ILMPD algorithm, an area-efficient architecture is devised, where several optimization methods are proposed for fewer resources and higher clock frequency. Compared with the state-of-the-art design, the presented ILMPD detector can deliver a nearly $3\times $ higher area efficiency. A reconfigurable version of the proposed detector has also been developed, which can well support modulations QPSK to 256-QAM and still exhibits a superior area efficiency. [ABSTRACT FROM AUTHOR]

This article develops a novel passive stochastic gradient algorithm. In passive stochastic approximation, the stochastic gradient algorithm does not have control over the location where noisy gradients of the cost function are evaluated. Classical passive stochastic gradient algorithms use a kernel that approximates a Dirac delta to weigh the gradients based on how far they are evaluated from the desired point. In this article, we construct a multikernel passive stochastic gradient algorithm. The algorithm performs substantially better in high dimensional problems and incorporates variance reduction. We analyze the weak convergence of the multikernel algorithm and its rate of convergence. In numerical examples, we study the multikernel version of the passive least mean squares algorithm for transfer learning to compare the performance with the classical passive version. [ABSTRACT FROM AUTHOR]

Through the combination of contraction mapping and pseudospectral method, we propose a successive approximation technique to approximate the solution of a class of regulator equations with periodic exosystems and hyperbolic zero dynamics. In this scheme, the initial points of flows on the zero-error constrained manifolds are approximated successively as the fixed point of a contractive integral mapping. Accordingly, flows are obtained by utilizing the scaled Fourier–Gauss–Radau collocation method. Appropriate error analysis, in association with both regulation error and the error resulting from the approximate solution of the center manifold equation, is provided. Our analysis shows that the regulation error becomes negligible as we start the approximation process at an adequately large order and maintain it for a proper number of iterations. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel feature selection approach, named unsupervised feature selection with constrained $\ell _{2,0}$ -norm (row-sparsity constrained) and optimized graph (RSOGFS), which unifies feature selection and similarity matrix construction into a general framework instead of independently performing the two-stage process; thus, the similarity matrix preserving the local manifold structure of data can be determined adaptively. Unlike those sparse learning-based feature selection methods that can only solve the relaxation or approximation problems by introducing sparsity regularization term into the objective function, the proposed method directly tackles the original $\ell _{2,0}$ -norm constrained problem to achieve group feature selection. Two optimization strategies are provided to solve the original sparse constrained problem. The convergence and approximation guarantees for the new algorithms are rigorously proved, and the computational complexity and parameter determination are theoretically analyzed. Experimental results on real-world data sets show that the proposed method for solving a nonconvex problem is superior to the state of the arts for solving the relaxed or approximate convex problems. [ABSTRACT FROM AUTHOR]

Dimension reduction (DR) computes faithful low-dimensional (LD) representations of high-dimensional (HD) data. Outstanding performances are achieved by recent neighbor embedding (NE) algorithms such as $t$ -SNE, which mitigate the curse of dimensionality. The single-scale or multiscale nature of NE schemes drives the HD neighborhood preservation in the LD space (LDS). While single-scale methods focus on single-sized neighborhoods through the concept of perplexity, multiscale ones preserve neighborhoods in a broader range of sizes and account for the global HD organization to define the LDS. For both single-scale and multiscale methods, however, their time complexity in the number of samples is unaffordable for big data sets. Single-scale methods can be accelerated by relying on the inherent sparsity of the HD similarities they involve. On the other hand, the dense structure of the multiscale HD similarities prevents developing fast multiscale schemes in a similar way. This article addresses this difficulty by designing randomized accelerations of the multiscale methods. To account for all levels of interactions, the HD data are first subsampled at different scales, enabling to identify small and relevant neighbor sets for each data point thanks to vantage-point trees. Afterward, these sets are employed with a Barnes–Hut algorithm to cheaply evaluate the considered cost function and its gradient, enabling large-scale use of multiscale NE schemes. Extensive experiments demonstrate that the proposed accelerations are, statistically significantly, both faster than the original multiscale methods by orders of magnitude, and better preserving the HD neighborhoods than state-of-the-art single-scale schemes, leading to high-quality LD embeddings. Public codes are freely available at https://github.com/cdebodt. [ABSTRACT FROM AUTHOR]

In this article, we study a multiplayer Stackelberg–Nash game (SNG) pertaining to a nonlinear dynamical system, including one leader and multiple followers. At the higher level, the leader makes its decision preferentially with consideration of the reaction functions of all followers, while, at the lower level, each of the followers reacts optimally to the leader’s strategy simultaneously by playing a Nash game. First, the optimal strategies for the leader and the followers are derived from down to the top, and these strategies are further shown to constitute the Stackelberg–Nash equilibrium points. Subsequently, to overcome the difficulty in calculating the equilibrium points analytically, we develop a novel two-level value iteration-based integral reinforcement learning (VI-IRL) algorithm that relies only upon partial information of system dynamics. We establish that the proposed method converges asymptotically to the equilibrium strategies under the weak coupling conditions. Moreover, we introduce effective termination criteria to guarantee the admissibility of the policy (strategy) profile obtained from a finite number of iterations of the proposed algorithm. In the implementation of our scheme, we employ neural networks (NNs) to approximate the value functions and invoke the least-squares methods to update the involved weights. Finally, the effectiveness of the developed algorithm is verified by two simulation examples. [ABSTRACT FROM AUTHOR]