# Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization

arXiv: https://arxiv.org/abs/2209.07883 · HTML: https://mlsanity.com/paper/2209.07883/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 16 Sep 2022.

## Builds on (most cited first, 17 of 17)

- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approach](https://mlsanity.com/paper/1912.09135/) (2019)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Autotune: A Derivative-free Optimization Framework for Hyperparameter Tuning](https://mlsanity.com/paper/1804.07824/) (2018)
- [Convergence of trust-region methods based on probabilistic models](https://mlsanity.com/paper/1304.2808/) (2013)
- [A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Control](https://mlsanity.com/paper/1902.01272/) (2019)
- [A Stochastic Derivative Free Optimization Method with Momentum](https://mlsanity.com/paper/1905.13278/) (2019)
- [An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networks](https://mlsanity.com/paper/2012.01901/) (2020)
- [A stochastic Levenberg-Marquardt method using random models with complexity results](https://mlsanity.com/paper/1807.02176/) (2018)
- [Black-Box Optimization in Machine Learning with Trust Region Based Derivative Free Algorithm](https://mlsanity.com/paper/1703.06925/) (2017)
- [Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales](https://mlsanity.com/paper/1609.07428/) (2016)

## Built on by (most cited first, 6 of 6)

- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Optimization with Random Search](https://mlsanity.com/paper/2510.15610/) (2025)
- [Riemannian Dueling Optimization](https://mlsanity.com/paper/2603.00023/) (2026)
- [Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02190/) (2026)
- [TACO: Ternary Absolute-max Column-wise One-sparse Optimizer for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02199/) (2026)

## Abstract (arXiv)

In this paper, we propose a new zero order optimization method called minibatch stochastic three points (MiSTP) method to solve an unconstrained minimization problem in a setting where only an approximation of the objective function evaluation is possible. It is based on the recently proposed stochastic three points (STP) method (Bergou et al., 2020). At each iteration, MiSTP generates a random search direction in a similar manner to STP, but chooses the next iterate based solely on the approximation of the objective function rather than its exact evaluations. We also analyze our method's complexity in the nonconvex and convex cases and evaluate its performance on multiple machine learning tasks.