# Online Subset Selection using α-Core with no Augmented Regret

arXiv: https://arxiv.org/abs/2209.14222 · HTML: https://mlsanity.com/paper/2209.14222/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 72 references that are in the map.
- First posted on arXiv 28 Sep 2022.

## Builds on (most cited first, 29 of 29)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Scalable Greedy Feature Selection via Weak Submodularity](https://mlsanity.com/paper/1703.02723/) (2017)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Optimal approximation for unconstrained non-submodular minimization](https://mlsanity.com/paper/1905.12145/) (2019)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP](https://mlsanity.com/paper/1706.04690/) (2017)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Robust Maximization of Non-Submodular Objectives](https://mlsanity.com/paper/1802.07073/) (2018)
- [Weakly Submodular Function Maximization Using Local Submodularity Ratio](https://mlsanity.com/paper/2004.14650/) (2020)
- [Greedy Minimization of Weakly Supermodular Set Functions](https://mlsanity.com/paper/1502.06528/) (2015)
- [Online Sparse Linear Regression](https://mlsanity.com/paper/1603.02250/) (2016)
- [Combinatorial Penalties: Which structures are preserved by convex relaxations?](https://mlsanity.com/paper/1710.06273/) (2017)
- [Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice](https://mlsanity.com/paper/1805.06990/) (2018)
- [Approximate Core for Committee Selection via Multilinear Extension and Market Clearing](https://mlsanity.com/paper/2110.12499/) (2021)
- [Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression](https://mlsanity.com/paper/2102.09644/) (2021)
- [The General Graph Matching Game: Approximate Core](https://mlsanity.com/paper/2101.07390/) (2021)

## Abstract (arXiv)

We revisit the classic problem of optimal subset selection in the online learning set-up. Assume that the set [N] consists of N distinct elements. On the tth round, an adversary chooses a monotone reward function ft: 2[N] → ℝ_+ that assigns a non-negative reward to each subset of [N]. An online policy selects (perhaps randomly) a subset St subseteq [N] consisting of k elements before the reward function ft for the tth round is revealed to the learner. As a consequence of its choice, the policy receives a reward of ft(St) on the tth round. Our goal is to design an online sequential subset selection policy to maximize the expected cumulative reward accumulated over a time horizon. In this connection, we propose an online learning policy called SCore (Subset Selection with Core) that solves the problem for a large class of reward functions. The proposed SCore policy is based on a new polyhedral characterization of the reward functions called α-Core - a generalization of Core from the cooperative game theory literature. We establish a learning guarantee for the SCore policy in terms of a new performance metric called α-augmented regret. In this new metric, the performance of the online policy is compared with an unrestricted offline benchmark that can select all N elements at every round. We show that a large class of reward functions, including submodular, can be efficiently optimized with the SCore policy. We also extend the proposed policy to the optimistic learning set-up where the learner has access to additional untrusted hints regarding the reward functions. Finally, we conclude the paper with a list of open problems.