# The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2022.

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

- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization](https://mlsanity.com/paper/2405.01731/) (2024)
- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)
- [Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits](https://mlsanity.com/paper/2305.06743/) (2023)
- [Federated Learning Can Find Friends That Are Advantageous](https://mlsanity.com/paper/2402.05050/) (2024)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)
- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)
- [New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Framework](https://mlsanity.com/paper/2604.09940/) (2026)
- [Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling](https://mlsanity.com/paper/2609.38561/) (2026)

## Abstract (arXiv)

Gradient-free/zeroth-order methods for black-box convex optimization have been extensively studied in the last decade with the main focus on oracle calls complexity. In this paper, besides the oracle complexity, we focus also on iteration complexity, and propose a generic approach that, based on optimal first-order methods, allows to obtain in a black-box fashion new zeroth-order algorithms for non-smooth convex optimization problems. Our approach not only leads to optimal oracle complexity, but also allows to obtain iteration complexity similar to first-order methods, which, in turn, allows to exploit parallel computations to accelerate the convergence of our algorithms. We also elaborate on extensions for stochastic optimization problems, saddle-point problems, and distributed optimization.