We present adaptive algorithms with strong datadependent regret guarantees for the problem of bandit convex optimization. In the process, we develop a general framework from which the main previous results in this set...
详细信息
ISBN:
(纸本)9781510827806
We present adaptive algorithms with strong datadependent regret guarantees for the problem of bandit convex optimization. In the process, we develop a general framework from which the main previous results in this setting can be recovered. The key method is the introduction of adaptive regularization. By appropriately adapting the exploration scheme, we show that one can derive regret guarantees that can be significantly more favorable than those previously known. Moreover, our analysis also modularizes the problematic quantities in achieving the conjectured minimax optimal rates in the most general setting of the problem.
New adaptive algorithms based on multi-band decomposition of the error signal and application of a different convergence factor for each band are derived. With this approach, tracking ability and performance in steady...
详细信息
New adaptive algorithms based on multi-band decomposition of the error signal and application of a different convergence factor for each band are derived. With this approach, tracking ability and performance in steady state can be traded off along the frequency domain giving rise to estimates of the adaptive filter coefficients closer to the ideal response as compared to those obtained with conventional least-mean-square (LMS) and recursive least-squares (RLS) algorithms, particularly when the statistical properties of the analyzed signal vary along the frequency spectrum. A new adaptation technique for the forgetting factor depending exclusively on tbe autocorrelation values of the input signal is also introduced and a multi-band RLS algorithm, with an independent variable forgetting factor for each band, suitable for the analysis of nonstationary signals is described. Computer experiments comparing the performance of multi-band and conventional LMS and RLS algorithms are shown.
Although adaptive gradient algorithms are relatively robust, they generally have poor performance in the absence of "rich" excitation. It is well known that the convergence speed of the LMS algorithm deterio...
详细信息
Although adaptive gradient algorithms are relatively robust, they generally have poor performance in the absence of "rich" excitation. It is well known that the convergence speed of the LMS algorithm deteriorates when the condition number of the autocorrelation matrix of the input is large. This problem has been addressed using RLS, Weighted RLS (WRLS), as well as normalized frequency-domain algorithms. In this paper, we present an alternative approach that employs gradient projections in selected eigenvector subspaces to improve the convergence properties of LMS algorithms. We also use an auxiliary algorithm that iteratively updates selected eigensubspaces. The proposed algorithm is efficient in terms of complexity and its convergence speed approaches that of the WRLS for a certain class of excitation signals. (C) 2003 Published by Elsevier B.V.
We present a fast, adaptive multiresolution algorithm for applying integral operators with a wide class of radially symmetric kernels in dimensions one, two and three. This algorithm is made efficient by the use of se...
详细信息
We present a fast, adaptive multiresolution algorithm for applying integral operators with a wide class of radially symmetric kernels in dimensions one, two and three. This algorithm is made efficient by the use of separated representations of the kernel. We discuss operators of the class (-Delta + mu(2) I)(-alpha), where mu >= 0 and 0 < alpha < 3/2, and illustrate the algorithm for the Poisson and Schrodinger equations in dimension three. The same algorithm may be used for all operators with radially symmetric kernels approximated as a weighted sum of Gaussians, making it applicable across multiple fields by reusing a single implementation. This fast algorithm provides controllable accuracy at a reasonable cost, comparable to that of the Fast Multipole Method (FMM). It differs from the FMM by the type of approximation used to represent kernels and has the advantage of being easily extendable to higher dimensions. (C) 2007 Elsevier Inc. All rights reserved.
We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints, which are constraints that need to be satisfied when accumulated over a finite number o...
详细信息
ISBN:
(纸本)9781510829008
We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints, which are constraints that need to be satisfied when accumulated over a finite number of rounds T, but can be violated in intermediate rounds. For some user-defined trade-off parameter β ∈ (0,1), the proposed algorithm achieves cumulative regret bounds of O(Tmax{β,1-β}) and O(T1-β/2), respectively for the loss and the constraint violations. Our results hold for convex losses, can handle arbitrary convex constraints and rely on a single computationally efficient algorithm. Our contributions generalize over the best known cumulative regret bounds of Mahdavi et al. (2012a), which are respectively O(T1/2) and O(T3/4) for general convex domains, and respectively O(T2/3) and O(T2/3) when the domain is further restricted to be a polyhedral set. We supplement the analysis with experiments validating the performance of our algorithm in practice.
The aim of this paper is to develop efficient online adaptive algorithms for the generalized eigen-decomposition problem which arises in a variety of modern signal processing applications. First, we reinterpret the ge...
详细信息
The aim of this paper is to develop efficient online adaptive algorithms for the generalized eigen-decomposition problem which arises in a variety of modern signal processing applications. First, we reinterpret the generalized eigen-decomposition problem as an unconstrained minimization problem by constructing a novel cost function. Second, by applying projection approximation method and recursive least-square (RLS) technique to the cost function, a parallel adaptive algorithm for a basis for the r-dimensional (r > 0) dominant generalized eigen-subspace and a sequential algorithm based on deflation technique for the first r-dominant generalized eigenvectors are derived. These algorithms can be viewed as counterparts of the extended projection approximation subspace tracking (PAST) and PASTd algorithms, respectively. Furthermore, we modify the parallel algorithm to explicitly estimate the first r-generalized eigenvectors in parallel, not the generalized eigen-subspace. More important, the modified parallel algorithm can be used to extract multiple generalized eigenvectors of two nonstationary sequences, while the proposed sequential algorithm lacks this ability because of slow convergence of minor generalized eigenvectors due to error propagation of the deflation technique. Third, following convergence analysis methods for PAST and PASTd, we prove the asymptotic convergence properties of the proposed algorithms. Finally, computer simulations are performed to investigate the accuracy and the speed advantages of the proposed algorithms.
In this paper a family of adaptive algorithms robust to impulsive noise and with low computational cost are presented. Unlike other approaches, no cost functions or filtering of the gradient are considered in order to...
详细信息
ISBN:
(纸本)9783902661692
In this paper a family of adaptive algorithms robust to impulsive noise and with low computational cost are presented. Unlike other approaches, no cost functions or filtering of the gradient are considered in order to update the filter coefficients. Its initial basis is the basic LMS algorithm and its sign-error variant. The proposed algorithms can be considered as some sign-error variants of the LMS algorithm. The algorithms are successfully tested in terms of accuracy and convergence in a standard system identification simulation in which an impulsive noise is present. Simulations show that they improve the performance of LMS variants that are robust to impulsive noise.
This paper presents the application of adaptive algorithms to integrated chassis control. Integrated chassis control uses electronic stability control and active front steering as actuators. In order to generate the c...
详细信息
This paper presents the application of adaptive algorithms to integrated chassis control. Integrated chassis control uses electronic stability control and active front steering as actuators. In order to generate the control yaw moment using electronic stability control and active front steering, and to coordinate the relative magnitude of the tyre force generated by active front steering with that generated by electronic stability control, a fast and simple yaw moment distribution procedure is needed. For this purpose, adaptive methods, namely the least-mean-square algorithm, the sign-sign least-mean-squares algorithm and the leaky least-mean-square algorithm, are applied. To coordinate active front steering and electronic stability control in the leaky least-mean-square algorithm, a particular weight set is selected. To check the effectiveness of the adaptive algorithms in integrated chassis control, simulations using the vehicle simulation package CarSim((R)) were carried out.
The least mean squared (LMS) algorithm and its variants have been the most often used algorithms in adaptive signal processing. However the LMS algorithm suffers from a high computational complexity, especially with l...
详细信息
The least mean squared (LMS) algorithm and its variants have been the most often used algorithms in adaptive signal processing. However the LMS algorithm suffers from a high computational complexity, especially with large filter lengths. The Fourier transform-based block normalized LMS (FBNLMS) reduces the computation count by using the discrete Fourier transform (DFT) and exploiting the fast algorithms for implementing the DFT. Even though the savings achieved with the FBNLMS over the direct-LMS implementation are significant, the computational requirements of FBNLMS are still very high, rendering many real-time applications, like audio and video estimation, infeasible. The Hartley transform-based BNLMS (HBNLMS) is found to have a computational complexity much less than, and a memory requirement almost of the same order as, that of the FBNLMS. This paper is based on the cosine and sine symmetric implementation of the discrete Hartley transform (DHT), which is the key in-reducing the computational complexity of the FBNLMS by 33% asymptotically. (with respect to multiplications). The parallel implementation of the discrete cosine transform (DCT) in turn can lead to more efficient implementations of the HBNLMS.
We consider the important problem of energy balanced data propagation in wireless sensor networks and we extend and generalize previous works by allowing adaptive energy assignment. We consider the data gathering prob...
详细信息
We consider the important problem of energy balanced data propagation in wireless sensor networks and we extend and generalize previous works by allowing adaptive energy assignment. We consider the data gathering problem where data are generated by the sensors and must be routed toward a unique sink. Sensors route data by either sending the data directly to the sink or in a multi-hop fashion by delivering the data to a neighbouring sensor. Direct and neighbouring transmissions require different levels of energy consumption. Basically, the protocols balance the energy consumption among the sensors by computing the adequate ratios of direct and neighbouring transmissions. An abstract model of energy dissipation as a random walk is proposed, along with rigorous performance analysis techniques. Two efficient distributed algorithms are presented and analyzed, by both rigorous means and simulation. The first one is easy to implement and fast to execute. The protocol assumes that sensors know a-priori the rate of data they generate. The sink collects and processes all these information in order to compute the relevant value of the protocol parameter. This value is transmitted to the sensors which individually compute their optimal ratios of direct and neighbouring transmissions. The second protocol avoids the necessary a-priori knowledge of the data rate generated by sensors by inferring the relevant information from the observation of the data paths. Furthermore, this algorithm is based on stochastic estimation methods and is adaptive to environmental changes.
暂无评论