Research map / Optimization / Nonconvex and smooth optimization
Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization
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 MiSTP, a minibatch zero-order direct-search method that extends Stochastic Three Points by choosing the next iterate using only approximate (minibatch) function values, with convex and nonconvex complexity bounds and experiments on ML tasks.
Problem
Zero-order minimization of smooth finite-sum or stochastic objectives when only approximate (minibatch) function evaluations are available and derivatives are unavailable.
Approach
Extends the Stochastic Three Points method to minibatch function approximations: at each iteration a random direction is sampled, and the iterate is chosen as the best of the current point and its two perturbations {x - αs, x + αs} according to minibatch objective values, with complexity analysis under bounded approximation error.
Key results
- On regularized logistic regression, RSGF, ZO-CD and ZO-SVRG need almost 5 times more function queries than MiSTP for minibatch size 100 and about 2 times more for minibatch size 50.
- In the black-box adversarial attack on an MNIST DNN classifier, MiSTP achieves the least l2 distortion (8.85) versus RSGF (11.24), ZO-SVRG-Ave (11.15) and ZO-SVRG (18.06).
- MiSTP's nonconvex and convex complexity matches RSGF's O(sqrt(d)/sqrt(K)) rate, which is better in d than ZO-SVRG's O(d/K) rate, though worse in K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MiSTP instead of RSGF | Black-box adversarial attack generation · MNIST black-box adversarial attack | l2 distortion: 11.24 -> 8.85 | Helped |
| Use MiSTP instead of ZO-SVRG-Ave | Black-box adversarial attack generation · MNIST black-box adversarial attack | l2 distortion: 11.15 -> 8.85 | Helped |
| Use MiSTP instead of ZO-SVRG | Black-box adversarial attack generation · MNIST black-box adversarial attack | l2 distortion: 18.06 -> 8.85 | Helped |
| Use MiSTP instead of RSGF, ZO-SVRG, and ZO-CD | Zero-order optimization on regularized logistic regression · a1a | objective function value | Helped |
| Use MiSTP instead of RSGF, ZO-SVRG, and ZO-CD | Zero-order optimization on ridge regression · splice | objective function value | Mixed |
| Use minibatches instead of the full batch (ablation) | MiSTP on ridge regression · abalone and splice | convergence by epochs | Helped |
| Use minibatches instead of the full batch (ablation) | MiSTP on regularized logistic regression · a1a and australian | convergence by epochs | Helped |
| Vary minibatch size from full batch or 3000 to 6000 (ablation) | MiSTP neural network · MNIST | accuracy | Helped |
| Vary minibatch size from full batch or 3000 to 6000 (ablation) | MiSTP neural network · MNIST | loss | Helped |
Surprising findings
- Small minibatch sizes (e.g., 1 or 10) gave the best performance on some datasets, and the optimal minibatch size varied by dataset.
Limitations
- Theoretical guarantees assume bounded approximation error of minibatch function values, and the variance condition may require large minibatches.
- Experiments are limited to small LIBSVM problems, a small MNIST network, and a single adversarial attack setup.
- No derivation of an optimal minibatch size rule.
Experimental setup
Datasets: LIBSVM abalone LIBSVM splice LIBSVM a1a LIBSVM australian MNIST
Benchmarks: LIBSVM ridge regression LIBSVM regularized logistic regression MNIST neural network training MNIST black-box adversarial attack
Metrics: objective value vs. function queries objective value vs. epochs accuracy and loss least l2 distortion
Baselines: RSGF ZO-SVRG ZO-CD ZO-SVRG-Ave STP
Builds on: Stochastic Three Points (STP) RSGF ZO-SVRG
Closest papers by meaning
- Minibatch Stochastic Approximate Proximal Point Methods (NeurIPS 2020 · similarity 0.88)
- A Stochastic Derivative Free Optimization Method with Momentum (ICLR 2020 · similarity 0.87)
- On the Almost Sure Convergence of the Stochastic Three Points Algorithm (ICLR 2025 · similarity 0.87)
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.87)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.85)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · 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.