Subfunction Structure Matters: A New Perspective on Local Optima Networks

• URL: http://arxiv.org/abs/2504.17799v1
• Date: Thu, 17 Apr 2025 07:31:11 GMT
• Title: Subfunction Structure Matters: A New Perspective on Local Optima Networks
• Authors: S. L. Thomson, M. W. Przewozniczek,
• Abstract summary: Local optima networks (LONs) capture fitness information landscape.<n>We consider how LON analysis can be improved by incorporating subfunction-based information.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Local optima networks (LONs) capture fitness landscape information. They are typically constructed in a black-box manner; information about the problem structure is not utilised. This also applies to the analysis of LONs: knowledge about the problem, such as interaction between variables, is not considered. We challenge this status-quo with an alternative approach: we consider how LON analysis can be improved by incorporating subfunction-based information - this can either be known a-priori or learned during search. To this end, LONs are constructed for several benchmark pseudo-boolean problems using three approaches: firstly, the standard algorithm; a second algorithm which uses deterministic grey-box crossover; and a third algorithm which selects perturbations based on learned information about variable interactions. Metrics related to subfunction changes in a LON are proposed and compared with metrics from previous literature which capture other aspects of a LON. Incorporating problem structure in LON construction and analysing it can bring enriched insight into optimisation dynamics. Such information may be crucial to understanding the difficulty of solving a given problem with state-of-the-art linkage learning optimisers. In light of the results, we suggest incorporation of problem structure as an alternative paradigm in landscape analysis for problems with known or suspected subfunction structure.

Related papers

• A Differentiable Rank-Based Objective For Better Feature Learning [20.576291802100048]
  We present a new algorithm called difFOCI, which is applicable to a wider range of machine learning problems thanks to its differentiable nature and learnable parameters.<n>We evaluate difFOCI on increasingly complex problems ranging from basic variable selection in toy examples to saliency map comparisons in convolutional networks.
  arXiv  Detail & Related papers  (2025-02-13T16:15:43Z)
• Coherent Local Explanations for Mathematical Optimization [0.0]
  We introduce Coherent Local Explanations for Mathematical Optimization (CLEMO)<n>CLEMO provides explanations for multiple components of optimization models, the objective value and decision variables, which are coherent with the underlying model structure.<n>Our sampling-based procedure can provide explanations for the behavior of exact and exact solution algorithms.
  arXiv  Detail & Related papers  (2025-02-07T11:18:04Z)
• Geometric Neural Process Fields [58.77241763774756]
  Geometric Neural Process Fields (G-NPF) is a probabilistic framework for neural radiance fields that explicitly captures uncertainty.<n>Building on these bases, we design a hierarchical latent variable model, allowing G-NPF to integrate structural information across multiple spatial levels.<n> Experiments on novel-view synthesis for 3D scenes, as well as 2D image and 1D signal regression, demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2025-02-04T14:17:18Z)
• On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games [55.2480439325792]
  In a sequential decision-making problem, the information structure is the description of how events in the system occurring at different points in time affect each other. By contrast, real-world sequential decision-making problems typically involve a complex and time-varying interdependence of system variables. We formalize a novel reinforcement learning model which explicitly represents the information structure.
  arXiv  Detail & Related papers  (2024-03-01T21:28:19Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
  Two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it. We provide a unified theoretical analysis of tree-based hierarchical partitioning methods for online reinforcement learning. Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets.
  arXiv  Detail & Related papers  (2021-10-29T15:06:15Z)
• On the regularized risk of distributionally robust learning over deep neural networks [0.0]
  We study the relation between distributionally robust learning and different forms of regularization to enforce robustness of deep neural networks. We motivate a family of scalable algorithms for the training of robust neural networks.
  arXiv  Detail & Related papers  (2021-09-13T20:10:39Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)
• An Information-Theoretic Framework for Unifying Active Learning Problems [44.758281991246825]
  This paper presents an information-theoretic framework for unifying active learning problems. We first introduce a novel active learning criterion that subsumes an existing LSE algorithm. By exploiting the relationship between LSE and BO, we design a competitive information-theoretic acquisition function for BO.
  arXiv  Detail & Related papers  (2020-12-19T14:22:48Z)
• High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
  This paper proposes novel methods to solve the high dimensional Level Set Estimation problems using Bayesian Neural Networks. For each problem, we derive the corresponding theoretic information based acquisition function to sample the data points. Numerical experiments on both synthetic and real-world datasets show that our proposed method can achieve better results compared to existing state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-12-17T23:21:53Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• Total Deep Variation for Linear Inverse Problems [71.90933869570914]
  We propose a novel learnable general-purpose regularizer exploiting recent architectural design patterns from deep learning. We show state-of-the-art performance for classical image restoration and medical image reconstruction problems.
  arXiv  Detail & Related papers  (2020-01-14T19:01:50Z)

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.