  Blackwell's celebrated approachability theory provides a general framework
for a variety of learning problems, including regret minimization. However,
Blackwell's proof and implicit algorithm measure approachability using the
$\ell_2$ (Euclidean) distance. We argue that in many applications such as
regret minimization, it is more useful to study approachability under other
distance metrics, most commonly the $\ell_\infty$-metric. But, the time and
space complexity of the algorithms designed for $\ell_\infty$-approachability
depend on the dimension of the space of the vectorial payoffs, which is often
prohibitively large. Thus, we present a framework for converting
high-dimensional $\ell_\infty$-approachability problems to low-dimensional
pseudonorm approachability problems, thereby resolving such issues. We first
show that the $\ell_\infty$-distance between the average payoff and the
approachability set can be equivalently defined as a pseudodistance between a
lower-dimensional average vector payoff and a new convex set we define. Next,
we develop an algorithmic theory of pseudonorm approachability, analogous to
previous work on approachability for $\ell_2$ and other norms, showing that it
can be achieved via online linear optimization (OLO) over a convex set given by
the Fenchel dual of the unit pseudonorm ball. We then use that to show, modulo
mild normalization assumptions, that there exists an
$\ell_\infty$-approachability algorithm whose convergence is independent of the
dimension of the original vectorial payoff. We further show that that algorithm
admits a polynomial-time complexity, assuming that the original
$\ell_\infty$-distance can be computed efficiently. We also give an
$\ell_\infty$-approachability algorithm whose convergence is logarithmic in
that dimension using an FTRL algorithm with a maximum-entropy regularizer.
