Non-KKT Accumulation in Entropic Mirror Descent

A fundamental question in optimization is whether every accumulation point of a bounded mirror descent sequence—under appropriate stepsize conditions—must be a Karush-Kuhn-Tucker (KKT) stationary point. While this property holds for standard Euclidean methods like gradient descent, it has remained an open question for mirror descent, particularly in nonconvex settings where the Bregman divergence kernel may exhibit boundary blow-up.

The authors analyze the behavior of mirror descent using the Shannon entropy kernel on the nonnegative orthant and the probability simplex. They construct smooth, nonconvex objective functions and specific initialization sequences such that the mirror descent iterates track a continuous mirror-flow trajectory. To ensure the discrete iterates inherit the full accumulation set of the continuous flow, the authors introduce a smooth correction term, flat near the limiting circle, which forces the discrete sequence to lie exactly on the continuous trajectory. This construction allows them to demonstrate that the accumulation set contains non-KKT points.

The study provides the first counterexamples to KKT accumulation for bounded mirror descent sequences with nonincreasing objective values. Specifically, for the nonnegative orthant (n >= 3) and the probability simplex (n >= 4), the authors show that the accumulation set is a smooth boundary curve containing a relatively open arc of non-KKT points. The pathology is shown to stem from the inherent degeneracy of the Bregman geometry at the boundary, rather than from improper stepsize choices or a failure of the descent property.

This work resolves a long-standing theoretical ambiguity regarding the convergence of mirror descent. It demonstrates that standard Bregman-based optimization methods, which are widely used in machine learning and optimal transport, do not inherently guarantee convergence to KKT points in nonconvex landscapes. This highlights a critical limitation in the reliability of mirror descent for finding stationary points in constrained optimization problems where the boundary geometry is non-trivial.