- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates whether fairly allocating neighbour-evaluation budgets across archive solutions can accelerate Pareto-based multi-objective local search. The authors compare s-PLS, which systematically scans neighbourhoods; r-PLS, which selects archive solutions uniformly at random; and f-PLS, which prioritises the least-visited solutions. Under a fixed-archive model, the paper uses an arbitrary discrete distribution to characterise good-neighbour counts, derives the expected numbers of evaluations required by s-PLS and r-PLS to find the next good neighbour, and establishes sufficient conditions for comparing their efficiency. Under a fair-round model, it also proves that the waiting time of f-PLS is stochastically no greater than that of r-PLS.
The paper also presents experiments covering five classes of bi-objective combinatorial optimisation problems with 100, 200, and 500 variables. The results show that fairer strategies achieve better early-stage performance and final hypervolume (HV) on several problems, although these advantages do not hold universally.
Critical strengths
The paper provides a clear analytical framework for identifying when fairness is beneficial, rather than making a blanket claim that fairness is always better. The experiments demonstrate the practical relevance of the budget allocation problem under study.
Critical weaknesses
-
The theoretical contribution offers limited new insight and has a restricted scope of applicability, while the correspondence between its strongest guarantee and the algorithm’s actual search states remains unclear. The analysis is confined to the first success under a fixed archive and prescribed sampling schemes, and its additional predictive value for actual dynamic search has not been sufficiently demonstrated. The two main threshold theorems likewise provide sufficient conditions derived from bounds on local waiting times, rather than a characterisation of the entire search process.
-
The theory and experiments lack a direct, quantitative connection, leaving the paper’s main explanatory contribution insufficiently supported. The theory examines how many evaluations are needed to find the next good neighbour from the same fixed archive. The experiments primarily examine the HV achieved within a given budget by the different algorithms’ evolving archives. These quantities are not equivalent. Different good neighbours may contribute differently to HV, and discovering new solutions also changes the subsequent archive and search opportunities.
-
The paper’s current contributions seem more directly relevant to the multi-objective optimisation and heuristic search communities, with limited impact on the ICLR community.
Questions for authors
-
The paper derives waiting-time relationships among the three PLS strategies for finding the next good neighbour under a fixed archive, but does not directly validate how well these theoretical results explain actual search behaviour. Could the authors extract archive snapshots from the experiments and, using the same snapshots for each strategy under the corresponding theoretical assumptions, compare theoretically predicted and empirically measured waiting times? Could they also report the proportion of archive states satisfying the sufficient conditions in Theorems 1 and 2 across different problems and search stages? Furthermore, do shorter waiting times correspond to larger HV gains per evaluation?
-
Proposition 2 appears to omit an important assumption about the initial visit counts. The proof in Appendix C.7 relies on a complete fair-round structure, which requires equal initial visit counts across all archive solutions. However, Algorithm A.3 retains historical visit counts and initialises newly added solutions with a count of zero. Thus, the proposition does not appear to apply directly to arbitrary search states encountered during actual execution.
-
The theoretical analysis focuses on the number of evaluations needed to find the first good neighbour, which aligns more closely with the stopping condition of the ’ first-improvement variant. However, the main experiments use s-PLS with full neighbourhood scans, while the first-improvement variants are compared only in the appendix. Why was the variant not used as a primary experimental baseline to better align the theoretical analysis and experimental setup?
-
In the experiments, all problem sizes use the same absolute evaluation budget, while for some problems the neighbourhood size grows quadratically with the number of variables. I therefore suspect that the more pronounced performance gaps at larger problem sizes may primarily reflect an anytime-performance advantage under relatively tighter budgets, rather than a separate, independent advantage.