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
- 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) - 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) - A survey on multi-objective hyperparameter optimization algorithms for
Machine Learning [62.997667081978825]
This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms.
We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both.
We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
arXiv Detail & Related papers (2021-11-23T10:22:30Z) - 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) - Interactive Dimensionality Reduction for Comparative Analysis [28.52130400665133]
We introduce an interactive DR framework where we integrate our new DR method, called ULCA, with an interactive visual interface.
ULCA unifies two DR schemes, discriminant analysis and contrastive learning, to support various comparative analysis tasks.
We develop an optimization algorithm that enables analysts to interactively refine ULCA results.
arXiv Detail & Related papers (2021-06-29T15:05:36Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics.
Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis.
We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
arXiv Detail & Related papers (2020-06-23T04:25:36Z) - 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.