Reproduce “Amortized Implicit Differentiation for Stochastic Bilevel Optimization” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Michael Arbel, Julien Mairal
AmIGO addresses bilevel optimization by warm-starting the inner model solution and the auxiliary vector used to estimate outer gradients across updates. Under strong convexity of the inner objective and smoothness and variance assumptions, it achieves O(κ_g^9 ε^-2) query complexity for stochastic nonconvex outer optimization, matching the oracle’s ε^-2 dependence. On 20 Newsgroups, AmIGO-CG is fastest and performs best, but test accuracy later declines after 80%.
Key insights
- Viewing bilevel optimization as a singularly perturbed system enables a unified theoretical analysis of algorithms that manage the distinct time-scales of the outer variable, inner solution, and linear system solution.
- Warm-starting the successive approximations of both the inner-level solution and the implicit differentiation linear system solution effectively amortizes computational costs over iterations.
- The warm-start strategy allows the number of inner iterations for both the inner problem and the linear system solver to be set as constants that depend on problem conditioning rather than the desired final precision.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.