  Composite minimization is a powerful framework in large-scale convex
optimization, based on decoupling of the objective function into terms with
structurally different properties and allowing for more flexible algorithmic
design. We introduce a new algorithmic framework for complementary composite
minimization, where the objective function decouples into a (weakly) smooth and
a uniformly convex term. This particular form of decoupling is pervasive in
statistics and machine learning, due to its link to regularization. The main
contributions of our work are summarized as follows. First, we introduce the
problem of complementary composite minimization in general normed spaces;
second, we provide a unified accelerated algorithmic framework to address broad
classes of complementary composite minimization problems; and third, we prove
that the algorithms resulting from our framework are near-optimal in most of
the standard optimization settings. Additionally, we show that our algorithmic
framework can be used to address the problem of making the gradients small in
general normed spaces. As a concrete example, we obtain a nearly-optimal method
for the standard $\ell_1$ setup (small gradients in the $\ell_{\infty}$ norm),
essentially matching the bound of Nesterov (2012) that was previously known
only for the Euclidean setup. Finally, we show that our composite methods are
broadly applicable to a number of regression and other classes of optimization
problems, where regularization plays a key role. Our methods lead to complexity
bounds that are either new or match the best existing ones.
