PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions

Xuxing Chen, Tesi Xiao, Krishnakumar Balasubramanian

arXiv:2306.12067v1math.OCcs.LGstat.ML

TL;DR

Stochastic bilevel optimization must optimize an outer function at the solution of a strongly convex inner problem, often without knowing that solution or having unbiased hypergradient estimates. This paper introduces MA-SOBA, which achieves optimal sample complexity under standard smoothness assumptions, and extends the approach to robust multi-objective bilevel optimization. The robust extension achieves a sample-complexity order that fills a gap in the dependence on ϵ.

  • Problem

    The inner solution is often unknown, complicating bilevel optimization, while SOBA's optimal-complexity analysis relies on higher-order smoothness.

    Source: §1 · pp. 1–2

  • Method

    MA-SOBA adds a sequence of average hypergradients to SOBA, and a slight modification extends the framework to robust multi-objective bilevel optimization.

    Source: §1 · p. 2

  • Results

    MA-SOBA achieves optimal O(ϵ^-2) sample complexity under standard smoothness, while MORMA-SOBA's O(n^5 μ^-4 λ ϵ^-2) complexity fills a gap in the order of ϵ-dependency.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The proposed framework handles stochastic bilevel optimization without higher-order smoothness and also covers a robust multi-objective bilevel formulation.

    Source: §1 · p. 2

    SOBA's existing analysis assumes a Lipschitz Hessian for f and a Lipschitz third derivative for g.

    Source: §1 · p. 2

Abstract

from arXiv · show

Stochastic Bilevel optimization usually involves minimizing an upper-level (UL) function that is dependent on the arg-min of a strongly-convex lower-level (LL) function. Several algorithms utilize Neumann series to approximate certain matrix inverses involved in estimating the implicit gradient of the UL function (hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) [16] instead uses stochastic gradient descent steps to solve the linear system associated with the explicit matrix inversion. This modification enables SOBA to match the lower bound of sample complexity for the single-level counterpart in non-convex settings. Unfortunately, the current analysis of SOBA relies on the assumption of higher-order smoothness for the UL and LL functions to achieve optimality. In this paper, we introduce a novel fully single-loop and Hessian-inversion-free algorithmic framework for stochastic bilevel optimization and present a tighter analysis under standard smoothness assumptions (first-order Lipschitzness of the UL function and second-order Lipschitzness of the LL function). Furthermore, we show that by a slight modification of our approach, our algorithm can handle a more general multi-objective robust bilevel optimization problem. For this case, we obtain the state-of-the-art oracle complexity results demonstrating the generality of both the proposed algorithmic and analytic frameworks. Numerical experiments demonstrate the performance gain of the proposed algorithms over existing ones.

1 Introduction

Stochastic bilevel optimization minimizes an outer objective evaluated at the solution of a strongly convex inner problem, but that solution is often unknown and stochastic oracles complicate hypergradient estimation. The paper introduces MA-SOBA for optimal sample complexity under standard smoothness and extends the framework to robust multi-objective bilevel optimization.

1 Introduction

  • The objective Φ(x) evaluates an upper-level function at the solution y*(x) of a strongly convex lower-level problem, a setup used in applications including meta-learning and hyperparameter optimization.The paper considers stochastic oracles, extending bilevel empirical risk minimization to online and streaming data.Source: §1 · p. 1
  • Because y*(x) is often unknown, stochastic oracles provide neither a direct unbiased estimator of the required inverse Hessian nor of the hypergradient.Existing Hessian-inverse approximations can add computational burden and a log(ϵ^-1) sample-complexity factor.Source: §1 · pp. 1–2
  • SOBA matches the single-level complexity lower bound, but its current analysis requires higher-order smoothness, beyond the standard first-order Lipschitzness of the value function.The paper asks whether an optimal O(ϵ^-2) sample complexity is possible without those assumptions.Source: §1 · p. 2
  • MA-SOBA adds a sequence of average hypergradients to SOBA and achieves optimal O(ϵ^-2) sample complexity under standard smoothness assumptions.The average hypergradients converge to ∇Φ(x), providing a termination criterion in the stochastic setting.Source: §1 · p. 2
  • MORMA-SOBA extends the approach to min-max multi-objective bilevel optimization and finds an ϵ-first-order stationary point of a strongly concave regularized formulation.Its stated sample complexity is O(n^5 μ^-4 λ ϵ^-2), filling a gap in the order of ϵ-dependency.Source: §1 · p. 2

L SGD SGD O(1)

The section surveys stochastic bilevel methods for strongly convex lower-level problems and contrasts their computational and theoretical trade-offs. It presents the paper's framework as an optimal-complexity alternative to SOBA's higher-order-smoothness analysis and identifies other extensions as future work.

L SGD SGD O(1)

  • Neumann-series methods approximate the inverse Hessian but add a log(ϵ^-1) sample-complexity factor, while explicit stochastic Hessian inversion raises computational and numerical-stability challenges.AmIGO avoids these inversion techniques and attains O(ϵ^-2), but uses a double loop and a batch size that grows inversely with ϵ.Source: L SGD SGD O(1) · p. 3
  • MA-SOBA differs slightly from SOBA while retaining optimal sample complexity without higher-order smoothness assumptions.The comparison in Table 1 concerns stochastic solvers in the nonconvex-strongly-convex setting under smoothness assumptions.Source: L SGD SGD O(1) · p. 4
  • Variance-reduction methods may reach O(ϵ^-1.5) under mean-squared smoothness and same-random-seed query assumptions, but are outside this paper's comparison scope.The paper focuses its comparison on smoothness assumptions for f and g.Source: L SGD SGD O(1) · p. 4
  • Applying other recent bilevel advances to this framework is left for future work.The section identifies constrained lower-level problems, non-strongly-convex lower levels, and second-order stationarity as directions for further work.Source: L SGD SGD O(1) · p. 4

2 Proposed Framework: the MA-SOBA Algorithm

MA-SOBA builds on SOBA's coupled updates for the outer variable, inner solution, and auxiliary linear-system variable, adding an averaged hypergradient sequence. The sequence guides outer updates, while the one-step inner update leaves estimation bias that the framework must handle.

2 Proposed Framework: the MA-SOBA Algorithm

  • The inner update takes one gradient-descent step on g(x_k, ·), while the auxiliary z update performs gradient descent on a quadratic whose solution is z*(x_k).The outer update is an inexact hypergradient-descent step.Source: §2 · p. 4
  • Stochastic oracles supply unbiased estimators for the update directions without a Neumann approximation or explicit Hessian inversion.The update directions use stochastic oracles of the first and second derivatives of f and g.Source: §2 · p. 4
  • Because one-step updates need not make y_k equal y*(x_k), they introduce bias in the z and hypergradient updates.The biases decrease as y_k and z_k approach their corresponding solutions, but SOBA's analysis requires a Lipschitz Hessian for f and a Lipschitz third derivative for g.Source: §2 · p. 4
  • The moving-average sequence h_k aggregates past hypergradients and is used to update the outer variable x_k.For an unconstrained outer domain, the projected update reduces to a gradient-descent step.Source: §2 · p. 5

3 Theoretical Analysis

The analysis establishes convergence of MA-SOBA under standard smoothness and stochastic-oracle assumptions, without requiring the higher-order smoothness used in SOBA’s analysis. Its moving-average updates support both the convergence argument and a hypergradient-based stopping criterion.

3.1 Preliminaries and Assumptions

  • The analysis uses gradient mapping to characterize first-order stationarity, reducing to the ordinary gradient when X = R^d.The stated goal is an ϵ-stationary solution whose expected squared gradient-mapping norm is at most ϵ.Source: §3.1 · p. 5
  • The convergence theorem assumes strongly convex lower-level objectives and unbiased, bounded-variance stochastic oracles that are conditionally independent given the iteration history.The paper explicitly places these assumptions on the stochastic oracles and notes that some assumptions in SOBA [16] are stronger.Source: §3.1 · pp. 5–6

3.2 Convergence Results

  • MA-SOBA’s average hypergradients converge to the exact hypergradient, providing a reliable termination criterion even with estimation bias.The result also holds with an extra factor of log(K) in the convergence rate under decreasing step sizes.Source: §3.2 · p. 6

3.3 Proof Sketch of Theorem 1

  • The proof uses moving averages of x_k and h_k to control hypergradient-estimation bias without requiring the higher-order smoothness assumptions used in SOBA [16].The resulting bias analysis relies on the moving-average updates rather than Lipschitzness of ∇z*(x).Source: §3.3 · pp. 6–7

4 Min-Max Bilevel Optimization

The paper extends moving-average SOBA to robust multi-objective bilevel optimization by optimizing a regularized min-max formulation. MORMA-SOBA has a stated oracle complexity for finding a stationary point of that formulation, with complexity worsening as its regularization parameter approaches zero.

4 Min-Max Bilevel Optimization

  • The method targets a regularized min-max bilevel formulation that balances worst-case and average objective losses through λ.As µλ approaches zero, the regularized formulation approaches the nonconvex-concave problem; large µλ enforces uniform λ and average-loss minimization.Source: §4 · p. 7

4.1 Proposed Framework: the MORMA-SOBA Algorithm

  • MORMA-SOBA extends MA-SOBA with moving averages for the multi-objective setting, updating x with an average hypergradient and λ for the maximization.Its single-level counterpart is fundamentally similar to single-timescale averaged SGDA [54].Source: §4.1 · pp. 7–8
  • The authors report that MORBiT’s current proof cannot establish its claimed inner-iterate bound, leaving its subsequent convergence arguments incorrect in their current form.They attribute the issue to ambiguity and inconsistency regarding expectation and filtration.Source: §4.1 · p. 7

4.2 Convergence Results

  • MORMA-SOBA finds an ϵ-first-order stationary point of the regularized objective with sample complexity O(n^5 µλ^-4 ϵ^-2), which worsens as µλ approaches zero.The reported n and µλ dependence matches moving-average SGDA [54] for the single-level counterpart, while MORMA-SOBA also computes y*_i(x).Source: §4.2 · pp. 8–9

5 Experiments

The experiments compare MA-SOBA on hyperparameter optimization and data hyper-cleaning, and MORMA-SOBA on robust multi-task representation learning. The reported results favor the proposed methods across these tasks.

5 Experiments

  • The benchmark compares MA-SOBA with BSA, stocBiO, TTSA, and SOBA, excluding methods that use variance reduction.The experiments use Benchopt and the open-sourced bilevel benchmark.Source: §5 · p. 9
  • MA-SOBA achieves lower objective values after several iterations than all benchmark methods on IJCNN1 hyperparameter optimization.The authors attribute the improvement to convergence of the average hypergradients.Source: §5 · p. 10
  • MA-SOBA reaches lower test errors faster than benchmark methods on MNIST data hyper-cleaning.Training labels are corrupted with probability p, and sample weights are optimized using the validation set.Source: §5 · p. 10
  • MORMA-SOBA reduces both average and maximum loss faster than MORBiT in robust multi-task representation learning.The comparison uses shared representation learning across tasks.Source: §5 · p. 10

6 Conclusion

The conclusion presents MA-SOBA as a moving-average hypergradient method with optimal sample complexity under standard smoothness assumptions, and extends the framework to multi-objective bilevel optimization. The appendix reports additional IJCNN1 comparisons and experimental setup details.

6 Conclusion

  • MA-SOBA introduces a moving-average hypergradient step and achieves optimal sample complexity without the high-order smoothness assumptions used in prior analyses.The framework is also extended to generic min-max bilevel optimization in the multi-objective setting.Source: §6 · pp. 10–11

A.1 Experimental Details for MA-SOBA

  • The experimental comparisons use batch size 64, and inner-loop methods and Neumann or inversion subroutines use 10 steps per outer iteration.The oracle implementation may violate the independence assumption, and SRBA is excluded because no open-source implementation was available and its reported improvement over SABA was limited.Source: §A.1 · p. 15

A Experimental Details

  • The IJCNN1 task selects one regularization parameter per feature for logistic regression, using validation loss as the upper-level objective and regularized training loss as the lower-level objective.The dataset has 49,990 training samples, 91,701 validation samples, and 22 features.Source: §A.1.1 · p. 16

A.1.1 Hyperparameter Optimization on IJCNN1

  • MA-SOBA outperforms SOBA and achieves a slightly lower suboptimality gap than SABA on IJCNN1.The additional comparison includes variance-reduction methods; MRBO and AmIGO results were not reproducible due to conflicts in the current Benchopt developer version.Source: Figure 3 · p. 16, §A.1.1 · p. 16

A.1.2 Data Hyper-Cleaning on MNIST

The MNIST experiment evaluates data hyper-cleaning under label corruption, optimizing training-sample weights through a bilevel formulation. MA-SOBA performs comparably to SABA and is fastest to reach the best test accuracy at corruption probability p = 0.5.

A.1.2 Data Hyper-Cleaning on MNIST

  • Data hyper-cleaning trains a multinomial logistic regression model on the training set and uses validation data to assign each training sample a weight, aiming to drive weights for corrupted samples toward zero.Source: §A.1.2 · p. 17
  • MA-SOBA performs comparably to SABA and is fastest to reach the best test accuracy when p = 0.5.The experiment compares test error against runtime and oracle calls for corruption probabilities p ∈{0.5, 0.7, 0.9}.Source: Figure 4 · p. 17, §A.1.2 · p. 17

A.1.3 Moving Average vs. Variance Reduction

MA-SOBA uses a moving average of estimated hypergradients and is reported to perform comparably to SABA while achieving O(ϵ^-2) sample complexity under the paper’s smoothness assumptions. Moving averages also support online and streaming problems with a simple per-iteration update, unlike the storage and evaluation demands noted for variance-reduction methods.

A.1.3 Moving Average vs. Variance Reduction

  • SAGA stores previously evaluated gradients in a table, which can be memory-intensive for large sample sizes or dimensions.SARAH-type methods can improve sample dependence but require two gradient evaluations per iteration, at xk and xk−1.Source: §A.1.3 · p. 18
  • Moving-average methods handle expectation-form problems with online and streaming data using a simple update per iteration.The paper contrasts this with variance-reduction methods that typically rely on mean-squared smoothness, which is stronger than general smoothness of the objective.Source: §A.1.3 · p. 18
  • MA-SOBA achieves O(ϵ^-2) sample complexity under the stated smoothness assumptions, without requiring mean-squared smoothness.The paper reports empirical performance comparable to SABA, a variance-reduction approach using SAGA updates.Source: §A.1.3 · p. 18
  • Variance-reduction methods can add space costs, require double-loop implementations or double oracle computations, and offer less runtime benefit on expensive-oracle problems.The paper attributes SABA’s limited runtime improvement on one task to variables with dimensions 20,000 and 10 × 784.Source: §A.1.3 · pp. 18–19

A.2 Experimental Details for MORMA-SOBA

The MORMA-SOBA experiments compare the method with MORBiT on FashionMNIST binary-classification tasks, and report faster reductions in both maximum and average loss. The accompanying proof material states smoothness properties and lays out stochastic-oracle assumptions used in the analyses.

A.2 Experimental Details for MORMA-SOBA

  • The FashionMNIST setup uses 8 easy and 2 hard binary-classification tasks for representation learning, plus 7 unseen tasks for testing.A shared network maps 784-dimensional image inputs to a 100-dimensional representation, with a binary classifier learned for each task.Source: §A.2 · p. 19
  • MORBiT uses iterative automatic differentiation for hypergradients, while its reported implementation uses SGD with momentum and weight decay to optimize variables.MORMA-SOBA’s regularization parameter µλ is set to 0.01; the remaining parameters are described as constants.Source: §A.2 · pp. 19–20
  • MORMA-SOBA reduces both maximum and average loss faster than MORBiT on test sets of seen and unseen tasks.Figure 5 aggregates results over 10 runs per method; the evaluated methods use batch sizes 8 for inner steps and 128 for outer iterations.Source: Figure 5 · p. 20, §A.2 · p. 20

B Proofs

  • The proof material states that, under Assumption 1, Φ, y∗, and z∗ are differentiable and Lipschitz continuous with the stated respective constants.The stochastic-oracle setup assumes unbiased estimates with bounded variance, conditionally independent given the iterates through iteration k.Source: B Proofs · p. 21

B.1 Proof of Theorem 1

The proof of Theorem 1 combines bounds on hypergradient estimation, primal convergence, and dual convergence to control an optimality measure. Its analysis uses moving averages to avoid stronger smoothness requirements used in prior SOBA analysis.

B.1 Proof of Theorem 1

  • The proof separately bounds the variance of an intermediate estimate and compares this with the bounded-second-moment assumption used in [16].The authors characterize the variance bound explicitly rather than assuming the corresponding second moment is uniformly bounded.Source: §B.1 · pp. 23–24

B.1.1 Hypergradient Estimation Error

  • The hypergradient-error analysis uses moving averages to remove an additional smoothness assumption required in prior analysis.The paper also states that its refined analysis does not require the stronger assumptions needed to guarantee Assumption 3.7 in [16].Source: §B.1.1 · p. 24, §B.1 · p. 24

B.1.2 Primal Convergence

  • The primal-convergence analysis uses smoothness of Φ and the auxiliary function ηX to bound progress of the iterates.The section’s lemma statements are conditioned on Assumptions 1 and 2.Source: §B.1.2 · pp. 27–28

B.1.3 Dual Convergence

  • The dual-convergence analysis uses the moving-average update of hk to bound its convergence behavior.The proof invokes the variance bound for the intermediate estimate and Lipschitz continuity of ∇Φ.Source: §B.1.3 · pp. 28–29

B.1.4 Proof of Theorem 1

  • The proof establishes Theorem 1 by bounding the optimality measure using the primal and dual convergence results.The paper relates that measure to the gradient mapping and proves convergence bounds for primal and dual variables.Source: §B.1.4 · pp. 29–30

B.2 Proof of Theorem 2

The proof of Theorem 2 assembles smoothness, hypergradient-error, primal, and dual bounds for the multi-objective formulation. Its stated lemmas assume Assumptions 1 and 2 for all task functions and Assumption 3.

B.2 Proof of Theorem 2

  • The proof establishes Lipschitz continuity for the objective gradients and related functions used in the multi-objective analysis.The stated smoothness properties include gradients with respect to x and λ, and the gradient of the regularized objective with respect to λ.Source: §B.2 · pp. 31–32

B.2.1 Hypergradient Estimation Error

  • The hypergradient-error lemmas bound estimation errors for task-specific variables under the stated assumptions and stepsize conditions.The proof extends the single-objective error reasoning by applying the assumptions to each fi and gi.Source: §B.2.1 · pp. 34–35

B.2.2 Primal Convergence

  • The primal-convergence analysis bounds progress for the x and λ variables using the stated conditions on stepsizes.The section gives separate primal bounds for the regularized multi-objective formulation.Source: §B.2.2 · pp. 36–37

B.2.3 Dual Convergence

  • The dual-convergence analysis treats the moving-average variable hk and the simplex variable λk in its bounds.The proof notes that ∇1Φ(x, λ) equals ∇1Φµλ(x, λ) for all (x, λ).Source: §B.2.3 · p. 39

B.2.4 Proof of Theorem 2

  • Theorem 2 is concluded by combining the preceding bounds under the selected stepsize conditions.The proof derives its final estimate from the prior lemmas and records the stated Lipschitz constant used for ∇1Φµλ(x, ·).Source: §B.2.4 · pp. 40, 43

C Discussions on the Prior Work [29]

This discussion critiques the current analysis of MORBiT, citing ambiguity around expectations and filtrations and questioning whether its convergence results hold under the stationarity notion in [43].

C Discussions on the Prior Work [29]

  • The current analysis cannot establish its claimed convergence bound for the maximum tracking error, and its subsequent convergence arguments are incorrect in the paper’s current form.The discussion attributes this to ambiguity and inconsistency concerning expectation and filtration.Source: C Discussions on the Prior Work [29] · p. 43
  • The analysis writes max E[·] where E[max(·)] is needed, because the objectives are random given the filtration.The paper identifies this mismatch as making Lemma 14 in incorrect.Source: C Discussions on the Prior Work [29] · p. 43
  • Taking the maximum after expectation complicates the proof; applying Young’s inequality introduces O(β) terms that make further convergence analysis challenging.The inner-product term vanishes only when conditional expectation is taken with respect to F_k first.Source: C Discussions on the Prior Work [29] · p. 44
  • It is unclear whether the convergence results in (10a) and (10c) of hold under the stationarity notion in [43], based on the Moreau envelope after maximizing over λ.In [43], ε-stationarity is defined by ∇Φ_ℓ^{1/2}(x) ≤ ε.Source: C Discussions on the Prior Work [29] · p. 44
Loading 2306.12067v1…