  The recently introduced Gradient Methods with Memory use a subset of the past
oracle information to create an accurate model of the objective function that
enables them to surpass the Gradient Method in practical performance. The model
introduces an overhead that is substantial on all problems but the smooth
unconstrained ones. In this work, we introduce several Gradient Methods with
Memory that can solve composite problems efficiently, including unconstrained
problems with non-smooth objectives. The auxiliary problem at each iteration
still cannot be solved exactly but we show how to alter the model and how to
initialize the auxiliary problem solver to ensure that this inexactness does
not degrade the convergence guarantees. Moreover, we dynamically increase the
convergence guarantees as to provably surpass those of their memory-less
counterparts. These properties are preserved when applying acceleration and the
containment of inexactness further prevents error accumulation. Our methods are
able to estimate key geometry parameters to attain state-of-the-art worst-case
rates on many important subclasses of composite problems, where the objective
smooth part satisfies a strong convexity condition or a relaxation thereof. In
particular, we formulate a near-optimal restart strategy applicable to
optimization methods with sublinear convergence guarantees of any order. We
support the theoretical results with simulations.
