A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

• URL: http://arxiv.org/abs/2608.08898v1
• Date: Sun, 09 Aug 2026 20:19:51 GMT
• Title: A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures
• Abstract summary: We propose a novel approach to problem characterisation based on the representation of instances when implemented as a program.<n>We identify the Halstead volume as a measure of code complexity, which can be seen as a simplified version of the entropy of the program.<n>We show that the measures are negatively correlated with algorithm performance and therefore show potential as predictive meta-features for algorithm selection and other problem analysis.
• Score: 0.8422257363944294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Characterising optimisation problem instances is a fundamental part of understanding the behaviour and performance of different algorithms as well as providing information for algorithm selection and configuration. In this paper we propose a novel approach to problem characterisation based on the representation of instances when implemented as a program. The intuition is that the complexity of the code required to express an objective function should relate to the complexity of the search landscape. We identify the Halstead volume as a measure of code complexity, which can be seen as a simplified version of the entropy of the program. Given a code implementation of the objective function, the Halstead volume and entropy can be quickly calculated using existing libraries. We apply the proposed complexity measures to the well-known BBOB optimisation problem suite and the simple feed-forward neural network training task. We also show that the measures are negatively correlated with algorithm performance and therefore show potential as predictive meta-features for algorithm selection and other problem analysis. We envisage the proposed measures as complementary to other problem characterisation approaches, but with the advantages of not requiring any sampling of the search space, being invariant to transformations, and being very quick to calculate automatically.

Related papers

• Optimal Centered Active Excitation in Linear System Identification [48.09783075634403]
  We propose an active learning algorithm for linear system identification with optimal centered noise excitation.<n>We first establish lower bounds of the sample complexity for any active learning algorithm to attain the prescribed accuracy and confidence levels.
  arXiv  Detail & Related papers  (2026-04-07T07:16:16Z)
• Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints [0.0]
  Variational inequalities play a key role in machine learning research, such as generative adversarial networks, reinforcement learning, adversarial training, and generative models.<n>We propose some mirror descent-type algorithms that switch between productive and non-productive steps depending on the values of the functional constraints at iterations.<n>We prove their optimal convergence rate to achieve a solution with desired accuracy, for problems with bounded and monotone operators and Lipschitz convex functional constraints.
  arXiv  Detail & Related papers  (2026-02-24T18:56:00Z)
• Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
  This paper introduces Large Language Models (LLMs) into algorithm selection for the first time. LLMs not only captures the structural and semantic aspects of the algorithm, but also demonstrates contextual awareness and library function understanding. The selected algorithm is determined by the matching degree between a given problem and different algorithms.
  arXiv  Detail & Related papers  (2023-11-22T06:23:18Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem Instances [0.7046417074932257]
  In black-box optimization, it is essential to understand why an algorithm instance works on a set of problem instances while failing on others. We propose a methodology for formulating an algorithm instance footprint that consists of a set of problem instances that are easy to be solved and a set of problem instances that are difficult to be solved.
  arXiv  Detail & Related papers  (2023-06-01T09:28:06Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
  This paper proposes a novel surrogate-based global optimization algorithm to solve linearly constrained mixed-variable problems.<n>The proposed approach is based on constructing a piecewise affine surrogate of the objective function over feasible samples.<n>The two algorithms are evaluated on several unconstrained and constrained mixed-variable benchmark problems.
  arXiv  Detail & Related papers  (2023-02-09T15:04:35Z)
• Self-adaptive algorithms for quasiconvex programming and applications to machine learning [0.0]
  We provide a self-adaptive step-size strategy that does not include convex line-search techniques and a generic approach under mild assumptions. The proposed method is verified by preliminary results from some computational examples. To demonstrate the effectiveness of the proposed technique for large-scale problems, we apply it to some experiments on machine learning.
  arXiv  Detail & Related papers  (2022-12-13T05:30:29Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system. Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
  arXiv  Detail & Related papers  (2020-09-11T11:56:34Z)

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.