A Markovian Model for Learning-to-Optimize
We present a probabilistic model for stochastic iterative algorithms with the use case of optimization algorithms in mind. Based on this model, we present PAC-Bayesian generalization bounds for functions that are defined on the trajectory of the learned algorithm, for example, the expected (non-asymptotic) convergence rate and the expected time to reach the stopping criterion. Thus, not only does this model allow for learning stochastic algorithms based on their empirical performance, it also yields results about their actual convergence rate and their actual convergence time. We stress that, since the model is valid in a more general setting than learning-to-optimize, it is of interest for other fields of application, too. Finally, we conduct five practically relevant experiments, showing the validity of our claims.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsmodelvalidSimilar Papers 제목 키워드 기반
Violina: Various-of-trajectories Identification of Linear Time-invariant Non-Markovian Dynamics
We propose a new system identification method Violina (various-of-trajectories identification of linear time-invariant non-Markovian dynamics). In the Violina framework, we optimize the coefficient matrices of state-spac…
State Space ModelsDynamic Game Theoretic Neural Optimizer
The connection between training deep neural networks (DNNs) and optimal control theory (OCT) has attracted considerable attention as a principled tool of algorithmic design. Despite few attempts being made, they have bee…
image-classificationImage ClassificationPolicy Gradient Methods for Non-Markovian Reinforcement Learning
We study policy gradient methods for reinforcement learning in non-Markovian decision processes (NMDPs), where observations and rewards depend on the entire interaction history. To handle this dependence, the agent maint…
Reinforcement LearningStochastic Gradient Descent under Markovian Sampling Schemes
We study a variation of vanilla stochastic gradient descent where the optimizer only has access to a Markovian sampling scheme. These schemes encompass applications that range from decentralized optimization with a rando…
Markovian RNN: An Adaptive Time Series Prediction Network with HMM-based Switching for Nonstationary Environments
We investigate nonlinear regression for nonstationary sequential data. In most real-life applications such as business domains including finance, retail, energy and economy, timeseries data exhibits nonstationarity due t…
Time SeriesTime Series AnalysisTime Series Prediction