Exact gradient methods with memory.

Area of Science:

• Optimization methods
• Numerical analysis
• Machine learning algorithms

Background:

• The Inexact Gradient Method with Memory (IGMM) offers performance improvements over standard gradient methods by using a piecewise linear lower model.
• However, IGMM's reliance on solving auxiliary problems within a fixed tolerance limits its applicability and worst-case convergence rate.

Purpose of the Study:

• To modify IGMM to eliminate the tolerance parameter, broadening its applicability and improving convergence guarantees.
• To develop an accelerated version of the modified method without error accumulation.

Main Methods:

• Modification of the Inexact Gradient Method with Memory (IGMM) to create the Exact Gradient Method with Memory (EGMM).
• Development of an Accelerated Gradient Method with Memory (AGMM) by applying acceleration techniques to EGMM under stricter assumptions.
• Analysis of worst-case convergence rates for EGMM and AGMM.

Main Results:

• EGMM removes the tolerance parameter, achieving broad applicability similar to Bregman Distance Gradient Method/NoLips with a $$ worst-case convergence rate.
• AGMM achieves a superior worst-case convergence rate of $$ without error accumulation.
• Preliminary experiments show EGMM performs excellently, sometimes outperforming accelerated methods, and AGMM consistently surpasses the Fast Gradient Method.

Conclusions:

• The proposed Exact Gradient Method with Memory (EGMM) offers a more robust and broadly applicable alternative to IGMM.
• The Accelerated Gradient Method with Memory (AGMM) provides state-of-the-art convergence rates for memory-based optimization methods.
• Computational results validate the theoretical improvements and practical efficiency of EGMM and AGMM.