Optimization from Structured Samples for Coverage and Influence Functions

Channel:
Microsoft Research
Subscribers:
343,000
Published on ● Video Link: https://www.youtube.com/watch?v=ovMu8DCf0b4


Duration: 32:34
461 views
11

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.



Other Videos By Microsoft Research


2023-01-24SmartKC: A Low-cost, Smartphone-based Corneal Topographer
2023-01-11MSR-IISc AI Seminar Series: On Learning-Aware Mechanism Design - Michael I. Jordan
2022-12-22Tongue-Gesture Recognition in Head-Mounted Displays
2022-12-15Global Renewables Watch - AI for Good Lab - Geospatial
2022-12-15Toward a Healthy Research Ecosystem for Large Language Models | Panel Discussion
2022-12-14Joint Pricing and Inventory Management with Demand Learning
2022-12-14SITI 2022 - Panel Discussion and moderated Q&A session
2022-12-12Machine Learning for Combinatorial Optimization: Some Empirical Studies
2022-12-12Online Facility Location with Predictions
2022-12-12Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits
2022-12-12Optimization from Structured Samples for Coverage and Influence Functions
2022-12-06Personality Predictions from Automated Video Interviews: Explainable or Unexplainable Models?
2022-12-06Responsible AI: An Interdisciplinary Approach | Panel Discussion
2022-12-06Personalizing Responsibility within AI Systems: A Case for Designing Diversity
2022-12-06Evidence-based Evaluation for Responsible AI
2022-12-06Towards Trustworthy Recommender Systems: From Shallow Models to Deep Models to Large Models
2022-12-06Development of a Game-Based Assessment to Measure Creativity
2022-12-06Interpretability, Responsibility and Controllability of Human Behaviors
2022-12-06On the Adversarial Robustness of Deep Learning
2022-12-06The Long March Towards AI Fairness
2022-12-06Towards Human Value Based Natural Language Processing (NLP)