Timezone: »
Poster
Constrained Robust Submodular Partitioning
Shengjie Wang · Tianyi Zhou · Chandrashekhar Lavania · Jeff A Bilmes
In the robust submodular partitioning problem, we aim to allocate a set of items into $m$ blocks, so that the evaluation of the minimum block according to a submodular function is maximized. Robust submodular partitioning promotes the diversity of every block in the partition. It has many applications in machine learning, e.g., partitioning data for distributed training so that the gradients computed on every block are consistent. We study an extension of the robust submodular partition problem with additional constraints (e.g., cardinality, multiple matroids, and/or knapsack) on every block. For example, when partitioning data for distributed training, we can add a constraint that the number of samples of each class is the same in each partition block, ensuring data balance. We present two classes of algorithms, i.e., Min-Block Greedy based algorithms (with an $\Omega(1/m)$ bound), and Round-Robin Greedy based algorithms (with a constant bound) and show that under various constraints, they still have good approximation guarantees. Interestingly, while normally the latter runs in only weakly polynomial time, we show that using the two together yields strongly polynomial running time while preserving the approximation guarantee. Lastly, we apply the algorithms on a real-world machine learning data partitioning problem showing good results.
Author Information
Shengjie Wang (University of Washington)
Tianyi Zhou (University of Washington, Seattle)
Tianyi Zhou is a Ph.D. student in Computer Science at University of Washington and a member of MELODI lab led by Prof. Jeff A. Bilmes. He will be joining University of Maryland, College Park as a tenure-track assistant professor at the Department of Computer Science and affiliated with UMIACS in 2022. His research interests are in machine learning, optimization, and natural language processing. He has published ~60 papers at NeurIPS, ICML, ICLR, AISTATS, EMNLP, NAACL, COLING, KDD, ICDM, AAAI, IJCAI, ISIT, Machine Learning (Springer), IEEE TIP/TNNLS/TKDE, etc. He is the recipient of the Best Student Paper Award at ICDM 2013 and the 2020 IEEE TCSC Most Influential Paper Award.
Chandrashekhar Lavania
Jeff A Bilmes (University of Washington, Seattle)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Constrained Robust Submodular Partitioning »
Dates n/a. Room None
More from the Same Authors
-
2021 Poster: Class-Disentanglement and Applications in Adversarial Detection and Defense »
Kaiwen Yang · Tianyi Zhou · Yonggang Zhang · Xinmei Tian · Dacheng Tao -
2021 Poster: CO-PILOT: COllaborative Planning and reInforcement Learning On sub-Task curriculum »
Shuang Ao · Tianyi Zhou · Guodong Long · Qinghua Lu · Liming Zhu · Jing Jiang -
2020 Poster: Curriculum Learning by Dynamic Instance Hardness »
Tianyi Zhou · Shengjie Wang · Jeffrey A Bilmes -
2019 : Jeffrey Bilmes »
Jeff A Bilmes -
2019 Poster: Curriculum-guided Hindsight Experience Replay »
Meng Fang · Tianyi Zhou · Yali Du · Lei Han · Zhengyou Zhang -
2019 Poster: Learning to Propagate for Graph Meta-Learning »
LU LIU · Tianyi Zhou · Guodong Long · Jing Jiang · Chengqi Zhang -
2018 Poster: Diverse Ensemble Evolution: Curriculum Data-Model Marriage »
Tianyi Zhou · Shengjie Wang · Jeffrey A Bilmes -
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi -
2015 Poster: Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications »
Kai Wei · Rishabh K Iyer · Shengjie Wang · Wenruo Bai · Jeffrey A Bilmes -
2014 Poster: Divide-and-Conquer Learning by Anchoring a Conical Hull »
Tianyi Zhou · Jeffrey A Bilmes · Carlos Guestrin