Gradient sampling algorithm for subsmooth functions

Dimitris Boskos, Jorge Cortés, Sonia Martı́nezarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces a modified Gradient Sampling (mGS) algorithm designed to optimize "subsmooth" functions—complex, non-smooth objectives often found in robust engineering and AI. By relaxing strict theoretical requirements for smoothness, the authors provide a rigorous convergence proof and demonstrate how to solve "min-max" problems where function values and gradients can only be approximated.

What Problem Does This Paper Address?

In the world of optimization, "smoothness" (differentiability) is a luxury. Many modern challenges—like training neural networks, nonlinear control, or robust sensor placement—involve objective functions that are non-convex and non-smooth.

A particularly difficult class of problems involves minimizing the pointwise maximum of a family of functions (a "min-max" problem). Imagine trying to find the lowest point on a jagged mountain range formed by the intersection of many different slopes. In these cases, you often don't have a clean formula for the gradient, and the function might be non-differentiable at the very points you care about most.

Existing "Gradient Sampling" (GS) algorithms tackle this by sampling gradients in a small neighborhood to find a reliable descent direction. However, previous proofs of their success relied on a hidden technicality: the function had to be continuously differentiable on an "open set of full measure." This paper addresses the reality that many robust optimization problems violate this condition, providing a path forward for a broader class of "subsmooth" (lower-$C^2$) functions.

Methods

The authors propose the Modified Gradient Sampling (mGS) algorithm. Its core logic follows these steps:

  1. Oracle-Based Approximation: Since the objective function is defined by an inner maximization (finding the "worst-case" scenario), the algorithm uses an "oracle"—a sub-routine that approximates this maximum to a user-defined accuracy.
  2. Gradient Sampling: At each iteration, the algorithm samples gradients at several nearby points. This allows it to "see" the different slopes meeting at a non-smooth ridge.
  3. Descent Direction: It computes the "least-norm element" from the convex hull of these sampled gradients. Essentially, it finds the direction that most reliably moves "downhill" across all nearby slopes.
  4. Limited Armijo Line Search: It performs a step-size search adapted for the fact that function values are only known approximately.
  5. Subsmooth Framework: The key theoretical innovation is proving that this process works for lower-$C^2$ functions. These are functions that can be locally represented as the maximum of a family of smooth functions, a much more realistic assumption for robust optimization than previous requirements.

Datasets

As a theoretical and algorithmic paper, it does not use standard machine learning datasets like ImageNet or GLUE. Instead, the authors evaluate the algorithm using:

  • Synthetic Numerical Examples: Specifically, a Distributionally Robust Coverage Control problem.
  • Scenario: Optimizing the placement of a team of agents (e.g., sensors or robots) across a 1D environment to cover a region where the underlying probability density is uncertain.
  • Basis Functions: They use Haar wavelets to model the uncertain density, creating a high-dimensional, non-smooth optimization landscape.

Key Insights and Ideas

  • Relaxing the Smoothness Barrier: The "aha moment" is the realization that we don't need the objective function to be smooth "almost everywhere" in the classical sense. By shifting the focus to "subsmooth" functions, the authors bridge the gap between optimization theory and practical robust engineering.
  • Handling the "Black Box": The algorithm treats the inner maximization as a black box (the oracle). This makes the mGS algorithm highly modular; as long as you have a way to approximate the worst-case scenario, mGS can optimize the outer problem.
  • Attractivity Guarantees: The authors prove "attractivity" conditions. This means that even if you start your optimization far outside the desired search space, the algorithm is mathematically guaranteed to be "pulled" into the valid region and stay there.

Key Results

  • Convergence Proof: The paper provides a rigorous mathematical proof that the mGS algorithm converges to a Clarke stationary point (the non-smooth equivalent of a local minimum) with probability one.
  • Robustness to Non-Smoothness: In simulations, standard gradient descent failed to converge because it "zig-zagged" or got stuck near non-smooth boundaries. The mGS algorithm successfully navigated these "ridges" to find the optimal agent locations.
  • Practical Utility: The algorithm successfully solved a five-agent coverage problem under distributional uncertainty, proving it can handle the complexity of multi-agent systems where agents might overlap or cross boundaries.

Limitations and Future Work

  • Computational Overhead: Sampling multiple gradients at every single step is computationally expensive, especially as the number of decision variables (dimensions) increases.
  • Oracle Precision: The algorithm's success is tied to the accuracy of the inner maximization oracle. If the oracle is too slow or inaccurate, the overall optimization suffers.
  • Future Directions: The authors suggest exploring more efficient sampling schemes (perhaps using the distributed structure of a problem) and extending the theory to even more general "bilevel" optimization problems where the inner and outer goals are more complex.

Summary updated

Abstract

This paper considers non-smooth optimization problems where we seek to minimize the pointwise maximum of a continuously parameterized family of functions. Since the objective function is given as the solution to a maximization problem, neither its values nor its gradients are available in closed form, which calls for approximation. Our approach hinges upon extending the so-called gradient sampling algorithm, which approximates the Clarke generalized gradient of the objective function at a point by sampling its derivative at nearby locations. This allows us to select descent directions around points where the function may fail to be differentiable and establish algorithm convergence to a stationary point from any initial condition. Our key contribution is to prove this convergence by alleviating the requirement on continuous differentiability of the objective function on an open set of full measure. We further provide assumptions under which a desired convex subset of the decision space is rendered attractive for the iterates of the algorithm.
BibTeX
@misc{boskos2025gradient,
  author = {Dimitris Boskos and Jorge Cortés and Sonia Martı́nez},
  title = {{Gradient sampling algorithm for subsmooth functions}},
  year = {2025},
  eprint = {2503.16638},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.16638},
  howpublished = {arXiv},
}
Figure