  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. In this work, 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
problems, leading to complexity bounds that are either new or match the best
existing ones.
