# Gradient-Free Optimization for Non-Smooth Saddle Point Problems under Adversarial Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2022.

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

- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)

## Abstract (arXiv)

We consider non-smooth saddle point optimization problems. To solve these problems, we propose a zeroth-order method under bounded or Lipschitz continuous noise, possible adversarial. In contrast to the state-of-the-art algorithms, our algorithm is optimal in terms of both criteria: oracle calls complexity and the maximum value of admissible noise. The proposed method is simple and easy to implement as it is built on zeroth-order version of the stochastic mirror descent. The convergence analysis is given in terms of the average and probability. We also pay special attention to the duality gap r-growth condition (r≥ 1), for which we provide a modification of our algorithm using the restart technique. We also comment on infinite noise variance and upper bounds in the case of Lipschitz noise. The results obtained in this paper are significant not only for saddle point problems but also for convex optimization.