Research map / Learning theory and algorithms / Sample complexity
Lower Bounds of Uniform Stability in Gradient-Based Bilevel Algorithms for Hyperparameter Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes tight lower bounds on uniform (argument) stability for unrolling-differentiation (UD) and implicit-function-theorem (IFT) gradient-based hyperparameter optimization via lower-bounded expansion properties and a quadratic example.
Problem
Existing upper bounds on the uniform stability of gradient-based bilevel hyperparameter optimization (UD- and IFT-based) are known, but their tightness is unclear.
Approach
Introduce lower-bounded expansion properties (sigma-divergent and rho-growing update rules, mu-expansive losses) to derive stability lower bounds for SGD-based outer updates; combine with an inner-Lipschitz lower bound and a quadratic bilevel example to show the UD upper bound is matched.
Key results
- For UD-based HO with constant step size, the stability lower bound matches the existing upper bound up to constants, scaling as (1+c(1-1/m)gamma)^T/m with gamma ~ (1+eta*gamma_tr)^{2K}.
- With decreasing step sizes alpha_t = c/t, UD-based uniform argument stability is bounded between T^{ln(1+(1-1/m)c gamma')/m} and T^{(1-1/m)c gamma}/m, nearly tight.
- Lower bound on the Lipschitz constant of the inner output: L_theta_K >= sigma_tr/(eta mu_tr) [(1+eta mu_tr)^K - 1], matching the known upper bound order (1+eta gamma_tr)^K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Establish a lower bound for UD-based hyperparameter optimization | UD-based algorithm on the constructed quadratic HO example · Constructed quadratic HO example | uniform argument stability: T ln(1+(1−1/m)cγ′)/m ≲ ϵarg ≲ T (1−1/m)cγ/m | Mixed |
| Establish lower and upper bounds for a representative IFT-based algorithm | IFT-based algorithm on the constructed quadratic HO example · Constructed quadratic HO example | uniform argument stability: ≲T ln(1+(1−1/m)cγ′)/m; ≲T (1−1/m)cγ/m | Mixed |
Surprising findings
- Uniform stability appears to have reached its limit for characterizing UD-based HO generalization, since the lower bound matches the upper bound.
Limitations
- Restricted to smooth loss functions; nonsmooth cases remain open.
- Uniform stability lower bound does not directly imply a generalization lower bound.
- Analysis of the IFT-based algorithm yields only meaningful (non-matching) bounds.
Experimental setup
Metrics: uniform argument stability uniform stability hyperparameter output distance
Baselines: UD-based upper bound (Franceschi et al. / Bao et al.) IFT-based stability upper bound (Lei et al.)
Builds on: Hardt et al. stability of SGD Bao et al. stability upper bound for UD-based HO Lei and Ying stability analysis Zhang et al. SGD stability lower bound with smooth losses
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.88)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.87)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.87)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.87)
- Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · similarity 0.87)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.