Research map / Optimization / Nonconvex and smooth optimization
Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives non-asymptotic linear convergence rates for nonsmooth ITD and AID-FP for implicit differentiation of contractive fixed points under definable piecewise-smooth assumptions, and proposes NSID, a stochastic implicit-differentiation method with O(1/k) mean-square rates.
Problem
Efficiently computing the conservative (generalized) derivative of the fixed point of a parametric nondifferentiable contraction map, motivated by bilevel optimization, where the chain rule fails and inner maps may be accessible only via stochastic estimators.
Approach
Extends smooth ITD/AID convergence analysis to piecewise-smooth definable contractions via a generalized excess-based Lipschitz-type constant, and introduces NSID, which handles a composite fixed-point map G(T(w,λ),λ) with mini-batch estimators of T and its derivatives.
Key results
- Theory: AID-FP upper bound is always below ITD's at t=k, with AID-FP O(κ^2 e^{-t/κ}) vs ITD O(κ t e^{-t/κ}) rates.
- NSID achieves mean-square excess O(κ^5/k + κ^4/J + κ^{4+α}/t), giving O(κ^{5+α} ε^{-1}) sample complexity.
- Experiments on elastic net show AID-FP converges faster than ITD, with a wide gap after support identification; NSID converges faster initially than deterministic AID-FP on some settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AID-FP instead of ITD after support identification | Deterministic implicit differentiation · Synthetic elastic net | Jacobian-vector approximation error | Helped |
| Use conjugate gradient to solve the linear system | AID-CG · Synthetic elastic net | Convergence | Hurt |
| Use NSID rather than deterministic AID-FP | Stochastic implicit differentiation · Elastic net | Jacobian-vector approximation error | Helped |
| Use NSID rather than SID | Stochastic implicit differentiation · Elastic net | Convergence | Helped |
| Use NSID rather than SID | Stochastic implicit differentiation · Data poisoning | Convergence | Helped |
| Use decreasing rather than constant step sizes (ablation) | NSID · Elastic net and data poisoning | Jacobian-vector approximation error | Helped |
Surprising findings
- SID diverges on data poisoning and does not converge on elastic net for a specific lambda, due to bias from applying G to the stochastic estimate.
- The nonsmooth ITD bound can be much worse than AID when the ratio M/R is large near nondifferentiable regions.
Limitations
- Bilevel convergence to stationary points for nonsmooth case is not established; only fixed-point derivative rates.
- The constant M_lambda/R_lambda can blow up near nondifferentiable regions, so the bounds may be loose there.
- Step sizes for NSID (eta_i = Theta(1/i)) are problematic in practice.
Experimental setup
Datasets: synthetic linear regression (100 examples, 100 features) data poisoning logistic regression data
Benchmarks: synthetic elastic-net data poisoning elastic-net logistic regression
Metrics: approximation error (excess) geometric standard deviation over runs
Baselines: ITD AID-FP AID-CG SID
Builds on: Bolte et al. piggyback automatic differentiation for nonsmooth ITD stochastic implicit differentiation (SID) Grazzi et al. smooth ITD/AID rates conservative derivatives (Bolte and Pauwels)
Closest papers by meaning
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.86)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.86)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.85)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.85)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.85)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.