PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Iteration Complexity of Hypergradient Computation

Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, Saverio Salzo

arXiv:2006.16218v2stat.MLcs.LG

TL;DR

The paper addresses how to approximate hypergradients efficiently when bilevel problems involve costly or impossible-to-compute fixed-point solutions. It develops a unified complexity analysis for iterative and approximate implicit differentiation under contraction, finding that conjugate-gradient AID performs best in the supported comparisons.

  • Problem

    Hypergradients can be hard or impossible to compute exactly when an upper-level objective depends on an expensive parametric fixed-point solution.

  • Method

    The paper analyzes Iterative Differentiation and Approximate Implicit Differentiation under the assumption that the fixed-point mapping is a contraction.

  • Results

    The unified analysis provides linear iteration-complexity rates and suggests that conjugate-gradient AID offers the best computational efficiency among the studied methods.

  • Takeaways & Limitations

    AID with conjugate gradients is preferable in the contraction setting because it can provide better hypergradient approximation with lower space complexity.

  • Takeaways & Limitations

    When the contraction assumption is not satisfied, experiments on equilibrium models suggest that ITD is more reliable than AID methods.

Abstract

from arXiv · show

We study a general class of bilevel problems, consisting in the minimization of an upper-level objective which depends on the solution to a parametric fixed-point equation. Important instances arising in machine learning include hyperparameter optimization, meta-learning, and certain graph and recurrent neural networks. Typically the gradient of the upper-level objective (hypergradient) is hard or even impossible to compute exactly, which has raised the interest in approximation methods. We investigate some popular approaches to compute the hypergradient, based on reverse mode iterative differentiation and approximate implicit differentiation. Under the hypothesis that the fixed point equation is defined by a contraction mapping, we present a unified analysis which allows for the first time to quantitatively compare these methods, providing explicit bounds for their iteration complexity. This analysis suggests a hierarchy in terms of computational efficiency among the above methods, with approximate implicit differentiation based on conjugate gradient performing best. We present an extensive experimental comparison among the methods which confirm the theoretical findings.

1. Introduction

The paper studies bilevel problems whose upper-level objective depends on a parametric fixed-point solution, focusing on efficient hypergradient approximation. It unifies theoretical and experimental comparisons of iterative and implicit differentiation methods.

  • The bilevel framework: Bilevel formulations arise when a lower-level fixed-point solution enters an upper-level objective, including hyperparameter optimization, meta-learning, and equilibrium models.Applications include stable recurrent neural networks and graph neural networks.
  • Motivation: Large upper-level parameter spaces make black-box search impractical, motivating gradient-based methods and efficient hypergradient approximation when lower-level solutions are costly.
  • Methods: The paper compares Iterative Differentiation, which differentiates through fixed-point iterates, with Approximate Implicit Differentiation, which approximately solves an implicit hypergradient equation.AID includes fixed-point and conjugate-gradient approaches, while ITD can use forward- or reverse-mode automatic differentiation.
  • Contributions: The unified analysis provides non-asymptotic linear convergence rates and iteration-complexity results for ITD and AID when the fixed-point mapping is a contraction.The work extends complexity results for AID beyond meta-learning and addresses previously unavailable non-asymptotic ITD rates.
  • Contributions: The paper theoretically and numerically compares different ITD and AID strategies across several experimental scenarios.The methods have similar time costs under automatic differentiation, while reverse-mode ITD usually requires more memory than AID.

2. Theoretical Analysis

The analysis derives non-asymptotic linear hypergradient-approximation bounds for ITD and AID under contraction assumptions, then compares their iteration efficiency. AID-FP can outperform ITD, while AID-CG has the better asymptotic rate in strongly convex smooth settings.

  • Overview: The paper analyzes ITD and AID hypergradient approximation errors under contraction assumptions, with separate bounds for conjugate-gradient and fixed-point AID implementations.The analysis also treats the iteration complexity of both approaches.
  • Assumptions: Assumption B requires Φ(·, λ) to be a contraction with constant qλ ∈ (0, 1), ensuring a unique fixed point and invertibility of I − ∂1Φ.The inverse norm is bounded by 1/(1 − qλ).
  • Iterative Differentiation: ITD yields a non-asymptotic linear convergence rate for the gradient of the approximate objective ft toward the true hypergradient.The approximation is formed by differentiating through t fixed-point iterates using automatic differentiation.
  • Approximate Implicit Differentiation: AID converges linearly in both the lower-level iteration count t and the linear-system iteration count k when both solvers converge linearly.AID stores only the last lower-level iterate, unlike reverse-mode ITD, which stores the full optimization trajectory.
  • Method Comparison: When k = t, the AID-FP bound is lower than the ITD bound, suggesting faster convergence for AID-FP.The comparison uses qλ(1 − qtλ) < t for every t ≥ 1.
  • Method Comparison: AID-CG has a better asymptotic rate than AID-FP when the lower-level objective is Lipschitz smooth and strongly convex.The comparison applies to instances satisfying the stated strongly convex smooth setting.
  • Limitations: The analysis assumes initialization w0(λ) = 0; extending the bounds to warm starts depends on upper-level dynamics, leaving their theoretical benefit open.The paper notes that warm starts may be convenient in gradient-based bilevel optimization.

3. Experiments

The experiments evaluate hypergradient approximation methods on synthetic bilevel problems, benchmark tasks, and equilibrium models. Results broadly support the theoretical comparison, while showing that contractiveness and numerical precision affect observed behavior.

  • 3. Experiments: The experiments include high-dimensional hyperparameter optimization, multi-task or meta-learning objectives, and an equilibrium model on MNIST.The synthetic settings cover LR, KRR, BR, and HR; additional experiments use Parkinson, 20 newsgroup, Fashion MNIST, and EQM data.
  • 3.1. Hypergradient Approximation: Across four synthetic settings, hypergradient approximation error converges linearly after sufficient lower-level iterations.The experiments vary the number of lower-level iterations t and compare ITD, fixed-point AID, and conjugate-gradient AID.
  • 3.1. Hypergradient Approximation: CG gives the best average gradient estimate, followed by FP, while ITD performs worst.CG with k = 10 outperforms FP with k = 10 on 3 of 4 settings, although both remain far from convergence.
  • 3.1. Hypergradient Approximation: For KRR, BR, and HR, asymptotic error is considerably large and is suspected to reflect numerical error absent from the infinite-precision theory.Using double precision halves the asymptotic error, but the source was not investigated further.
  • 3.2. Bilevel Optimization: For Parkinson and Fashion MNIST, the methods show little difference at fixed t; on 20 newsgroup, CG with k = t reaches the lowest objective.Table 1 reports objective and test accuracy after task-specific numbers of gradient-descent steps.
  • 3.2. Bilevel Optimization: In EQM experiments, unconstrained runs make memory-less AID unstable across most learning rates, whereas enforcing ∥A∥ < 1 makes all methods successful and stable.With the spectral-norm constraint, FP is faster than CG on the normal equations and uses substantially less memory than ITD.

4. Conclusions

The paper studies iteration complexity for ITD and AID in bilevel problems whose fixed-point map is contractive. Its conclusions favor AID in the contractive setting but report greater ITD reliability when contractiveness fails.

  • 4. Conclusions: The paper establishes iteration-complexity results for ITD and AID under a contraction-mapping assumption.The analysis targets bilevel problems whose lower level is a parametric fixed-point equation.
  • 4. Conclusions: When the contraction assumption is not satisfied, equilibrium-model experiments suggest that ITD is more reliable than AID methods.The paper identifies locally contractive, nonsmooth, nonexpansive, and stochastic lower-level settings as directions for future analysis.

Appendix

The appendix contains proofs, a specialization of the bounds to one-step gradient descent, and additional experimental details and results.

  • Appendix: Appendix A presents proofs of the results stated in Section 2.
  • Appendix: Appendix B specializes the Section 2 bounds to lower-level solutions represented by a one-step gradient-descent fixed-point map.
  • Appendix: Appendix C gives details of the Section 3 experiments and additional results.

A. Proofs of the Results in Section 2

The appendix proves differentiability and non-asymptotic error bounds for ITD and AID hypergradient approximations under contraction and regularity assumptions. It also develops the fixed-point implementation of AID and supporting lemmas.

  • Differentiability: Theorem A.1 establishes differentiability of the fixed-point solution w(·) and upper-level objective f(·) under assumptions on the contraction map.
  • Strongly convex specialization: The appendix specializes the differentiability argument to strongly convex lower-level objectives represented by a gradient-descent map.The map is defined as Φ(w, λ) = w − α(λ)∇1ℓ(w, λ).
  • Supporting lemmas: Lemma 2.2 supplies uniqueness of the fixed point and invertibility of I − ∂1Φ(w, λ) under the contraction assumption.
  • ITD: The ITD proof bounds the difference between the approximate and exact hypergradients after t fixed-point iterations.The bound is stated in Theorem 2.1 and relies on differentiability of the iterated objective and contraction-based estimates.
  • AID: The AID proof derives a general approximation-error bound for estimates based on t lower-level and k inner iterations.Under Assumption B, the parameter μλ can be set to 1 − qλ to obtain the specialized bound.
  • AID-FP: Propositions A.1 and A.2 support the refined AID-FP iteration-complexity bound by analyzing the fixed-point iteration for the implicit derivative.Theorem 2.4 states the resulting AID-FP bound under the contraction and regularity assumptions.

B. Gradient Descent as a Contraction Map

For a strongly convex lower-level loss, gradient descent defines a contraction when its step size is below 2/Lℓ(λ), with an optimal condition-number-dependent choice. This contraction structure supports the paper’s derivative bounds and implementation choices for hypergradient approximation.

  • Contraction condition: If α(λ) ∈ (0, 2/Lℓ(λ)), the gradient-descent map Φ(·, λ) is a contraction with constant qλ.The contraction constant is qλ = max{1 − α(λ)µℓ(λ), α(λ)Lℓ(λ) − 1}.
  • Contraction condition: The optimal step size is α(λ) = 2/(Lℓ(λ) + µℓ(λ)).This choice yields a contraction factor expressed through the lower-level condition number κ(λ).
  • Conditioning: The lower-level condition number is κ(λ) = Lℓ(λ)/µℓ(λ).The analysis relates the contraction and derivative approximation behavior to this condition number.
  • Derivative analysis: The paper writes derivatives of the gradient-descent map explicitly to establish bounds used by the hypergradient analysis.The derivative expressions involve the map’s partial derivatives and their variation with respect to the state.
  • Implementation: At the fixed point, computing ∇α(λ) is unnecessary because the first term on the right-hand side of equation (35) vanishes.The implementation also replaces ∂2Φ(w, λ) with a simpler expression in both gradient approximations for the experiments in case (2).

C.1. Hypergradient Approximation

The synthetic experiments evaluate hypergradient approximation procedures across several problem settings, using sampled data and parameter values chosen to make lower-level convergence difficult. The authors report substantial asymptotic error in three settings and attribute it partly to numerical precision.

  • Experimental setup: Synthetic data are generated by sampling feature matrices from normal distributions and constructing labels for the different experimental settings.The experiments use problem-specific dimensions and label-generation procedures.
  • Experimental setup: The results in Figure 1 average over 20 sampled λ values drawn uniformly from problem-specific intervals.The intervals differ across LR, KRR, BR, and HR, and are selected so qλ is close to 1.
  • Results: The asymptotic error is considerably large for KRR, BR, and HR.The authors suspect hypergradient approximation error exceeds the numerical error in the closed-form exact hypergradient.
  • Results: Using double precision halves the asymptotic error in the observed experiments.The theoretical analysis assumes infinite-precision arithmetic and does not account for this numerical error source.

C.2. Bilevel Optimization

The bilevel experiments optimize upper-level parameters with gradients estimated by ITD or AID while computing lower-level iterates using a shared solver. Results are reported both at approximate and more accurately computed lower-level solutions.

  • Experimental setup: The supplementary experiments cover problems of type (2) and provide additional results for the bilevel optimization study.These experiments concern Parkinson, 20 Newsgroup, and Fashion MNIST settings.
  • Optimization procedure: Upper-level gradient descent uses ITD or AID estimates computed with fixed t and k throughout optimization.The estimated gradient is g(λ) = ∇ft(λ) for ITD and g(λ) = ˆ∇f(λ) for AID.
  • Optimization procedure: All methods compute wt(λ) using t steps of the same lower-level algorithm.Heavy-ball is used for Parkinson, while gradient descent with manually chosen step sizes is used for the other settings.
  • Optimization procedure: The step size ζ is selected by grid search over 30 logarithmically spaced values for each problem.The selected value minimizes the approximate objective at problem-specific iteration counts.
  • Reported metrics: Table 1 reports the approximate objective ft(λs) and test accuracy computed on wt(λs).Table 2 instead evaluates f(λs) and test accuracy using a more accurate or closed-form lower-level solution.
  • Caveat: The step size is constant with respect to λ, although the optimal step size would vary with λ.This is identified as an experimental limitation for the considered setup.

C.3. Equilibrium Models with Convolutions

Convolutional equilibrium-model experiments compare hypergradient methods under projected and unprojected dynamics, while visualizations show filter-map evolution toward fixed-point representations. Projection produces clearer differences in method behavior, and fixed-point optimization may fail without contractiveness.

  • Model and setup: The convolutional EQMs use state feature maps, convolutional kernels, max pooling, and a multiclass logistic classifier.The experiments set the number of feature maps to h = 10 and project the convolution operator into a unit spectral ball.
  • Results: The results show more marked differences among methods, especially without projection.The projected convolutional EQMs outperform the simpler dynamics, with the fixed-point method slightly better than the others.
  • Results: Without projection, fixed-point hypergradient optimization does not reliably converge for all tested step sizes.The observation supports the importance of the contractiveness assumption for AID methods.
  • Figure 3: Figure 3 summarizes five-seed means and point-wise minimum–maximum ranges for ITD and AID hypergradient estimates.All methods use t = k = 20, and upper-level optimization uses 1500 Nesterov iterations with projection except for † methods.
  • Figure 4: Figure 4 shows ten 14 × 14 filter maps evolving over 20 EQM iterations from zero initialization toward approximate fixed-point representations.Rows correspond to filters and the horizontal direction corresponds to EQM iterations.
Loading 2006.16218v2…