We introduce and analyse a new family of algorithms which generalizes and unifies both the mirror descent and the dual averaging algorithms. In the framework of this family, we define a new algorithm for constrained optimization with the aim of combining the advantages of mirror descent and dual averaging. In practice, this new algorithm converges as fast as mirror descent and dual averaging, and in some situations greatly outperforms them. Besides, we demonstrate how our algorithms can also be applied to solving variational inequalities.

This is joint work with Anatoli Juditsky and Eric Moulines.