Blog
About

1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach

      Preprint

      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          The experimental design problem concerns the selection of k points from a potentially large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected k design points. Statistical efficiency is measured by optimality criteria, including A(verage), D(eterminant), T(race), E(igen), V(ariance) and G-optimality. Except for the T-optimality, exact optimization is NP-hard. We propose a polynomial-time regret minimization framework to achieve a \((1+\varepsilon)\) approximation with only \(O(p/\varepsilon^2)\) design points, for all the optimality criteria above. In contrast, to the best of our knowledge, before our work, no polynomial-time algorithm achieves \((1+\varepsilon)\) approximations for D/E/G-optimality, and the best poly-time algorithm achieving \((1+\varepsilon)\)-approximation for A/V-optimality requires \(k = \Omega(p^2/\varepsilon)\) design points.

          Related collections

          Most cited references 8

          • Record: found
          • Abstract: not found
          • Article: not found

          Graph Sparsification by Effective Resistances

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Relative-Error $CUR$ Matrix Decompositions

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

                Bookmark

                Author and article information

                Journal
                14 November 2017
                Article
                1711.05174

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                33 pages, 4 tables. A preliminary version of this paper titled "Near-Optimal Experimental Design via Regret Minimization" with weaker results appeared in the Proceedings of the 34th International Conference on Machine Learning (ICML 2017), Sydney
                stat.ML cs.LG stat.CO

                Comments

                Comment on this article