Stochastic Optimization with Random Search

• URL: http://arxiv.org/abs/2510.15610v1
• Date: Fri, 17 Oct 2025 12:57:46 GMT
• Title: Stochastic Optimization with Random Search
• Authors: El Mahdi Chayti, Taha El Bakkali El Kadi, Omar Saadi, Martin Jaggi,
• Abstract summary: We revisit random search for optimization, where only noisy function evaluations are available.<n>We show that the method works under weaker smoothness assumptions than previously considered, and that stronger assumptions enable improved guarantees.
• Score: 39.143454487196536
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit random search for stochastic optimization, where only noisy function evaluations are available. We show that the method works under weaker smoothness assumptions than previously considered, and that stronger assumptions enable improved guarantees. In the finite-sum setting, we design a variance-reduced variant that leverages multiple samples to accelerate convergence. Our analysis relies on a simple translation invariance property, which provides a principled way to balance noise and reduce variance.

Related papers

• Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method [2.339665141986377]
  We show that such guarantees can also be achieved under the weaker assumption of bounded variance.<n>This method combines a subproblem solver, which inherently reduces variance, with a probability booster that amplifies reliability into high-confidence results.
  arXiv  Detail & Related papers  (2024-02-14T07:34:22Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization [1.7513645771137178]
  We consider unconstrained optimization problems with no available gradient information. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a simulation function using finite differences within a common random number framework. We develop modified versions of a norm test and an inner product quasi-Newton test to control the sample sizes used in the approximations and provide global convergence results to the neighborhood of the optimal solution.
  arXiv  Detail & Related papers  (2021-09-24T21:49:25Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference. Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures. We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
  arXiv  Detail & Related papers  (2021-06-30T11:00:24Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• Variance Regularization for Accelerating Stochastic Optimization [14.545770519120898]
  We propose a universal principle which reduces the random error accumulation by exploiting statistic information hidden in mini-batch gradients. This is achieved by regularizing the learning-rate according to mini-batch variances.
  arXiv  Detail & Related papers  (2020-08-13T15:34:01Z)
• Incremental Without Replacement Sampling in Nonconvex Optimization [0.0]
  Minibatch decomposition methods for empirical risk are commonly analysed in an approximation setting, also known as sampling with replacement. On the other hands modern implementations of such techniques are incremental: they rely on sampling without replacement, for which available analysis are much scarcer. We provide convergence guaranties for the latter variant by analysing a versatile incremental gradient scheme.
  arXiv  Detail & Related papers  (2020-07-15T09:17:29Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  We propose a new accelerated first-order method called clipped-SSTM for smooth convex optimization with heavy-tailed distributed noise in gradients. We prove new complexity that outperform state-of-the-art results in this case. We derive the first non-trivial high-probability complexity bounds for SGD with clipping without light-tails assumption on the noise.
  arXiv  Detail & Related papers  (2020-05-21T17:05:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.