Inexact zeroth-order nonsmooth and nonconvex stochastic composite optimization and applications

Spyridon Pougkakiotis, Dionysis KalogeriasJournal of Nonlinear and Variational Analysis 2026 · DOI

TL;DR

This paper introduces a novel zeroth-order optimization algorithm that can handle complex, non-smooth, and non-convex problems, even when function evaluations are noisy and inexact. This algorithm offers a more robust and general approach to solving a wide range of challenging optimization tasks, particularly in areas like two-stage stochastic programming and minimax optimization, where existing methods fall short.

What Problem Does This Paper Address?

Many real-world optimization problems, especially in machine learning and operations research, are characterized by being:

  • Nonsmooth: The objective function might have sharp corners or kinks, making traditional gradient-based methods difficult to apply.
  • Nonconvex: The objective function can have multiple local minima, making it hard to find the global optimum.
  • Stochastic: The problem involves randomness, meaning we're optimizing an expected value.
  • Composite: The objective function is a sum of two parts: a smooth (or Lipschitz continuous) stochastic function and a potentially non-smooth, but convex, deterministic function (like a regularization term or a constraint).
  • Inexact Oracles: Crucially, evaluating the objective function (or its components) is often done through numerical simulations or approximations, meaning the evaluations are not perfectly accurate and can be noisy or biased.

Existing methods often struggle with combinations of these properties, particularly when dealing with inexact function evaluations. This paper aims to bridge this gap by developing a method that can handle these complexities simultaneously, offering a more practical and general solution.

Methods

The core contribution is a zeroth-order optimization algorithm, named Z-iProxSG. Here's what makes it novel:

  • Zeroth-Order: Instead of requiring gradients (which can be hard to compute or estimate for nonsmooth functions), it only uses function value evaluations. This is achieved by using a smoothed version of the objective function.
  • Inexact Oracle Handling: The algorithm is specifically designed to work with noisy and biased function evaluations, a common scenario in practical applications. It incorporates an "inexact noisy oracle" that returns a function value with a bounded error.
  • Composite Optimization: It effectively handles the composite structure of the objective function, where a smooth stochastic part is combined with a convex, extended-valued part.
  • Surrogate Problem: The algorithm operates on a smoothed surrogate of the original objective function. This smoothing is achieved through "uniform randomized smoothing," which helps to make the function more amenable to analysis and optimization.
  • Proximal Stochastic Gradient Descent: The algorithm is a variant of proximal stochastic gradient descent, which is known for its ability to handle convex regularizers.
  • Novel Stationarity Notion: To analyze convergence, the authors introduce a new notion of "surrogate (λ,µ, ε)-Moreau envelope stationarity." This provides a practical criterion for determining when the algorithm has found a sufficiently good approximate solution, even in the presence of inexactness.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Robustness to Noise is Key: The ability to handle inexact function evaluations is not just a minor improvement; it's crucial for making optimization methods practical in many real-world scenarios where perfect evaluations are impossible.
  • Smoothing as a Unifier: Randomized smoothing acts as a powerful tool to bridge the gap between nonsmooth/nonconvex functions and methods that rely on smoother properties, enabling gradient-free optimization.
  • Generalization is Powerful: The proposed algorithm and its theoretical framework are designed to be general, applying to a wide range of problems without requiring strong assumptions like convexity of lower-level problems or uniqueness of solutions.
  • New Stationarity for Practicality: The novel stationarity condition is designed to be computationally verifiable and relevant for inexact optimization, offering a more realistic measure of progress than traditional exact stationarity.

Key Results

  • Non-Asymptotic Convergence: The algorithm is proven to converge non-asymptotically to a stationary point of a related surrogate problem. This means the convergence rate is bounded and doesn't rely on the number of iterations going to infinity.
  • Applicability to Challenging Problems: The paper demonstrates how the algorithm can be applied to:
  • Two-stage nonconvex stochastic programming: Problems where decisions are made in stages, with uncertainty in the second stage.
  • Nonconvex-nonconcave stochastic minimax optimization: Problems involving finding a saddle point, common in game theory and adversarial machine learning.
  • Improved Generality: The method works under milder assumptions than many existing approaches, particularly concerning the structure of the lower-level problems in two-stage and minimax settings.
  • Theoretical Guarantees: The convergence analysis provides theoretical backing for the algorithm's performance, even with inexact oracles.

Limitations and Future Work

  • Computational Overhead: The algorithm requires two function evaluations per iteration to estimate the smoothed gradient, which is a trade-off for its generality and robustness.
  • Oracle Error Dependence: The convergence rate is influenced by the bound on the oracle error ($\delta$). While the paper provides bounds, achieving optimal rates might require $\delta$ to be sufficiently small relative to other problem parameters.
  • Future Directions: The authors suggest extending the analysis to accommodate stochastic upper bounds on the oracle error, which could lead to more nuanced error propagation analysis. Further research could also explore adapting the method to specific problem structures for potentially faster convergence.

Summary updated

Abstract

In this paper, we present an inexact zeroth-order method suitable for the solution of nonsmooth and nonconvex stochastic composite optimization problems, in which the objective is split into a realvalued Lipschitz continuous stochastic function and an extended-valued (deterministic) proper, closed, and convex one.The algorithm operates under inexact oracles providing noisy (and biased) stochastic evaluations of the underlying finite-valued part of the objective function.We show that the proposed method converges (non-asymptotically), under very mild assumptions, close to a stationary point of an appropriate surrogate problem which is related (in a precise mathematical sense) to the original one.This, in turn, provides a new notion of approximate stationarity suitable nonsmooth and nonconvex stochastic composite optimization, generalizing conditions used in the available literature.In light of the generic oracle properties under which the algorithm operates, we showcase the applicability of the approach in a wide range of problems including large classes of two-stage nonconvex stochastic optimization and nonconvex-nonconcave minimax stochastic optimization instances, without requiring convexity of the lower level problems, or even uniqueness of the associated lower level solution maps.We showcase how the developed theory can be applied in each of these cases under general assumptions, providing algorithmic methodologies that go beyond the current state-of-the-art appearing in each respective literature, enabling the solution of problems that are out of reach for currently available methodologies.
BibTeX
@article{pougkakiotis2026inexact,
  author = {Spyridon Pougkakiotis and Dionysis Kalogerias},
  title = {{Inexact zeroth-order nonsmooth and nonconvex stochastic composite optimization and applications}},
  journal = {Journal of Nonlinear and Variational Analysis},
  year = {2026},
  doi = {10.23952/jnva.10.2026.2.4},
}
Figure