acceptodds
Withdrawn from ICLR 2027

Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak–Łojasiewicz Objectives

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study optimizing -smooth and -Polyak–Łojasiewicz (PL) objectives with unbiased stochastic gradients under -heavy-tailed noise (). In the unrestricted **high-dimensional** setting, we establish the noise-adaptive lower bound for attaining -suboptimal function value. Under the generalized mirror-PL condition, we propose a centered-clipped mirror-descent method that achieves a high-probability upper bound matching the lower bound up to logarithmic factors. We further provide the improved tight stochastic complexity in **fixed** dimensions.

Primary area:
optimization
Keywords:
Heavy tailed noise, High-probability guarantee, High-dimensional minimax bounds, Fixed-dimensional Improvements

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.80 over 5 reviews, above 27% of the others.
Reviewer_37FUOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates lower and upper bounds of smooth PL objectives under heavy-tailed noise. It establishes a high-dimensional lower bound consisting of deterministic cost and the heavy-tailed stochastic cost terms, which improves upon prior work. The paper then proposes centered-clipped mirror descent (CC-MD) with a high probability upper bound matching it up to logarithmic factors. The paper also studies complexity under a finite fixed problem dimension through techniques like stochastic bisection and gradient flow trapping. No experiments are conducted.

Critical strengths
  1. The lower bound proof is a solid contribution to the field, filling a gap in the existing literature.
  2. The authors propose CC-MD with high probability guarantees that nearly matches the lower bound.
Critical weaknesses
  1. The upper and lower bounds do not fully match. Even in high dimensions, the agreement is only up to logarithmic factors. More importantly, the deterministic condition number dependence remains unresolved for fixed d≥2d\geq 2, and the stochastic bounds also have a gap when d>3d>3 and α/(α−1)<d−1\alpha/(\alpha-1)<d-1. The scope of the paper's "tight" characterization should be presented more carefully; the quantitative improvement over existing high-probability PL results (Sadiev et al., 2023) also deserves a clearer comparison.

  2. The necessity of Algorithm 1's centered-clipped estimator is unclear. In the proof of Lemma C.4, Eq. (180) already establishes ∣at−∇f(xt)∣≤2rt/4\\|a_t-\nabla f(x_t)\\|\le2r_t/4 with high probability for the geometric-median pilot. This appears sufficient to apply Lemma C.5 and reproduce the same stagewise convergence proof by simply setting g^t=at\hat g_t=a_t, without the second sample collection or centered clipping. The additional design should be justified against standard median-of-means, gradient clipping, and normalization.

  3. Definition 4.1 is closely related to an existing condition. The proposed mirror-PL is precisely the Bregman forward-backward envelope Dρ(x)\mathcal D_\rho(x) of Fatkhullin & He (2024, Assumption 4.6) when the nonsmooth term vanishes and ρ=L\rho=L. Their 22-Bregman Prox-PL condition has the same inequality form, although the parameter requirements in the two analyses differ. The authors cite Fatkhullin & He (2024) but should explicitly explain this connection and avoid presenting the geometric condition itself as a new contribution.

  4. The paper provides little practical insight or motivation for a broader deep learning audience. PL optimization is an important theoretical subject, but the manuscript offers neither numerical experiments nor concrete learning problems illustrating when its global PL or mirror-PL assumptions and heavy-tailed oracle model apply. For an ICLR submission, a more compelling discussion of practical relevance would be valuable even if the paper remains entirely theoretical.

  5. The presentation needs careful polishing. The prose often has an overly mechanical, AI-polished feel, with repetitive exposition, AI-generated notation, awkward punctuation, and inconsistent writing conventions. The concern here is the quality of presentation, not the use of AI tools itself. The bibliography also contains duplicate entries (e.g., Arjevani et al., 2023a/2023b, and Cutkosky and Mehta, 2021a/2021b). These all confirm the need for a more careful review of the presentation.

  6. Regarding the paper's format, it seems the text fonts differ from default ICLR format. The authors should ensure the text is formatted correctly for the ICLR submission.

Questions for authors
  1. Is the centered-clipped half of the estimator in Algorithm 1 actually necessary? In particular, Eq. (180) of Lemma C.4 seems to imply that the geometric median pilot ata_t alone satisfies the estimation error condition used in Lemma C.5, with the same order of oracle complexity and roughly half as many samples per estimator call. Does any step of Theorem 4.3 fail if g^t\hat g_t is replaced directly by ata_t? If not, what theoretical or practical advantage does the additional clipping provide?
  2. Can the authors clarify which assumptions or guarantees genuinely require centered clipping instead of conventional clipping, normalization, or a median-of-means estimator, especially on unbounded domains?
Reviewer_W7SROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This work studies smooth PL optimization problems under heavy-tailed noise. In the high-dimensional setting, the authors establish matching upper and lower bounds on the stochastic gradient oracle complexity and propose a centered-clipped mirror descent algorithm that achieves the upper bound. Furthermore, they derive complexity bounds for fixed-dimensional problems.

Critical strengths
  • The paper establishes matching upper and lower bounds in the high-dimensional setting up to logarithmic factors, thus providing tight convergence guarantees for stochastic optimization under the PL condition and heavy-tailed noise.
  • The paper further provides complexity bounds for fixed-dimensional problems, establishing matching upper and lower bounds in one dimension and deriving dimension-specific bounds for higher-dimensional settings.
Critical weaknesses
  • The paper is not very clearly written, making it difficult to follow in several parts. Specifically, the theoretical results are not sufficiently motivated. The explanations of the intuition and main ideas behind these results (e.g., in the paragraphs following Theorems 4.3, 5.1, and 5.2) are somewhat difficult to follow. Maybe a more detailed presentation with intermediate derivations would have been preferable. Overall, in my opinion, substantial revisions to the writing and organization are needed to improve the clarity of the paper.
  • The design of Algorithm 1 could be better motivated. A more detailed discussion of the design choices and their role in obtaining the convergence guarantees would strengthen the presentation.
  • The parameter choices in Theorem 4.3 depend on unknown problem and noise parameters. For example, the number of stages SS and the clipping thresholds rsr_s depend on the optimality gap Δ0\Delta_0, and the block sizes bsb_s depend on the noise parameters σ\sigma and α\alpha.
  • One minor limitation is that the fixed-dimensional bounds in Theorem 5.2 are not entirely tight for d≥2d\geq 2, as there remains a gap between the upper and lower bounds in their dependence on the condition number κ\kappa.
Questions for authors

See weaknesses.

Reviewer_CsuGOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the stochastic first-order complexity of smooth nonconvex optimization under a heavy-tailed stochastic-gradient oracle. The authors consider objectives satisfying a global Polyak--Lojasiewicz (PL) condition and assume that the stochastic gradient has a finite centered α\alpha-moment for 1<α≤21< \alpha \leq 2.

The main theoretical result is a high-dimensional lower bound showing that any adaptive randomized gradient-only algorithm requires \begin{align*} \Omega\left( \kappa\log\frac{\Delta_0}{\epsilon} + \kappa \left(\frac{\sigma^2}{\mu\epsilon}\right)^{\theta_\alpha} \right) \end{align*} stochastic-gradient oracle calls, under sufficiently large condition number and dimension. The paper also develops a high-probability upper bound based on centered clipping and mirror descent under a μ\mu-mirror-PL condition. In the unconstrained Euclidean case, the mirror-PL condition reduces to the standard PL condition, and the resulting upper bound matches the lower bound up to logarithmic factors.

The paper further investigates the dependence on dimension and provides refined lower and upper bounds for fixed-dimensional settings. Overall, the paper provides a technically interesting characterization of stochastic optimization under heavy-tailed noise and discusses how the geometry and dimension affect the complexity.

Critical strengths

1. Interesting combination of heavy-tailed noise and PL geometry. The paper studies a meaningful setting where the objective has favorable optimization geometry while the stochastic oracle may have heavy-tailed noise. The separation between deterministic optimization difficulty and stochastic estimation difficulty is conceptually interesting.

2. Strong lower-bound construction. The high-dimensional lower bound considers arbitrary adaptive randomized gradient-only algorithms and uses carefully constructed hard instances involving hidden directions and heavy-tailed oracle observations. The resulting lower bound captures both the deterministic transient and the stochastic estimation cost.

3. Upper and lower bounds are closely related. The proposed centered-clipping mirror-descent method provides a high-probability upper bound whose dependence on κ\kappa, σ\sigma, μ\mu, and ϵ\epsilon is consistent with the main lower bound, up to logarithmic factors. The discussion of the distinction between ordinary PL and mirror-PL in constrained domains is also useful.

4. The paper goes beyond the high-dimensional setting. The fixed-dimensional results are valuable because the main high-dimensional lower bound requires a dimension that can grow with the target accuracy. The additional analysis helps clarify how the complexity changes when the dimension is fixed.

Critical weaknesses

1. The global PL assumption may be quite strong for the claimed machine-learning relevance. The main lower bound assumes that the objective is globally LL-smooth and globally μ\mu-PL. Although PL is weaker than convexity and allows nonconvex functions, the global PL condition is still a strong structural assumption for realistic neural-network training objectives. The paper does not provide a concrete neural-network training example satisfying the global PL condition together with the heavy-tailed stochastic-gradient oracle assumption. Thus, it is not clear how directly the theoretical characterization applies to practical neural-network optimization.

2. The dimension requirement of the main lower bound is restrictive. Theorem 3.1 requires \begin{align*} d\geq d_{\mathrm{hd}}, \qquad d_{\mathrm{hd}} = \widetilde O_\alpha\left( \kappa^2 \left[ \frac{\Delta_0}{\epsilon}+Q_\epsilon \right] \right). \end{align*} In particular, the required dimension grows as ϵ\epsilon becomes smaller. This is a substantial restriction and means that the main lower bound is not directly a fixed-dimensional result. Although Section 5 provides fixed-dimensional refinements, the practical interpretation of the high-dimensional lower bound remains unclear.

3. The connection between the abstract heavy-tailed oracle and practical stochastic gradients is unclear. The lower bound allows a very general stochastic-gradient oracle satisfying only an unbiasedness condition and a finite centered α\alpha-moment. The hard instances use specially constructed heavy-tailed oracle distributions. It is unclear whether such oracles can arise from standard finite-sum or population-risk stochastic gradients. Consequently, the connection between the oracle lower bound and the complexity of practical stochastic-gradient training could be discussed more carefully.

4. The meaning of “matched” could be stated more precisely. The paper describes the upper and lower bounds as matched. The dependence on ϵ\epsilon is indeed the same, but the two results differ in their guarantee: the lower bound is stated in expectation/constant confidence, whereas the upper bound is high probability and hides logarithmic factors. Moreover, the upper bound is obtained for a specific mirror-descent algorithm under mirror-PL, whereas the lower bound applies to arbitrary gradient-only algorithms under ordinary global PL. Thus, “matched” should be understood as matching the main parameter dependence up to logarithmic factors, rather than as an exact characterization under identical settings.

Questions for authors

1. Global PL and neural-network training. Can the authors provide concrete nontrivial examples of neural-network or other machine-learning objectives that satisfy the global LL-smooth and μ\mu-PL conditions assumed in Theorem 3.1? In particular, are these conditions expected to hold globally for any practically relevant neural-network training problems, or should the results primarily be viewed as a theoretical characterization for the PL function class?

2. Dimension requirement. Theorem 3.1 requires \begin{align*} d\geq \widetilde O_\alpha\left( \kappa^2 \left[ \frac{\Delta_0}{\epsilon}+Q_\epsilon \right] \right). \end{align*} Is the dependence of the required dimension on 1/ϵ1/\epsilon intrinsic to the problem, or is it mainly an artifact of the particular hidden-direction/zero-chain construction used in the proof? Could a similar lower bound be established in a dimension independent of ϵ\epsilon?

3. Heavy-tailed stochastic-gradient oracle. Can the authors provide examples where the heavy-tailed oracle used in the lower-bound model is realized by stochastic gradients arising from a standard finite-sum or population-risk objective? If not, how should the lower bound be interpreted in the context of practical stochastic-gradient optimization?

4. Mirror-PL condition. Can the authors provide nontrivial machine-learning examples satisfying the μ\mu-mirror-PL condition on a genuinely constrained or non-Euclidean domain? Since mirror-PL reduces to ordinary PL in the unconstrained Euclidean case, such examples would help clarify the additional practical scope provided by the mirror formulation.

5. Meaning of “matched.” Table 1 describes several results as “Matched” or “Stochastic term matched.” Could the authors clarify precisely what notion of matching is intended? In particular, the lower bound is in expectation/constant confidence, whereas the upper bound is high probability and hides logarithmic factors. Is the claim intended to mean matching dependence on κ,σ,μ,ϵ\kappa,\sigma,\mu,\epsilon up to logarithmic factors, rather than matching the exact complexity under identical success criteria?

6. Fixed-dimensional versus high-dimensional results. How should the high-dimensional lower bound in Theorem 3.1 be related to the fixed-dimensional results in Section 5? In particular, which result should be regarded as the main characterization for applications in machine learning, where the dimension is large but fixed for a given model and does not normally grow as the target accuracy ϵ\epsilon decreases?

Reviewer_sNbnOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper characterizes the optimal first-order oracle complexity of minimizing smooth PL objectives under conditionally unbiased stochastic gradients satisfying only a finite centered α\alpha-moment. The central question is to pin down the joint dependence on the condition number κ\kappa, noise level σ\sigma, accuracy level ϵ\epsilon, tail exponent α\alpha, and dimension dd, in a way that is noise-adaptive (recovers the exact-gradient complexity as σ\sigma goes to 0), which holds with high probability.

Critical strengths
  1. It seems to me that the complexity of PL optimization under heavy-tailed noise has not been pinned down in a noise-adaptive, dimension-aware, high-probability framework. The paper does this, and the answer is clean: κAϵ+κQϵ\kappa A_{\epsilon}+\kappa Q_{\epsilon} in high dimension, with a genuine dimension-dependent separation in the stochastic term for fixed dd.

  2. Technically, the separation into two logically independent hard families, a Bernoulli-thinned stochastic chain and a geometrically weighted exact chain, is the right idea, thus I think the lower bound is the technical centerpiece.

Critical weaknesses

The bound is tight only in a narrow regime, thus I think the "tightness" claim is overstated. In fixed dimension d=1d=1, the complexity is fully matched. It is good. In fixed dimension d=2,3d=2,3, only the stochastic term is matched. For d>3d>3, the phase-diagram entry (Eq. 23) is explicitly not claimed tight ("No necessity claim is made for the extra factor"). That is a substantial regime of the parameter space. So the headline claim of "tight complexity" is valid only in d=1d=1 and in the high-dimensional asymptotic regime. The abstract and introduction should be substantially weakened.

  1. The lower bound's dimension threshold is very large: the high-dimensional lower bound holds in dimension dhdd_{hd}. For example, when κ=10\kappa = 10 and Δ0/epsilon=1000\Delta_0/epsilon=1000, this is already dimension \tiledO(105)\tiled O(10^5), For larger κ\kappa, it is enormous. Given that the fixed-dimensional results show a genuinely different complexity in d=1d=1 (no κ\kappa-multiplier on the stochastic term), the gap between "fixed dd” and d=O(κ2Qϵd=O(\kappa^2 Q_{\epsilon}" is large and unexplained.

  2. The upper bound is presented as matching, but it is only for mirror-PL, which is strictly stronger than PL on constrained domains

  3. Theorem 5.1 is stated for expected risk, while Theorem 5.2 is stated for high-probability complexity. The expected-risk to high-probability reduction for the fixed-dimensional lower bound is not spelled out.

Questions for authors

It seems to me the PL condition is too strong, it will be better if the authors could provide some real examples in machine learning/deep learning. In addition, I am wondering if there are any real applications that match the studied problem settings (PL, heavy tailed, smoothness, and so on)

  1. The authors did not provide any numerical experiments to verify the theoretical findings. It is very important if the authors can conduct some experiments.

  2. Algorithm 1 presents “clipped” method, which is not very applicable in real applications.

Reviewer_ahZxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents upper bounds as well as lower bound for the generalization performance under PL objectives with unbiased stochastic gradients.

Overall the results are interesting, but many are very close to existing work and the distinction and improvements should perhaps be better highlighted.

Overall I would sharpen the following discussions:

  • The lower bound improves over Yue et al. Which gave the same rate to deterministic algorithms. Here the improvement is that the lower bound is also for non-deterministic algorithms. But as the author state, the technical leap is overall standard (Arjevani et al.).
  • The comparison with Masiha should also be further developed: Yes, you explain the technical differences between the model, but you might want to add a discussion about the conceptual difference. In a particular, how that difference translates to different technical challenges.
  • Explicitly quantify the improvement in the upper bound compared to Sadiev.

Finally, I found all the "Idea" paragraphs almost useless. They are mostly dense, with abundance of information which is unclear and not clear what are the important contributions, challenges etc..

Critical strengths

The overall results are novel, and improvements over the existing literature.

Critical weaknesses

Further discussion on the technical depth of the contributions.

Questions for authors

no questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.