# Lower Complexity Bounds for Minimizing Regularized Functions

arXiv: https://arxiv.org/abs/2202.04545 · HTML: https://mlsanity.com/paper/2202.04545/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2022.

## Built on by (most cited first, 2 of 2)

- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity](https://mlsanity.com/paper/2409.10773/) (2024)

## Abstract (arXiv)

In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of the objective. The smooth part has H"older continuous gradient of degree nu ∈ [0, 1] and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order O(k- p(1 + 3nu) / (2(p - 1 - nu))) for the functional residual, where k is the iteration counter and p is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes O(k-6). It can be achieved by the Fast Gradient Method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.