 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources3
 Resource Type

30
 Availability

30
 Author / Contributor
 Filter by Author / Creator


Singh, M. (3)

Tantipongpipat, U. (2)

Xie, W. (2)

Madan, M (1)

Madan, V. (1)

Nikolov, A (1)

Tantipongpipat, U (1)

#Tyler Phillips, Kenneth E. (0)

& *Soto, E. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Attari, S. Z. (0)

& Ayala, O. (0)

& Babbitt, W. (0)

& Baek, Y. (0)

& Bai, F. (0)

& BarthCohen, L. (0)

 Filter by Editor


& Ahn, J. (0)

& Bateiha, S. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Beygelzimer (0)

A. Ghate, K. Krishnaiyer (0)

A. I. Sacristán, J. C. (0)

A. Weinberg, D. MooreRusso (0)

A. Weinberger (0)

A.I. Sacristán, J.C. CortésZavala (0)

A.I., Dimitrova (0)

ACS (0)

AIAA (0)

AIAA Propulsion and Energy 2021 (0)

AIAA SciTech (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In an optimal design problem, we are given a set of linear experiments v1,…,vn∈Rd and k≥d, and our goal is to select a set or a multiset S⊆[n] of size k such that Φ((∑i∈Sviv⊤i)−1) is minimized. When Φ(M)=Determinant(M)1/d, the problem is known as the Doptimal design problem, and when Φ(M)=Trace(M), it is known as the Aoptimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Millermore »

Madan, M ; Singh, M. ; Tantipongpipat, U ; Xie, W. ( , Conference on Learning Theory, COLT 2019)In an optimal design problem, we are given a set of linear experiments v1,…,vn∈Rd and k≥d, and our goal is to select a set or a multiset S⊆[n] of size k such that Φ((∑i∈Sviv⊤i)−1) is minimized. When Φ(M)=Determinant(M)1/d, the problem is known as the Doptimal design problem, and when Φ(M)=Trace(M), it is known as the Aoptimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Millermore »and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for Doptimal design and Aoptimal design problems. We show that the local search algorithms are asymptotically optimal when kd is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for Doptimal design and Aoptimal design problems when kd is large.« less

Nikolov, A ; Singh, M. ; Tantipongpipat, U. ( , Symposium on Discrete Algorithms (SODA))We study the Aoptimal design problem where we are given vectors υ1, …, υn ∊ ℝd, an integer k ≥ d, and the goal is to select a set S of k vectors that minimizes the trace of (∑i∊Svivi⊺)−1. Traditionally, the problem is an instance of optimal design of experiments in statistics [35] where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick k of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placementmore »in wireless networks [22], sparse least squares regression [8], feature selection for kmeans clustering [9], and matrix approximation [13, 14, 5]. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for Aoptimal design. Given a matrix, proportional volume sampling involves picking a set of columns S of size k with probability proportional to µ(S) times det(∑i∊Svivi⊺) for some measure µ. Our main result is to show the approximability of the Aoptimal design problem can be reduced to approximate independence properties of the measure µ. We appeal to hardcore distributions as candidate distributions µ that allow us to obtain improved approximation algorithms for the Aoptimal design. Our results include a dapproximation when k = d, an (1 + ∊)approximation when and approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for k ≤ d and obtain a kapproximation. We also show that the proportional volume sampling algorithm gives approximation algorithms for other optimal design objectives (such as Doptimal design [36] and generalized ratio objective [27]) matching or improving previous best known results. Interestingly, we show that a similar guarantee cannot be obtained for the Eoptimal design problem. We also show that the Aoptimal design problem is NPhard to approximate within a fixed constant when k = d.« less