Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective

Jelena Diakonikolas, Cristóbal Guzmán

TL;DR

This paper introduces a new lens for nonsmooth optimization: Bounded Local Subgradient Variation (BVG). By measuring how much a function's slope changes within small local regions—rather than just relying on a global Lipschitz constant—the authors derive more fine-grained complexity bounds and demonstrate that parallelization can provide massive speedups for specific classes of nonsmooth problems, such as piecewise-linear functions.

What Problem Does This Paper Address?

In the world of optimization, "nonsmooth" functions (those with sharp kinks or discontinuous gradients) are notoriously difficult. Traditional theory relies on the Lipschitz constant, which essentially bounds the maximum possible slope of the function. However, this is a "coarse" metric. Two functions might have the same global Lipschitz constant, but one might be "nearly smooth" everywhere except for a single point, while the other is jagged throughout.

Current complexity bounds often fail to distinguish between these cases, leading to pessimistic worst-case results. Furthermore, randomized smoothing—a common technique to handle nonsmoothness—often introduces a heavy dependence on the dimension ($d$), making it impractical for high-dimensional problems. This paper seeks to answer: What specific structures make some nonsmooth problems easier than others, and how can we exploit them?

Methods

The authors propose two new regularity conditions that define "Optimization on a Finer Scale":

  1. BVGmax (Bounded Maximum Local Variation): This requires that the subgradient doesn't change by more than a constant $L_r$ within a small radius $r$.
  2. BVGavg (Bounded Mean Local Oscillation): A weaker, average-case version inspired by Bounded Mean Oscillation (BMO) in harmonic analysis.

They analyze these properties using two primary algorithmic frameworks:

  • AGD+ (Accelerated Gradient Descent): Applied to convex problems. They show that BVGmax functions behave like "approximately smooth" functions, allowing for quadratic upper bounds that lead to faster convergence.
  • Randomized Smoothing: They use convolution with a uniform kernel over a ball to create a smooth approximation ($f_r$). Crucially, they prove that the "closeness" of this approximation depends on the mean width of the subgradient set around the optima.
  • Goldstein’s Method: For nonconvex, nonsmooth problems, they generalize this method to work with the local BVG constant rather than the global Lipschitz constant.

Datasets

As a theoretical paper focused on oracle complexity and convergence analysis, no empirical datasets were used. Instead, the authors provide several constructive mathematical examples (e.g., Examples 3.9, 3.10, and 3.11) to prove that the BVG class is strictly richer than the Lipschitz class and to demonstrate how local variation can be exponentially smaller than global Lipschitz constants.

Key Insights and Ideas

  • Slope Variation vs. Growth: The "bottom line" is that the complexity of an optimization problem is determined not by how fast the function grows, but by how rapidly its slope changes over small distances.
  • The Power of Parallelism: One of the most striking insights is that parallel oracle complexity for nonsmooth Lipschitz convex optimization can be significantly lower than sequential complexity. For piecewise-linear functions with a polynomial number of pieces, the dependence on dimension $d$ can be reduced from $\text{poly}(d)$ to nearly dimension-independent $O(\ln(d)^{1/4})$.
  • Resolving the Lower Bound Contradiction: Existing lower bounds suggest that parallelizing nonsmooth optimization shouldn't help much. The authors resolve this by noting that those lower bounds assume queries are confined to a unit ball. By using randomized smoothing (which queries slightly outside the local region), they bypass these traditional barriers.
  • Mean Width Matters: The complexity of parallel optimization is directly tied to the "geometric complexity" (mean width) of the subgradient set near the minimizer. A "simple" subgradient set leads to much faster convergence.

Key Results

  • Convex Complexity: They establish that for BVGmax functions, the iteration complexity is $O(\frac{L_r}{r\epsilon} \|x_* - x_0\|_2 + \frac{L_r^2 \|x_* - x_0\|_2^2}{\epsilon^2})$. This replaces the standard Lipschitz constant with the potentially much smaller local variation constant $L_r$.
  • Nonconvex Complexity: For nonconvex problems, they show that a $(\delta, \epsilon)$-stationary point can be found in $O(\frac{\Delta L_r^2}{\epsilon^3 \delta} \ln \frac{\Delta}{\epsilon \delta \beta})$ queries, independent of the global Lipschitz constant.
  • Parallel Speedup: They demonstrate the first positive result for parallelizing a non-trivial class of nonsmooth problems (piecewise-linear) where the "depth" of the algorithm is essentially dimension-independent.

Limitations and Future Work

  • Parameter Tuning: The current results often require knowing (or estimating via line search) the radius $r$ and the variation constant $L_r$. The authors suggest that developing fully "parameter-free" versions of these algorithms is a key next step.
  • Higher-Order Methods: The paper focuses on first-order (gradient-based) methods. Exploring whether second-order or higher-order optimization can further exploit BVG structure is an open question.
  • Adaptivity: While the paper discusses local variation, the algorithms aren't yet fully adaptive to changing local variation as they move through the search space; they currently rely on a fixed radius $r$. Integrating recent adaptive gradient techniques into the BVG framework remains a promising research direction.

Summary updated

Abstract

We initiate the study of nonsmooth optimization problems under bounded local subgradient variation, which postulates bounded difference between (sub)gradients in small local regions around points, in either average or maximum sense. The resulting class of objective functions encapsulates the classes of objective functions traditionally studied in optimization, which are defined based on either Lipschitz continuity of the objective or H\"{o}lder/Lipschitz continuity of its gradient. Further, the defined class contains functions that are neither Lipschitz continuous nor have a H\"{o}lder continuous gradient. When restricted to the traditional classes of optimization problems, the parameters defining the studied classes lead to more fine-grained complexity bounds, recovering traditional oracle complexity bounds in the worst case but generally leading to lower oracle complexity for functions that are not ``worst case.'' Some highlights of our results are that: (i) it is possible to obtain complexity results for both convex and nonconvex problems with the (local or global) Lipschitz constant being replaced by a constant of local subgradient variation and (ii) mean width of the subdifferential set around the optima plays a role in the complexity of nonsmooth optimization, particularly in parallel settings. A consequence of (ii) is that for any error parameter $\epsilon > 0$, parallel oracle complexity of nonsmooth Lipschitz convex optimization is lower than its sequential oracle complexity by a factor $\tilde{\Omega}\big(\frac{1}{\epsilon}\big)$ whenever the objective function is piecewise linear with polynomially many pieces in the input size. This is particularly surprising as existing parallel complexity lower bounds are based on such classes of functions. The seeming contradiction is resolved by considering the region in which the algorithm is allowed to query the objective.
BibTeX
@inproceedings{diakonikolas2026optimization,
  author = {Jelena Diakonikolas and Cristóbal Guzmán},
  title = {{Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective}},
  booktitle = {SIAM},
  year = {2026},
  doi = {10.1137/24m1659510},
}
Figure