acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Subgradient Descent at Sharply Repulsive Points: A Bounded Noise Counterexample and Gaussian Noise Avoidance

Abstract

Motivated by the open question of Bianchi, Hachem, and Schechtman (Bianchi et al., 2024, Remark 4), we show that in the non-weakly convex definable setting, omnidirectional noise with conditional fourth-moment control does not suffice for universal almost-sure avoidance of sharply repulsive critical points. We demonstrate this failure by constructing a globally Lipschitz, coercive, definable objective that is not weakly convex. For this objective and its sufficiently small linear perturbations, stochastic subgradient descent with independent noise uniformly distributed on a ball in converges with probability 1 to a nonminimal sharply repulsive critical point from every initial point in a specified ball. A two-cycle argument establishes uniform bounds on the rescaled iterates, yielding convergence to the sharply repulsive critical point. In contrast, for locally Lipschitz definable objectives, Gaussian noise ensures simultaneous almost-sure avoidance of any finite collection of sharply repulsive points. Through a construction of difference quotient functions, we show that convergence to any such point with positive probability would produce a stationary distribution with expected descent , whereas a global positive lower bound on the Fréchet subgradient norms of the limiting functions forces strictly positive expected descent under the same distribution. This contradiction proves avoidance, with the everywhere positive Gaussian density playing a key role.

Primary area:
optimization
Keywords:
Stochastic subgradient descent, Lipschitz continuous functions, Sharply repulsive points, Counterexample, Gaussian noise

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_CcdbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper disproves the following conjecture: the non-weakly convex definable setting, for locally Lipschitz objectives, centered omnidirectional noise with conditional fourth-moment bounded is sufficient for SGD to avoid nonminimal sharply repulsive critical points (admits an active manifold MM, is a local minimizer when restrict to MM and is Clarke critical but not limiting critical). To show this, the paper gives a counterexample on R2R^2 and uses a two-cycle argument to establish convergence to 0 (sharply repulsive) with probability 1.

On the other hand, the paper shows that, when the noise is not only centered and omnidirectional but also has bounded second moment, and the density is bounded, continuous, and everywhere positive, it is sufficient to avoid such critical points.

Critical strengths
  • The paper disproves an open conjecture, with an explicit example. The example is also for globally Lipschitz, coercive (more than what's the conjecture requires). The proof is clearly explained: the two-cycle argument shows how bounded rescaled oscillations become convergence to 0 as step sizes shrink.
  • The paper provides a complementary positive result and helps to distinguish insufficient noise assumptions from sufficient ones.
  • The proof of theorem 3.1 is provided through difference quotient rescaling combined with a stationary distribution contradiction, which could be useful for studying nonsmooth dynamics.
Critical weaknesses
  • The main weakness of the paper is that Theorem 3.1 only establishes avoidance to points with 0∉∂Lf(x)0 \notin \partial_L f(x) but not convergence of SGD. The paper also does not establish avoidance of active strict saddles beyond weak convexity in general.
Questions for authors
  • Is it possible to establish escape time in Theorem 3.1, ie, the number of iterations needed to leave a chosen neighborhood of the bad point? What about convergence in Theorem 3.1?
  • Is everywhere positivity a necessary condition, can it be more general?
  • What are the challenges to establish avoidance of active strict saddles beyond weak convexity?
Reviewer_gWY9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Summary

This paper provides a counterexample that disproves a conjecture from [1] on the noise assumption for escaping saddle points in nonsmooth nonconvex optimization. The authors provide a 2D example to demonstrate convergence to a sharply repulsive critical point. The main result also shows that under Gaussian noise, avoidance of a sharply repulsive critical point is achievable. A toy experiment validates the theoretical finding.

Critical strengths

Strength

The paper addresses a concrete problem in the literature. The counterexample is neat and intuitive. The authors also provide a nice diagram that illustrates the proof idea.

Critical weaknesses

Weaknesses

I have two concerns on the presentation of the main results

  1. Assumptions for the two main results The main result now contains a restriction on the stepsize. In [1], the authors establish avoidance under 1) noise assumption 2) weak convexity 3) any stepsize schedule of form Θ(1/nα),α∈(1/2,1]\Theta(1/n^{\alpha}), \alpha \in (1/2, 1]. However, Theorem 2.1 only contains the case α=1\alpha = 1, and strictly speaking, it is not sufficient to disprove the conjecture. On page 24, the paper briefly discusses how the result extends to α∈(1/2,1]\alpha \in (1/2, 1]. But the current results are not satisfying.

    A similar issue happens to the Gaussian avoidance result. The avoidance explicitly assumes Gaussian noise, which is quite restrictive in my opinion. From the paper's discussion, it looks like what you really need is that the noise distribution has a positive support everywhere. It would be better to state the avoidance result by providing a general condition on the noise assumption.

  2. The scope of this result seems narrow.

    The paper's motivation is essentially the noise assumption from [1]. Although the analysis techniques look solid and interesting, it is technically very heavy and dense. I find the proof details hard to follow, especially because of the overwhelming amount of notation. Given the short ICLR review period, I feel this paper is better suited to a journal publication.

Overall, I think the paper tackles a concrete problem with interesting ideas. But given the density of the technical material and the current presentation quality, I recommend weak rejection and believe the paper is more suitable for a journal publication.

Questions for authors

Questions

  1. Could you address the two restrictions on the main results?

References

[1] Bianchi, P., Hachem, W., & Schechtman, S. (2024). Stochastic subgradient descent escapes active strict saddles on weakly convex functions. Mathematics of Operations Research, 49(3), 1761-1790.

Reviewer_FPWWOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The manuscript studies the ability of stochastic subgradient algorithms to escape non locally optimal critical points. This problem has been studied extensively for smooth costs, where critical points correspond to first-order stationary points. In this setting, the problem is that of escaping from saddle-points. The present manuscript investigates the more general non-differentiable setup. In this context, it is known that escape from critical points will occur as long as the function is weakly convex. The authors relax this condition.

In particular, the authors show that when the noise is bounded uniformly, the stochastic subgradient algorithm may get stuck in repulsive critical points by constructing a counterexample (2). On the other hand, if the density of the noise is non-zero everywhere, the authors establish escape from non locally optimal critical points.

Critical strengths

The manuscript makes a clear contribution. The arguments appear sensible and as far as I can tell correct.

Critical weaknesses

It is unclear how much value there is in dropping the weak convexity condition, since it is naturally satisfied in most non-convex learning problems. There are no rates or finite-time guarantees attached to the ability to successfully escape these points.

Questions for authors

Is there a practical non-convex loss function which falls into the setting considered by the authors but does not satisfy weak convexity? If yes, what is it? If not, why do we need to worry about dropping weak convexity? Are there any rate or finite time guarantees that can be derived in this case? What are the analytical novelties that allowed the authors to go beyond previous results established for weakly convex costs?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.