We provide a second-order stochastic differential equation (SDE), which characterizes the continuous-time dynamics of accelerated stochastic mirror descent (ASMD) for strongly convex functions. This SDE plays a central role in designing new discrete-time ASMD algorithms via numerical discretization, and providing neat analyses of their convergence rates based on Lyapunov functions. Our results suggest that the only existing ASMD algorithm, namely, AC-SA proposed in Ghadimi & Lan (2012) is one instance of its kind, and we can actually derive new instances of ASMD with fewer tuning parameters. This sheds light on revisiting accelerated stochastic optimization through the lens of SDEs, which can lead to a better understanding of acceleration in stochastic optimization, as well as new simpler algorithms. Numerical experiments on both synthetic and real data support our theory.
more »
« less
Accelerated Stochastic Mirror Descent: From Continuous-time Dynamics to Discrete-time Algorithms
We present a new framework to analyze accelerated stochastic mirror descent through the lens of continuous-time stochastic dynamic systems. It enables us to design new algorithms, and perform a unified and simple analysis of the convergence rates of these algorithms. More specifically, under this framework, we provide a Lyapunov function based analysis for the continuous-time stochastic dynamics, as well as several new discrete-time algorithms derived from the continuous-time dynamics. We show that for general convex objective functions, the derived discrete-time algorithms attain the optimal convergence rate. Empirical experiments corroborate our theory.
more »
« less
- PAR ID:
- 10063535
- Date Published:
- Journal Name:
- International Conference on Artificial Intelligence and Statistics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper, a higher order time-discretization scheme is proposed, where the iterates approximate the solution of the stochastic semilinear wave equation driven by multiplicative noise with general drift and diffusion. We employ variational method for its error analysis and prove an improved convergence order of $\frac 32$ for the approximates of the solution. The core of the analysis is Hölder continuity in time and moment bounds for the solutions of the continuous and the discrete problem. Computational experiments are also presented.more » « less
-
Contagious processes on networks, such as spread of disease through physical proximity or information diffusion over social media, are continuous-time processes that depend upon the pattern of interactions between the individuals in the network. Continuous-time stochastic epidemic models are a natural fit for modeling the dynamics of such processes. However, prior work on such continuous-time models doesn’t consider the dynamics of the underlying interaction network which involves addition and removal of edges over time. Instead, researchers have typically simulated these processes using discrete-time approximations, in which one has to trade off between high simulation accuracy and short computation time. In this paper, we incorporate continuous-time network dynamics (addition and removal of edges) into continuous-time epidemic simulations. We propose a rejection-sampling based approach coupled with the well-known Gillespie algorithm that enables exact simulation of the continuous-time epidemic process. Our proposed approach gives exact results, and the computation time required for simulation is reduced as compared to discrete-time approximations of comparable accuracy.more » « less
-
We develop a general framework for stationary marked point processes in discrete time. We start with a careful analysis of the sample paths. Our initial representation is a sequence {(tj,kj) :j∈Z} of times tj∈Z and marks kj∈K, with batch arrivals (i.e.,tj=tj+1) allowed. We also define alternative interarrival time and sequence representations and show that the three different representations are topologically equivalent. Then, we develop discrete analogs of the familiar stationary stochastic constructs in continuous time: time-stationary and point-stationary random marked point processes, Palm distributions, inversion formulas and Campbell’s theorem with an application to the derivation of a periodic-stationary Little’s law. Along the way,we provide examples to illustrate interesting features of the discrete-time theory.more » « less
-
Krause, Andreas ; Brunskill, Emma ; Cho, Kyunghyun ; Engelhardt, Barbara ; Sabato, Sivan ; Scarlett, Jonathan (Ed.)Transfer operators provide a rich framework for representing the dynamics of very general, nonlinear dynamical systems. When interacting with reproducing kernel Hilbert spaces (RKHS), descriptions of dynamics often incur prohibitive data storage requirements, motivating dataset sparsification as a precursory step to computation. Further, in practice, data is available in the form of trajectories, introducing correlation between samples. In this work, we present a method for sparse learning of transfer operators from $\beta$-mixing stochastic processes, in both discrete and continuous time, and provide sample complexity analysis extending existing theoretical guarantees for learning from non-sparse, i.i.d. data. In addressing continuous-time settings, we develop precise descriptions using covariance-type operators for the infinitesimal generator that aids in the sample complexity analysis. We empirically illustrate the efficacy of our sparse embedding approach through deterministic and stochastic nonlinear system examples.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
