Research map / Optimization / Optimizers
ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization
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 ReLIZO, a zeroth-order optimizer that models gradient estimation as a QCLP with an analytical solution, reusing prior-iteration queries to cut per-iteration function evaluations while keeping sample size fixed.
Problem
Zeroth-order optimization needs many function queries per iteration for accurate gradient estimation, which is costly in tasks like AutoML and RL; prior linear-interpolation methods scale poorly with dimension or require orthogonal samples, and smoothing methods are biased and hard to reuse.
Approach
Estimate the gradient direction as a linear combination of sampled directions by solving a quadratically constrained linear program (analytical Lagrange solution, pseudo-inverse form), with no orthogonality requirement, and reuse queries from the previous iteration whose displacement is below a distance bound; Gram-matrix entries are indexed from prior iterations to cut computation.
Key results
- On NAS-Bench-201 ReLIZO used 11885 queries vs 19550 for ZO-AdaMM/ZO-SGD/ZO-signSGD (about 39% fewer) and achieved the best ZO accuracy on most columns (e.g., CIFAR-10 test 92.45%).
- On universal black-box attack over 100 CIFAR-10 images, ReLIZO reached 92% attack success rate vs 87% for ZO-AdaMM at similar l2 distortion (~1.37).
- On OPT-1.3b SST2 full-parameter fine-tuning, ReLIZO reached 93.4% accuracy, exceeding SGD (91.1%) and other ZO methods, with 35.7 GB memory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ReLIZO instead of ZO-AdaMM | universal adversarial attack on CIFAR-10 · CIFAR-10 universal attack | attack success rate: 87% -> 92% | Helped |
| use ReLIZO instead of ZO-SGD | NAS-Bench-201 search · CIFAR-10 test | test accuracy: 91.60 -> 92.45 | Helped |
| use ReLIZO instead of ZO-SGD | NAS-Bench-201 search · CIFAR-100 test | test accuracy: 67.49 -> 69.03 | Helped |
| use ReLIZO instead of ZO-SGD | NAS-Bench-201 search · ImageNet-16-120 test | test accuracy: 41.71 -> 42.31 | Helped |
| reuse prior queries with ReLIZO | NAS-Bench-201 search · NAS-Bench-201 | number of queries: 19550 -> 11885 | Helped |
| use ReLIZO instead of SGD | OPT-1.3b full fine-tuning · SST2, full fine-tuning | accuracy: 91.1 -> 93.4 | Helped |
| use ReLIZO instead of SGD | OPT-1.3b fine-tuning · SST2, LoRA | accuracy: 93.6 -> 93.1 | Hurt |
| use ReLIZO instead of SGD | OPT-1.3b fine-tuning · SST2, Prefix-Tuning | accuracy: 93.1 -> 91.8 | Hurt |
| add sampling momentum (ablation) | ReLIZO on NAS-Bench-201 · CIFAR10 test | test accuracy: 92.45 -> 93.41 | Helped |
| increase reusable distance bound from b = 0 to b = η (ablation) | ReLIZO on ARGTRIGLS · ARGTRIGLS | objective value (iter=500): 0.133 -> 8.158 | Hurt |
| increase reusable distance bound from b = 0 to b = η (ablation) | ReLIZO on ARGTRIGLS · ARGTRIGLS | total reuse rate: 0% -> 96.8% | Helped |
Surprising findings
- ReLIZO fine-tuning with full parameters on OPT-1.3b surpasses first-order SGD accuracy (93.4 vs 91.1) while using less memory.
- Reducing the reusable distance bound and capping reuse rate can recover performance; aggressive reuse (b=η, ~97% reuse) slows convergence on ARGTRIGLS.
Limitations
- Reuse benefit diminishes when a single function query is cheap, making the QCLP solve relatively costlier.
- Reuse rate depends on the reusable distance bound b; large b degrades convergence on rugged landscapes (e.g., ARGTRIGLS)
- Convergence analysis is for convex functions and relies on an assumed norm condition and a minimum step size of order 1/d.
Experimental setup
Datasets: CUTEst CIFAR-10 NAS-Bench-201 SST2
Benchmarks: CUTEst CIFAR-10 NAS-Bench-201 SST2
Metrics: objective value attack success rate l2 distortion top-1 accuracy number of queries memory (GB)
Baselines: ZO-SGD ZO-signSGD ZO-AdaMM ZO-SMD
Builds on: ZO-SGD ZO-signSGD ZO-AdaMM linear interpolation gradient estimation
Closest papers by meaning
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.87)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.87)
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.86)
- Improving the Straight-Through Estimator with Zeroth-Order Information (NeurIPS 2025 · similarity 0.85)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.85)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.84)
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.