Research map / Optimization / Nonconvex and smooth optimization

Stochastic Optimization with Random Search

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity · 0 citations (OpenAlex)

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 Mi2P, a two-point minibatch random search (sign-based comparison of noisy function evaluations) and analyzes its convergence under (L0,L1)-smoothness, finite-sum variance reduction, and inexact helper/human feedback.

Problem

Derivative-free stochastic nonconvex optimization with only noisy function evaluations, where prior stochastic random search (MiSTP) had suboptimal O(d^3/eps^6) complexity under strong individual smoothness.

Approach

A two-point minibatch random search that updates by the sign of the difference of noisy estimates at x±ηs; translation invariance means only the difference error matters, which allows balancing noise and enabling snapshot-free variance reduction in the finite-sum case.

Key results

• Under average (L0,L1)-smoothness with bounded variance, Mi2P achieves Õ(d^3σ0^2/ε^6) calls, matching MiSTP but under weaker assumptions.
• Under standard sample smoothness, complexity improves to Õ(dσ1^2/ε^4), matching gradient-estimation methods such as RSGF.
• On logistic regression (Breast Cancer, n=455, d=30), Mi2P underperforms for b=1,5 but matches or surpasses RSGF and beats ZO-CD for larger batch sizes.

Surprising findings

• Naive momentum adaptation (replacing gradients with function differences) does not yield gains for random search, due to scale-invariant signal-to-noise ratio of the difference oracle.

Limitations

• Analysis assumes (L0,L1)-smoothness and bounded variance; heavy-tailed noise and weaker smoothness left open.
• Momentum does not transfer directly to random search, so variance reduction relies on larger minibatches.
• Experiments are limited to a single small logistic regression task; small batches underperform.

Experimental setup

Datasets: Breast Cancer Wisconsin

Benchmarks: Breast Cancer Wisconsin logistic regression

Metrics: objective value vs function queries

Baselines: RSGF ZO-CD MiSTP

Builds on: Stochastic Three Points (STP) MiSTP RSGF (L0,L1)-smoothness

Closest papers by meaning

• Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
• On the Almost Sure Convergence of the Stochastic Three Points Algorithm (ICLR 2025 · similarity 0.89)
• High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.89)
• Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.88)
• Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.88)
• Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.88)