Generalizing Algorithmic Frameworks to Arbitrary Norms

36 concepts36 papers2 proposals

Most classical algorithms in optimization, clustering, and machine learning are built on the foundation of Euclidean geometry. The $L_2$ norm (least squares) is the default because its "round" geometry allows for simple gradients and well-behaved Hilbert spaces. However, real-world data often demands different geometries: $L_1$ for robustness against outliers, $L_\infty$ for worst-case safety margins, or $L_p$ for specific sparsity patterns.

Recent research is systematically breaking this Euclidean dependency, rebuilding core algorithmic tools to work across the entire family of $L_p$ norms.

The Geometry of the Objective

The choice of norm defines what "distance" means in a high-dimensional space. In clustering, for instance, the $k$-means objective minimizes squared Euclidean distances ($L_2$), while $k$-median minimizes the sum of distances ($L_1$). Anagnostopoulos et al. demonstrated that this distinction can be bridged; they showed that one-sided clustering problems can be solved with constant-factor approximations for any $p \ge 1$. This suggests that the underlying structure of partitioning data is not strictly tied to the "roundness" of Euclidean space.

This generalization extends to complex structural constraints. Bajpai et al. developed algorithms for the Priority Matroid Median problem, noting that while their current work focuses on the $L_1$ median objective, the framework can be adapted to other $L_p$ norms, though the approximation factors scale with the power $p$. Similarly, Davies et al. have moved toward combinatorial clustering algorithms that avoid slow linear programming, aiming for a unified framework that supports diverse $L_p$ objectives without sacrificing speed.

Optimization Beyond the Euclidean Gradient

In optimization, the "steepest descent" direction depends entirely on the norm used to measure step size. Standard Gradient Descent is optimal for $L_2$, but it can be inefficient when the objective function's smoothness is defined relative to a different norm.

To address this, researchers are generalizing performance guarantees:

  • Worst-Case Bounds: Taylor et al. established exact worst-case convergence rates for proximal gradient methods, noting that extending these to non-Euclidean norms is the next theoretical frontier.
  • Mirror Descent: When working in high-dimensional spaces where Euclidean steps are suboptimal, Fazel et al. suggest using mirror descent to adapt to the natural geometry of the problem, specifically for submodular maximization.
  • Black-Box Optimization: Even when gradients are unknown, the choice of norm matters. Lobanov et al. developed zero-order stochastic gradient methods for overparameterized problems, identifying the extension to non-Euclidean constrained landscapes as a critical next step.

Robustness and Efficiency in Practice

Generalizing norms is not just a theoretical exercise; it changes how models handle noise and scale. In neural network security, Lin et al. introduced Constrained Gradient Descent to find adversarial examples. While highly effective for $L_\infty$ perturbations, the authors highlight the need to verify if these soft-constraint mechanisms translate to $L_2$ or $L_0$ metrics.

In data engineering, the "Euclidean default" can be a bottleneck. Abo Khamis et al. optimized relational database learning for $L_2$ but noted that adapting these functional dependency optimizations for $L_1$ would significantly broaden their applicability. Similarly, in streaming contexts, Chou et al. achieved constant-time updates for tracking $L_2$ norms, leaving the door open for similar breakthroughs in tracking $L_p$ norms for $p < 2$.

Why It Works: The Unified View

The reason these generalizations are possible is that many geometric properties are not unique to $L_2$. For example, Whitehouse et al. introduced "Geometric Condition Numbers" based on simplex volumes to approximate measures. While initially framed for least squares, the authors suggest these geometric primitives can be generalized to $L_p$ errors.

By treating the norm as a parameter rather than a constant, the field is moving toward a "norm-agnostic" style of algorithm design. Whether it is Pasechnyuk et al. generalizing quantized decentralized optimization or DeVore et al. expanding the approximation theory of ReLU networks to $L_p$ spaces, the goal is the same: ensuring that our computational tools are as flexible as the data they process.

Key Foundational Work

Fitting Tree Metrics: Hierarchical Clustering and Phylogeny (2011) — contributed 2 concept elements to this direction.
An Efficient Algorithm for 2D Euclidean 2-Center with Outliers (2008) — contributed 1 concept elements to this direction.
LEAST SQUARES APPROXIMATIONS OF MEASURES VIA GEOMETRIC CONDITION NUMBERS (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generalization_to_other_norms_d7759f03,
  title = {generalization to other norms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalization-to-other-norms/rdr_d7759f03b1964ba28faef7bb4cb37d21},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_generalization_to_other_norms_d7759f03_v1,
  title = {generalization to other norms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalization-to-other-norms/rdr_d7759f03b1964ba28faef7bb4cb37d21/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake