PaperlayerView exact revision on arXiv

Source-linked AI summary

A First Order Method for Solving Convex Bi-Level Optimization Problems

Shoham Sabach, Shimrit Shtern

arXiv:1702.03999v1math.OC

TL;DR

The paper addresses convex bi-level problems with a smooth-plus-nonsmooth inner objective and a strongly convex outer objective constrained to inner minimizers. It adapts the Sequential Averaging Method into BiG-SAM and establishes a global sublinear O(1/k) rate in inner objective values, while also extending the setting to nonsmooth outer objectives through the Moreau envelope.

  • Problem

    The paper studies how to solve bi-level problems whose inner level has smooth and nonsmooth terms and whose outer level optimizes over the inner solution set.

  • Method

    BiG-SAM adapts an existing fixed-point algorithm, the Sequential Averaging Method, to convex bi-level optimization.

  • Results

    O(1/k) global convergence in inner objective values is established for BiG-SAM, including a setting with a strongly convex but nonsmooth outer objective via its Moreau envelope.

  • Takeaways & Limitations

    BiG-SAM offers a simpler outer-level computation than MNG and applies to outer objectives that are strongly convex without being smooth.

  • Takeaways & Limitations

    The framework assumes a unique MNP solution and, in its main smooth formulation, a continuously differentiable outer objective with Lipschitz-continuous gradient.

Abstract

from arXiv · show

In this paper we study convex bi-level optimization problems for which the inner level consists of minimization of the sum of smooth and nonsmooth functions. The outer level aims at minimizing a smooth and strongly convex function over the optimal solutions set of the inner problem. We analyze a first order method which is based on an existing fixed-point algorithm. Global sublinear rate of convergence of the method is established in terms of the inner objective function values.

1 Introduction

The paper studies convex bi-level optimization with a smooth-plus-nonsmooth inner problem and a strongly convex outer objective over the inner solution set. It proposes BiG-SAM, a first-order method with an O(1/k) global rate in inner objective values, simpler outer computations, and applicability to nonsmooth strongly convex outer functions.

  • The outer problem minimizes a strongly convex differentiable function over the nonempty optimal solution set of the inner problem.
  • The inner problem minimizes a continuously differentiable convex function plus an extended-valued, possibly nonsmooth function.
  • Existing convergence analyses establish convergence but leave the convergence rates of the considered algorithms unknown.
  • O(1/k) convergence in inner objective values is established for the Minimal Norm Gradient method, whose analysis covers a specific indicator-function case.
  • BiG-SAM achieves a non-asymptotic O(1/k) global rate in inner objective values while using only an outer-gradient computation instead of MNG's additional half-space minimization.The inner operation has the same complexity as MNG, while the outer operation is simpler.
  • BiG-SAM also handles strongly convex outer objectives that are not necessarily smooth, solving with respect to the Moreau envelope and including sparsity-term examples.

2 Optimization Framework and Mathematical Tools

The paper formulates the inner level as convex composite minimization and the outer level as a Minimal Norm Problem over its solution set. It develops proximal-gradient and fixed-point tools, reviews MNG's computational burden, and motivates the SAM-based approach.

  • 2.1 Convex Bi-Level Optimization: The inner problem minimizes ϕ(x)=f(x)+g(x), with convex smooth f, possibly nonsmooth extended-valued g, and a nonempty solution set.
  • 2.1 Convex Bi-Level Optimization: The proximal-gradient method is a fixed-point iteration whose fixed points coincide with the inner problem's optimal solutions.
  • 2.1 Convex Bi-Level Optimization: The outer Minimal Norm Problem minimizes ω over the optimal solution set X* of the inner problem.
  • 2.1 Convex Bi-Level Optimization: The Moreau envelope of a strongly convex ω remains strongly convex, with parameter σ/(1+sσ).
  • 2.1 Convex Bi-Level Optimization: For differentiable strongly convex ω with Lipschitz gradient, the mapping S_s=I−s∇ω is a contraction when s≤2/(L_ω+σ).
  • 2.2 The Minimal Norm Gradient Method: MNG requires computing the prox-gradient mapping, ∇ω, and a minimization over two half-spaces, with the third task potentially requiring nested optimization.Nested schemes can accumulate computational error and have unclear per-iteration stopping criteria.
  • 2.2 The Minimal Norm Gradient Method: MNG's rate is evaluated on a feasible sequence because its iterates need not belong to the constraint set X.
  • 2.2 The Minimal Norm Gradient Method: BiG-SAM is based on the Sequential Averaging Method, an existing algorithm for a class of fixed-point problems.

3 The Sequential Averaging Method

The Sequential Averaging Method (SAM) solves a fixed-point problem by averaging a contraction mapping with a nonexpansive mapping, with diminishing averaging parameters. Applied to convex bi-level optimization, it yields BiG-SAM, which converges to the outer solution among inner minimizers and has an O(1/k) inner-objective rate.

  • General framework: SAM seeks a fixed point of a nonexpansive mapping that also satisfies a variational inequality induced by a contraction mapping.The fixed point is selected as the point that is “better” than other fixed points according to the contraction-based criterion.
  • General framework: Under its parameter conditions, SAM produces bounded iterates and converges to a fixed point satisfying the associated variational inequality.These properties are recorded in the general SAM results and form the basis for the bi-level analysis.
  • General framework: With a suitable parameter choice, the gap between each iterate and its image under T converges at the non-asymptotic rate O(1/k).The paper presents this as the first rate-of-convergence result to a fixed point for the considered SAM framework.
  • BiG-SAM: For smooth outer objectives, BiG-SAM achieves an O(1/k) rate in inner objective values and improves on the rate previously reported for MNG.The result holds when f, g, and ω satisfy Assumptions A and B.
  • Nonsmooth outer objectives: BiG-SAM also applies when the outer objective is strongly convex but nonsmooth by replacing it with its Moreau envelope.The Moreau envelope is smooth and strongly convex, while the resulting method is equivalent to SAM with the proximal mapping of ω as the contraction.
  • BiG-SAM: For bi-level optimization, T is the prox-gradient mapping associated with the inner composite problem, while S is associated with the outer objective.T is nonexpansive with Fix(T) equal to the inner solution set X∗, and S is chosen as a contraction under the outer assumptions.
  • BiG-SAM: BiG-SAM generates a sequence converging to the solution of the minimum-norm-type outer problem over the inner optimal set.The result follows by interpreting SAM’s variational inequality with the mappings selected for the bi-level problem.

4 Rate of Convergence Analysis

The analysis establishes convergence rates for SAM and BiG-SAM under contraction and nonexpansiveness assumptions, yielding an O(1/k) inner-objective rate. It also extends BiG-SAM to nonsmooth strongly convex outer objectives through Moreau smoothing, with accuracy-dependent iteration costs.

  • General rate analysis: The main rate result applies to any contraction mapping S and establishes a superior convergence rate for BiG-SAM in terms of inner objective values.The analysis first derives a general fixed-point result for SAM, then specializes it to BiG-SAM.
  • General rate analysis: Under the stated SAM assumptions, the relevant sequence converges to a fixed point of T with the derived convergence rate.The framework assumes S is a contraction, T is nonexpansive, and Fix(T) is nonempty.
  • BiG-SAM rate: For BiG-SAM, the inner objective function values converge to an optimal solution of the inner problem at rate O(1/k).The result is stated for step-size t ≤ 1/Lf and the prescribed averaging sequence.
  • Nonsmooth outer objectives: When the outer objective is strongly convex but nonsmooth, BiG-SAM is applied to its Moreau envelope, whose gradient is Lipschitz continuous.The resulting outer step requires computing the proximal mapping of the original objective.
  • Nonsmooth outer objectives: With a nonsmooth outer objective, the method converges to the optimal solution with respect to the Moreau envelope rather than directly with respect to the original objective.The relevant solution minimizes the smoothed outer objective over the inner optimal solutions set.
  • Nonsmooth outer objectives: The smoothing accuracy parameter δ controls the gap to the desired outer value and affects the iteration complexity, which is O(1/εδ²).Choosing δ = √ε yields an O(1/ε²) rate in terms of inner objective values.

5 Numerical Experiments

The experiments compare MNG with three BiG-SAM variants on noisy linear inverse problems, evaluating runtime, feasibility, and optimality gaps. BiG-SAM generally reaches better feasibility and convergence outcomes, while MNG often incurs the highest runtime.

  • Experimental setup: The experiments reconstruct vectors from noisy linear inverse problems using a bi-level formulation with nonnegative inner solutions and a positive definite outer matrix Q.The Phillips, Baart, and Foxgood problems were tested with noise magnitudes ρ = 10^-1, 10^-2, and 10^-3 across 100 Monte Carlo realizations.
  • Experimental setup: BiG-SAM was tested with γ = 0.1, 0.5, and 1 on a Unix server using MATLAB R2016a without parallelization.The experiments used 32 Intel Xeon CPUs and 250GB RAM.
  • Runtime comparison: MNG usually required more iterations than BiG-SAM with γ = 0.1 but fewer than BiG-SAM with γ = 0.5, yet its mean runtime was highest in most cases.MNG often stopped because of the 500-second time limit rather than reaching the termination criterion.
  • Gap comparison: After 250 seconds, all BiG-SAM variants except γ = 1 on Foxgood with ρ = 0.001 achieved superior RFG values to MNG, by up to 2 orders of magnitude.In most cases, BiG-SAM also obtained slightly better ROG values, especially at higher noise magnitudes.
  • Convergence profiles: For a Phillips instance with ρ = 0.01 and n = 100, BiG-SAM variants converged faster than MNG after the first 10 seconds, with lower γ improving convergence speed.The same behavior appeared when measuring distance to the optimal solution x∗.

Appendix A Proof of Proposition 2

Appendix A supplies two proofs of Proposition 2 using convex-analysis and proximal-mapping arguments. The result establishes strong convexity of the Moreau envelope and contraction of the associated proximal mapping.

  • First proof: The first proof uses infimal convolution and conjugacy to relate the Moreau envelope to the conjugate of the original strongly convex function.The Moreau envelope is represented as the infimal convolution of ω with a squared-norm function.
  • Second proof: The second proof begins by establishing that the proximal mapping of a strongly convex function is a β-contraction.The contraction factor is β = 1/(1 + sσ).
  • Second proof: The proximal mapping is proven to be a 1/(1 + sσ)-contraction.The proof derives this using an auxiliary convex function and non-expansiveness of the proximal mapping.
  • First proof: The Moreau envelope Msω is strongly convex with parameter σ/(1 + sσ).This follows by transferring Lipschitz continuity of the conjugate gradient back to strong convexity.

Appendix B Proof of Proposition 3

Appendix B proves Proposition 3 by expanding the gradient-step distance, applying strong convexity, and selecting a step-size bound that makes the remaining term nonpositive.

  • Gradient-step estimate: The proof expands the squared distance between gradient steps as a quadratic expression involving gradients of ω.The expansion is given in equation (B.1).
  • Gradient-step estimate: Strong convexity of ω supplies the inequality needed to control the gradient inner product and norm terms.The estimate is combined with the expansion from (B.1).
  • Step-size condition: For any s ≤ 2/(σ + Lω), the second term is nonpositive, yielding the desired result.The step-size restriction is the key condition used to complete the proof.

Appendix C Proof of Lemma 3

Appendix C proves Lemma 3 by splitting the iteration indices into k ≤ J and k > J. The proof verifies the claimed bounds separately using the definitions of a_k and b_k.

  • Case k ≤ J: For k ≤ J, the proof uses b_k = 1 and the recursion a_k = (1 − γ)a_{k−1} for k = 2, 3, …, J.The initial inequalities establish the induction range for this case.
  • Case k > J: For k > J, the induction uses b_{k+1} = 2/(γ(k + 1)) together with b_k ≤ 2/(γk).The proof notes that k > J ≥ 2 to establish the required inequality.
Loading 1702.03999v1…