Multilevel Stochastic Gradient Descent for Optimal Control Under Uncertainty

Niklas Baumgarten, David Schneiderhan · 2025

Read Multilevel Stochastic Gradient Descent for Optimal Control Under Uncertainty by Niklas Baumgarten, David Schneiderhan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02647.txt.

Introduction

Niklas Baumgarten and David Schneiderhan wrote this paper in two thousand twenty-five. It finds the best control for systems ruled by partial differential equations when the inputs are not known for sure, with a multilevel gradient method.

The twist is the gradient source: a parallel multilevel Monte Carlo scheme stands in for the true gradient. That gives tight rein over both the bias from coarse grids and the noise from sampling. Resources go where they pay most. The method homes in at a linear rate, yet never pays for the full gradient at top fidelity. On a two-dimensional case of flow through soil with wild coefficients, it beats plain batched descent on speed and accuracy both. Step rules and budget plans are weighed too.

Catalog record

CREATORNiklas Baumgarten, David Schneiderhan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-02647

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multilevel Stochastic Gradient Descent for Optimal Control Under Uncertainty Niklas Baumgarten, David Schneiderhan Abstract . We present a multilevel stochastic gradient descent method for the optimal control of systems governed by partial differential equations under uncertain input data. The gradient descent method used to find the optimal control leverages a parallel multilevel Monte Carlo method as stochastic gradient estimator. As a result, we achieve precise control over the stochastic gradient’s bias, introduced by numerical approximation, and its sampling error, arising from the use of incomplete gradients, while optimally managing computational resources. We show that the method exhibits linear convergence in the number of optimization steps while avoiding the cost of computing the full gradient at the highest fidelity. Numerical experiments demonstrate that the method significantly outperforms the standard (mini-) batched stochastic gradient descent method in terms of convergence speed and accuracy. The method is particularly well-suited for high-dimensional control problems, taking advantage of parallel computing resources and a distributed multilevel data structure. Additionally, we evaluate and implement different step size strategies, optimizer schemes, and budgeting techniques. The method’s performance is studied using a two-dimensional elliptic subsurface diffusion problem with log-normal coefficients and Matérn covariance. † † footnotetext: [email protected] [email protected] 1 Introduction The state of a physical, technological, or economical process, as a function of space and time, is often described by partial differential equations (PDEs). Controlling the state of such processes, for example, by imposing boundary conditions or external forces, is of significant interest in all the aforementioned applications. However, determining the optimal control of a PDE-governed system is a computationally demanding task, particularly when the PDE involves high-dimensional, uncertain input data and the control has to be found with high precision. Known methods to uncertain optimal control problems (OCPs) focus on minimizing the expected distance between the state and a desired target. Finding solutions to such problems often requires three key functionalities: solving the minimization problem, e.g. by using stochastic gradient descent (SGD) methods; addressing the uncertainty through sufficient sampling of the input data; and discretizing the PDEs with finite element (FE) methods. Approaches which fall under this description can be found in [ 1 , 2 , 3 , 4 , 5 ] . Motivated by this work, we take an integrated approach, combining all three functionalities in a single algorithm which leverages multilevel variance reduction, as in multilevel Monte Carlo (MLMC) methods [ 6 , 7 ] , and parallel computing resources. Even though other sampling methods to discretize the input space involve sparse grids [ 8 , 9 ] and quasi-Monte Carlo methods [ 10 , 11 ] , we based our approach on the budgeted multilevel Monte Carlo (BMLMC) method [ 12 , 13 , 14 ] , which provides high-performance and broad applicability. As baseline algorithm, we consider a step size controlled parallel (mini-) batched stochastic gradient descent (BSGD) method, e.g. used in [ 15 , 16 ] , and show that our method improves it significantly in terms of convergence speed, achievable accuracy, scalability and robustness (cf. Figure 5 for a direct numerical comparison). As a model problem, we consider a two-dimensional elliptic subsurface diffusion problem with log-normal coefficients (illustrations in Figure 1 ), generated using the memory efficient stochastic PDE sampling technique of [ 17 ] . We intentionally choose a high-dimensional elliptic problem to not lay the focus on the PDE, but rather on the algorithm and its properties. To get the gradients for the SGD, BSGD or the here introduced multilevel stochastic gradient descent (MLSGD) method, we solve the adjoint system corresponding to the PDE constraint as outlined in [ 1 ] , also related to the adjoint Monte Carlo method described in [ 18 ] . Previous multilevel ideas for OCPs can be found in [ 19 ] for pathwise control, or in [ 20 ] for sample average approximation (SAA) assembled into a large linear system — similar to [ 12 ] — then solved using a multigrid algorithm. The results in [ 21 , 22 ] provide a foundation for multilevel gradient estimation of OCPs, e.g., then used in a nonlinear conjugate gradient method. The approaches in [ 3 , 4 ] address the optimization problem using stochastic approximation (SA), tracing back to [ 23 ] , in the form of a SGD method. Our method embeds the mentioned multilevel gradient estimation in this SGD approach. In [ 24 ] , the SA is also extended to a multilevel setting, considering [ 25 ] , from which we draw further motivation to develop the MLSGD proposed with this paper. Related ideas can also be found in the context of Bayesian inverse problems, where the Stein variation gradient descent has also been extended by multilevel ideas [ 26 , 27 ] . Machine learning has been the main driver for the development of novel SGD methods to enable large-scale training of neural networks, often striking the balance between per-iteration cost and expected improvements [ 28 ] . Features such as variance (noise) reduction and parallelism through BSGD [ 29 ] , adaptive moment estimation (ADAM) [ 30 ] , adaptive step sizes [ 31 ] , or averaging and aggregation schemes [ 32 , 33 ] , have been successfully applied to various problems improving performance. We take inspiration in these approaches, incorporating them into the proposed MLSGD method for OCPs and conjecture that the algorithm is applicable in machine learning as well. Concluded, recent developments, theory and existing algorithms motivate the combination of multilevel variance reduction and SGD methods, however, we have not found a highly-performant, adaptive, and parallel method for high-dimensional control problems yet. With this paper, we propose new ways to realize such a method which in particular features: Algorithmic description and convergence analysis Building on the assumptions and notations in Section 2 , we present a detailed description of the MLSGD method for OCPs in Algorithm 1 and Algorithm 2 , incorporating the standard BSGD method recalled in Section 3 and the MLMC estimation from Section 4 . In Section 5 , we establish the linear convergence of the proposed method in terms of optimization steps through Theorem 5.2 and Corollary 5.4 . This result follows from bounding the error of the gradient estimation through an appropriate choice of the multilevel batch size (see Lemma 5.1 ). The method achieves this convergence rate (like an SAA approach) with a complexity similar to the standard MLMC method, as it circumvents full gradient evaluations (as done for SA) at the highest level. As a result, MLSGD improves convergence rates, speed, and accuracy by adapting the multilevel batch size. Adaptivity, budgeting and error control by resources In extension to the new MLSGD method presented in Section 5 , we incorporate the adaptive step size rule from [ 31 ] , adaptive multilevel batches similar to [ 22 ] , the optimal distribution of the computational load as in [ 14 ] , and a posteriori error control with dynamic programming [ 13 ] into Algorithm 3 . Furthermore, we impose the given computational resources, such as the total available memory and the reserved CPU-time budget, as additional constraints to the optimization problem resulting in 6.1 . The

Read the complete text