Research map / Optimization / Nonconvex and smooth optimization
DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
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.
Proposes DTZO, a distributed trilevel zeroth-order learning framework that builds cascaded polynomial relaxations via Gaussian-smoothing zeroth-order cuts, with non-asymptotic convergence guarantees.
Problem
Trilevel learning when first-order gradients at every level are unavailable (black-box models, privacy) and data is distributed across workers; prior trilevel methods need gradients and prior zeroth-order work covers only single-level or bilevel.
Approach
Zeroth-order cutting planes built from Gaussian-smoothed function evaluations (no gradients or subgradients) iteratively refine cascaded inner and outer polynomial relaxations of the lower-level constraints, combined with an exterior penalty and a distributed parameter-server update.
Key results
- On robust hyperparameter optimization, DTZO reaches 0.7927 on MNIST and 0.8513 on USPS versus 0.7501 and 0.7987 for the best baseline AFTO+ZO.
- Theory gives iteration complexity O(1/epsilon^2) for the epsilon-stationary point, the first such guarantee for trilevel zeroth-order optimization, with the dimension dependence O(sum d_i^6).
- On backdoor attacks against black-box LLMs (Qwen-1.8B-Chat), DTZO outperforms FedRZObl on ASR and ACC across SST-2, COLA, and MRPC (Figures 1-3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · MNIST | average across accuracy: 0.7501 -> 0.7927 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · QMNIST | average across accuracy: 0.7389 -> 0.7804 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · F-MNIST | average across accuracy: 0.6448 -> 0.7007 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · USPS | average across accuracy: 0.7987 -> 0.8513 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · MelbournePedestrian | average across accuracy: 0.6924 -> 0.7250 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · Crop | average across accuracy: 0.6016 -> 0.6351 | Helped |
| Use DTZO instead of AFTO+ZO | distributed robust hyperparameter optimization · UWaveGestureLibraryAll | average across accuracy: 0.7689 -> 0.8243 | Helped |
| Add nonlinear zeroth order cuts instead of using linear cuts (ablation) | DTZO · robust hyperparameter optimization | average across accuracy | Helped |
| Add cascaded polynomial approximation instead of single-layer polynomial approximation (ablation) | DTZO · robust hyperparameter optimization | average across accuracy | Helped |
Limitations
- Iteration complexity scales as O(sum d_i^6), which is high in variable dimension.
- Baseline ZO-estimator variants of FEDNEST, ADBO and AFTO carry no theoretical guarantees, so comparisons are heuristic.
- The method relies on bounded-domain and L-smooth assumptions and an exterior penalty formulation.
Experimental setup
Datasets: GLUE SST-2 GLUE COLA GLUE MRPC MNIST USPS Fashion MNIST QMNIST MelbournePedestrian Crop UWaveGestureLibraryAll
Benchmarks: GLUE SST-2 GLUE COLA GLUE MRPC MNIST USPS Fashion MNIST QMNIST MelbournePedestrian Crop UWaveGestureLibraryAll
Metrics: attack success rate (ASR) clean accuracy (ACC) average of clean accuracy and adversarial robustness
Baselines: FedZOO FEDNEST+ZO ADBO+ZO FedRZObl AFTO+ZO
Builds on: AFTO FedRZObl cutting plane distributed bilevel optimization (ADBO) Gaussian smoothing zeroth-order gradient estimation (Ghadimi & Lan 2013)
Closest papers by meaning
- Provably Convergent Federated Trilevel Learning (AAAI 2024 · similarity 0.88)
- Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence (AAAI 2025 · similarity 0.84)
- Zeroth-Order Optimization Finds Flat Minima (NeurIPS 2025 · similarity 0.83)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.83)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.82)
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning (ICML 2025 · similarity 0.82)
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.