Reproduce “Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Behrooz Tahmasebi, Melanie Weber

This research quantifies the cost of enforcing symmetry in machine learning models, demonstrating an exponential difference: achieving exact symmetry necessitates averaging over all $|G|$ group elements, while approximate symmetry requires only $O(\log |G|)$ operations, offering a theoretical basis for its practical utility.

Key insights

  • Enforcing exact symmetry on sufficiently rich function spaces (those including polynomial features up to a certain degree) inherently requires averaging over all elements of the group $G$, leading to a complexity proportional to $|G|$.
  • In stark contrast, approximate symmetry can be achieved with high probability by averaging over a small, randomly sampled subset of group elements, leading to a complexity logarithmic in the group size, $O(\log |G|/\epsilon)$.
  • This establishes an exponential separation in complexity, theoretically explaining why approximate symmetry is computationally and sample-efficient compared to exact symmetry, particularly for large groups.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.