pipette
ENEnglish

Fully First-Order Optimization for Implicit Multilevel Compositions via Recursive Perturbations

Xiaoyu Wang, Shiqian Ma

Preprint

En palabras de los autores

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 bias of the exact perturbation estimator. For the warm-started method with finitely many inner iterations, this gives Thus, for fixed problem data and finite depth, yields an outer-iteration dependence. For strongly convex minimization chains, we also derive condition-number-dependent first-order oracle complexity bounds.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 51 pages, 7 figures and 5 tables