PaperlayerView exact revision on arXiv

Source-linked AI summary

Bi-ZOL: Bilevel Zeroth-Order Learning with Nonsmooth Responses

Zhisen Jiang, Saverio Bolognani

arXiv:2609.08021v1math.OCcs.SYeess.SY

TL;DR

Lower-level-constrained bilevel optimization in response-oracle settings combines unavailable lower-level model information with potentially nonsmooth response mappings, so classical response Jacobians may not exist. Bi-ZOL preserves the bilevel chain-rule structure while estimating response sensitivity, and its experiments report smaller stationarity gaps and lower hyperobjective values than vanilla zeroth-order smoothing on incentive-based tracking problems.

  • Problem

    In response-oracle settings, lower-level model information is unavailable and constraints can make the response nonsmooth, so the response Jacobian required by classical hypergradient methods may not exist or be computable from oracle queries.

    Source: §I · p. 1

  • Method

    Bi-ZOL keeps upper-level partial derivatives at the true response and uses zeroth-order smoothing only to estimate the unavailable response sensitivity.

    Source: §I · p. 2, A. Approximate Hypergradient of… · p. 4

  • Results

    On incentive-based tracking problems, Bi-ZOL achieves smaller stationarity gaps and lower hyperobjective values than vanilla zeroth-order smoothing.

    Source: §VI · p. 13

  • Takeaways & Limitations

    Piecewise affine response mappings are the zero-bias special case in the stationarity-transfer analysis.

    Source: D. Bi-ZOL Stationarity Certificates · p. 7

    Transfer to Clarke Frank–Wolfe stationarity requires certain local generalized-Jacobian conditions and is not claimed for arbitrary nonsmooth response maps.

    Source: D. Bi-ZOL Stationarity Certificates · p. 7

Abstract

from arXiv · show

This paper studies lower-level-constrained bilevel optimization in a response-oracle setting, where lower-level model information is unavailable and the induced response mapping is locally Lipschitz but potentially nonsmooth. In this setting, the classical response Jacobian and reduced hypergradient may fail to exist. We propose Bilevel Zeroth-Order Learning (Bi-ZOL), a structure-guided zeroth-order method for finding stationary points of the nonsmooth reduced problem. Instead of estimating the gradient of a fully smoothed reduced hyperobjective, Bi-ZOL separates the bilevel chain-rule structure: it keeps the exact upper-level partial gradients at the queried response and uses zeroth-order sampling only to estimate the response Jacobian. This construction yields an approximate hypergradient that is more directly aligned with the Clarke chain-rule subdifferential. We show that the Bi-ZOL direction admits a partial-smoothing interpretation, quantify its pointwise structural bias, and prove finite-time convergence to a $(\delta,\epsilon)$-Bi-ZOL Frank--Wolfe stationary point. The bias is $O(\delta)$ for piecewise $C^{1,1}$ responses under local regularity and vanishes for piecewise affine responses on active-cell neighborhoods. Experiments on incentive-based tracking problems show that Bi-ZOL achieves smaller stationarity gaps and lower hyperobjective values than vanilla zeroth-order smoothing under comparable response-oracle budgets.

I. INTRODUCTION

Lower-level-constrained bilevel problems are difficult in response-oracle settings because model derivatives may be unavailable and constraints can make the response nonsmooth. Bi-ZOL uses the bilevel chain-rule structure to estimate response sensitivity, then analyzes its stationarity certificate and the regularity assumptions needed to relate it to the original problem.

I. INTRODUCTION

  • Response-oracle methods lack lower-level derivatives needed by classical hypergradient approaches, while inequality constraints can make the response locally Lipschitz but nondifferentiable.Active-set changes can cause this nonsmoothness even when the objective functions are smooth.Source: §I · p. 1
  • Prior approaches smooth or reformulate the lower-level problem, use learned generalized sensitivities, or smooth the full reduced hyperobjective, each with distinct limitations.Full smoothing can neglect available upper-level derivatives and introduce avoidable bias in the stationary structure.Source: §I · pp. 1–2
  • Bi-ZOL keeps upper-level partial derivatives at the true response and applies zeroth-order smoothing only to the unavailable response sensitivity.This structure-guided approximate hypergradient is tied to the nonsmooth bilevel Clarke chain rule rather than the gradient of a fully smoothed objective.Source: §I · p. 2
  • Bi-ZOL defines a Frank–Wolfe stationarity certificate and proves finite-time convergence to it, with structural bias O(δ) for locally regular piecewise C1,1 responses and zero bias for piecewise affine responses.The certificate transfers to Clarke Frank–Wolfe stationarity under the corresponding conditions.Source: §I · p. 2

A. Notation and Preliminaries

  • Preliminaries define local Lipschitz continuity and use Clarke subdifferentials and generalized Jacobians to describe nonsmooth first-order geometry.The notation section also specifies unit-ball and Big-O conventions.Source: Nonsmooth analysis · p. 2, Notation · p. 2

II. PROBLEM FORMULATION

  • The formulation assumes a nonempty compact convex upper-level feasible set and a single-valued, locally Lipschitz lower-level response on a neighborhood of that set.The upper-level objective is continuously differentiable with bounded regularity constants.Source: §II · p. 3

III. NONSMOOTH BILEVEL FIRST-ORDER GEOMETRY

The section replaces the classical hypergradient, which may be undefined for nonsmooth responses, with a chain-rule-based approximate direction. Bi-ZOL preserves exact upper-level partial derivatives and smooths only the unavailable response sensitivity.

A. Approximate Hypergradient of Lower-level Constrained Bilevel Problem via Randomized Smoothing

  • At nonsmooth points, the reduced hyperobjective’s first-order object is a Clarke subdifferential containing limiting chain-rule directions, rather than a single classical hypergradient.When the response is continuously differentiable, this set reduces to the classical hypergradient.Source: A. Approximate Hypergradient of… · p. 3
  • Bi-ZOL replaces the undefined response Jacobian with the Jacobian of a smoothed response while evaluating both upper-level partial derivatives at the true response.The response smoothing is defined by averaging response values over a query neighborhood.Source: A. Approximate Hypergradient of… · p. 4
  • Unlike full smoothing, Bi-ZOL does not average the upper-level partial derivatives across the neighborhood, avoiding distortion of the known upper-level landscape and unnecessary variance.Full smoothing applies finite differences to the entire hyperobjective.Source: A. Approximate Hypergradient of… · p. 4

B. Anchored Chain-Rule Model

  • The Bi-ZOL direction is the gradient of a partially smoothed anchored model and belongs to that model’s Goldstein subdifferential; the unsmoothed anchored model preserves the hyperobjective’s Clarke first-order geometry at the anchor.The anchored model freezes upper-level partial derivatives while retaining the response map.Source: B. Anchored Chain-Rule Model · p. 4, Figure 1 · p. 4

C. Structural Bias of a Bi-ZOL Direction

The pointwise structural bias of a Bi-ZOL direction is controlled by how the response’s Clarke generalized-Jacobian set varies near the anchor. Under structured response conditions, this bias is O(δ) or exactly zero.

C. Structural Bias of a Bi-ZOL Direction

  • The structural bias is governed by local movement of the response’s Clarke generalized-Jacobian set, not merely by the size of its elements.The paper defines a local set-variation modulus to measure this movement.Source: C. Structural Bias of a Bi-ZOL Direction · p. 5
  • When local generalized-Jacobian variation is linearly controlled, the Bi-ZOL direction has O(δ) pointwise structural bias.For piecewise C1,1 responses, the paper gives a bound under δ-regularity.Source: C. Structural Bias of a Bi-ZOL Direction · p. 5
  • For piecewise affine responses, the approximate hypergradient belongs exactly to the Clarke chain-rule subdifferential when the smoothing neighborhood intersects only active cells.If the anchor is inside one affine cell, the same zero-bias result holds while the neighborhood remains within that cell.Source: C. Structural Bias of a Bi-ZOL Direction · p. 6
  • Piecewise affine response maps include solution maps of strongly convex multi-parametric quadratic programs with affine constraints, as used in explicit model predictive control.The paper also notes similar structures in power-system constrained quadratic-program applications.Source: C. Structural Bias of a Bi-ZOL Direction · p. 6

D. Bi-ZOL Stationarity Certificates

The section defines Bi-ZOL stationarity using a Frank–Wolfe gap and relates that certificate to stationarity of the original nonsmooth reduced problem. The transfer requires local conditions controlling structural bias.

D. Bi-ZOL Stationarity Certificates

  • A small Bi-ZOL Frank–Wolfe gap transfers to an ε-Clarke Frank–Wolfe certificate only when the structural-bias condition is satisfied.The transfer is pointwise and does not establish finite-time Clarke stationarity for arbitrary nonsmooth responses.Source: D. Bi-ZOL Stationarity Certificates · p. 7
  • For δ-regular points of finite piecewise C1,1 responses, local conditions can support stationarity transfer; piecewise affine responses are the zero-bias special case.When the structural-bias term vanishes, no extra upper bound on δ is needed.Source: D. Bi-ZOL Stationarity Certificates · p. 7
  • With a smooth response and Lipschitz response Jacobian, Bi-ZOL stationarity reduces to standard smooth Frank–Wolfe stationarity under the stated accuracy condition.The section uses Frank–Wolfe gaps because the upper-level feasible set is constrained.Source: D. Bi-ZOL Stationarity Certificates · pp. 6–8

IV. SOLUTION METHODS

The solution-method section turns the approximate hypergradient into a response-query algorithm and uses a Frank–Wolfe scheme to control its approximate stationarity measure.

IV. SOLUTION METHODS

  • The method preserves current upper-level first-order information and surrogates only the response sensitivity.This is the approximate hypergradient defined in the preceding section.Source: §IV · p. 8
  • Bi-ZOL estimates its approximate hypergradient using zeroth-order response queries.The queries estimate the response sensitivity without requiring lower-level model access.Source: §IV · p. 8
  • The resulting Frank–Wolfe scheme controls the approximate stationarity measure Gδ(x).The measure is the Bi-ZOL Frank–Wolfe gap defined in the prior section.Source: §IV · p. 8

A. Zeroth-order approximation of the smoothed response Jacobian

Bi-ZOL estimates response sensitivity with two-point response queries while retaining upper-level derivatives at the observed response. Its analysis bounds the resulting bias and establishes finite-time convergence and response-oracle complexity under the stated assumptions.

A. Zeroth-order approximation of the smoothed response Jacobian

  • The two-point estimator randomizes only response sensitivity and is unbiased for the Bi-ZOL approximate hypergradient, with a variance bound used in convergence analysis.The single-sample case is B = 1.Source: A. Zeroth-order approximation of the… · p. 8

B. Bi-ZOL algorithm

  • Bi-ZOL alternates response observation, response-sensitivity estimation, and a Frank–Wolfe update; its moving anchored linearization ties the direction to the current response pair.Perturbed response queries estimate sensitivity rather than creating new upper-level iterates.Source: B. Bi-ZOL algorithm · p. 8

C. Convergence analysis and oracle complexity

  • The smooth ancillary function is an analysis device, not the optimized objective; evaluating upper-level partial derivatives at y(x) rather than yδ(x) creates the bias bounded by κbiasδ.The bias contributes at most κbiasδ to the Frank–Wolfe gap bound.Source: C. Convergence analysis and oracle… · p. 9
  • The convergence result bounds the expected Bi-ZOL Frank–Wolfe gap by O(ϵ) under the stated parameter choices, for both a uniformly sampled iterate and the expected minimum gap.The bound concerns the Bi-ZOL certificate; the Clarke-type certificate adds a structural smoothing term.Source: C. Convergence analysis and oracle… · p. 9
  • Each iteration uses 2B perturbed response queries and one current-point response query, and the smoothing-induced term leads the oracle complexity for small ϵ.The paper gives a response-oracle complexity bound for a target Bi-ZOL Frank–Wolfe accuracy.Source: C. Convergence analysis and oracle… · pp. 9–10
  • Response-dimension dependence is governed by combined sensitivity and bias quantities, and normalized average-interaction scaling can keep MyLy at O(1) even when Ly grows as O(√m).The stated example has My = O(m^-1/2) when local gradients are uniformly bounded.Source: C. Convergence analysis and oracle… · p. 10

V. SIMULATION RESULTS

The simulation section evaluates Bi-ZOL on an incentive-based tracking problem with capacity-limited responses. It examines convergence, hyperobjective values against VZO, and scalability across problem dimensions.

V. SIMULATION RESULTS

  • The evaluation uses an incentive-based tracking problem with capacity-limited responses.The section investigates Algorithm 1 numerically.Source: §V · p. 10
  • The experiments assess whether the Bi-ZOL Frank–Wolfe gap and hyperobjective value decrease, and compare hyperobjective results with VZO across batch sizes.Source: §V · p. 10
  • The section also tests the solution algorithm's scalability across different problem dimensions.Source: §V · p. 10

A. Simulation setup

The simulations use a tracking objective with constrained response maps and compare Bi-ZOL with VZO. On the PWA experiment, Bi-ZOL reduces the exact Clarke Frank–Wolfe gap relative to VZO under the same response-oracle budget.

1) Upper level:

  • The upper-level objective penalizes control effort, induced-response tracking error, and control-response coupling, with the upper-level signal constrained to a box.Source: 1) Upper level · p. 10

2) Lower level:

  • The lower-level response is the projection of d + Ax onto a capacity set; the box set yields a PWA map, while the ball set has a curved active boundary and is not PWA.Source: 2) Lower level · p. 10

A. Simulation setup

  • Bi-ZOL and VZO comparisons use the same smoothing radius, Frank–Wolfe stepsize, and batch size, with matched problem instances and initial points across ten runs.The curves show empirical means and standard deviations across runs.Source: 2) Lower level · p. 10

B. Convergence behavior

  • The PWA convergence experiment uses n = 20 and m = 200 and tracks active constraints and perturbations crossing active-set boundaries.The diagnostics confirm that constraints are active along the trajectory.Source: B. Convergence behavior · pp. 10–11
  • Bi-ZOL significantly reduces the exact Clarke Frank–Wolfe gap along the PWA trajectory, while VZO remains at a larger gap under the same response-oracle budget.The figure plots stationarity gaps against cumulative response-oracle budget.Source: B. Convergence behavior · p. 11, Figure 3 · p. 11
  • As batch size B increases, all Frank–Wolfe gaps improve further because the two-point estimator's variance is reduced.Source: B. Convergence behavior · p. 11

C. Hyperobjective value

Bi-ZOL outperforms VZO in hyperobjective value and normalized objective gap across the reported response settings and dimensions. Its partial-smoothing design and finite-time stationarity guarantees connect the empirical comparisons to the method’s bilevel structure.

C. Hyperobjective value

  • Across batch sizes, Bi-ZOL reaches lower hyperobjective values than VZO in the PWA setting; its advantage is most visible at low-to-moderate batch sizes.Both methods improve as batch size increases, and their gap decreases; except at B = 1, Bi-ZOL is generally more stable across runs.Source: Figure 4 · p. 11, C. Hyperobjective value · pp. 11–12, Table I · p. 11
  • Bi-ZOL maintains a lower final objective on the non-PWA response map with a curved active boundary, and its relative improvement is larger than in the PWA case.The comparison also reports continued decreases in the stationarity certificate.Source: Figure 5 · p. 12, C. Hyperobjective value · p. 12, Table II · p. 12

D. Sensitivity to problem dimensions

  • 0.0121 (Bi-ZOL) versus 0.4443 (VZO) overall average normalized gaps; Bi-ZOL also wins all 160 paired runs across tested dimension pairs and seeds.The dimension-sensitivity results use a fixed response-oracle budget.Source: Figure 6 · p. 12, D. Sensitivity to problem dimensions · pp. 12–13
  • As upper-level dimension n increases from 20 to 100, both methods’ normalized gaps increase, but Bi-ZOL remains closer to the best observed objective value.The passage attributes the more stable gap over tested dimensions to keeping upper-level partial derivatives exact while sampling only the response-sensitivity term.Source: D. Sensitivity to problem dimensions · p. 13, Table III · p. 13

VI. CONCLUSIONS

  • Bi-ZOL estimates only the response-sensitivity term while using exact upper-level partial derivatives; the paper proves finite-time Frank–Wolfe stationarity guarantees and reports smaller gaps and lower hyperobjective values than vanilla smoothing.The conclusion also states that the certificate transfers to Clarke Frank–Wolfe stationarity of the original nonsmooth reduced problem.Source: §VI · p. 13

APPENDIX A PROOFS FOR NONSMOOTH FIRST-ORDER GEOMETRY

The appendix establishes nonsmooth chain-rule geometry, relates an anchored scalar smoothing construction to Goldstein stationarity, and analyzes the stochastic response-sensitivity estimator.

A. Proof of Proposition 1

  • Limiting gradients of the reduced objective belong to the set formed from upper-level partial gradients and the Clarke generalized Jacobian of the response map.The proof uses local Lipschitz continuity to obtain locally bounded response Jacobians and their convergent subsequences.Source: A. Proof of Proposition 1 · p. 13

B. Proof of Proposition 2

  • The proof identifies the anchored scalar function’s Clarke subdifferential with the reduced-objective subdifferential, then uses uniform smoothing to establish a Goldstein inclusion.The smoothing relation is attributed to [28, Theorem 3.1].Source: B. Proof of Proposition 2 · pp. 13–14

A. Proof of Lemma 1

  • The estimator analysis reduces Bi-ZOL’s stochastic response-sensitivity term to a two-point estimate of the anchored scalar function and averages B independent samples.The scalar function is hx(u) = dy(x)ᵀy(u), and the response map is assumed Lipschitz on the query region.Source: A. Proof of Lemma 1 · p. 14

B. Proof of Lemma 2

The proof establishes the smoothed hypergradient’s Lipschitz behavior by bounding its upper-level partial-gradient term and combining that estimate with a bound for the response-Jacobian term.

B. Proof of Lemma 2

  • The smoothed hypergradient has the form ∇1φ(x, yδ(x)) + Jyδ(x)ᵀ∇2φ(x, yδ(x)).The proof bounds the change in the first term by (L1x + L1yLy)∥x − x′∥ and combines it with an estimate for the second term.Source: B. Proof of Lemma 2 · pp. 14–15

C. Proof of Lemma 3

The proof bounds the structural bias in the smoothed hypergradient and uses that bound in the Frank–Wolfe descent analysis underlying the finite-time guarantee.

C. Proof of Lemma 3

  • ∥∇¯φδ(x) − gδ(x)∥ is bounded by (L1y + MJL2y)∥yδ(x) − y(x)∥.Multiplying this estimate by D bounds the corresponding Frank–Wolfe inner-product term.Source: C. Proof of Lemma 3 · p. 15

D. Proof of Theorem 1

  • The theorem proof bounds descent using smoothness, the Frank–Wolfe oracle, and the bias estimate, then takes conditional expectation and divides by T to prove (39).The conditional-expectation step invokes Lemma 1.Source: D. Proof of Theorem 1 · pp. 15–16
Loading 2609.08021v1…