An official website of the United States government
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
-
-
Jaggi, Martin (Ed.)A classical approach for solving discrete time nonlinear control on a nite horizon consists in repeatedly minimizing linear quadratic approximations of the original problem around current candidate solutions. While widely popular in many domains, such an approach has mainly been analyzed locally. We provide detailed convergence guarantees to stationary points as well as local linear convergence rates for the Iterative Linear Quadratic Regulator (ILQR) algorithm and its Di erential Dynamic Programming (DDP) variant. For problems without costs on control variables, we observe that global convergence to minima can be ensured provided that the linearized discrete time dynamics are surjective, costs on the state variables are gradient dominated. We further detail quadratic local convergence when the costs are self-concordant. We show that surjectivity of the linearized dynamics hold for appropriate discretization schemes given the existence of a feedback linearization scheme. We present complexity bounds of algorithms based on linear quadratic approximations through the lens of generalized Gauss-Newton methods. Our analysis uncovers several convergence phases for regularized generalized Gauss-Newton algorithms.more » « less
-
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
-
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
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
