Fully First-Order Optimization for Implicit Multilevel Compositions via Recursive Perturbations
Abstract
We study optimization over a finite composition of implicit response maps generated by smooth potentials with strongly monotone signed gradients. This class includes chains mixing strongly convex minimization and strongly convex--strongly concave saddle responses. We propose a fully first-order method based on recursively perturbed response solves. The central issue is stability under inexact response solves: a downstream adjoint error changes the perturbation vector of the next upstream perturbed problem. We establish coupled bounds for the forward response errors and backward errors in the scaled response differences whose coefficients remain bounded as the perturbation parameter δ decreases. A triangular Lyapunov construction combines these bounds with the O(δ) bias of the exact perturbation estimator. For the warm-started method with finitely many inner iterations, this gives 1/K∑k=0K−1|∇Φ(xk)|2 ≤ O(K−1)+O(δ2). Thus, for fixed problem data and finite depth, δ=O(ε) yields an O(ε−2) outer-iteration dependence. For strongly convex minimization chains, we also derive condition-number-dependent first-order oracle complexity bounds.
Related
- Recursive Multilevel Decomposition of Pairwise Comparison Matrices: Algorithms and Inconsistency Diagnostics
- Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
- Optimization of a Perturbed Implicit Sweeping Process by Constrained Discontinuous Controls
- Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
- Adversarial Training with Large Step Sizes: Implicit Bias, Optimization, and Sharpness
BibTeX
@misc{wang2026fully,
title = {{Fully First-Order Optimization for Implicit Multilevel Compositions via Recursive Perturbations}},
author = {Xiaoyu Wang and Shiqian Ma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25670},
eprint = {2610.25670},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25670},
}
RIS
TY - UNPB
TI - Fully First-Order Optimization for Implicit Multilevel Compositions via Recursive Perturbations
AU - Xiaoyu Wang
AU - Shiqian Ma
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25670
UR - https://arxiv.org/abs/2610.25670
AB - We study optimization over a finite composition of implicit response maps generated by smooth potentials with strongly monotone signed gradients. This class includes chains mixing strongly convex minimization and strongly convex--strongly concave saddle responses. We propose a fully first-order method based on recursively perturbed response solves. The central issue is stability under inexact response solves: a downstream adjoint error changes the perturbation vector of the next upstream perturbed problem. We establish coupled bounds for the forward response errors and backward errors in the scaled response differences whose coefficients remain bounded as the perturbation parameter δ decreases. A triangular Lyapunov construction combines these bounds with the O(δ) bias of the exact perturbation estimator. For the warm-started method with finitely many inner iterations, this gives 1/K∑_k=0^K−1|∇Φ(x^k)|^2 ≤ O(K^−1)+O(δ^2). Thus, for fixed problem data and finite depth, δ=O(ε) yields an O(ε^−2) outer-iteration dependence. For strongly convex minimization chains, we also derive condition-number-dependent first-order oracle complexity bounds.
ER -