Search

This paper proposes a new online learning algorithm which is based on adaptive control (AC) theory, thus, we call this proposed algorithm as AC algorithm. Comparing to the gradient descent (GD) and exponential gradient (EG) algorithm which have been applied to online prediction problems, we find a new form of AC theory for online prediction problems and investigate two key questions: how to get a new update law which has a tighter upper bound on the error than the square loss? How to compare the upper bound for accumulated losses for the three algorithms? We obtain a new update law which fully utilizes model reference AC theory. Moreover, we present upper bound on the worst-case expected loss for AC algorithm and compare it with previously known bounds for the GD and EG algorithm. The loss bound we get in this paper is a time-varying function, which provides increasingly accurate estimates for upper bound. The AC algorithm has a much smaller loss only if the number of the samples meets certain conditions which can be seen in this paper. We also performed experiments which show that our update law is reasonably feasible and our upper bound is quite tight on both simple artificial and real data sets. The main contributions of this paper are twofold. First of all, we develop a new online algorithm called AC algorithm, and second, we obtain improved bounds, see Theorems 2–4 in this paper. [ABSTRACT FROM AUTHOR]

Motivated by application of complex-valued signal processing techniques in statistical pattern recognition, classification, and Gaussian mixture (GM) modeling, this paper derives analytical expressions for computing the Bhattacharyya coefficient/distance (BC/BD) between two improper complex-valued Gaussian distributions. The BC/BD is one of the most widely used statistical measures for evaluating class separability in classification problems, feature extraction in pattern recognition, and for GM reduction (GMR) purposes. The BC provides an upper bound on the Bayes error, which is commonly known as the best criterion to evaluate feature sets. Although the computation of the BC/BD between real-valued signals is a well-known result, it has not yet been extended to the case of improper complex-valued Gaussian densities. This paper addresses this gap. We analyze the role of the pseudocovariance matrix, which characterizes the noncircularity of the signal, and show that it carries critical second-order statistical information for computing the BC/BD. We derive upper and lower bounds on the BD in terms of the eigenvalues of the covariance and pseudocovariance matrices of the underlying densities. The theoretical bounds are then used to introduce the concept of $\beta $ -dominance in the context of statistical distance measures. The BC is pseudometric, since it fails to satisfy the triangle inequality. Using the Matusita distance (a full-metric variant of the BC), we propose an intuitively pleasing indirect distance measure for comparing two general GMs. Finally, we investigate the application of the proposed BC/BD measures for GMR purposes and develop two BC-based GMR algorithms. [ABSTRACT FROM AUTHOR]

Classification algorithms have been traditionally designed to simultaneously reduce errors caused by bias as well by variance. However, there occur many situations where low generalization error becomes extremely crucial to getting tangible classification solutions, and even slight overfitting causes serious consequences in the test results. In such situations, classifiers with low Vapnik–Chervonenkis (VC) dimension can bring out positive differences due to two main advantages: 1) the classifier manages to keep the test error close to training error and 2) the classifier learns effectively with small number of samples. This paper shows that a class of classifiers named majority vote point (MVP) classifiers, on account of very low VC dimension, can exhibit a generalization error that is even lower than that of linear classifiers. This paper proceeds by theoretically formulating an upper bound on the VC dimension of the MVP classifier. Later, through empirical analysis, the trend of exact values of VC dimension is estimated. Finally, case studies on machine fault diagnosis problems and prostate tumor detection problem revalidate the fact that an MVP classifier can achieve a lower generalization error than most other classifiers. [ABSTRACT FROM PUBLISHER]

In this paper, we derive a deep connection between the Vapnik-Chervonenkis (VC) entropy and the Rademacher complexity. For this purpose, we first refine some previously known relationships between the two notions of complexity and then derive new results, which allow computing an admissible range for the Rademacher complexity, given a value of the VC-entropy, and vice versa. The approach adopted in this paper is new and relies on the careful analysis of the combinatorial nature of the problem. The obtained results improve the state of the art on this research topic. [ABSTRACT FROM AUTHOR]

Linear discriminant analysis (LDA) is a well-known technique for linear classification, feature extraction, and dimension reduction. To improve the accuracy of LDA under the high dimension low sample size (HDLSS) settings, shrunken estimators, such as Graphical Lasso, can be used to strike a balance between biases and variances. Although the estimator with induced sparsity obtains a faster convergence rate, however, the introduced bias may also degrade the performance. In this paper, we theoretically analyze how the sparsity and the convergence rate of the precision matrix (also known as inverse covariance matrix) estimator would affect the classification accuracy by proposing an analytic model on the upper bound of an LDA misclassification rate. Guided by the model, we propose a novel classifier, $\mathcal {DBSDA}$ , which improves classification accuracy through debiasing. Theoretical analysis shows that $\mathcal {DBSDA}$ possesses a reduced upper bound of misclassification rate and better asymptotic properties than sparse LDA (SDA). We conduct experiments on both synthetic datasets and real application datasets to confirm the correctness of our theoretical analysis and demonstrate the superiority of $\mathcal {DBSDA}$ over LDA, SDA, and other downstream competitors under HDLSS settings. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of synchronization for inertial neural networks (INNs) with heterogeneous time-varying delays (HTVDs) through quantized sampled-data control. The control scheme, which takes the communication limitations of quantization and variable sampling into account, is first employed for tackling the synchronization of INNs. A novel Lyapunov–Krasovskii functional (LKF) is constructed for synchronizing an error system. Compared with existing LKFs by the largest upper bound of all HTVDs, the proposed LKF is superior, since it can make full use of the information on the lower and upper bounds of each HTVD. Based on the LKF and a new integral inequality technique, less conservative synchronization criteria are derived. The desired quantized sampled-data controller is designed by solving a set of linear matrix inequalities. Finally, a numerical example is given to illustrate the effectiveness and conservatism reduction of the proposed results. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of finite-time consensus of multiagent systems on a fixed directed interaction graph with a new protocol. Existing finite-time consensus protocols can be divided into two types: 1) continuous and 2) discontinuous, which were studied separately in the past. In this paper, we deal with both continuous and discontinuous protocols simultaneously, and design a centralized switching consensus protocol such that the finite-time consensus can be realized in a fast speed. The switching protocol depends on the range of the initial disagreement of the agents, for which we derive an exact bound to indicate at what time a continuous or a discontinuous protocol should be selected to use. Finally, we provide two numerical examples to illustrate the superiority of the proposed protocol and design method. [ABSTRACT FROM AUTHOR]

This paper presents a pair of hypothesis spaces (HSs) of vector-valued functions intended to be used in the context of multitask classification. While both are parameterized on the elements of reproducing kernel Hilbert spaces and impose a feature mapping that is common to all tasks, one of them assumes this mapping as fixed, while the more general one learns the mapping via multiple kernel learning. For these new HSs, empirical Rademacher complexity-based generalization bounds are derived, and are shown to be tighter than the bound of a particular HS, which has appeared recently in the literature, leading to improved performance. As a matter of fact, the latter HS is shown to be a special case of ours. Based on an equivalence to Group-Lasso type HSs, the proposed HSs are utilized toward corresponding support vector machine-based formulations. Finally, experimental results on multitask learning problems underline the quality of the derived bounds and validate this paper’s analysis. [ABSTRACT FROM PUBLISHER]

Although hash function learning algorithms have achieved great success in recent years, most existing hash models are off-line, which are not suitable for processing sequential or online data. To address this problem, this paper proposes an online hash model to accommodate data coming in stream for online learning. Specifically, a new loss function is proposed to measure the similarity loss between a pair of data samples in hamming space. Then, a structured hash model is derived and optimized in a passive-aggressive way. Theoretical analysis on the upper bound of the cumulative loss for the proposed online hash model is provided. Furthermore, we extend our online hashing (OH) from a single model to a multimodel OH that trains multiple models so as to retain diverse OH models in order to avoid biased update. The competitive efficiency and effectiveness of the proposed online hash models are verified through extensive experiments on several large-scale data sets as compared with related hashing methods. [ABSTRACT FROM AUTHOR]

This paper proposes two homotopy methods for solving the compressed sensing (CS) problem, which combine the homotopy technique with the iterative hard thresholding (IHT) method. The homotopy methods overcome the difficulty of the IHT method on the choice of the regularization parameter value, by tracing solutions of the regularized problem along a homotopy path. We prove that any accumulation point of the sequences generated by the proposed homotopy methods is a feasible solution of the problem. We also show an upper bound on the sparsity level for each solution of the proposed methods. Moreover, to improve the solution quality, we modify the two methods into the corresponding heuristic algorithms. Computational experiments demonstrate effectiveness of the two heuristic algorithms, in accurately and efficiently generating sparse solutions of the CS problem, whether the observation is noisy or not. [ABSTRACT FROM AUTHOR]

This paper proposes a novel and efficient pairing nu-support vector regression (pair- v -SVR) algorithm that combines successfully the superior advantages of twin support vector regression (TSVR) and classical $\varepsilon $ -SVR algorithms. In spirit of TSVR, the proposed pair- v -SVR solves two quadratic programming problems (QPPs) of smaller size rather than a single larger QPP, and thus has faster learning speed than classical $\varepsilon $ -SVR. The significant advantage of our pair- v -SVR over TSVR is the improvement in the prediction speed and generalization ability by introducing the concepts of the insensitive zone and the regularization term that embodies the essence of statistical learning theory. Moreover, pair- v -SVR has additional advantage of using parameter v for controlling the bounds on fractions of SVs and errors. Furthermore, the upper bound and lower bound functions of the regression model estimated by pair- v -SVR capture well the characteristics of data distributions, thus facilitating automatic estimation of the conditional mean and predictive variance simultaneously. This may be useful in many cases, especially when the noise is heteroscedastic and depends strongly on the input values. The experimental results validate the superiority of our pair- v -SVR in both training/prediction speed and generalization ability. [ABSTRACT FROM PUBLISHER]

A rough neuron is defined as a pair of conventional neurons that are called the upper and lower bound neurons. In this paper, the sinusoidal rough-neural networks (SR-NNs) are used to identify the discrete dynamic nonlinear systems (DDNSs) with or without noise in series–parallel configuration. In the identification of periodic nonlinear systems, sinusoidal activation functions provide more efficient neural networks than the sigmoidal activation functions. Based on the Lyapunov stability theory, an online learning algorithm is developed to train the SR-NNs. The asymptotically convergence of the identification error to zero and the boundedness of parameters as well as predictions are proved. SR-NNs are used to identify some DDNSs and the cement rotary kiln (CRK). CRK is a complex nonlinear system in the cement factory, which produces the cement clinker. The experiments show that the SR-NNs in the identification of nonlinear systems have better performances than multilayer perceptrons (MLPs), sinusoidal neural networks, and rough MLPs, particularly in the presence of noise. [ABSTRACT FROM AUTHOR]

Goal representation heuristic dynamic programming (GrHDP) control design has been developed in recent years. The control performance of this design has been demonstrated in several case studies, and also showed applicable to industrial-scale complex control problems. In this paper, we develop the theoretical analysis for the GrHDP design under certain conditions. It has been shown that the internal reinforcement signal is a bounded signal and the performance index can converge to its optimal value monotonically. The existence of the admissible control is also proved. Although the GrHDP control method has been investigated in many areas before, to the best of our knowledge, this is the first study of presenting the theoretical foundation of the internal reinforcement signal and how such an internal reinforcement signal can provide effective information to improve the control performance. Numerous simulation studies are used to validate the theoretical analysis and also demonstrate the effectiveness of the GrHDP design. [ABSTRACT FROM PUBLISHER]

Fisher’s criterion is one of the most popular discriminant criteria for feature extraction. It is defined as the generalized Rayleigh quotient of the between-class scatter distance to the within-class scatter distance. Consequently, Fisher’s criterion does not take advantage of the discriminant information in the class covariance differences, and hence, its discriminant ability largely depends on the class mean differences. If the class mean distances are relatively large compared with the within-class scatter distance, Fisher’s criterion-based discriminant analysis methods may achieve a good discriminant performance. Otherwise, it may not deliver good results. Moreover, we observe that the between-class distance of Fisher’s criterion is based on the $\ell _{2}$ -norm, which would be disadvantageous to separate the classes with smaller class mean distances. To overcome the drawback of Fisher’s criterion, in this paper, we first derive a new discriminant criterion, expressed as a mixture of absolute generalized Rayleigh quotients, based on a Bayes error upper bound estimation, where mixture of Gaussians is adopted to approximate the real distribution of data samples. Then, the criterion is further modified by replacing $\ell _{2}$ -norm with $\ell _{1}$ one to better describe the between-class scatter distance, such that it would be more effective to separate the different classes. Moreover, we propose a novel $\ell _{1}$ -norm heteroscedastic discriminant analysis method based on the new discriminant analysis (L1-HDA/GM) for heteroscedastic feature extraction, in which the optimization problem of L1-HDA/GM can be efficiently solved by using the eigenvalue decomposition approach. Finally, we conduct extensive experiments on four real data sets and demonstrate that the proposed method achieves much competitive results compared with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In this paper, the first probably approximately correct (PAC) algorithm for continuous deterministic systems without relying on any system dynamics is proposed. It combines the state aggregation technique and the efficient exploration principle, and makes high utilization of online observed samples. We use a grid to partition the continuous state space into different cells to save samples. A near-upper Q operator is defined to produce a near-upper Q function using samples in each cell. The corresponding greedy policy effectively balances between exploration and exploitation. With the rigorous analysis, we prove that there is a polynomial time bound of executing nonoptimal actions in our algorithm. After finite steps, the final policy reaches near optimal in the framework of PAC. The implementation requires no knowledge of systems and has less computation complexity. Simulation studies confirm that it is a better performance than other similar PAC algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, we give and prove the lower bounds of the Vapnik–Chervonenkis (VC)-dimension of the univariate decision tree hypothesis class. The VC-dimension of the univariate decision tree depends on the VC-dimension values of its subtrees and the number of inputs. Via a search algorithm that calculates the VC-dimension of univariate decision trees exhaustively, we show that our VC-dimension bounds are tight for simple trees. To verify that the VC-dimension bounds are useful, we also use them to get VC-generalization bounds for complexity control using structural risk minimization in decision trees, i.e., pruning. Our simulation results show that structural risk minimization pruning using the VC-dimension bounds finds trees that are more accurate as those pruned using cross validation. [ABSTRACT FROM PUBLISHER]

This paper investigates the problem of sampled-data stabilization for neural-network-based control systems with an optimal guaranteed cost. Using time-dependent Lyapunov functional approach, some novel conditions are proposed to guarantee the closed-loop systems exponentially stable, which fully use the available information about the actual sampling pattern. Based on the derived conditions, the design methods of the desired sampled-data three-layer fully connected feedforward neural-network-based controller are established to obtain the largest sampling interval and the smallest upper bound of the cost function. A practical example is provided to demonstrate the effectiveness and feasibility of the proposed techniques. [ABSTRACT FROM AUTHOR]

In this paper, we study the separation of synchronous sources (SSS) problem, which deals with the separation of sources whose phases are synchronous. This problem cannot be addressed through independent component analysis methods because synchronous sources are statistically dependent. We present a two-step algorithm, called phase locked matrix factorization (PLMF), to perform SSS. We also show that SSS is identifiable under some assumptions and that any global minimum of PLMFs cost function is a desirable solution for SSS. We extensively study the algorithm on simulated data and conclude that it can perform SSS with various numbers of sources and sensors and with various phase lags between the sources, both in the ideal (i.e., perfectly synchronous and nonnoisy) case, and with various levels of additive noise in the observed signals and of phase jitter in the sources. [ABSTRACT FROM AUTHOR]

Recently, researchers in the artificial neural network field have focused their attention on connectionist models composed by several hidden layers. In fact, experimental results and heuristic considerations suggest that deep architectures are more suitable than shallow ones for modern applications, facing very complex problems, e.g., vision and human language understanding. However, the actual theoretical results supporting such a claim are still few and incomplete. In this paper, we propose a new approach to study how the depth of feedforward neural networks impacts on their ability in implementing high complexity functions. First, a new measure based on topological concepts is introduced, aimed at evaluating the complexity of the function implemented by a neural network, used for classification purposes. Then, deep and shallow neural architectures with common sigmoidal activation functions are compared, by deriving upper and lower bounds on their complexity, and studying how the complexity depends on the number of hidden units and the used activation function. The obtained results seem to support the idea that deep networks actually implements functions of higher complexity, so that they are able, with the same number of resources, to address more difficult problems. [ABSTRACT FROM AUTHOR]

In online learning, the dynamic regret metric chooses the reference oracle that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications, such as online recommendation (since the customers’ preference always evolves over time). While the online gradient (OG) method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this article, we show that proximal OG (a general version of OG) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound. It is highlighted that we provide a new and general lower bound of dynamic regret. It provides new understanding about the difficulty to follow the dynamics in the online setting. [ABSTRACT FROM AUTHOR]

Twin support vector machine (TWSVM), which constructs two nonparallel classifying hyperplanes, is widely applied to various fields. However, TWSVM solves two quadratic programming problems (QPPs) separately such that the final classifiers lack consistency and enough prediction accuracy. Moreover, by reason of only considering the 1-norm penalty for slack variables, TWSVM is not well defined in the geometrical view. In this article, we propose a novel elastic net nonparallel hyperplane support vector machine (ENNHSVM), which adopts elastic net penalty for slack variables and constructs two nonparallel separating hyperplanes simultaneously. We further discuss the properties of ENNHSVM theoretically and derive the violation tolerance upper bound to better demonstrate the relative violations of training samples in the same class. In particular, we design a safe screening rule for ENNHSVM to speed up the calculations. We finally compare the performance of ENNHSVM on both synthetic datasets and benchmark datasets with the Lagrangian SVM, the twin parametric-margin SVM, the elastic net SVM, the TWSVM, and the nonparallel hyperplane SVM. [ABSTRACT FROM AUTHOR]

This article addresses the simultaneous state and unknown input estimation problem for a class of discrete time-varying complex networks (CNs) under redundant channels and dynamic event-triggered mechanisms (ETMs). The redundant channels, modeled by an array of mutually independent Bernoulli distributed stochastic variables, are exploited to enhance transmission reliability. For energy-saving purposes, a dynamic event-triggered transmission scheme is enforced to ensure that every sensor node sends its measurement to the corresponding estimator only when a certain condition holds. The primary objective of the investigation carried out is to construct a recursive estimator for both the state and the unknown input such that certain upper bounds on the estimation error covariances are first guaranteed and then minimized at each time instant in the presence of dynamic event-triggered strategies and redundant channels. By solving two series of recursive difference equations, the desired estimator gains are computed. Finally, an illustrative example is presented to show the usefulness of the developed estimator design method. [ABSTRACT FROM AUTHOR]

Deep neural networks (DNNs) are shown to be excellent solutions to staggering and sophisticated problems in machine learning. A key reason for their success is due to the strong expressive power of function representation. For piecewise linear neural networks (PLNNs), the number of linear regions is a natural measure of their expressive power since it characterizes the number of linear pieces available to model complex patterns. In this article, we theoretically analyze the expressive power of PLNNs by counting and bounding the number of linear regions. We first refine the existing upper and lower bounds on the number of linear regions of PLNNs with rectified linear units (ReLU PLNNs). Next, we extend the analysis to PLNNs with general piecewise linear (PWL) activation functions and derive the exact maximum number of linear regions of single-layer PLNNs. Moreover, the upper and lower bounds on the number of linear regions of multilayer PLNNs are obtained, both of which scale polynomially with the number of neurons at each layer and pieces of PWL activation function but exponentially with the number of layers. This key property enables deep PLNNs with complex activation functions to outperform their shallow counterparts when computing highly complex and structured functions, which, to some extent, explains the performance improvement of deep PLNNs in classification and function fitting. [ABSTRACT FROM AUTHOR]

In this article, we study the generalization performance of multitask learning (MTL) by considering MTL as a learning process of vector-valued functions (VFs). We will answer two theoretical questions, given a small size training sample: 1) under what conditions does MTL perform better than single-task learning (STL)? And 2) under what conditions does MTL guarantee the consistency of all tasks during learning? In contrast to the conventional task-summation based MTL, the introduction of VF form enables us to detect the behavior of each task and the task-group relatedness in MTL. Specifically, the task-group relatedness examines how the success (or failure) of some tasks affects the performance of the other tasks. By deriving the specific deviation and symmetrization inequalities for VFs, we obtain a generalization bound for MTL to the upper bound of the joint probability that there is at least one task with a large generalization gap. To answer the first question, we discuss how the synergic relatedness between task groups affects the generalization performance of MTL and shows that MTL outperforms STL if almost any pair of complementary task groups is predominantly synergic. Moreover, to answer the second question, we present a sufficient condition to guarantee the consistency of each task in MTL, which requires that the function class of each task should not have high complexity. In addition, our findings provide a strategy to examine whether the task settings will enjoy the advantages of MTL. [ABSTRACT FROM AUTHOR]

The zeroing neural network (ZNN) activated by nonlinear activation functions plays an important role in many fields. However, conventional ZNN can only realize finite-time convergence, which greatly limits the application of ZNN in a noisy environment. Generally, finite-time convergence depends on the original state of ZNN, but the original state is often unknown in advance. In addition, when meeting with different noises, the applied nonlinear activation functions cannot tolerate external disturbances. In this article, on the strength of this idea, two prescribed-time and robust ZNN (PTR-ZNN) models activated by two nonlinear activation functions are put forward to address the time-variant Stein matrix equation. The proposed two PTR-ZNN models own two remarkable advantages simultaneously: 1) prescribed-time convergence that does not rely on original states and 2) superior noise-tolerance performance that can tolerate time-variant bounded vanishing and nonvanishing noises. Furthermore, the detailed theoretical analysis is provided to guarantee the prescribed-time convergence and noise-tolerance performance, with the convergence upper bounds of steady-state residual errors calculated. Finally, simulative comparison results indicate the effectiveness and the superiority of the proposed two PTR-ZNN models for the time-variant Stein matrix equation solving. [ABSTRACT FROM AUTHOR]

Residual connections significantly boost the performance of deep neural networks. However, few theoretical results address the influence of residuals on the hypothesis complexity and the generalization ability of deep neural networks. This article studies the influence of residual connections on the hypothesis complexity of the neural network in terms of the covering number of its hypothesis space. We first present an upper bound of the covering number of networks with residual connections. This bound shares a similar structure with that of neural networks without residual connections. This result suggests that moving a weight matrix or nonlinear activation from the bone to a vine would not increase the hypothesis space. Afterward, an $\mathcal O(1 / \sqrt {N})$ margin-based multiclass generalization bound is obtained for ResNet, as an exemplary case of any deep neural network with residual connections. Generalization guarantees for similar state-of-the-art neural network architectures, such as DenseNet and ResNeXt, are straightforward. According to the obtained generalization bound, we should introduce regularization terms to control the magnitude of the norms of weight matrices not to increase too much, in practice, to ensure a good generalization ability, which justifies the technique of weight decay. [ABSTRACT FROM AUTHOR]

This article tackles the recursive filtering problem for a class of stochastic nonlinear time-varying complex networks (CNs) suffering from both the state saturations and the deception attacks. The nonlinear inner coupling and the state saturations are taken into account to characterize the nonlinear nature of CNs. From the defender’s perspective, the randomly occurring deception attack is governed by a set of Bernoulli binary distributed white sequence with a given probability. The objective of the addressed problem is to design a state-saturated recursive filter such that, in the simultaneous presence of the state saturations and the randomly occurring deception attacks, a certain upper bound is guaranteed on the filtering error covariance, and such an upper bound is then minimized at each time instant. By employing the induction method, an upper bound on the filtering error variance is first constructed in terms of the solutions to a set of matrix difference equations. Subsequently, the filter parameters are appropriately designed to minimize such an upper bound. Finally, a numerical simulation example is provided to demonstrate the feasibility and usefulness of the proposed filtering scheme. [ABSTRACT FROM AUTHOR]

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability. [ABSTRACT FROM AUTHOR]

We investigate the adversarial multiarmed bandit problem and introduce an online algorithm that asymptotically achieves the performance of the best switching bandit arm selection strategy. Our algorithms are truly online such that we do not use the game length or the number of switches of the best arm selection strategy in their constructions. Our results are guaranteed to hold in an individual sequence manner, since we have no statistical assumptions on the bandit arm losses. Our regret bounds, i.e., our performance bounds with respect to the best bandit arm selection strategy, are minimax optimal up to logarithmic terms. We achieve the minimax optimal regret with computational complexity only log-linear in the game length. Thus, our algorithms can be efficiently used in applications involving big data. Through an extensive set of experiments involving synthetic and real data, we demonstrate significant performance gains achieved by the proposed algorithm with respect to the state-of-the-art switching bandit algorithms. We also introduce a general efficiently implementable bandit arm selection framework, which can be adapted to various applications. [ABSTRACT FROM AUTHOR]

We analyze an online learning algorithm that adaptively combines outputs of two constituent algorithms (or the experts) running in parallel to estimate an unknown desired signal. This online learning algorithm is shown to achieve and in some cases outperform the mean-square error (MSE) performance of the best constituent algorithm in the steady state. However, the MSE analysis of this algorithm in the literature uses approximations and relies on statistical models on the underlying signals. Hence, such an analysis may not be useful or valid for signals generated by various real-life systems that show high degrees of nonstationarity, limit cycles and that are even chaotic in many cases. In this brief, we produce results in an individual sequence manner. In particular, we relate the time-accumulated squared estimation error of this online algorithm at any time over any interval to the one of the optimal convex mixture of the constituent algorithms directly tuned to the underlying signal in a deterministic sense without any statistical assumptions. In this sense, our analysis provides the transient, steady-state, and tracking behavior of this algorithm in a strong sense without any approximations in the derivations or statistical assumptions on the underlying signals such that our results are guaranteed to hold. We illustrate the introduced results through examples. [ABSTRACT FROM PUBLISHER]

Passivity method is very effective to analyze large-scale nonlinear systems with strong nonlinearities. However, when most parts of the nonlinear system are unknown, the published neural passivity methods are not suitable for feedback stability. In this brief, we propose a novel sliding mode learning algorithm and sliding mode feedback passivity control. We prove that for a wide class of unknown nonlinear systems, this neural sliding mode control can passify and stabilize them. This passivity method is validated with a simulation and real experiment tests. [ABSTRACT FROM PUBLISHER]