Optimization from Structured Samples for Coverage and Influence Functions @MicrosoftResearch

Microsoft Research | Optimization from Structured Samples for Coverage and Influence Functions @MicrosoftResearch | Uploaded December 2022 | Updated October 2024, 1 week ago.
2022 Data-driven Optimization Workshop: Optimization from Structured Samples for Coverage and Influence Functions

Speaker: Zhijie Zhang, Fuzhou University

We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we cannot obtain a constant approximation ratio for the maximum coverage problem using polynomial independent samples of the form {S_i,f(S_i )}_(i=1)^t (BRS, STOC17), even if coverage functions are (1-ϵ)-PMAC learnable using these samples (BDF+, SODA12). In this work, to circumvent the impossibility result of OPS, we propose a stronger model called optimization from structured samples (OPSS), where the data samples encode the structural information of the functions. We show that under OPSS model, the maximum coverage problem enjoys constant approximation under mild assumptions on the sample distribution. We further generalize the result and show that influence maximization also enjoys constant approximation under this model.

$Optimization from Structured Samples for Coverage and Influence Functions 2022 Data-driven Optimization Workshop: Optimization from Structured Samples for Coverage and Influence Functions Speaker: Zhijie Zhang, Fuzhou University We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we cannot obtain a constant approximation ratio for the maximum coverage problem using polynomial independent samples of the form {S_i,f(S_i )}_(i=1)^t (BRS, STOC17), even if coverage functions are (1-ϵ)-PMAC learnable using these samples (BDF+, SODA12). In this work, to circumvent the impossibility result of OPS, we propose a stronger model called optimization from structured samples (OPSS), where the data samples encode the structural information of the functions. We show that under OPSS model, the maximum coverage problem enjoys constant approximation under mild assumptions on the sample distribution. We further generalize the result and show that influence maximization also enjoys constant approximation under this model.$

Evaluation and Understanding of Foundation Models

Fighting the Global Social Media Infodemic: from Fake News to Harmful Content

Final intern talk: Distilling Self-Supervised-Learning-Based Speech Quality Assessment into Compact

AI Forum 2023 | The Emergence of General AI for Medicine

End-to-end Reinforcement Learning for the Large-scale Traveling Salesman Problem

Online Facility Location with Predictions

Improving text prediction accuracy using neurophysiology

AI Case Studies for Natural Science Research with Bonnie Kruft

Lightning talks: Sustainably nourishing the world