Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles

This paper tackles a fundamental bottleneck in modern AI: the reliance on gradient information. As models grow larger and training data becomes more complex, the ability to optimise functions without explicit gradients—a technique known as zeroth-order (ZO) optimisation—is increasingly valuable. The authors provide a rigorous theoretical analysis of a specific ZO method (random Gaussian smoothing) applied to a class of functions called quasar-convex (QC) and strongly quasar-convex (SQC).

What Was Achieved

The core contribution is a set of convergence guarantees. The paper proves that a simple ZO scheme can efficiently minimise QC and SQC functions in both unconstrained and constrained settings. Quasar-convexity is a weaker condition than standard convexity but stronger than general non-convexity; it captures functions where the gradient points roughly toward the global minimum, even if the landscape is not perfectly bowl-shaped. The authors show that with random Gaussian smoothing, the ZO algorithm achieves a convergence rate comparable to first-order methods for this function class, albeit with a polynomial dependence on the problem dimension. This is a significant theoretical step because it provides a rigorous justification for using ZO methods on problems where gradients are unavailable or prohibitively expensive.

Why This Matters for AI

The practical implications are substantial. Many real-world AI tasks involve "black-box" functions. For example, hyperparameter tuning, reinforcement learning with policy gradients (where the reward function is a black box), and adversarial attack generation often rely on ZO methods. The paper’s findings mean that for problems exhibiting quasar-convex structure—which includes many well-behaved neural network loss landscapes near the optimum—practitioners can now trust that a simple, gradient-free approach will converge reliably. This is particularly relevant for:

• Privacy-preserving AI: ZO methods do not require backpropagation, reducing the risk of leaking training data through gradient updates.
• Hardware-constrained deployment: Running inference on edge devices often lacks the computational graph needed for gradients; ZO allows on-device fine-tuning.
• Scientific computing: Many physical simulations are non-differentiable, making ZO the only viable optimisation path.

Caveats and Practical Considerations

The analysis does not claim that ZO methods will outperform gradient-based methods when gradients are available. The convergence rate has a dimension-dependent term, meaning ZO can be slow for very high-dimensional problems (e.g., large language models). However, for moderate-dimensional problems (e.g., tens of thousands of parameters) or problems where gradient computation is the primary bottleneck, this result provides a strong theoretical foundation for using ZO as a practical alternative. The paper also assumes the function is quasar-convex, which may not hold globally for all neural network loss landscapes, but is a reasonable approximation for many well-conditioned problems.

Key Takeaways

• Rigorous guarantees: Random Gaussian smoothing ZO methods provably converge for quasar-convex and strongly quasar-convex functions, matching first-order rates up to a dimension factor.
• Practical relevance: Validates the use of gradient-free optimisation for black-box AI tasks like hyperparameter tuning, RL, and adversarial attacks.
• Dimensionality is the cost: The method’s efficiency degrades in very high dimensions, making it best suited for problems where gradient access is the primary bottleneck, not parameter count.
• Bridges theory and practice: Provides a theoretical backbone for a widely used heuristic, giving AI practitioners confidence in applying ZO methods to structured non-convex problems.