Many learning objectives are unchanged when interchangeable parts are swapped. Examples include the centers in $k$-means, the planes in hyperplane clustering, the community parameters in a stochastic block model, and the hidden units of a network layer. Exact combinatorial solvers handle this redundancy with symmetry-breaking constraints: extra inequalities, such as "center 1's first coordinate is at most center 2's", that keep one representative of each set of equivalent solutions. As these problems move from exact solvers to stochastic gradient methods (gradient steps on random minibatches, often with heavy-tailed noise), the natural move is to bring the constraints along, either as a projection step or as a penalty.
We argue this transplant is the wrong one. For block-permutation symmetries, projecting onto a coordinate-ordering cone creates artificial walls where a run can stall. The useful operation is different: periodically fold the iterate onto its nearest-to-a-reference equivalent copy, an alignment by relabeling. Folding never changes the objective and never shrinks the noise. It also satisfies the same distance-contraction inequality that projection does. That last property lets existing high-probability analyses, which bound the failure rate of a single run rather than its average behavior, go through with the distance to the nearest copy of the optimum in place of the distance to a fixed optimum. The result is a single-run guarantee for averaged iterates in symmetric nonconvex problems, where naive averaging fails outright. We test it against exact-solver ground truth from the symmetry-breaking literature.
Core Claim
Let $G$ be a finite group of relabelings acting on parameters $x$, with $f(gx)=f(x)$ for all $g\in G$. Fix a reference point $r$. Its Dirichlet cell is the set of points that are at least as close to $r$ as any of their relabeled copies are; folding maps $x$ to the copy $gx$ in that cell, which amounts to Hungarian-style alignment to $r$. We make three claims.
The first is negative. Projected stochastic gradient descent onto the coordinate-ordering cones used in exact formulations creates boundary stationary points. These cones follow the label-ordering constraints of Community detection in the stochastic block model by mixed integer programming and the hyperplane ordering of Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations. The stationary points arise because $f$ is invariant under swapping whole blocks, not under reflection across the wall $c_{1,1}=c_{2,1}$. Two centers that must "pass" each other in the first coordinate are then blocked.
The second is a positive lemma. For any $x^*$ in the cell and any $y$, folding cannot increase the distance to $x^*$. Combined with $f$ being unchanged, this means the one-step descent inequality used by the white-box martingale analysis of High Probability Convergence of Stochastic Gradient Methods holds for folded SGD. It holds exactly as it does for projected SGD, but without truncating any noise component.
The third is the target theorem. Suppose $f$ is convex or Polyak–Łojasiewicz (gradient norm controls suboptimality) on a neighborhood $U$ of the solution orbit. Then clipped SGD with folding and a folded running average satisfies, with probability at least $1-\delta$, the bound
$$ f(\bar x_T)-f^* \;\le\; \mathcal{O}\!\left(\frac{d_G(x_0,x^*)^2+\sigma^2\log(1/\delta)}{T}+\frac{\sigma\, d_G(x_0,x^*)}{\sqrt{T}}\right), $$
on the event that the trajectory stays in $U$. Here $\bar x_T$ is the folded average after $T$ steps, $\sigma$ is the noise scale, and $d_G(x_0,x^*)=\min_{g}\|x_0-gx^*\|$ is the distance to the nearest copy of the optimum. The form copies the sub-Gaussian convex rate of Liu et al., with their initial distance replaced by $d_G$.
The probability of leaving $U$ is then bounded separately. That bound is a confinement statement using the bounded clipped increments and Freedman-type concentration, as in Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis. Under bounded $\mathfrak{p}$-th noise moments, we expect the $\sigma/\sqrt{T}$ term to become $T^{-(\mathfrak{p}-1)/\mathfrak{p}}$, matching From Optimization to Generalization under Heavy-Tailed Data: The Role of Gradient Clipping.
One fact shapes the whole proposal. If the noise distribution is itself unchanged by relabeling, the last folded iterate has the same law as the last unconstrained iterate folded afterward. Folding therefore cannot help last-iterate function values. Its value lies elsewhere: it makes averaging meaningful, it makes the guarantee depend on $d_G$, and it avoids the stalls that constraints introduce. The proposal is built around those three effects and claims nothing more.
Relation to Prior Work
Several papers supply the symmetry-breaking ideas we reinterpret. Symmetry Breaking Constraints: Recent Results surveys lexicographic "keep the canonical representative" constraints. Breaking symmetries in all different problems shows these collapse to a simple chain $x_1<\dots<x_n$ for interchangeable variables; that chain is the one case where the ordering cone is a well-shaped cell, and it serves as our sanity case. Efficient Symmetry Breaking for Boolean Satisfiability breaks only generator symmetries to keep overhead linear. By analogy, we fold over swaps of adjacent labels or over a Hungarian alignment rather than enumerating all of $G$. All three operate in exact search, where pruning a branch is free of side effects. In stochastic search, a constraint changes the noise dynamics, and that is the gap we study.
Two papers motivate the work and also provide ground truth: Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations and Community detection in the stochastic block model by mixed integer programming. Both certify global optima on small instances and both explicitly hit size limits; Coniglio suggests combining exact solving with subsampling. Optimizing over trained GNNs via symmetry breaking has the same character and stops at 9 atoms. We use their certified optima to measure single-run failure rates, which none of them study.
Several papers supply the convergence analysis. These are the white-box martingale construction of Liu et al., Liu's refined clipped analysis, Shestakov et al.'s decoupling of clipped SGD from dataset-size noise, and High-Probability Bounds for the Last Iterate of Clipped SGD. All of them assume an unconstrained domain or a convex constraint set and a single optimum basin. Our contribution is the folding lemma that transfers their arguments to a symmetric, multi-basin landscape.
A Sequential Quadratic Programming Method With High-Probability Complexity Bounds for Nonlinear Equality-Constrained Stochastic Optimization is the closest work combining hard constraints with high-probability rates. It handles only exact equality constraints, while symmetry-breaking constraints are inequalities. We sidestep that problem rather than extend SQP.
Two results act as constraints on the design. Equivariant Symmetry Breaking Sets shows that breaking symmetry with arbitrary noise damages equivariant models. Our fold never changes the model; it only chooses which equivalent copy is reported and averaged, so this objection does not apply. Ziyin et al. (Title) and High Probability Bounds for Non-Convex Stochastic Optimization with Momentum stress that noise and unconstrained mobility drive escape from saddles. This is the tension the file flags between constraints and escape. Folding is our answer to it: noise magnitude is preserved, and the dynamics are unchanged up to relabeling.
Research Program
The theory proceeds in three steps.
The first step proves the folding contraction lemma for Dirichlet cells of any finite isometric group, and for alignment to a moving reference, the running average. The moving reference is the delicate case: the cell drifts, so we will bound the drift by the averaging step size.
The second step characterizes the stationary points of projected SGD on coordinate-ordering cones for block permutations. We will show by construction that these are spurious for two-center $k$-means and two-plane clustering. We will also show they vanish in the pure-coordinate case covered by Puget's chain, where an invariant gradient is tangent to the walls.
The third step proves the high-probability theorem above in the light-tailed setting first, then under heavy-tailed noise with clipping. Its confinement part bounds, with probability $1-\delta$, the largest excursion of the folded trajectory from the solution orbit.
A secondary analysis covers symmetric saddles, the stochastic analogue of the "zero-bound trap". At a point where two labels coincide, the escape direction is antisymmetric. Projection replaces the escape coordinate $u$ by $\max(0,\cdot)$ and folding replaces it by $|\cdot|$. We will quantify how clipping slows escape in each case, which addresses the file's concern that clipping suppresses the noise needed to leave such points.
The algorithm itself is small. It runs clipped SGD (optionally with momentum, applying the same relabeling to the optimizer state). Every $m$ steps it folds the iterate by Hungarian alignment to the running average, then updates the running average with the folded iterate.
Baselines
The naive reference point is unconstrained clipped SGD with plain iterate averaging. It shows what happens with no symmetry treatment at all. We expect its average to collapse toward symmetric, merged configurations whenever runs switch labels. Unconstrained last-iterate clipped SGD is reported alongside it. As argued above, this baseline is equivalent in law to post-hoc canonicalization, so it is the honest bar for last-iterate quality.
The strongest stochastic competitor is the direct transplant of solver-style constraints. This is projected clipped SGD onto the ordering cone of the exact formulations: label ordering for the block model as in Serrano and Vidal, and normal-vector ordering for hyperplane clustering as in Coniglio. We also run a smooth penalty version of the same constraints. Both are the obvious thing a practitioner would try, and both are what the file's Gaps 1 and 3 propose. They will share the data, minibatch sizes, clipping rule, step-size schedule, iteration budget, and an equal grid over step size and clipping threshold.
The strongest overall method on these instances is the exact solver itself. Coniglio reports a median 40.9× speedup over the baseline solver on the low-dimensional hyperplane testbed, with 42 of 43 instances solved to global optimality versus 20 for the baseline. Serrano and Vidal report certified optima for synthetic block-model graphs up to 20 nodes, with symmetry breaking giving up to a 2× speedup. We found no reported result on Lacuna for stochastic gradient methods on $k$-HC$_2$ or the degree-corrected block model, so stochastic baselines will be run fresh.
Two ablations isolate the key ingredient. The first folds iterates but does not average. The second is a post-hoc version that stores all iterates and aligns them to the final iterate before averaging. The proposal beats the transplant if two things hold: its $(1-\delta)$-quantile optimality gap is lower at every $\delta$ tested, and its fraction of runs stalled at boundary points is near zero while projection's is not. It beats naive averaging if the averaged gap is small where naive averaging's is order one.
Why not just…?
Why not just rely on random initialization and noise to break symmetry? For the last iterate, this is exactly right, and we concede it: folding cannot improve last-iterate values when the noise is unchanged by relabeling. The proposal's claims concern averaged iterates and quotient-distance guarantees. Noise-driven symmetry breaking is precisely what causes label switching, and label switching is what ruins plain averaging. The naive-averaging baseline will show this directly.
Why not just canonicalize once at the end? For the last iterate, this is equivalent to our method. For averaging it requires storing every iterate, or choosing an alignment reference only after the fact. The post-hoc ablation tests whether online alignment to the running average loses anything. If the two match, we will report the online version as a streaming convenience, not as an accuracy gain. The theory covers both.
Why not just keep the ordering constraints but use them as soft penalties? A penalty on $c_{1,1}-c_{2,1}$ creates the same barrier as the hard wall, only softened. Centers that need to pass each other still face an uphill barrier unrelated to $f$. The penalty baseline, swept over penalty weights, tests whether any weight avoids stalling without also losing the canonicalization.
Why not just use the exact solver? On the instances where we evaluate, we do: it provides the ground truth. But the cited papers report hard size ceilings of 20 nodes and 9 atoms. Our scaling experiments go beyond those sizes, where no certificate exists. In that regime, a single-run probability bound is the only guarantee available.
Proposed Experiments
The first testbed is low-dimensional $k$-hyperplane clustering on Coniglio's instances, using the certified global optima. For each instance and method we run 1,000 seeds and plot the empirical $(1-\delta)$-quantile of the optimality gap against $\log(1/\delta)$. Tails that decay exponentially, as the theory predicts, appear as a straight line; heavy-tailed failures bend upward.
The second testbed is degree-corrected block models of up to 20 nodes with Serrano–Vidal exact optima, using a continuous soft-assignment likelihood. Hub-node degree heterogeneity is varied to induce heavy-tailed gradient noise. This tests the clipped heavy-tailed version of the theorem.
The third testbed is a controlled synthetic study. We take a permutation-invariant objective and add Pareto gradient noise with tail parameter in $\{1.2, 1.4, 1.6, 1.8\}$, mirroring Liu's 50-dimensional testbed. Because $d_G$ and the basin are known exactly here, we can check whether the observed rate scales with $d_G$ rather than $\|x_0-x^*\|$.
The decisive checks are three. Projection must show a measurable rate of stalled runs on block-permutation problems but not on the pure-coordinate chain. Folded averaging must match the predicted $\log(1/\delta)$ dependence while naive averaging does not. The excess failure probability of the folded method must track the measured probability of leaving the basin, which would confirm that confinement, not folding itself, is the binding term.
Finally, we scale the block model to graphs well beyond 20 nodes with planted communities, measuring recovery quantiles. This shows whether the guarantee remains informative past the exact solvers' ceiling.
References
- Community detection in the stochastic block model by mixed integer programming
- Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations
- High Probability Convergence of Stochastic Gradient Methods
- Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis
- From Optimization to Generalization under Heavy-Tailed Data: The Role of Gradient Clipping
- Symmetry Breaking Constraints: Recent Results
- Breaking symmetries in all different problems
- Efficient Symmetry Breaking for Boolean Satisfiability
- Optimizing over trained GNNs via symmetry breaking
- High-Probability Bounds for the Last Iterate of Clipped SGD
- A Sequential Quadratic Programming Method With High-Probability Complexity Bounds for Nonlinear Equality-Constrained Stochastic Optimization
- Equivariant Symmetry Breaking Sets
- SGD Can Converge to Local Maxima
- High Probability Bounds for Non-Convex Stochastic Optimization with Momentum