Optimal Convergence Rate for Mirror Descent Methods with Special Time-Varying Step Sizes Rules

In this paper, the optimal convergence rate without the presence of a logarithmic factor is proved for mirror descent methods with special time-varying step sizes for solving classical constrained non-smooth problems, and problems with the composite model. The proven result is an improvement on the well-known rate \(O\left( N^{-1/2} \log (N) \right) \) (N is the total number of iterations performed by the algorithm) for the mirror descent algorithms with the time-varying step sizes under consideration. It was studied a new weighting scheme that assigns smaller weights to the initial points and larger weights to the most recent points. This scheme improves the convergence rate of the studied mirror descent methods which in the conducted numerical experiments outperform the other methods providing a better solution in all the considered test problems.