Zeroth-order methods for non-smooth stochastic problems under heavy-tailed noise

Nail Bashirov, Alexander Gasnikov, Aleksandr LobanovICOMP Publication 2024 · OpenReview

TL;DR

This paper introduces new zeroth-order optimization algorithms designed to handle non-smooth problems corrupted by heavy-tailed noise, a more realistic scenario than previously assumed bounded noise. The proposed methods, which incorporate clipping and batching techniques, achieve optimal convergence rates and provide theoretical guarantees for iteration complexity, oracle complexity, and maximal noise levels.

What Problem Does This Paper Address?

Gradient-free optimization methods, also known as zeroth-order methods, are increasingly vital in areas like reinforcement learning and LLM fine-tuning where direct gradient computation is infeasible or inefficient. While optimal algorithms exist for problems with uniformly bounded noise variance, this assumption is often violated in practice. Many real-world scenarios involve heavy-tailed noise distributions (e.g., from data distributions in LLMs/GANs or reward distributions in multi-armed bandits), which can severely degrade the performance of standard algorithms. This paper tackles the challenge of developing robust zeroth-order optimization techniques that can effectively handle non-smooth convex and convex-concave problems under such heavy-tailed, unbounded noise conditions, including adversarial noise.

Methods

The authors propose several novel gradient-free algorithms:

  • ZO-clipped-SSTM-OPF: For convex and strongly-convex problems.
  • R-ZO-clipped-SSTM-OPF: An extension for strongly-convex problems using a restart technique.
  • ZO-clipped-SEG: For non-smooth convex-concave saddle point problems.

These algorithms build upon existing frameworks but introduce key modifications to address heavy-tailed noise:

  • Clipping Operator: Inspired by [18], a clipping operator is applied to the estimated gradient. This technique limits the norm of the gradient estimate, effectively mitigating the impact of extreme noise values and preventing them from destabilizing the optimization process.
  • Batching: To improve computational efficiency, especially when dealing with multiple noisy gradient estimates, the algorithms utilize batching. This allows for parallel computation of gradient approximations.
  • Smoothing Technique: For non-smooth problems, a Gaussian smoothing scheme is employed to make the objective function differentiable, allowing gradient-based analysis.
  • Theoretical Analysis: The paper provides rigorous asymptotic convergence analysis, deriving bounds for iteration complexity, oracle complexity, and the maximal admissible noise level. These bounds are shown to be optimal in various settings.

Datasets

Not discussed in the paper. The experiments use synthetic problems (quadratic minimization and a bilinear optimization problem) to evaluate the proposed algorithms.

Key Insights and Ideas

  • Heavy-tailed noise is a critical challenge: The paper strongly emphasizes that assuming bounded noise variance is often unrealistic and leads to suboptimal performance in practice. Heavy-tailed noise requires specialized techniques.
  • Clipping is a powerful defense: The clipping operator proves to be a crucial component for achieving robust convergence in the presence of unbounded noise. It effectively "tames" extreme gradient estimates.
  • Optimality under realistic assumptions: The proposed algorithms achieve theoretical optimality in terms of convergence rates, not just under ideal conditions but also under the more challenging assumption of heavy-tailed noise.
  • Balancing iteration and oracle complexity: The analysis provides insights into the trade-offs between the number of iterations and the number of function evaluations (oracle calls), which are important considerations for practical algorithm selection.

Key Results

The paper presents theoretical guarantees for the proposed algorithms:

  • Optimal Convergence Rates: For convex and strongly-convex problems, the algorithms achieve optimal iteration and oracle complexities, matching or improving upon existing results under heavy-tailed noise assumptions. For instance, for the convex case, the iteration complexity is $O(\max(\frac{d^{1/4}M_2R}{\epsilon^2}, \frac{dGM_2R}{\epsilon^\alpha}))$.
  • Saddle Point Performance: The ZO-clipped-SEG algorithm for saddle point problems also provides theoretical guarantees, establishing the first asymptotic boundary for convex-concave saddle problems under heavy-tailed noise.
  • Maximal Admissible Noise: The analysis yields bounds on the maximal admissible noise level (both stochastic and adversarial) that still allow for guaranteed convergence. For example, for noisy OPF, $\Delta \le \min(\frac{G^\alpha}{\sqrt{dM_2R}}, \frac{\epsilon^2}{\sqrt{dM_2R}})$.
  • Numerical Validation: Experiments on synthetic problems demonstrate that the clipping technique significantly improves convergence and allows methods to reach a lower error floor compared to non-clipped counterparts, especially under heavy-tailed noise. Figure 1 shows that clipped methods converge to a lower error floor.

Limitations and Future Work

  • Assumptions: While the paper relaxes the bounded variance assumption, it still relies on other assumptions like the existence of a $\mu$-strongly convex or convex-concave structure and certain smoothness properties of the smoothed function.
  • Computational Cost: While batching improves efficiency, the theoretical analysis focuses on asymptotic bounds, and practical performance might still be sensitive to hyperparameter tuning (e.g., learning rates, clipping parameters).
  • Future Directions: The authors suggest extending their work to composite convex optimization problems and decentralized learning settings. They also aim to provide zeroth-order analysis for these more complex scenarios.

Summary updated

Abstract

Recently gradient-free optimisation methods have become a major tool in reinforcement learning and memory-efficient LLM fine-tuning. Under the standard setting of uniformly bounded noise variance an optimal accelerated algorithm has been derived. However, the assumption of bounded variance is strict and usually is not fulfilled in practice. Therefore, we will relax it, allowing the noise distribution to be heavy-tailed and, thus, broadening the class of problems to be solved. We propose gradient-free algorithms with zeroth-order oracle under adversarial noise with unbounded variance, for non-smooth convex and convex-concave optimisation problems. We apply clipping operator to deal with heavy-tailedness and batching to allow efficient computation via parallelization. Our analysis provides asymptotic bounds for such key parameters as iteration complexity, oracle complexity and maximal adversarial noise level.
BibTeX
@inproceedings{bashirov2024zeroth,
  author = {Nail Bashirov and Alexander Gasnikov and Aleksandr Lobanov},
  title = {{Zeroth-order methods for non-smooth stochastic problems under heavy-tailed noise}},
  booktitle = {ICOMP Publication},
  year = {2024},
  url = {https://openreview.net/forum?id=iiPWyBbKYp},
}
Figure