  Key to structured prediction is exploiting the problem structure to simplify
the learning process. A major challenge arises when data exhibit a local
structure (e.g., are made by "parts") that can be leveraged to better
approximate the relation between (parts of) the input and (parts of) the
output. Recent literature on signal processing, and in particular computer
vision, has shown that capturing these aspects is indeed essential to achieve
state-of-the-art performance. While such algorithms are typically derived on a
case-by-case basis, in this work we propose the first theoretical framework to
deal with part-based data from a general perspective. We derive a novel
approach to deal with these problems and study its generalization properties
within the setting of statistical learning theory. Our analysis is novel in
that it explicitly quantifies the benefits of leveraging the part-based
structure of the problem with respect to the learning rates of the proposed
estimator.
