# A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis

arXiv: https://arxiv.org/abs/2404.03838 · HTML: https://mlsanity.com/paper/2404.03838/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 4 Apr 2024.

## Builds on (most cited first, 12 of 12)

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [Runtime Analysis of the SMS-EMOA for Many-Objective Optimization](https://mlsanity.com/paper/2312.10290/) (2023)
- [Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments](https://mlsanity.com/paper/2006.04663/) (2020)
- [Analysis of the (1+1) EA on LeadingOnes with Constraints](https://mlsanity.com/paper/2305.18267/) (2023)
- [Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems](https://mlsanity.com/paper/2306.03409/) (2023)

## Abstract (arXiv)

We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.