PaperlayerView exact revision on arXiv

Source-linked AI summary

A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization

Feiyang Ye, Baijiong Lin, Xiaofeng Cao, Yu Zhang, Ivor Tsang

arXiv:2401.09257v2cs.LG

TL;DR

Existing gradient-based MOBLO methods require Hessian computations that can make them inefficient. FORUM reformulates MOBLO as constrained multi-objective optimization and solves it with first-order multi-gradient aggregation; it reports state-of-the-art performance on three multi-task learning benchmarks.

  • Problem

    Existing gradient-based MOBLO methods compute Hessian-based hypergradients, with time and memory costs that grow significantly with lower-level dimension and iteration count.

    Source: §1 · p. 1

  • Method

    FORUM reformulates MOBLO as a constrained multi-objective problem using a value-function approach and solves it with first-order multi-gradient aggregation.

    Source: §1 · p. 1

  • Results

    FORUM achieves state-of-the-art performance on three benchmark datasets under multi-task learning.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    The paper reports theoretical efficiency analysis and non-asymptotic convergence guarantees alongside empirical effectiveness across learning problems.

    Source: §6 · p. 7

    The analysis focuses on MOBLO with a singleton lower-level solution set and a non-convex upper-level subproblem.

    Source: §1 · p. 1

Abstract

from arXiv · show

In this paper, we study the Multi-Objective Bi-Level Optimization (MOBLO) problem, where the upper-level subproblem is a multi-objective optimization problem and the lower-level subproblem is for scalar optimization. Existing gradient-based MOBLO algorithms need to compute the Hessian matrix, causing the computational inefficient problem. To address this, we propose an efficient first-order multi-gradient method for MOBLO, called FORUM. Specifically, we reformulate MOBLO problems as a constrained multi-objective optimization (MOO) problem via the value-function approach. Then we propose a novel multi-gradient aggregation method to solve the challenging constrained MOO problem. Theoretically, we provide the complexity analysis to show the efficiency of the proposed method and a non-asymptotic convergence result. Empirically, extensive experiments demonstrate the effectiveness and efficiency of the proposed FORUM method in different learning problems. In particular, it achieves state-of-the-art performance on three multi-task learning benchmark datasets. The code is available at https://github.com/Baijiong-Lin/FORUM.

1 Introduction

MOBLO combines multiple upper-level objectives with a scalar lower-level optimization problem. FORUM addresses the inefficiency of existing gradient-based methods with a first-order approach, and the paper reports theoretical guarantees and strong benchmark performance.

1 Introduction

  • MOBLO has a vector-valued upper-level objective and a scalar lower-level problem whose optimal solution set constrains the lower-level variable.The paper focuses on a singleton lower-level solution set and a non-convex upper-level subproblem.Source: §1 · p. 1
  • Existing gradient-based MOBLO methods use Hessian-vector products and can incur sharply increasing time and memory costs, particularly in deep neural networks.MOML and MoCo compute hypergradients through iterative differentiation.Source: §1 · p. 1
  • FORUM reformulates MOBLO as constrained multi-objective optimization and uses multi-gradient aggregation, without computing high-order Hessians.The paper also provides complexity analysis and a non-asymptotic convergence analysis.Source: §1 · pp. 1–2
  • FORUM achieves state-of-the-art performance on three multi-task learning benchmark datasets.The paper evaluates the method on multi-objective data hyper-cleaning and multi-task learning.Source: §1 · p. 2

2 Related Works

Related work situates FORUM among gradient-based multi-objective optimization and bi-level methods. Existing MOBLO approaches use iterative differentiation, while other formulations and objectives differ from the problem considered here.

2 Related Works

  • Gradient-based multi-objective optimization seeks Pareto-optimal solutions; MGDA uses quadratic programming to choose updates that decrease all objectives simultaneously.The passage contrasts this with linear scalarization, which combines objectives into one.Source: §2 · p. 2
  • Iterative-differentiation bi-level methods approximate hypergradients along the lower-level optimization trajectory, while value-function methods reformulate the problem into a simpler structure.The paper describes value-function reformulation as naturally yielding a first-order algorithm.Source: §2 · p. 2
  • MOML and MoCo require Hessian-based hypergradient calculations; mini-batch MOBLO and MORBiT address different objectives or formulations.The mini-batch approach targets many upper-level objectives, while MORBiT formulates its upper-level subproblem as min-max.Source: §2 · p. 2

3 The FORUM Algorithm

FORUM first recasts MOBLO as constrained multi-objective optimization using a lower-level value function, then aggregates gradients to update the variables while addressing the constraint. The method uses an approximate lower-level solution and a stabilized weight sequence.

3.1 Reformulation of MOBLO

  • The value-function approach reformulates MOBLO as an equivalent constrained multi-objective problem, but its constraint is ill-posed and the exact lower-level solution can be intractable.The method approximates the lower-level solution with T gradient-descent steps and uses this to approximate the constraint and its gradient.Source: §3.1 · p. 2

3.2 Multi-Gradient Aggregation Method

  • The aggregation direction seeks to decrease every potentially conflicting upper-level objective while also decreasing the approximated constraint function.A dynamic threshold based on the constraint gradient is used to enforce its decrease during optimization.Source: §3.2 · p. 3
  • FORUM obtains objective weights through a quadratic program and smooths them with a momentum update before computing the direction and updating the variables.The quadratic program's matrix dimension depends on the number of objectives, not the dimension of z; the momentum update is used to generate a stable weight sequence.Source: §3.2 · p. 3

4 Analysis

The analysis evaluates FORUM’s time and space costs and establishes a non-asymptotic convergence result.

4.1 Complexity Analysis

  • Each FORUM upper-level iteration costs O(mn + p(m + T)) time and O(mn + mp) space.The analysis notes that the quadratic-program cost can be negligible when m ≪ n + p.Source: §4.1 · p. 3
  • The analysis concludes that FORUM is more efficient than MOML and MoCo in both time and space complexity.MOML and MoCo each require O(mp(n+p)T) time per upper-level iteration; their stated space costs are O(mn + mpT) and O(2mn + mpT), respectively.Source: §4.1 · p. 4

4.2 Convergence Analysis

  • The convergence guarantee assumes Lipschitz upper-level gradients, a strongly convex and smooth lower-level objective, and bounded initial feasibility.The theorem’s stated schedule requires η ≤ 1/Lf, µ = O(K^-1/2), β = O(K^-3/4), and T ≥ C.Source: §4.2 · p. 4
  • FORUM achieves a O(K^-1/4 + Γ(T)) convergence rate, depending on the numbers of upper- and lower-level steps K and T.Γ(T) decays exponentially with T.Source: §4.2 · p. 4

5 Experiments

Experiments assess FORUM’s effectiveness and efficiency in multi-objective data hyper-cleaning and multi-task learning, including comparisons with existing methods across benchmark datasets.

5.1 Data Hyper-Cleaning

  • Data hyper-cleaning assigns weights to training examples to reduce noisy-label influence, while multi-task learning uses loss weights to balance tasks.Both problems are formulated as bi-level optimization tasks.Source: §5.1 · p. 4, §5.2 · p. 5
  • On MNIST and FashionMNIST, FORUM outperforms MOML and MoCo on test-set classification accuracy and F1 score.Table 2 reports means and standard deviations over three random seeds.Source: §5.1 · p. 5, Table 2 · p. 5
  • FORUM uses less time per iteration across tested configurations; its memory stays nearly constant as T changes and grows only slightly with p.MOML and MoCo use more time, with memory increasing faster with T and linearly with p; Figure 1 results match the complexity analysis.Source: §5.1 · p. 5, Figure 1 · p. 5
  • FORUM is insensitive to η and performs better with positive ρ than with ρ = 0; large ρ values include 0.5, 0.7, and 0.9.Figure 2 reports average accuracy on MNIST and FashionMNIST.Source: §5.1 · p. 5, Figure 2 · p. 5

5 Experiments

  • The experiments cover noisy-label MNIST and FashionMNIST, plus Office-31 classification, NYUv2 scene understanding, and QM9 molecular-property prediction.For data hyper-cleaning, half the training samples in each image dataset are assigned another random class.Source: §5.1 · p. 4, §5.2 · pp. 5–6

5.2 Multi-Task Learning

  • Across Office-31, NYUv2, and QM9, FORUM leads baselines on ∆p; it also leads Office-31 average accuracy and alone beats STL on NYUv2 ∆p.The authors describe these results as state of the art; Table 3 reports Office-31 accuracy, Table 4 NYUv2 results, and Table 5 QM9 MAE.Source: Table 3 · p. 6, §5.2 · p. 6, Table 4 · p. 7

6 Conclusion

The conclusion presents FORUM as a fully first-order method for multi-objective bi-level optimization, with theoretical guarantees and strong benchmark results.

6 Conclusion

  • FORUM reformulates MOBLO as constrained multi-objective optimization and uses multi-gradient aggregation without hypergradient computation.The paper characterizes the method as fully first-order.Source: §6 · p. 7
  • The analysis provides a complexity result and a non-asymptotic convergence guarantee for a non-convex multi-objective upper-level subproblem.Source: §6 · p. 7
  • Experiments on learning problems show effectiveness and efficiency; FORUM achieves state-of-the-art performance on three multi-task learning benchmark datasets.Source: §6 · p. 7

A.1 Gradient Approximation Error Bound

The appendix bounds the error from approximating the constraint gradient, derives a quadratic formulation for the dual subproblem, and explains why convergence requires convergent gradient weights.

A.1 Gradient Approximation Error Bound

  • The constraint-gradient approximation error decays exponentially with the number of lower-level iterations T.The bound is stated under Assumption 2 and a step-size condition.Source: §A.1 · p. 9

A.2 Dual Problem of Problem (8)

  • The dual subproblem becomes differentiable quadratic optimization, with a closed-form ν for fixed λ and a quadratic program for λ.The derivation differentiates with respect to d, substitutes the resulting expression, and reduces the remaining optimization to λ.Source: §A.2 · p. 9

A.3 Discussion on the Weights Sequence

  • Gradient aggregation for non-convex MOO requires a convergent weight sequence to guarantee convergence to a stationary point.The discussion notes that when consecutive weights do not converge, the relevant bound cannot converge to zero for either constant or decreasing step sizes.Source: §A.3 · p. 10

B Convergence Analysis

The appendix states constrained-MOO KKT conditions and explains why convergence is assessed using stationarity and feasibility rather than complementary slackness or unconstrained Pareto stationarity.

B.1 KKT Conditions

  • Constrained-MOO KKT conditions combine weighted objective gradients and the constraint gradient with feasibility and complementary slackness.The conditions require λ in the simplex, ν nonnegative, q(z*) ≤ 0, and νq(z*) = 0.Source: §B.1 · p. 10
  • Because the constraint q(z) is ill-posed, complementary slackness cannot be satisfied, so convergence is measured by stationarity and feasibility.The paper describes this target as weak stationarity.Source: §B.1 · p. 10
  • Unconstrained Pareto stationarity is not a convergence criterion for the reformulated constrained MOO problem.The stated criterion is the constrained problem's local optimality condition: KKT stationarity and feasibility.Source: §B.1 · p. 10

B.2 Lemmas

The lemmas bound lower-level approximation errors and constraint behavior, while the convergence analysis assumes bounded constraint values along the generated sequence.

B.2 Lemmas

  • Under the stated step-size condition, the lower-level constraint value decays exponentially with its iteration count T.The lemma also bounds the constraint-gradient approximation error by the distance between the approximate and optimal lower-level solutions.Source: §B.2 · p. 10
  • If q(z_k) is bounded and T is sufficiently large, the constraint value is bounded by an exponentially decaying term plus O(Γ(T) + μ).The lemma also states that the approximate and true constraint gradients satisfy a constant-factor norm bound.Source: §B.2 · p. 11
  • The analysis assumes q(z_k) remains bounded along the generated sequence, yielding a local convergence claim for a finite sequence.The authors contrast this with earlier assumptions they describe as self-contradictory.Source: §B.2 · p. 11

B.3 Proof of the Theorem 1

The proof relates the stationarity and feasibility measures to gradient approximation and algorithm parameters, then specifies step-size choices for its conclusion.

B.3 Proof of the Theorem 1

  • The stationarity measure K(z_k) is bounded by the update norm and the multiplier-weighted discrepancy between approximate and true constraint gradients.That discrepancy is O(Γ(T)) in the proof.Source: §B.3 · pp. 12–13
  • In the proof, using Lemma 3(a), the constraint value at zk satisfies q(zk) = O(Γ1(k) + Γ(T) + µ), with no further interpretation of the Γ terms supplied in the cited passage.Source: §B.3 · p. 13
  • The proof sets μ = O(K^-1/2) and β = O(K^-3/4) to reach its stated conclusion.The supplied proof passage does not state the conclusion's full bound.Source: §B.3 · p. 13

C Synthetic MOBLO

A synthetic MOBLO problem illustrates FORUM’s convergence under the assumptions required by the analysis. Across the tested initializations, FORUM approaches the optimal solution set and the constrained-problem measures converge to zero.

C Synthetic MOBLO

  • The problem’s optimal solution set is P = {(α, ω) | α = ω1 = ω2 = c, c ∈ [1, 2]}.Here ω = (ω1, ω2), and the problem satisfies the assumptions required in Section 4.2.Source: C Synthetic MOBLO · p. 13
  • The comparison uses GD for both upper- and lower-level subproblems, 50 lower-level iterations, and FORUM settings ρ = 0.3 and βk = (k + 1)^−3/4.All methods use step sizes μ = 0.3 and η = 0.05; E is the Euclidean distance to P.Source: C Synthetic MOBLO · p. 13
  • FORUM reaches an optimal solution across all tested initializations, with distance E approaching zero and initialization only slightly affecting convergence speed.The evaluation measures E as the Euclidean distance from solution z to the optimal solution set P.Source: C Synthetic MOBLO · p. 13
  • Both K(z) and q(z) converge to zero across all tested settings, indicating that FORUM solves the corresponding constrained optimization problem.The authors present this result as demonstrating the convergence result in Section 4.2.Source: C Synthetic MOBLO · p. 13

D Comparison with Non-Gradient-Based Methods

On multi-objective data hyper-cleaning, FORUM is reported as more effective than Bayesian and NSGA-II methods. The comparison reports means and standard deviations over three random seeds.

D Comparison with Non-Gradient-Based Methods

  • FORUM is reported as more effective than the Bayesian and NSGA-II methods on multi-objective data hyper-cleaning.The passage provides no specific metric values for this comparison.Source: D Comparison with Non-Gradient-Based… · p. 13
  • The comparison evaluates Bayesian and NSGA-II approaches by learning a model with SGD for a given α, computing upper-level objectives, and updating α with the non-gradient method.The methods are implemented using Hyperopt and Optuna, respectively.Source: D Comparison with Non-Gradient-Based… · p. 13
  • Each experiment is repeated over three random seeds, with the mean and standard deviation reported in Table 6.The best result is marked in bold.Source: Table 6 · p. 14

Related papers

Loading 2401.09257v2…