Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization

arXiv2305.18730MaRDI QIDQ6438439

Author name not available (Why is that?)

Publication date: 30 May 2023

Abstract: In this paper, we consider non-convex multi-block bilevel optimization (MBBO) problems, which involve $mgg1$ lower level problems and have important applications in machine learning. Designing a stochastic gradient and controlling its variance is more intricate due to the hierarchical sampling of blocks and data and the unique challenge of estimating hyper-gradient. We aim to achieve three nice properties for our algorithm: (a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ blocks and sampling $B$ samples for each sampled block per-iteration; (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator. However, it is non-trivial to achieve all of these by observing that existing works only achieve one or two of these properties. To address the involved challenges for achieving (a, b, c), we propose two stochastic algorithms by using advanced blockwise variance-reduction techniques for tracking the Hessian matrices (for low-dimensional problems) or the Hessian-vector products (for high-dimensional problems), and prove an iteration complexity of $O(fracmepsilo{n}^{-3}mathbbI(I<m)IsqrtI+fracmepsilo{n}^{-3}IsqrtB)$ for finding an $epsilon$-stationary point under appropriate conditions. We also conduct experiments to verify the effectiveness of the proposed algorithms comparing with existing MBBO algorithms.

Has companion code repository: https://github.com/optimization-ai/icml2023_bsvrb

This page was built for publication: Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438439)