Empirical Evaluation of No Free Lunch Violations in Permutation-Based Optimization

• URL: http://arxiv.org/abs/2603.03613v1
• Date: Wed, 04 Mar 2026 00:55:25 GMT
• Title: Empirical Evaluation of No Free Lunch Violations in Permutation-Based Optimization
• Authors: Grzegorz Sroka,
• Abstract summary: We study an iterative-search setting with sampling without replacement, where algorithms differ only in evaluation order.<n>Results show how objective reformulation and benchmark design can generate structured local departures from NFL intuition.<n>This message applies to evolutionary computation as well as to statistical procedures based on relabeling, resampling, and permutation tests.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The No Free Lunch (NFL) theorem guarantees equal average performance only under uniform sampling of a function space closed under permutation (c.u.p.). We ask when this averaging ceases to reflect what benchmarking actually reports. We study an iterative-search setting with sampling without replacement, where algorithms differ only in evaluation order. Binary objectives allow exhaustive evaluation in the fully enumerable case, and efficiency is defined by the first time the global minimum is reached. We then construct two additional benchmarks by algebraically recombining the same baseline functions through sums and differences. Function-algorithm relations are examined via correlation structure, hierarchical clustering, delta heatmaps, and PCA. A one-way ANOVA with Tukey contrasts confirms that algebraic reformulations induce statistically meaningful shifts in performance patterns. The uniformly sampled baseline remains consistent with the global NFL symmetry. In contrast, the algebraically modified benchmarks yield stable re-rankings and coherent clusters of functions and sampling policies. Composite objectives can also exhibit non-additive search effort despite being built from simpler components. Monte Carlo experiments indicate that order effects persist in larger spaces and depend on function class. Taken together, the results show how objective reformulation and benchmark design can generate structured local departures from NFL intuition. They motivate algorithm choice that is aware of both the problem class and the objective representation. This message applies to evolutionary computation as well as to statistical procedures based on relabeling, resampling, and permutation tests.

Related papers

• CAIRO: Decoupling Order from Scale in Regression [13.755937210012883]
  We propose a framework that decouples regression into two distinct stages.<n>In the first stage, we learn a scoring function by minimizing a scale-invariant ranking loss.<n>In the second, we recover the target scale via isotonic regression.
  arXiv  Detail & Related papers  (2026-02-16T03:50:05Z)
• RANSAC Scoring Functions: Analysis and Reality Check [0.0]
  We revisit the problem of assigning a score (a quality of fit) to candidate geometric models.<n>We show that a threshold-based parameterization leads to a unified view of likelihood-based and robust M-estimators.
  arXiv  Detail & Related papers  (2025-12-22T20:08:46Z)
• Efficient Covariance Estimation for Sparsified Functional Data [51.69796254617083]
  proposed Random-knots (Random-knots-Spatial) and B-spline (Bspline-Spatial) estimators of the covariance function are computationally efficient.<n>Asymptotic pointwise of the covariance are obtained for sparsified individual trajectories under some regularity conditions.
  arXiv  Detail & Related papers  (2025-11-23T00:50:33Z)
• Dynamic Stability of LLM-Generated Code [6.120340803716395]
  Current evaluations of LLMs for code generation overlook the fact that functionally correct solutions can differ significantly in algorithmic complexity.<n>We introduce a principled framework for evaluating the dynamic stability of generated code.<n>Our findings call for stability-aware objectives in code generation and new benchmarks with test cases for robust, real-world evaluation.
  arXiv  Detail & Related papers  (2025-11-07T09:58:06Z)
• Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models [25.51914785590587]
  We study the problem of causal structure learning from a linear non-Gaussian structural equation model.<n>Recent results show that using mere observational data identifies the causal graph only up to a permutation-equivalence class.
  arXiv  Detail & Related papers  (2025-09-25T09:34:24Z)
• Learning covariate importance for matching in policy-relevant observational research [2.6361497319422176]
  We propose the Priority-Aware one-to-one Matching Algorithm (PAMA)<n>It is a semi-supervised framework that learns a covariate importance measure from a subset data of units that are paired by experts and uses it to match additional units.<n>It is applied to a real-world study of in-person schooling and COVID-19 transmission.
  arXiv  Detail & Related papers  (2024-03-19T02:24:16Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  We propose a model agnostic post-processing framework xOrder for achieving fairness in bipartite ranking. xOrder is compatible with various classification models and ranking fairness metrics, including supervised and unsupervised fairness metrics. We evaluate our proposed algorithm on four benchmark data sets and two real-world patient electronic health record repositories.
  arXiv  Detail & Related papers  (2023-07-27T07:42:44Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models [49.038420266408586]
  We show that sorting variables by increasing variance often yields an ordering close to a causal order. We propose an efficient baseline algorithm termed $R2$-SortnRegress that exploits high $R2$-sortability. Our findings reveal high $R2$-sortability as an assumption about the data generating process relevant to causal discovery.
  arXiv  Detail & Related papers  (2023-03-31T17:05:46Z)
• Learning by Sorting: Self-supervised Learning with Group Ordering Constraints [75.89238437237445]
  This paper proposes a new variation of the contrastive learning objective, Group Ordering Constraints (GroCo) It exploits the idea of sorting the distances of positive and negative pairs and computing the respective loss based on how many positive pairs have a larger distance than the negative pairs, and thus are not ordered correctly. We evaluate the proposed formulation on various self-supervised learning benchmarks and show that it not only leads to improved results compared to vanilla contrastive learning but also shows competitive performance to comparable methods in linear probing and outperforms current methods in k-NN performance.
  arXiv  Detail & Related papers  (2023-01-05T11:17:55Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.