A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

Radoslav Harman; Lenka Filová; Peter Richtarik

doi:10.1080/01621459.2018.1546588

A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

Radoslav Harman, Lenka Filová, Peter Richtarik

Research output: Contribution to journal › Article › peer-review

41 Scopus citations

Abstract

We propose a class of subspace ascent methods for computing optimal approximate designs that covers existing algorithms as well as new and more efficient ones. Within this class of methods, we construct a simple, randomized exchange algorithm (REX). Numerical comparisons suggest that the performance of REX is comparable or superior to that of state-of-the-art methods across a broad range of problem structures and sizes. We focus on the most commonly used criterion of D-optimality, which also has applications beyond experimental design, such as the construction of the minimum-volume ellipsoid containing a given set of data points. For D-optimality, we prove that the proposed algorithm converges to the optimum. We also provide formulas for the optimal exchange of weights in the case of the criterion of A-optimality, which enable one to use REX and some other algorithms for computing A-optimal and I-optimal designs.

Original language	English (US)
Pages (from-to)	1-30
Number of pages	30
Journal	Journal of the American Statistical Association
DOIs	https://doi.org/10.1080/01621459.2018.1546588
State	Published - Dec 13 2018

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The work of the first two authors was supported by Grant Number 1/0521/16 from the Slovak Scientific Grant Agency (VEGA). The last author acknowledges support through the KAUST baseline research funding scheme. We are also grateful to Valerii Fedorov, Anatoly Zhigljavsky, Luc Pronzato, Bernhard Spangl, Samuel Rosa and two anonymous referees for insightful comments on the first version of this paper.

Access to Document

10.1080/01621459.2018.1546588

https://repository.kaust.edu.sa/bitstream/10754/626844/6/3_14_2019_A%20Randomiz.pdf

Cite this

@article{8ba32b8f52d84321b4b678ef7630b7b6,

title = "A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments",

abstract = "We propose a class of subspace ascent methods for computing optimal approximate designs that covers existing algorithms as well as new and more efficient ones. Within this class of methods, we construct a simple, randomized exchange algorithm (REX). Numerical comparisons suggest that the performance of REX is comparable or superior to that of state-of-the-art methods across a broad range of problem structures and sizes. We focus on the most commonly used criterion of D-optimality, which also has applications beyond experimental design, such as the construction of the minimum-volume ellipsoid containing a given set of data points. For D-optimality, we prove that the proposed algorithm converges to the optimum. We also provide formulas for the optimal exchange of weights in the case of the criterion of A-optimality, which enable one to use REX and some other algorithms for computing A-optimal and I-optimal designs.",

author = "Radoslav Harman and Lenka Filov{\'a} and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The work of the first two authors was supported by Grant Number 1/0521/16 from the Slovak Scientific Grant Agency (VEGA). The last author acknowledges support through the KAUST baseline research funding scheme. We are also grateful to Valerii Fedorov, Anatoly Zhigljavsky, Luc Pronzato, Bernhard Spangl, Samuel Rosa and two anonymous referees for insightful comments on the first version of this paper.",

year = "2018",

month = dec,

day = "13",

doi = "10.1080/01621459.2018.1546588",

language = "English (US)",

pages = "1--30",

journal = "Journal of the American Statistical Association",

issn = "0162-1459",

publisher = "Taylor and Francis Ltd.",

}

TY - JOUR

T1 - A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

AU - Harman, Radoslav

AU - Filová, Lenka

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The work of the first two authors was supported by Grant Number 1/0521/16 from the Slovak Scientific Grant Agency (VEGA). The last author acknowledges support through the KAUST baseline research funding scheme. We are also grateful to Valerii Fedorov, Anatoly Zhigljavsky, Luc Pronzato, Bernhard Spangl, Samuel Rosa and two anonymous referees for insightful comments on the first version of this paper.

PY - 2018/12/13

Y1 - 2018/12/13

N2 - We propose a class of subspace ascent methods for computing optimal approximate designs that covers existing algorithms as well as new and more efficient ones. Within this class of methods, we construct a simple, randomized exchange algorithm (REX). Numerical comparisons suggest that the performance of REX is comparable or superior to that of state-of-the-art methods across a broad range of problem structures and sizes. We focus on the most commonly used criterion of D-optimality, which also has applications beyond experimental design, such as the construction of the minimum-volume ellipsoid containing a given set of data points. For D-optimality, we prove that the proposed algorithm converges to the optimum. We also provide formulas for the optimal exchange of weights in the case of the criterion of A-optimality, which enable one to use REX and some other algorithms for computing A-optimal and I-optimal designs.

AB - We propose a class of subspace ascent methods for computing optimal approximate designs that covers existing algorithms as well as new and more efficient ones. Within this class of methods, we construct a simple, randomized exchange algorithm (REX). Numerical comparisons suggest that the performance of REX is comparable or superior to that of state-of-the-art methods across a broad range of problem structures and sizes. We focus on the most commonly used criterion of D-optimality, which also has applications beyond experimental design, such as the construction of the minimum-volume ellipsoid containing a given set of data points. For D-optimality, we prove that the proposed algorithm converges to the optimum. We also provide formulas for the optimal exchange of weights in the case of the criterion of A-optimality, which enable one to use REX and some other algorithms for computing A-optimal and I-optimal designs.

UR - http://hdl.handle.net/10754/626844

UR - https://www.tandfonline.com/doi/full/10.1080/01621459.2018.1546588

UR - http://www.scopus.com/inward/record.url?scp=85064509940&partnerID=8YFLogxK

U2 - 10.1080/01621459.2018.1546588

DO - 10.1080/01621459.2018.1546588

M3 - Article

SN - 0162-1459

SP - 1

EP - 30

JO - Journal of the American Statistical Association

JF - Journal of the American Statistical Association

ER -

A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint