Analysis of Online Composite Mirror Descent Algorithm.

Area of Science:

• Optimization algorithms
• Machine learning theory

Background:

• Online composite mirror descent (OCMD) is a key algorithm for convex optimization.
• Existing analyses often require averaging or boundedness assumptions, limiting applicability.
• Improving convergence rates and relaxing these assumptions is crucial for practical use.

Purpose of the Study:

• To analyze the convergence of the OCMD algorithm under weaker assumptions.
• To derive improved convergence rates for excess risk and last iterate.
• To enhance the theoretical understanding of OCMD for sparse learning.

Main Methods:

• Utilizing a strongly convex differentiable mirror map to capture data geometry.
• Analyzing a convex objective function comprising loss and sparsity-inducing regularizer.
• Employing a novel error decomposition based on excess Bregman distance.
• Refining analysis of objective function self-bounding properties for one-step progress bounds.

Main Results:

• Achieving convergence rates of order O(1/t^p) for excess risk with polynomially decaying step sizes.
• Improving upon existing error analyses by removing averaging and boundedness requirements.
• Sharpening convergence rates for the last iterate in online gradient descent without boundedness assumptions.

Conclusions:

• The enhanced analysis provides significant theoretical improvements for OCMD.
• The results are applicable to a class of objective functions with Hölder continuous gradients.
• This work advances the understanding of efficient online learning algorithms for sparse data.