Features in machine learning problems are often time-varying and may be related to outputs in an algebraic or dynamical manner. The dynamic nature of these machine learning problems renders current higher order accelerated gradient descent methods unstable or weakens their convergence guarantees. Inspired by methods employed in adaptive control, this paper proposes new algorithms for the case when time-varying features are present, and demonstrates provable performance guarantees. In particular, we develop a unified variational perspective within a continuous time algorithm. This variational perspective includes higher order learning concepts and normalization, both of which stem from adaptive control, and allows stability to be established for dynamical machine learning problems where time-varying features are present. These higher order algorithms are also examined for provably correct learning in adaptive control and identification. Simulations are provided to verify the theoretical results.
This work continues in the tradition of @cite_26 and @cite_55 whereby insight is gained into accelerated gradient descent methods through a continuous lens. Future work will be to obtain discrete time implementations of our algorithms with matching rates @cite_48 @cite_27 , and to connect those back to classic discrete time adaptive control algorithms @cite_19 @cite_11 @cite_30 . Other fruitful directions forward would be to study these accelerated algorithms within the context of output feedback control, and to rigorously prove convergence rates when the regressor vectors are persistently exciting @cite_38 @cite_25 .
@cite_30 @cite_38 @cite_26 @cite_48 @cite_55 @cite_19 @cite_27 @cite_25 @cite_11
1569320505 2963610705 2528062157 2893838930 2963430672 2147873335 2787367827 2162725061
This unified survey focuses on linear discrete-time systems and explores the natural extensions to nonlinear systems. In keeping with the importance of computers to practical applications, the authors emphasize discrete-time systems. Their approach summarizes the theoretical and practical aspects of a large class of adaptive algorithms.1984 edition. The convergence properties of adaptive systems in terms of excitation conditions on the regressor vector are well known. With persistent excitation of the regressor vector in model reference adaptive control the state error and the adaptation error are globally exponentially stable or, equivalently, exponentially stable in the large. When the excitation condition, however, is imposed on the reference input or the reference model state, it is often incorrectly concluded that the persistent excitation in those signals also implies exponential stability in the large. The definition of persistent excitation is revisited so as to address some possible confusion in the adaptive control literature. It is then shown that persistent excitation of the reference model only implies local persistent excitation (weak persistent excitation). Weak persistent excitation of the regressor is still sufficient for uniform asymptotic stability in the large, but not exponential stability in the large. We show that there exists ... We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex. Author(s): Wilson, Ashia | Advisor(s): Jordan, Michael I; Recht, Benjamin | Abstract: Optimization is among the richest modeling languages in science. In statistics and machine learning, for instance, inference is typically posed as an optimization problem. While there are many algorithms designed to solve optimization problems, and a seemingly greater number of convergence proofs, essentially all proofs follow a classical approach from dynamical systems theory: they present a Lyapunov function and show it decreases. The primary goal of this thesis is to demonstrate that making the Lyapunov argument explicit greatly simplifies, clarifies, and to a certain extent, unifies, convergence theory for optimization.The central contributions of this thesis are the following results: we• present several variational principles whereby we obtain continuous-time dynamical systems useful for optimization;• introduce Lyapunov functions for both the continuous-time dynamical systems and discrete-time algorithms and demonstrate how to move between these Lyapunov functions;• utilize the Lyapunov framework as well as numerical analysis and integration techniques to obtain upper bounds for several novel discrete-time methods for optimization, a few of which have matching lower bounds. Accelerated gradient methods play a central role in optimization, achieving optimal rates in many settings. Although many generalizations and extensions of Nesterov’s original acceleration method have been proposed, it is not yet clear what is the natural scope of the acceleration concept. In this paper, we study accelerated methods from a continuous-time perspective. We show that there is a Lagrangian functional that we call the Bregman Lagrangian, which generates a large class of accelerated methods in continuous time, including (but not limited to) accelerated gradient descent, its non-Euclidean extension, and accelerated higher-order gradient methods. We show that the continuous-time limit of all of these methods corresponds to traveling the same curve in spacetime at different speeds. From this perspective, Nesterov’s technique and many of its generalizations can be viewed as a systematic way to go from the continuous-time curves generated by the Bregman Lagrangian to a family of discrete-time accelerated algorithms. This paper establishes global convergence for a class of adaptive control algorithms applied to discrete-time multiinput multioutput deterministic linear systems. It is shown that the algorithms will ensure that the systems inptus and outputs remain bounded for all time and that the output tracking error converges to zero. Accelerated gradient methods have had significant impact in machine learning -- in particular the theoretical side of machine learning -- due to their ability to achieve oracle lower bounds. But their heuristic construction has hindered their full integration into the practical machine-learning algorithmic toolbox, and has limited their scope. In this paper we build on recent work which casts acceleration as a phenomenon best explained in continuous time, and we augment that picture by providing a systematic methodology for converting continuous-time dynamics into discrete-time algorithms while retaining oracle rates. Our framework is based on ideas from Hamiltonian dynamical systems and symplectic integration. These ideas have had major impact in many areas in applied mathematics, but have not yet been seen to have a relationship with optimization. This paper establishes global convergence of a stochastic adaptive control algorithm for discrete time linear systems. It is shown that, with probability one, the algorithm will ensure the system inputs and outputs are sample mean square bounded and the conditional mean square output tracking error achieves its global minimum possible value for linear feedback control. Thus, asymptotically, the adaptive control algorithm achieves the same performance as could be achieved if the system parameters were known.