Zero-Order Stochastic Conditional Gradient Sliding Method for Non-smooth Convex Optimization

A. V. Lobanov, Anton Anikin, Alexander Gasnikov, Alexander Gornov, С.н. ЧукановCommunications 2023 · DOI · OpenAlex

Abstract

The conditional gradient idea proposed by Marguerite Frank and Philip Wolfe in 1956 was so well received by the community that new algorithms (also called Frank--Wolfe type algorithms) are still being actively created. In this paper, we study a non-smooth stochastic convex optimization problem with constraints. Using a smoothing technique and based on an accelerated batched first-order Stochastic Conditional Gradient Sliding method, we propose a novel gradient-free Frank--Wolfe type algorithm called Zero-Order Stochastic Conditional Gradient Sliding (ZO-SCGS). This algorithm is robust not only for the class of non-smooth problems, but surprisingly also for the class of smooth black box problems, outperforming the SOTA algorithms in the smooth case in term oracle calls. In practical experiments we confirm our theoretical results.

Introduction

Optimization lies at the heart of modern machine learning, yet many practical problems do not provide the luxury of explicit gradient information. In "black-box" scenarios—ranging from the tuning of complex physical simulations to the generation of adversarial attacks—researchers must rely solely on function evaluations. Furthermore, when optimization occurs over complex constraint sets (such as high-dimensional matrices or probability simplexes), traditional projection-based methods become computationally prohibitive.

The Frank-Wolfe (or Conditional Gradient) algorithm has long been a favorite for constrained optimization because it replaces expensive projections with simpler linear optimization steps. However, extending Frank-Wolfe to non-smooth, zero-order settings has remained a significant challenge. This paper introduces Zero-Order Stochastic Conditional Gradient Sliding (ZO-SCGS), an algorithm that bridges this gap and sets a new state-of-the-art for oracle complexity.

The ZO-SCGS Framework

The ZO-SCGS method is built upon an accelerated "sliding" framework, designed to minimize the number of Linear Minimization Oracle (LMO) calls while maintaining high accuracy. The algorithm integrates four critical components:

  1. Smoothing via $l_2$ Randomization: To handle non-smooth objective functions $f(x)$, the algorithm optimizes a smooth approximation $f_\gamma(x)$. This is achieved by evaluating the function at points perturbed by a random vector on a sphere, effectively "blurring" the sharp edges of the function.
  2. Central Finite Difference (CFD) Estimation: Instead of true gradients, ZO-SCGS uses a two-point query system. By evaluating the function at $x + \gamma e$ and $x - \gamma e$, the algorithm produces a more stable and accurate gradient estimate than one-point "direct" difference methods.
  3. Conditional Gradient Sliding: The "sliding" technique allows the algorithm to decouple the number of gradient evaluations from the number of LMO calls. This acceleration ensures that the algorithm does not waste computational effort on linear subproblems when the gradient estimate hasn't changed significantly.
  4. Strategic Batching: To mitigate the noise inherent in stochastic zero-order queries, the algorithm processes a batch of random directions at each step. This stabilizes the trajectory of the optimization.

Theoretical Breakthroughs

The most striking contribution of ZO-SCGS is its oracle complexity. For a desired accuracy $\epsilon$, the algorithm requires $T = O(d/\epsilon^2)$ function queries in the Euclidean setting. This represents a significant leap over previous state-of-the-art (SOTA) zero-order methods, which typically require $O(\epsilon^{-3})$ calls.

Interestingly, while the algorithm was designed for non-smooth problems, it exhibits superior performance on smooth black-box problems as well. The theoretical convergence rate for iterations is established as $N = O(d^{1/4}/\epsilon)$, providing a robust guarantee for high-dimensional tasks.

Experimental Validation

The researchers evaluated ZO-SCGS using a synthetic black-box quadratic optimization problem: $$\min \frac{1}{2}\langle x, Ax \rangle - \langle b, x \rangle$$ subject to a simplex constraint $Q = \{x \in \mathbb{R}^d : \|x\|_1 = 1, x \geq 0\}$.

In a 100-dimensional setting, ZO-SCGS was compared against the Zero-Order Conditional Gradient (ZSCG) method. The results confirmed the theoretical predictions: ZO-SCGS reached target error levels with significantly fewer function evaluations. The experiments also highlighted a practical insight regarding batch sizes; while theory suggests increasing batch sizes, a well-chosen fixed batch size often provides the best balance of speed and stability in practice.

Conclusion and Future Directions

ZO-SCGS provides a powerful new tool for projection-free, gradient-free optimization. By achieving an $\epsilon^{-2}$ complexity, it narrows the gap between first-order and zero-order methods. Future research may look toward extending this framework to non-convex landscapes, such as those found in deep neural networks, and exploring its robustness under significant adversarial noise.

Summary updated

BibTeX
@inproceedings{lobanov2023zero,
  author = {A. V. Lobanov and Anton Anikin and Alexander Gasnikov and Alexander Gornov and С.Н. Чуканов and Aleksandr Lobanov},
  title = {{Zero-Order Stochastic Conditional Gradient Sliding Method for Non-smooth Convex Optimization}},
  booktitle = {Communications},
  year = {2023},
  doi = {10.1007/978-3-031-43257-6\_8},
}

Loading related content...

Figure