# An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2023.

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

- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Forward Learning for Gradient-based Black-box Saliency Map Generation](https://mlsanity.com/paper/2403.15603/) (2024)
- [Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale](https://mlsanity.com/paper/2501.19099/) (2025)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection](https://mlsanity.com/paper/2405.14519/) (2024)
- [Memory Savings at What Cost? A Study of Alternatives to Backpropagation](https://mlsanity.com/paper/2506.21833/) (2025)
- [AttestLLM: Efficient Attestation Framework for Billion-scale On-device LLMs](https://mlsanity.com/paper/2509.06326/) (2025)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)
- [Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling](https://mlsanity.com/paper/2609.38561/) (2026)

## Abstract (arXiv)

Finite-difference methods are a class of algorithms designed to solve black-box optimization problems by approximating a gradient of the target function on a set of directions. In black-box optimization, the non-smooth setting is particularly relevant since, in practice, differentiability and smoothness assumptions cannot be verified. To cope with nonsmoothness, several authors use a smooth approximation of the target function and show that finite difference methods approximate its gradient. Recently, it has been proved that imposing a structure in the directions allows improving performance. However, only the smooth setting was considered. To close this gap, we introduce and analyze O-ZD, the first structured finite-difference algorithm for non-smooth black-box optimization. Our method exploits a smooth approximation of the target function and we prove that it approximates its gradient on a subset of random em orthogonal directions. We analyze the convergence of O-ZD under different assumptions. For non-smooth convex functions, we obtain the optimal complexity. In the non-smooth non-convex setting, we characterize the number of iterations needed to bound the expected norm of the smoothed gradient. For smooth functions, our analysis recovers existing results for structured zeroth-order methods for the convex case and extends them to the non-convex setting. We conclude with numerical simulations where assumptions are satisfied, observing that our algorithm has very good practical performances.