Active Learning for Contextual Search with Binary Feedback

References

• Albert AE (1961) The sequential design of experiments for infinitely many states of nature. Ann. Math. Statist. 32(3):774–799.Crossref, Google Scholar
• Araman VF, Caldentey R (2021) Diffusion approximations for a class of sequential experimentation problems. Management Sci., ePub ahead of print December 28, https://doi.org/10.1287/mnsc.2021.4195.Link, Google Scholar
• Awasthi P, Balcan MF, Long PM (2017) The power of localization for efficiently learning linear separators with noise. J. ACM 63(6):1–27.Crossref, Google Scholar
• Balcan M-F, Long P (2013) Active and passive learning of linear separators under log-concave distributions. Shalev-Shwartz S, Steinwart I, eds. Proc. 26th Annual Conf. on Learn. Theory, vol. 30, 288–316.Google Scholar
• Balcan M-F, Zhang H (2017) Sample and computationally efficient learning algorithms under s-concave distributions. Proc. 31st Inter. Conf. Neural Inform. Processing Systems (Curran Associates Inc., New York), 4799–4808.Google Scholar
• Balcan M-F, Beygelzimer A, Langford J (2009) Agnostic active learning. J. Comput. System Sci. 75(1):78–89.Crossref, Google Scholar
• Balcan M-F, Broder A, Zhang T (2007) Margin based active learning. Bshouty NH, Gentile C, eds. Learning Theory, (Springer Berlin Heidelberg), 35–50.Google Scholar
• Bastani H, Bayati M (2020) Online decision making with high-dimensional covariates. Oper. Res. 68(1):276–294.Link, Google Scholar
• Bastani H, Bayati M, Khosravi K (2021) Mostly exploration-free algorithms for contextual bandits. Management Sci. 67(3):1329–1349.Link, Google Scholar
• Ben-David S, Urner R (2014) The sample complexity of agnostic learning under deterministic labels. Balcan MF, Feldman V, Szepesvári C, eds. Proc. 27th Annual Conf. on Learn. Theory, vol. 35, 527–542.Google Scholar
• Chen X, Chen Y, Li X (2022) Asymptotically optimal sequential design for rank aggregation. Math. Oper. Res. Forthcoming.Google Scholar
• Chernoff H (1959) Sequential design of experiments. Ann. Math. Statist. 30(3):755–770.Crossref, Google Scholar
• Cohen MC, Lobel I, Leme RP (2020) Feature-based dynamic pricing. Management Sci. 66(11):4921–4943.Link, Google Scholar
• Cohn DA (1996) Neural network exploration using optimal experiment design. Neural Networks 9(6):1071–1083.Crossref, Google Scholar
• Cohn D, Atlas L, Ladner R (1994) Improving generalization with active learning. Machine Learn. 15(2):201–221.Crossref, Google Scholar
• Dasgupta S (2005a) Analysis of a greedy active learning strategy. Adv. Neural Inform. Processing Systems 18 (NIPS 2018).Google Scholar
• Dasgupta S (2005b) Coarse sample complexity bounds for active learning. Adv. Neural Inform. Processing Systems 18 (NIPS 2018).Google Scholar
• Elfving G (1952) Optimum allocation in linear regression theory. Ann. Math. Statist. 23(2):255–262.Crossref, Google Scholar
• Feng Y, Caldentey R, Ryan CT (2022) Robust learning of consumer preferences. Oper. Res. 70(2):918–962.Link, Google Scholar
• Hanneke S (2007) A bound on the label complexity of agnostic active learning. Proc. 24th Internat. Conf. on Machine Learn., 353–360.Google Scholar
• Hanneke S (2014) Theory of disagreement-based active learning. Foundations Trends Machine Learn. 7(2–3):131–309.Crossref, Google Scholar
• Kershaw D (1983) Some extensions of W. Gautschi’s inequalities for the gamma function. Math. Comput. 41(164):607–611.Google Scholar
• Krishnamurthy A, Lykouris T, Podimata C, Schapire RE (2021) Contextual search in the presence of irrational agents. Proc. 53rd Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 910–918.Google Scholar
• Leme RP, Schneider J (2018) Contextual search via intrinsic volumes. Proc. IEEE 59th Annual Sympos. on Foundations of Comput. Sci. (IEEE Los Alamitos, CA), 268–282.Google Scholar
• Li X, Chen Y, Chen X, Liu J, Ying Z (2021) Optimal stopping and worker selection in crowdsourcing: An adaptive sequential probability ratio test framework. Statist. Sinica 31:519–546.Google Scholar
• Lobel I, Leme RP, Vladu A (2018) Multidimensional binary search for contextual decision-making. Oper. Res. 66(5):1346–1361.Link, Google Scholar
• Mammen E, Tsybakov AB (1999) Smooth discrimination analysis. Ann. Statist. 27(6):1808–1829.Crossref, Google Scholar
• Naghshvar M, Javidi T (2013) Active sequential hypothesis testing. Ann. Statist. 41(6):2703–2738.Crossref, Google Scholar
• Settles B (2012) Active Learning (Morgan & Claypool, Williston, VT).Crossref, Google Scholar
• Shiffrin RM, Nosofsky RM (1994) Seven plus or minus two: A commentary on capacity limitations. Psych. Rev. 101:357–361.Google Scholar
• Stewart N, Brown GDA, Chater N (2005) Absolute identification by relative judgment. Psych. Rev. 112(4):881–911.Crossref, Google Scholar
• Vapnik V (2013) The Nature of Statistical Learning Theory (Springer Science & Business Media, New York).Google Scholar
• Vapnik VN, Chervonenkis AY (2015) On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity (Springer, Berlin), 11–30.Crossref, Google Scholar
• Wager S, Xu K (2021) Diffusion asymptotics for sequential experiments. Preprint, submitted January, https://arxiv.org/abs/2101.09855.Google Scholar
• Wang Y, Singh A (2016) Noise-adaptive margin-based active learning and lower bounds under Tsybakov noise condition. Proc. 30th AAAI Conf. on Artificial Intelligence (AAAI, Menlo Park, CA), 2180–2186.Google Scholar
• Wang Z, Zenios S (2020) Adaptive design of clinical trials: A sequential learning approach. Preprint, submitted October, https://dx.doi.org/10.2139/ssrn.3713924.Google Scholar
• Zhang C, Chaudhuri K (2014) Beyond disagreement-based agnostic active learning. Adv. Neural Inform. Processing Systems 27 (NIPS 2014).Google Scholar