  Optimization problems often involve vector norms, which has led to extensive
research on developing algorithms that can handle objectives beyond the
$\ell_p$ norms. Our work introduces the concept of submodular norms, which are
a versatile type of norms that possess marginal properties similar to
submodular set functions. We show that submodular norms can accurately
represent or approximate well-known classes of norms, such as $\ell_p$ norms,
ordered norms, and symmetric norms. Furthermore, we establish that submodular
norms can be applied to optimization problems such as online facility location,
stochastic probing, and generalized load balancing. This allows us to develop a
logarithmic-competitive algorithm for online facility location with symmetric
norms, to prove a logarithmic adaptivity gap for stochastic probing with
symmetric norms, and to give an alternative poly-logarithmic approximation
algorithm for generalized load balancing with outer $\ell_1$ norm and inner
symmetric norms.
