- 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
- The lower bound proof is a solid contribution to the field, filling a gap in the existing literature.
- The authors propose CC-MD with high probability guarantees that nearly matches the lower bound.
Critical weaknesses
-
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 , and the stochastic bounds also have a gap when and . 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.
-
The necessity of Algorithm 1's centered-clipped estimator is unclear. In the proof of Lemma C.4, Eq. (180) already establishes 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 , without the second sample collection or centered clipping. The additional design should be justified against standard median-of-means, gradient clipping, and normalization.
-
Definition 4.1 is closely related to an existing condition. The proposed mirror-PL is precisely the Bregman forward-backward envelope of Fatkhullin & He (2024, Assumption 4.6) when the nonsmooth term vanishes and . Their -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.
-
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.
-
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.
-
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
- 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 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 is replaced directly by ? If not, what theoretical or practical advantage does the additional clipping provide?
- 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?