A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

References

• Ahipasaoglu, S. D. (2015), “A First-order Algorithm for the A-optimal Experimental Design Problem: A Mathematical Programming Approach,” Statistics and Computing, 25, 1113–1127.
   Web of Science ®Google Scholar
• Ahipasaoglu, S. D. (2015), “Fast Algorithms for the Minimum Volume Estimator,” Journal of Global Optimization, 62, 351–370.
   Web of Science ®Google Scholar
• Atkinson, A. C., Donev, A. N., and Tobias, R. D. (2007), Optimum Experimental Designs, With SAS, Oxford: Oxford University Press.
   Google Scholar
• Atwood, C.L. (1973), “Sequences Converging to D-Optimal Designs of Experiments,” The Annals of Statistics 1, 342–352. DOI: 10.1214/aos/1176342371.
   Web of Science ®Google Scholar
• Böhning, D. (1986), “A Vertex-Exchange-Method in D-Optimal Design Theory,” Metrika 33, 337–347. DOI: 10.1007/BF01894766.
   Google Scholar
• De Castro, Y., Gamboa, F., Henrion, D., Hess, R., and Lasserre, J. B. (2019), “Approximate Optimal Designs for Multivariate Polynomial Regression,” Annals of Statistics 47, 127–155. DOI: 10.1214/18-AOS1683.
   Web of Science ®Google Scholar
• Chambolle, A., Ehrhardt, M. J., Richtárik, P., and Schönlieb, C. B. (2017), “Stochastic Primal–Dual Hybrid Gradient Algorithm With Arbitrary Sampling and Imaging Applications,” arXiv:1706.04957, 1–25.
   Google Scholar
• Coetzer, R., and Haines, L.(2017), “The Construction of D-and I-optimal Designs for Mixture Experiments With Linear Constraints on the Components,” Chemometrics and Intelligent Laboratory Systems, 171, 112–124. DOI: 10.1016/j.chemolab.2017.10.007.
   Web of Science ®Google Scholar
• Cook, R. D., and Nachtsheim, C. J. (1982), “Model Robust, Linear-Optimal Designs,” Technometrics, 24, 49–54. DOI: 10.1080/00401706.1982.10487708.
   Web of Science ®Google Scholar
• Cornell, J. A. (2011), Experiments With Mixtures: Designs, Models, and the Analysis of Mixture Data (Vol. 403). New York: Wiley.
   Google Scholar
• Csiba, D., and Richtárik, P. (2017), “Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Lojasiewicz Functions,” arXiv preprint arXiv:1709.03014.
   Google Scholar
• Dette, H., Pepelyshev, A., and Zhigljavsky, A. (2008), “Improving Updating Rules in Multiplicative Algorithms for Computing D-optimal Designs,” Computational Statistics & Data Analysis, 53, 312–320. DOI: 10.1016/j.csda.2008.10.002.
   Web of Science ®Google Scholar
• Fedorov, V.V. (1972), Theory of Optimal Experiments, New York: Academic Press.
   Google Scholar
• Fedorov, V.V., and Hackl, P. (2012), Model-oriented Design of Experiments (Vol 125). New York: Springer Science & Business Media.
   Google Scholar
• Fercoq, O., and Richtárik, P. (2015), “Accelerated, Parallel and PROXimal Coordinate Descent.” SIAM Journal on Optimization, 25, pp. 1997–2023. DOI: 10.1137/130949993.
   Web of Science ®Google Scholar
• Gaffke, N., and Schwabe, R. (2019), “Quasi-Newton Algorithm for Optimal Approximate Linear Regression Design: Optimization in Matrix Space,” Journal of Statistical Planning and Inference, 198, 62–78. DOI: 10.1016/j.jspi.2018.03.005.
   Web of Science ®Google Scholar
• Goos, P., Jones, B., and Syafitri, U. (2016), “I-Optimal Design of Mixture Experiments,” Journal of the American Statistical Association, 111, 899–911. DOI: 10.1080/01621459.2015.1136632.
   Web of Science ®Google Scholar
• Gower, R.M., and Richtárik, P. (2015), “Randomized Iterative Methods for Linear Systems,” SIAM Journal on Matrix Analysis and Applications, 36, 1660–1690. DOI: 10.1137/15M1025487.
   Web of Science ®Google Scholar
• Gürbüzbalaban, M., Ozdaglar, A., and Parrilo, P. (2015), “Why Random Reshuffling Beats Stochastic Gradient Descent,” arXiv preprint arXiv:1510.08560.
   Google Scholar
• Harman, R. (2014), “Multiplicative Methods for Computing D-optimal Stratified Designs of Experiments,” Journal of Statistical Planning and Inference, 146, 82–94. DOI: 10.1016/j.jspi.2013.10.003.
   Web of Science ®Google Scholar
• Harman, R., and Pronzato, L. (2007), “Improvements on Removing Nonoptimal Support Points in D-optimum Design Algorithms,” Statistics & Probability Letters, 77, 90–94. DOI: 10.1016/j.spl.2006.05.014.
   Web of Science ®Google Scholar
• Jaggi, M., Smith, V., Takáč, M., Terhorst, J., Krishnan, S., Hofmann, T., and Jordan, M.I. (2014), “Communication-Efficient Distributed Dual Coordinate Ascent,” in Advances in Neural Information Processing Systems, eds. Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Red Hook, NY: Curran Associates, Inc., 3068–3076.
   Google Scholar
• Konečný, J., Liu, J., Richtárik, P., and Takáč, M. (2016), “Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting,” IEEE Journal of Selected Topics in Signal Processing, 10, 242–255. DOI: 10.1109/JSTSP.2015.2505682.
   Web of Science ®Google Scholar
• Lee, Y. T., and Sidford, A. (2010), “Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems,” IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS).
   Google Scholar
• Leventhal, D., and Lewis, A. S. (2010), “Randomized Methods for Linear Constraints: Convergence Rates and Conditioning,” Mathematics of Operations Research, 35, 641–654. DOI: 10.1287/moor.1100.0456.
   Web of Science ®Google Scholar
• Mandal, A., Wong, W. K., and Yu, Y. (2015), “Algorithmic Searches for Optimal Designs,” in Handbook of Design and Analysis of Experiments, eds. Dean A., Morris M., Stufken J., Bingham D., Boca Raton, FL: CRC Press, pp. 755–783.
   Google Scholar
• Molchanov, I., and Zuyev, S. (2002), “Steepest Descent Algorithms in a Space of Measures,” Statistics and Computing, 12, 115–123. DOI: 10.1023/A:1014878317736.
   Web of Science ®Google Scholar
• Myers, R.H., Montgomery, D.C., and Anderson-Cook, C.M. (2016), Response Surface Methodology: Process and Product Optimization Using Designed Experiments, Hoboken, NJ: John Wiley & Sons.
   Google Scholar
• Necoara, I., Nesterov, Y., and Glineur, F. (2011), “A Random Coordinate Descent Method on Large Optimization Problems With Linear Constraints,” manuscript.
   Google Scholar
• Nesterov, Y. (2012), “Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems,” SIAM Journal on Optimization, 22, 341–362. DOI: 10.1137/100802001.
   Web of Science ®Google Scholar
• Pázman, A. (1986), Foundations of Optimum Experimental Design, Dordrecht: Reidel.
   Google Scholar
• Platt, J. (1998), “Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines,” manuscript. https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/
   Google Scholar
• Pronzato, L. (2013), “A Delimitation of the Support of Optimal Designs for Kiefer’s ϕp -class of Criteria,” Statistics & Probability Letters, 83, 2721–2728. DOI: 10.1016/j.spl.2013.09.009.
   Web of Science ®Google Scholar
• Pronzato, L., and Pázman, A. (2013), Design of Experiments in Nonlinear Models (Vol. 212), Lecture Notes in Statistics, Springer.
   Google Scholar
• Pronzato, L., and Zhigljavsky, A.A. (2014), “Algorithmic Construction of Optimal Designs on Compact Sets for Concave and Differentiable Criteria,” Journal of Statistical Planning and Inference, 154, 141–155. DOI: 10.1016/j.jspi.2014.04.005.
   Web of Science ®Google Scholar
• Pukelsheim, F. (2006), “Optimal Design of Experiments (Classics in Applied Mathematics),” Philadelphia, PA: Society for Industrial and Applied Mathematics.
   Google Scholar
• Qu, Z., Richtárik, P., and Zhang, T. (2015), “Quartz: Randomized Dual Coordinate Ascent With Arbitrary Sampling,” in Advances in Neural Information Processing Systems, eds. C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, 865–873. Red Hook, NY: Curran Associates, Inc.
   Google Scholar
• R Core Team (2016), R: A Language and Environment for Statistical Computing, Vienna, Austria: R Foundation for Statistical Computing, available at https://www.R-project.org/.
   Google Scholar
• Richtárik, P., and Takáč, M. (2016), “Parallel Coordinate Descent Methods for Big Data Optimization,” Mathematical Programming, 144, 433–484. DOI: 10.1007/s10107-015-0901-6.
   Web of Science ®Google Scholar
• Richtárik, P., and Takáč, M. (2016), “Distributed Coordinate Descent Method for Learning With Big Data,” Journal of Machine Learning Research, 17, 1–25.
   Web of Science ®Google Scholar
• Sagnol, G. (2011), “Computing Optimal Designs of Multiresponse Experiments Reduces to Second-order Cone Programming,” Journal of Statistical Planning and Inference, 121, 1684–1708. DOI: 10.1016/j.jspi.2010.11.031.
   Web of Science ®Google Scholar
• Sagnol, G., and Harman, R. (2015), “Computing Exact D-Optimal Designs by Mixed Integer Second Order Cone Programming,” The Annals of Statistics, 43, 2198–2224. DOI: 10.1214/15-AOS1339.
   Web of Science ®Google Scholar
• Silvey, S. D., Titterington, D. H., and Torsney, B. (1978), “An Algorithm for Optimal Designs on a Design Space,” Communications in Statistics – Theory and Methods, 7, 1379–1389. DOI: 10.1080/03610927808827719.
   Web of Science ®Google Scholar
• Shalev-Shwartz, S., and Zhang, T. (2013), “Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization,” Journal of Machine Learning Research, 14, 567–599.
   Web of Science ®Google Scholar
• Sun, R., and Ye, Y. (2016), “Worst-case Complexity of Cyclic Coordinate Descent: O(n2) Gap With Randomized Version.” arXiv:1604.07130, pp. 1–39.
   Google Scholar
• Teeyapan, K., Theera-Umpon, N., and Auephanwiriyakul, S. (2017), “Ellipsoidal Support Vector Data Description,” Neural Computing and Applications, 28, 337–347. DOI: 10.1007/s00521-016-2343-3.
   Web of Science ®Google Scholar
• Titterington, D.M. (1975), “Optimal Design: Some Geometrical Aspects of D-optimality.” Biometrika, 62, 313–320. DOI: 10.1093/biomet/62.2.313.
   Web of Science ®Google Scholar
• Titterington, D.M. (1978), “Estimation of Correlation Coefficients by Ellipsoidal Trimming,” Applied Statistics, 27, 227–234.
   Google Scholar
• Todd, M. J. (2016), “Minimum-Volume Ellipsoids: Theory and Algorithms,” Philadelphia, PA: Society for Industrial and Applied Mathematics.
   Google Scholar
• Todd, M. J., and Yildirim, E. A. (2007), “On Khachiyan’s Algorithm for the Computation of Minimum-Volume Enclosing Ellipsoids,” Discrete Applied Mathematics, 155, 1731–1744. DOI: 10.1016/j.dam.2007.02.013.
   Web of Science ®Google Scholar
• Torsney, B., and Martín-Martín, R. (2009), “Multiplicative Algorithms for Computing Optimum Designs,” Journal of Statistical Planning and Inference, Vol 139, pp. 3947–3961. DOI: 10.1016/j.jspi.2009.05.007.
   Web of Science ®Google Scholar
• Uciǹski, D., and Patan, M. (2007), “D-optimal Design of a Monitoring Network for Parameter Estimation of Distributed Systems,” Journal of Global Optimization, 39, 291–322. DOI: 10.1007/s10898-007-9139-z.
   Web of Science ®Google Scholar
• Yang, M., Biedermann, S., and Tang, E. (2013), “On Optimal Designs for Nonlinear Models: A General and Efficient Algorithm,” Journal of the American Statistical Association, 108, 1411–1420. DOI: 10.1080/01621459.2013.806268.
   Web of Science ®Google Scholar
• Yu, Y. (2010), “Monotonic Convergence of a General Algorithm for Computing Optimal Designs,” The Annals of Statistics, 38, 1593–1606. DOI: 10.1214/09-AOS761.
   Web of Science ®Google Scholar
• Yu, Y. (2011), “D-optimal Designs Via a Cocktail Algorithm,” Statistics and Computing, 21, 475–481.
   Web of Science ®Google Scholar
• Van Aelst, S., and Rousseeuw, P. (2009), “Minimum Volume Ellipsoid,” Wiley Interdisciplinary Reviews: Computational Statistics, 1, 71–82. DOI: 10.1002/wics.19.
   Google Scholar
• Vandenberghe, L., Boyd, S., and Wu, S. (1998), “Determinant Maximization With Linear Matrix Inequality Constraints,” SIAM Journal on Matrix Analysis, 19, 499–533. DOI: 10.1137/S0895479896303430.
   Web of Science ®Google Scholar
• Wynn, H.P. (1970), “The Sequential Generation of D-optimum Experimental Designs,” The Annals of Mathematical Statistics, 41, 1655–1664. DOI: 10.1214/aoms/1177696809.
   Google Scholar