Optimal Sampling Gaps for Adaptive Submodular Maximization
원문 초록
Running machine learning algorithms on large and rapidly growing volumes of data is often computationally expensive, one common trick to reduce the size of a data set, and thus reduce the computational cost of machine learning algorithms, is \emph{probability sampling}. It creates a sampled data set by including each data point from the original data set with a known probability. Although the benefit of running machine learning algorithms on the reduced data set is obvious, one major concern is that the performance of the solution obtained from samples might be much worse than that of the optimal solution when using the full data set. In this paper, we examine the performance loss caused by probability sampling in the context of adaptive submodular maximization. We consider a simple probability sampling method which selects each data point with probability at least $r\in[0,1]$. If we set $r=1$, our problem reduces to finding a solution based on the original full data set. We define sampling gap as the largest ratio between the optimal solution obtained from the full data set and the optimal solution obtained from the samples, over independence systems. Our main contribution is to show that if the sampling probability of each data point is at least $r$ and the utility function is policywise submodular, then the sampling gap is both upper bounded and lower bounded by $1/r$. We show that the property of policywise submodular can be found in a wide range of real-world applications, including pool-based active learning and adaptive viral marketing.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Near-Polynomially Competitive Active Logistic Regression
대규모 언어 모델 시대에 축소되는 언어 다양성의 지형
The Shrinking Landscape of Linguistic Diversity in the Age of Large Language Models
언어는 단순한 의사소통 도구를 넘어 개인의 정체성, 심리 상태, 사회적 맥락에 관한 풍부한 정보를 담으며, 심리학·마�eting·의료 등 다양한 분야에 유용한 통찰을 제공한다. 서로 다른 도메인의 일곱 데이터셋과 88만 건 이상의 텍스트에 걸친 세 가지 연구를 통해, 대규모 언어 모델(LLM)이 쓰기 보조 도구로 널리 채택되는 것이 언어 다양성 감소와 연관되어 있으며, 언어가 제공하는 사회·심리적 통찰을 훼손함을 보인다. LLM이 텍스트를 다듬고 재작성할 때 핵심 내용은 유지되지만, LLM은 또한 문체를 동질화하여 데이터셋과 모델 전반에서 통계적으로 유의미하게(p <= .05) 문장 복잡도 분산을 21–50% 줄이고, 지배적 특성과 연관된 패턴은 강화하면서 다른 패턴은 억제하여 개성보다 순응을 강조한다. 이러한 경향은 서로 다른 LLM, 프롬프트, 맥락에서도 일관되며, 진단 과정, 개인화, 채용 평가, 문화 보존 등에 잠재적 함의를 갖는다.
CriticLean: Critic-Guided Reinforcement Learning for Mathematical Formalization
Active Learning for Manifold Gaussian Process Regression
Scalable Subset Selection in Linear Mixed Models
The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.