Stochastic Approximation

Enhanced Derivative-Free Optimization Using Adaptive Correlation-Induced Finite Difference Estimators ArXiv ID: 2502.20819 “View on arXiv” Authors: Unknown Abstract Gradient-based methods are well-suited for derivative-free optimization (DFO), where finite-difference (FD) estimates are commonly used as gradient surrogates. Traditional stochastic approximation methods, such as Kiefer-Wolfowitz (KW) and simultaneous perturbation stochastic approximation (SPSA), typically utilize only two samples per iteration, resulting in imprecise gradient estimates and necessitating diminishing step sizes for convergence. In this paper, we first explore an efficient FD estimate, referred to as correlation-induced FD estimate, which is a batch-based estimate. Then, we propose an adaptive sampling strategy that dynamically determines the batch size at each iteration. By combining these two components, we develop an algorithm designed to enhance DFO in terms of both gradient estimation efficiency and sample efficiency. Furthermore, we establish the consistency of our proposed algorithm and demonstrate that, despite using a batch of samples per iteration, it achieves the same convergence rate as the KW and SPSA methods. Additionally, we propose a novel stochastic line search technique to adaptively tune the step size in practice. Finally, comprehensive numerical experiments confirm the superior empirical performance of the proposed algorithm. ...

An Asymptotic CVaR Measure of Risk for Markov Chains ArXiv ID: 2405.13513 “View on arXiv” Authors: Unknown Abstract Risk sensitive decision making finds important applications in current day use cases. Existing risk measures consider a single or finite collection of random variables, which do not account for the asymptotic behaviour of underlying systems. Conditional Value at Risk (CVaR) is the most commonly used risk measure, and has been extensively utilized for modelling rare events in finite horizon scenarios. Naive extension of existing risk criteria to asymptotic regimes faces fundamental challenges, where basic assumptions of existing risk measures fail. We present a complete simulation based approach for sequentially computing Asymptotic CVaR (ACVaR), a risk measure we define on limiting empirical averages of markovian rewards. Large deviations theory, density estimation, and two-time scale stochastic approximation are utilized to define a ’tilted’ probability kernel on the underlying state space to facilitate ACVaR simulation. Our algorithm enjoys theoretical guarantees, and we numerically evaluate its performance over a variety of test cases. ...

Asymptotic Error Analysis of Multilevel Stochastic Approximations for the Value-at-Risk and Expected Shortfall ArXiv ID: 2311.15333 “View on arXiv” Authors: Unknown Abstract Crépey, Frikha, and Louzi (2023) introduced a nested stochastic approximation algorithm and its multilevel acceleration to compute the value-at-risk and expected shortfall of a random financial loss. We hereby establish central limit theorems for the renormalized estimation errors associated with both algorithms as well as their averaged versions. Our findings are substantiated through a numerical example. ...