  Algorithmic reproducibility measures the deviation in outputs of machine
learning algorithms upon minor changes in the training process. Previous work
suggests that first-order methods would need to trade-off convergence rate
(gradient complexity) for better reproducibility. In this work, we challenge
this perception and demonstrate that both optimal reproducibility and
near-optimal convergence guarantees can be achieved for smooth convex
minimization and smooth convex-concave minimax problems under various
error-prone oracle settings. Particularly, given the inexact initialization
oracle, our regularization-based algorithms achieve the best of both worlds -
optimal reproducibility and near-optimal gradient complexity - for minimization
and minimax optimization. With the inexact gradient oracle, the near-optimal
guarantees also hold for minimax optimization. Additionally, with the
stochastic gradient oracle, we show that stochastic gradient descent ascent is
optimal in terms of both reproducibility and gradient complexity. We believe
our results contribute to an enhanced understanding of the
reproducibility-convergence trade-off in the context of convex optimization.
