Fixed-Target Runtime Analysis

• URL: http://arxiv.org/abs/2004.09613v3
• Date: Tue, 5 Oct 2021 17:41:02 GMT
• Title: Fixed-Target Runtime Analysis
• Authors: Maxim Buzdalov and Benjamin Doerr and Carola Doerr and Dmitry Vinokurov
• Abstract summary: runtime analysis classically studies the time needed to find an optimal solution. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort.
• Score: 8.246980996934347
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.

Related papers

• Multi-objective Pseudo Boolean Functions in Runtime Analysis: A Review [3.3472202807168774]
  We survey commonly used multi-objective functions in the theory domain and systematically review their features, limitations and implications to practical use. We present several new functions with more realistic features, such as local optimality and nonlinearity of the Pareto front, through simply mixing and matching classical single-objective functions.
  arXiv  Detail & Related papers  (2025-03-24T21:42:33Z)
• Near-optimal Active Reconstruction [3.037563407333583]
  We design an algorithm for the Next Best View (NBV) problem in the context of active object reconstruction. We rigorously derive sublinear bounds for the cumulative regret of our algorithm, which guarantees near-optimality. We evaluate the performance of our algorithm empirically within our simulation framework.
  arXiv  Detail & Related papers  (2025-03-24T09:17:53Z)
• Learning to Align Multi-Faceted Evaluation: A Unified and Robust Framework [61.38174427966444]
  Large Language Models (LLMs) are being used more and more extensively for automated evaluation in various scenarios. Previous studies have attempted to fine-tune open-source LLMs to replicate the evaluation explanations and judgments of powerful proprietary models. We propose a novel evaluation framework, ARJudge, that adaptively formulates evaluation criteria and synthesizes both text-based and code-driven analyses.
  arXiv  Detail & Related papers  (2025-02-26T06:31:45Z)
• Leveraging Slither and Interval Analysis to build a Static Analysis Tool [0.0]
  This paper presents our progress toward finding defects that are sometimes not detected or completely detected by state-of-the-art analysis tools. We developed a working solution built on top of Slither that uses interval analysis to evaluate the contract state during the execution of each instruction.
  arXiv  Detail & Related papers  (2024-10-31T09:28:09Z)
• Tighter Performance Theory of FedExProx [85.92481138826949]
  We revisit FedExProx - a recently proposed distributed optimization method designed to enhance convergence properties of parallel algorithms via extrapolation. We develop a novel analysis framework, establishing a tighter linear convergence rate for non-strongly convex quadratic problems. We extend the applicability of our analysis to general functions satisfying the Polyak-Lojasiewicz condition, outperforming the previous strongly convex analysis.
  arXiv  Detail & Related papers  (2024-10-20T11:53:25Z)
• Investigating the Impact of Quantization on Adversarial Robustness [22.637585106574722]
  Quantization is a technique for reducing the bit-width of deep models to improve their runtime performance and storage efficiency. In real-world scenarios, quantized models are often faced with adversarial attacks which cause the model to make incorrect inferences. We conduct a first-time analysis of the impact of the quantization pipeline components that can incorporate robust optimization.
  arXiv  Detail & Related papers  (2024-04-08T16:20:15Z)
• It Is Time To Steer: A Scalable Framework for Analysis-driven Attack Graph Generation [50.06412862964449]
  Attack Graph (AG) represents the best-suited solution to support cyber risk assessment for multi-step attacks on computer networks. Current solutions propose to address the generation problem from the algorithmic perspective and postulate the analysis only after the generation is complete. This paper rethinks the classic AG analysis through a novel workflow in which the analyst can query the system anytime.
  arXiv  Detail & Related papers  (2023-12-27T10:44:58Z)
• A Comparative Visual Analytics Framework for Evaluating Evolutionary Processes in Multi-objective Optimization [7.906582204901926]
  We present a visual analytics framework that enables the exploration and comparison of evolutionary processes in EMO algorithms. We demonstrate the effectiveness of our framework through case studies on benchmarking and real-world multi-objective optimization problems.
  arXiv  Detail & Related papers  (2023-08-10T15:32:46Z)
• Best-Effort Adaptation [62.00856290846247]
  We present a new theoretical analysis of sample reweighting methods, including bounds holding uniformly over the weights. We show how these bounds can guide the design of learning algorithms that we discuss in detail. We report the results of a series of experiments demonstrating the effectiveness of our best-effort adaptation and domain adaptation algorithms.
  arXiv  Detail & Related papers  (2023-05-10T00:09:07Z)
• A Scale-Independent Multi-Objective Reinforcement Learning with Convergence Analysis [0.6091702876917281]
  Many sequential decision-making problems need optimization of different objectives which possibly conflict with each other. We develop a single-agent scale-independent multi-objective reinforcement learning on the basis of the Advantage Actor-Critic (A2C) algorithm. A convergence analysis is then done for the devised multi-objective algorithm providing a convergence-in-mean guarantee.
  arXiv  Detail & Related papers  (2023-02-08T16:38:55Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Analysis of Genetic Algorithm on Bearings-Only Target Motion Analysis [0.0]
  Target motion analysis using only bearing angles is an important study for tracking targets in water. Several methods including Kalman-like filters and evolutionary strategies are used to get a good predictor.
  arXiv  Detail & Related papers  (2020-01-15T15:40:01Z)

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.