Timezone: »
Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine learning. We develop faster techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. This variant is one of the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on a new connection between sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads to significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks to hypergraph clustering problems.
Author Information
Nate Veldt (Texas A&M)
Austin Benson (Cornell University)
Jon Kleinberg (Cornell University)
More from the Same Authors
-
2021 : Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2021 : Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2023 Poster: On the Relationship Between Relevance and Conflict in Online Social Link Recommendations »
Yanbang Wang · Jon Kleinberg -
2022 : Panel »
Meena Jagadeesan · Avrim Blum · Jon Kleinberg · Celestine Mendler-Dünner · Jennifer Wortman Vaughan · Chara Podimata -
2022 Poster: Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective »
Rongzhe Wei · Haoteng YIN · Junteng Jia · Austin Benson · Pan Li -
2022 Poster: Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures »
Emmanuel Abbe · Samy Bengio · Elisabetta Cornacchia · Jon Kleinberg · Aryo Lotfi · Maithra Raghu · Chiyuan Zhang -
2021 : Algorithmic Monoculture and Social Welfare »
Jon Kleinberg -
2021 : Spotlight 2: Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2021 Poster: Optimality and Stability in Federated Learning: A Game-theoretic Approach »
Kate Donahue · Jon Kleinberg -
2021 Poster: Detecting Individual Decision-Making Style: Exploring Behavioral Stylometry in Chess »
Reid McIlroy-Young · Russell Wang · Siddhartha Sen · Jon Kleinberg · Ashton Anderson -
2020 Poster: Better Set Representations For Relational Reasoning »
Qian Huang · Horace He · Abhay Singh · Yan Zhang · Ser Nam Lim · Austin Benson -
2020 Poster: Entrywise convergence of iterative methods for eigenproblems »
Vasileios Charisopoulos · Austin Benson · Anil Damle -
2019 Poster: Neural Jump Stochastic Differential Equations »
Junteng Jia · Austin Benson -
2018 Poster: Found Graph Data and Planted Vertex Covers »
Austin Benson · Jon Kleinberg -
2016 Poster: General Tensor Spectral Co-clustering for Higher-Order Data »
Tao Wu · Austin Benson · David Gleich -
2015 : Beyond Nodes and Edges: Multiresolution Models of Complex Networks »
Austin Benson -
2014 Poster: Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices »
Austin Benson · Jason D Lee · Bartek Rajwa · David F Gleich -
2014 Spotlight: Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices »
Austin Benson · Jason D Lee · Bartek Rajwa · David F Gleich