Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “Deterministic algorithm”

Optimal deterministic algorithm generation

Alexander Mitsos, Jaromił Najman, Ioannis G. Kevrekidis · Journal of Global Optimization · 2018

Abstract A formulation for the automated generation of algorithms via mathematical programming (optimization) is proposed. The formulation is based on the concept of optimizing within a parameterized family of algorithms, or equivalently a family of functions describing the algorithmic steps. The optimization variables are the parameters—within this family of algorithms—that encode algorithm design: the computational steps of which the selected algorithms consist. The objective function of the optimization problem encodes the merit function of the algorithm, e.g., the computational cost (possibly also including a cost component for memory requirements) of the algorithm execution. The constraints of the optimization problem ensure convergence of the algorithm, i.e., solution of the problem at hand. The formulation is described prototypically for algorithms used in solving nonlinear equations and in performing unconstrained optimization; the parametrized algorithm family considered is that of monomials in function and derivative evaluation (including negative powers). A prototype implementation in GAMS is provided along with illustrative results demonstrating cases for which well-known algorithms are shown to be optimal. The formulation is a mixed-integer nonlinear program. To overcome the multimodality arising from nonconvexity in the optimization problem, a combination of brute force and general-purpose deterministic global algorithms is employed to guarantee the optimality of the algorithm devised. We then discuss several directions towards which this methodology can be extended, their scope and limitations.

Cited by 12Open access

Deterministic Policy Imitation Gradient Algorithm

Fumihiro Sasaki, Atsuo Kawaguchi · 2018

The goal of imitation learning (IL) is to enable a learner to imitate an expert’s behavior given the expert’s demonstrations. Recently, generative adversarial imitation learning (GAIL) has successfully achieved it even on complex continuous control tasks. However, GAIL requires a huge number of interactions with environment during training. We believe that IL algorithm could be more applicable to the real-world environments if the number of interactions could be reduced. To this end, we propose a model free, off-policy IL algorithm for continuous control. The keys of our algorithm are two folds: 1) adopting deterministic policy that allows us to derive a novel type of policy gradient which we call deterministic policy imitation gradient (DPIG), 2) introducing a function which we call state screening function (SSF) to avoid noisy policy updates with states that are not typical of those appeared on the expert’s demonstrations. Experimental results show that our algorithm can achieve the goal of IL with at least tens of times less interactions than GAIL on a variety of continuous control tasks.

Cited by 1

A deterministic Bitstream Descartes Algorithm

Kurt Mehlhorn, Michael Sagraloff · 2010

Project co-funded by the European Commission within FP6 (2002–2006) We describe a variant of the Descartes algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients of the polynomial can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is deterministic and has same asymptotic complexity as the randomized bitstream Descartes algorithm of Eigenwillig et. al. [EKK + 05]. Besides being deterministic, the algorithm is also somewhat simpler to analyse.

Cited by 0

Enhanced deep deterministic policy gradient algorithm

Jianping CHEN, Chao HE, Quan LIU et al. · SHILAP Revista de lepidopterología · 2018

With the problem of slow convergence for deep deterministic policy gradient algorithm,an enhanced deep deterministic policy gradient algorithm was proposed.Based on the deep deterministic policy gradient algorithm,two sample pools were constructed,and the time difference error was introduced.The priority samples were added when the experience was played back.When the samples were trained,the samples were selected from two sample pools respectively.At the same time,the bisimulation metric was introduced to ensure the diversity of the selected samples and improve the convergence rate of the algorithm.The E-DDPG algorithm was used to pendulum problem.The experimental results show that the E-DDPG algorithm can effectively improve the convergence performance of the continuous action space problems and have better stability.

Cited by 0Open access

Iterative algorithm of deterministic blind beamforming

Qinshan Yang, Qihu Li · 2004

A method based on the model of propagation channel is proposed. In the method, Givens transform is used to calculate the expected information matrix step by step, ignore the irrelative results. In this way, the computational complex and memory needed are reduced. The method can be used without the preinformation of source number. The online structure of the algorithm makes it easy to be realized in parallel multi-DSP. Computer simulation verified the correctness and effectiveness of the method proposed.

Cited by 0

An Efficient Deterministic Algorithm for the

Resource Discovery Problem, Vijay K. Garg, Adnan Aziz · 2007

We address the problem of how best to get a group of machines on a network to learn of each others existence; this is referred to as the Resource Discovery Problem (RDP). Straightforward algorithms for RDP are slow or have high communication cost. Harchol et al. [3] recently presented name-dropper, a randomized distributed algorithm for RDP which has low time and communication complexity. However, name-dropper has significant limitations --- (1.) the use of randomization precludes it from providing a guaranteed bound on runtime, and, more significantly, (2.) it has no mechanism by which convergence can be detected; in order to provide a high probability of convergence, the number of machines on the network must be known a priori to all machines. We present fast-leader, a deterministic distributed algorithm for RDP which overcomes these limitations while matching name-dropper's time and communication costs.

Cited by 0

A DETERMINISTIC ALGORITHM FOR THE MCD

Mia Hubert, Peter J. Rousseeuw, Tim Verdonck · 2010

The minimum covariance determinant (MCD) method is a robust estimator of multivariate location and scatter (Rousseeuw, 1984). The MCD is highly resistant to outliers, and it is often applied by itself and as a building block for other robust multivariate methods. Computing the exact MCD is very hard, so in practice one resorts to approximate algorithms. Most often the FASTMCD algorithm of Rousseeuw and Van Driessen (1999) is used. This algorithm starts by drawing many random subsets, followed by so-called concentration steps. The FASTMCD algorithm is affine equivariant but not permutation invariant. In this article we present a deterministic algorithm, denoted as DetMCD, which does not use random subsets and is even faster. It is permutation invariant and very close to affine equivariant. We illustrate DetMCD on real and simulated data sets, with applications involving principal component analysis, multivariate regression, and classification. Supplemental material (Matlab code of the DetMCD algorithm and the data sets) are available online.

Cited by 0

Deterministic quantum annealing expectation-maximization algorithm

Hideyuki Miyahara, Koji Tsumura, Yuki Sughiyama · Journal of Statistical Mechanics Theory and Experiment · 2017

Abstract Maximum likelihood estimation (MLE) is one of the most important methods in machine learning, and the expectation-maximization (EM) algorithm is often used to obtain maximum likelihood estimates. However, EM heavily depends on initial configurations and fails to find the global optimum. On the other hand, in the field of physics, quantum annealing (QA) was proposed as a novel optimization approach. Motivated by QA, we propose a quantum annealing extension of EM, which we call the deterministic quantum annealing expectation-maximization (DQAEM) algorithm. We also discuss its advantage in terms of the path integral formulation. Furthermore, by employing numerical simulations, we illustrate how DQAEM works in MLE and show that DQAEM moderate the problem of local optima in EM.

Cited by 9Open access