A Markovian Model for Learning-to-Optimize

2024/08/21 by Michael Sucker, Sucker, Michael, Peter Ochs +1
Computer Science · Decision Sciences · Engineering · #Advanced Data Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Probability (math.PR) #Simulation Techniques and Applications

paper · pdf · doi:10.48550/arxiv.2408.11629

openalex publication_date 2024/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Related

• Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation
• PAC-Bayesian Learning of Optimization Algorithms
• A Generalization Result for Convergence in Learning-to-Optimize
• A Probabilistically Motivated Learning Rate Adaptation for Stochastic Optimization
• Data-Driven Performance Guarantees for Classical and Learned Optimizers