Orbit Regularization

Renato Negrinho, Andre Martins

Introduction

In machine learning, regularization is the standard tool used to prevent overfitting by favoring "simple" models over complex ones. Typically, this is achieved by adding a penalty term to the loss function, such as the $\ell_1$ norm (Lasso) for sparsity or the $\ell_2$ norm (Ridge) for smooth weight decay. However, these are often treated as distinct, disconnected tools tailored for specific tasks (e.g., $\ell_1$ for sparse vectors, nuclear norm for low-rank matrices).

This paper introduces Orbit Regularization, a unifying framework that treats machine learning regularization through the lens of group theory. By constraining model parameters to an "orbitope"—the convex hull of a group's orbit—the authors demonstrate that classic regularizers are actually special cases of a single, broader geometric principle called group-induced majorization.

The Core Concept: The Orbitope

The authors identify a lack of a unified geometric language to describe regularization techniques. They ask: Can we define model complexity not just as a scalar penalty, but relative to a "prototype" or "seed" vector under certain symmetries?

To answer this, they introduce the concept of the Orbitope. The recipe for orbit regularization involves three steps:

  1. Pick a Group ($G$): This represents the symmetries or invariances expected in your parameters (e.g., permutations, sign flips, or rotations).
  2. Pick a Seed Vector ($v$): This acts as your "prototype" model.
  3. Generate the Orbitope: Take all possible transformations of $v$ by $G$ (the orbit) and find their convex hull. This creates a bounded "safe zone" for your parameters.
Geometric representation of orbitopes $\mathcal{O}_G(v)$ and their normal cones $K_G(v)$ for continuous and discrete groups.

The authors define $G$-majorization: a model $w$ is considered "simpler" than $v$ if it lies inside $v$'s orbitope. To make this practical for optimization, they identify two critical geometric components:

  • Matching Functions: Used for Conditional Gradient (Frank-Wolfe) algorithms, essentially aligning the gradient with the group's orbit.
  • Region Cones: Used for Projected Gradient algorithms. For the permutation group, projecting onto this cone elegantly reduces to the well-known problem of isotonic regression.

Key Insights and The "Grand Unification"

A major contribution of this framework is its ability to decouple invariance from complexity. The group captures the structure (what stays the same if you shuffle or flip signs), while the seed vector captures the scale and complexity.

By changing the group and the seed, the authors show how to recover famous regularizers:

  • Orthogonal Group + any seed = $\ell_2$ regularization.
  • Signed Permutation Group + sparse seed = $\ell_1$ regularization.
  • Symmetric Group + specific seed = The "Permutahedron."

Furthermore, they reveal a deep mathematical link between the "signed permutahedron" and the Sorted $\ell_1$-norm (SLOPE), proving that SLOPE is essentially the dual norm of this specific orbitope.

Experimental Results

The paper relies on synthetic datasets (linear regression with $n \times d$ matrices, where $d=500$) to provide a controlled environment for proof-of-concept. They created "true" weight vectors with varying levels of sparsity, added Gaussian noise, and compared their orbit-based methods against standard $\ell_1$ and $\ell_2$ baselines.

Reconstruction error versus sample size comparing standard $\ell_1$ and $\ell_2$ regularizers against orbit-based methods (perm, sigperm).

Key findings include: * Superiority with "Perfect" Seeds: When the "shape" of the true model is known (i.e., using a seed in the same orbit as the true weights), Orbit Regularization significantly outperforms $\ell_1$ and $\ell_2$ in terms of reconstruction error, especially in low-data regimes. * Effective Path Exploration: Because we rarely know the perfect seed beforehand, the authors propose a continuation strategy—an algorithm that starts with a tiny orbitope and gradually grows it to fit the data. This approach successfully traced a regularization path that found models slightly better than standard baselines. * Algorithmic Efficiency: The necessary sub-steps for optimization can be done in $O(d \log d)$ time for many important groups (like permutations), making the framework computationally feasible for high-dimensional problems.

Limitations and Future Directions

While Orbit Regularization provides a beautiful theoretical unification, challenges remain. Choosing the initial group and understanding how to move between orbits during the continuation algorithm is still largely heuristic. Additionally, the paper focuses primarily on finite groups and the orthogonal group; exploring more complex structures like reflection groups remains an open frontier. Finally, while the synthetic results are highly promising, validating this framework on complex, real-world tasks—such as deep learning weight regularization—is the crucial next step for this research.

Summary updated

Abstract

We propose a general framework for regularization based on group majorization. In this framework, a group is defined to act on the parameter space and an orbit is fixed; to control complexity, the model parameters are confined to lie in the convex hull of this orbit (the orbitope). Common regularizers are recovered as particular cases, and a connection is revealed between the recent sorted 1 -norm and the hyperoctahedral group. We derive the properties a group must satisfy for being amenable to optimization with conditional and projected gradient algorithms. Finally, we suggest a continuation strategy for orbit exploration, presenting simulation results for the symmetric and hyperoctahedral groups.
BibTeX
@inproceedings{negrinho2014orbit,
  author = {Renato Negrinho and Andre Martins},
  title = {{Orbit Regularization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure