Abstract
In nonsmooth optimization, traditional complexity analysis often relies on the global Lipschitz constant, a metric that can be overly pessimistic by failing to account for local structural regularities. This paper introduces the concept of Bounded Local Subgradient Variation (BVG) to provide a more nuanced "finer scale" perspective. By measuring subgradient changes within small local regions, the authors derive improved complexity bounds for both convex and nonconvex problems. Notably, this framework reveals that specific classes of nonsmooth problems, such as piecewise-linear functions, can achieve significant speedups through parallelization, effectively reducing the dependence on dimensionality.
Introduction: Beyond the Lipschitz Constant
Nonsmooth functions—those containing sharp kinks or discontinuous gradients—are ubiquitous in machine learning and operations research. Historically, the difficulty of optimizing these functions has been quantified by the Lipschitz constant $L$, which bounds the maximum possible slope. However, $L$ is a "coarse" global property. It cannot distinguish between a function that is smooth everywhere except for a single point and one that is jagged throughout its domain.
This lack of granularity leads to worst-case complexity results that may not reflect the actual difficulty of a specific problem instance. Furthermore, standard techniques like randomized smoothing often introduce a heavy dependence on the dimension $d$, limiting their utility in high-dimensional settings. This research addresses these gaps by asking: what specific structures make some nonsmooth problems easier than others, and how can we exploit them?
The BVG Framework: Optimization on a Finer Scale
The authors propose two primary regularity conditions to capture local behavior:
- BVGmax (Bounded Maximum Local Variation): This condition stipulates that the subgradient does not change by more than a constant $L_r$ within a small radius $r$.
- BVGavg (Bounded Mean Local Oscillation): A weaker, average-case version inspired by Bounded Mean Oscillation (BMO) in harmonic analysis, focusing on the expected variation.
As illustrated in the figure above, the local variation $r$ provides a lens to see how "nearly smooth" a function is. While both $f_1$ and $f_2$ might share the same global Lipschitz constant, their local subgradient variations differ significantly, which directly impacts optimization complexity.
Algorithmic Strategies
The paper analyzes these properties through three main algorithmic lenses:
- Accelerated Gradient Descent (AGD+): When applied to convex BVGmax functions, the authors show these functions behave like "approximately smooth" objectives. This allows for the application of quadratic upper bounds, leading to faster convergence rates than those predicted by standard Lipschitz theory.
- Randomized Smoothing: The authors use convolution with a uniform kernel over a ball to create a smooth approximation $f_r$. They prove that the fidelity of this approximation depends on the mean width of the subgradient set around the optima, rather than just the global slope.
- Goldstein’s Method: For nonconvex, nonsmooth problems, the authors generalize this classic method to utilize the local BVG constant $L_r$ instead of the global Lipschitz constant $L$, providing more efficient stationary point guarantees.
Key Insights: The Power of Parallelism
One of the most significant contributions of this work is the demonstration of parallel speedups for nonsmooth optimization. Traditional lower bounds suggest that parallelizing nonsmooth Lipschitz convex optimization offers little benefit. However, the authors resolve this contradiction by noting that those bounds assume queries are strictly confined to a unit ball.
By employing randomized smoothing—which queries slightly outside the immediate local region—the authors bypass these traditional barriers. For piecewise-linear functions with a polynomial number of pieces, they show the dependence on dimension $d$ can be reduced from $\text{poly}(d)$ to a nearly dimension-independent $O(\ln(d)^{1/4})$. This suggests that the complexity of parallel optimization is fundamentally tied to the "geometric complexity" (mean width) of the subgradient set near the minimizer.
Results and Complexity Bounds
The theoretical analysis yields several improved bounds:
- Convex Case: The iteration complexity for BVGmax functions is established as $O(\frac{L_r}{r\epsilon} \|x_* - x_0\|_2 + \frac{L_r^2 \|x_* - x_0\|_2^2}{\epsilon^2})$. Here, the standard Lipschitz constant is replaced by the potentially much smaller local variation constant $L_r$.
- Nonconvex Case: 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, removing the dependence on the global Lipschitz constant.
- Parallel Efficiency: The work provides the first positive result for parallelizing a non-trivial class of nonsmooth problems where the algorithm's "depth" is essentially independent of the dimension.
Conclusion and Future Directions
By shifting the focus from global growth to local slope variation, the BVG perspective offers a more accurate reflection of optimization difficulty. While this framework provides a robust theoretical foundation, several avenues for future work remain. Key among these is the development of "parameter-free" algorithms that do not require prior knowledge of the radius $r$ or the variation constant $L_r$. Additionally, exploring how second-order methods or fully adaptive gradient techniques might further exploit BVG structures could lead to even more efficient optimization routines.
Summary updated