Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization
This work addresses optimization challenges in fields like PDEs and deep learning by providing efficient algorithms for bound-constrained problems with noisy gradients, though it is incremental as it builds on existing AdaGrad methods.
The authors tackled the problem of bound-constrained optimization with noisy gradients by presenting two noise-tolerant algorithms, a multi-level method and a domain-decomposition method, which generalize AdaGrad and achieve an $O(ε^{-2})$ iteration complexity to compute an $ε$-approximate critical point with high probability.
Two OFFO (Objective-Function Free Optimization) noise tolerant algorithms are presented that handle bound constraints, inexact gradients and use second-order information when available.The first is a multi-level method exploiting a hierarchical description of the problem and the second is a domain-decomposition method covering the standard addditive Schwarz decompositions. Both are generalizations of the first-order AdaGrad algorithm for unconstrained optimization. Because these algorithms share a common theoretical framework, a single convergence/complexity theory is provided which covers them both. Its main result is that, with high probability, both methods need at most $O(ε^{-2})$ iterations and noisy gradient evaluations to compute an $ε$-approximate first-order critical point of the bound-constrained problem. Extensive numerical experiments are discussed on applications ranging from PDE-based problems to deep neural network training, illustrating their remarkable computational efficiency.