Towards the Inferrence of Structural Similarity of Combinatorial Landscapes

• URL: http://arxiv.org/abs/2312.02720v1
• Date: Tue, 5 Dec 2023 12:34:51 GMT
• Title: Towards the Inferrence of Structural Similarity of Combinatorial Landscapes
• Abstract summary: One of the most common problem-solvings is by analogy. For a given problem, a solver can be viewed as a strategic walk on its fitness landscape. By using local optima network as a proxy of fitness landscapes, this paper proposed to leverage graph data mining techniques to explore latent structural information embedded in those landscapes.
• Score: 5.1059158939850064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the most common problem-solving heuristics is by analogy. For a given problem, a solver can be viewed as a strategic walk on its fitness landscape. Thus if a solver works for one problem instance, we expect it will also be effective for other instances whose fitness landscapes essentially share structural similarities with each other. However, due to the black-box nature of combinatorial optimization, it is far from trivial to infer such similarity in real-world scenarios. To bridge this gap, by using local optima network as a proxy of fitness landscapes, this paper proposed to leverage graph data mining techniques to conduct qualitative and quantitative analyses to explore the latent topological structural information embedded in those landscapes. By conducting large-scale empirical experiments on three classic combinatorial optimization problems, we gain concrete evidence to support the existence of structural similarity between landscapes of the same classes within neighboring dimensions. We also interrogated the relationship between landscapes of different problem classes.

Related papers

• GenAI for Systems: Recurring Challenges and Design Principles from Software to Silicon [62.2138479061386]
  Generative AI is reshaping how computing systems are designed, optimized, and built, yet research remains fragmented across software, architecture, and chip design communities.<n>This paper takes a cross-stack perspective, examining how generative models are being applied from code generation and distributed runtimes through hardware design space exploration to RTL synthesis, physical layout, and verification.
  arXiv  Detail & Related papers  (2026-02-16T22:45:33Z)
• Subfunction Structure Matters: A New Perspective on Local Optima Networks [0.0]
  Local optima networks (LONs) capture fitness information landscape.<n>We consider how LON analysis can be improved by incorporating subfunction-based information.
  arXiv  Detail & Related papers  (2025-04-17T07:31:11Z)
• Landscaping Linear Mode Connectivity [76.39694196535996]
  linear mode connectivity (LMC) has garnered interest from both theoretical and practical fronts. We take a step towards understanding it by providing a model of how the loss landscape needs to behave topographically for LMC.
  arXiv  Detail & Related papers  (2024-06-24T03:53:30Z)
• Is attention required for ICL? Exploring the Relationship Between Model Architecture and In-Context Learning Ability [39.42414275888214]
  We evaluate 13 models capable of causal language modeling across a suite of synthetic in-context learning tasks. All the considered architectures can perform in-context learning under a wider range of conditions than previously documented. Several attention alternatives are sometimes competitive with or better in-context learners than transformers.
  arXiv  Detail & Related papers  (2023-10-12T05:43:06Z)
• Similarity of Neural Architectures using Adversarial Attack Transferability [47.66096554602005]
  We design a quantitative and scalable similarity measure between neural architectures. We conduct a large-scale analysis on 69 state-of-the-art ImageNet classifiers. Our results provide insights into why developing diverse neural architectures with distinct components is necessary.
  arXiv  Detail & Related papers  (2022-10-20T16:56:47Z)
• A Collection of Deep Learning-based Feature-Free Approaches for Characterizing Single-Objective Continuous Fitness Landscapes [0.0]
  Landscape insights are crucial for problem understanding as well as for assessing benchmark set diversity and composition. In this work we provide a collection of different approaches to characterize optimization landscapes. We demonstrate and validate our devised methods on the BBOB testbed and predict, with the help of Deep Learning.
  arXiv  Detail & Related papers  (2022-04-12T12:46:31Z)
• Fitness Landscape Footprint: A Framework to Compare Neural Architecture Search Problems [12.901952926144258]
  We use fitness landscape analysis to study a neural architecture search problem. We study two problems, the classical image classification benchmark CIFAR-10, and the Remote-Sensing problem So2Sat LCZ42.
  arXiv  Detail & Related papers  (2021-11-02T13:20:01Z)
• Kinship Verification Based on Cross-Generation Feature Interaction Learning [53.62256887837659]
  Kinship verification from facial images has been recognized as an emerging yet challenging technique in computer vision applications. We propose a novel cross-generation feature interaction learning (CFIL) framework for robust kinship verification.
  arXiv  Detail & Related papers  (2021-09-07T01:50:50Z)
• Weakly supervised cross-domain alignment with optimal transport [102.8572398001639]
  Cross-domain alignment between image objects and text sequences is key to many visual-language tasks. This paper investigates a novel approach for the identification and optimization of fine-grained semantic similarities between image and text entities.
  arXiv  Detail & Related papers  (2020-08-14T22:48:36Z)
• Few-shot Visual Reasoning with Meta-analogical Contrastive Learning [141.2562447971]
  We propose to solve a few-shot (or low-shot) visual reasoning problem, by resorting to analogical reasoning. We extract structural relationships between elements in both domains, and enforce them to be as similar as possible with analogical learning. We validate our method on RAVEN dataset, on which it outperforms state-of-the-art method, with larger gains when the training data is scarce.
  arXiv  Detail & Related papers  (2020-07-23T14:00:34Z)
• Understanding Deep Architectures with Reasoning Layer [60.90906477693774]
  We show that properties of the algorithm layers, such as convergence, stability, and sensitivity, are intimately related to the approximation and generalization abilities of the end-to-end model. Our theory can provide useful guidelines for designing deep architectures with reasoning layers.
  arXiv  Detail & Related papers  (2020-06-24T00:26:35Z)

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.