From Multitask Gradient Descent to Gradient-Free Evolutionary Multitasking: A Proof of Faster Convergence

Area of Science:

• Optimization Algorithms
• Evolutionary Computation
• Machine Learning Theory

Background:

• Evolutionary multitasking solves multiple optimization tasks simultaneously, leveraging information from related tasks for improved performance.
• Existing evolutionary multitasking algorithms lack theoretical guarantees for faster convergence compared to single-task approaches.

Purpose of the Study:

• To theoretically analyze the convergence benefits of information transfer in evolutionary multitasking.
• To introduce and validate novel algorithms that demonstrate provably faster convergence.

Main Methods:

• Developed a novel multitask gradient descent (MTGD) algorithm incorporating a multitask interaction term.
• Derived the convergence properties of MTGD and provided the first proof of its faster convergence relative to single-task gradient descent.
• Formulated a gradient-free multitask evolution strategies (MTES) algorithm based on MTGD, leveraging the asymptotic approximation of single-task evolution strategies (ES) to gradient descent.

Main Results:

• The convergence of the proposed MTGD algorithm was mathematically derived.
• The study presents the first theoretical proof demonstrating faster convergence for MTGD compared to its single-task counterpart.
• Numerical experiments validated that MTES converges faster than single-task ES on various benchmarks and practical problems.

Conclusions:

• The theoretical framework and proposed algorithms (MTGD and MTES) establish faster convergence for evolutionary multitasking.
• Information transfer in multitasking optimization demonstrably accelerates convergence, supported by both theoretical proofs and empirical evidence.
• This work bridges the gap between the practical success and theoretical understanding of evolutionary multitasking algorithms.