Guaranteed Non convex Optimization Submodular Maximization Over Continuous Domains

Title: ICML 2020 Tutorial on Submodular Optimization: From Discrete to Continuous and Back

Speakers: Hamed Hassani (UPenn), Amin Karbasi (Yale)

1. Hamed Hassani

School of Engineering and Applied Sciences
University of Pennsylvania
Philadelphia, PA 19104

2. Amin Karbasi

Yale Institute for Network Science
Yale University
New Haven, CT 06520

Slides

1. Module 1
2. Module 2
3. Module 3
4. Module 4

Videos

1. Part I
2. Part II
3. Part III
4. Part IV

Brief Description and Outline

This tutorial will cover recent advancements in discrete optimization methods for large-scale machine learning. Traditionally, machine learning has been harnessing convex optimization to design fast algorithms with provable guarantees for a broad range of applications. In recent years, however, there has been a surge of interest in applications that involve discrete optimization. For discrete domains, the analog of convexity is considered to be submodularity, and the evolving theory of submodular optimization has been a catalyst for progress in extraordinarily varied application areas including active learning and experimental design, vision, sparse reconstruction, graph inference, video analysis, clustering, document summarization, object detection, information retrieval, network inference, interpreting neural network, and discrete adversarial attacks.

As applications and techniques of submodular optimization mature, a fundamental gap between theory and application emerges. In the past decade, paradigms such as large-scale learning, distributed systems, and sequential decision making have enabled a quantum leap in the performance of learning methodologies. Incorporating these paradigms in discrete problems has led to fundamentally new frameworks for submodular optimization. The goal of this tutorial is to cover rigorous and scalable foundations for discrete optimization in complex, dynamic environments, addressing challenges of scalability and uncertainty, and facilitating distributed and sequential learning in broader discrete settings. More specifically, we will cover advancements in four areas:

1. Submodular Optimization with Perfect Information.

State-of-the-art submodular optimization techniques have mostly assumed perfect knowledge about the optimization problem and the environment. More precisely, the existing techniques have been designed based on the availability of an oracle with full information about the objective function at any queried point. In this context, recent work in submodular optimization has widely focused on developing fast, efficient, and provable methodologies in the presence of massive, high-dimensional data:

• Fast Greedy Methods. The first class of methods consider cases where the size and dimension of the data is large, but data can be fully accessible and stored in memory. Accordingly, fast greedy algorithms have been proposed recently with almost optimal run-time efficiency in terms of the query complexity and dimension of data while maintaining optimal quality guarantees in terms of objective value 1, 2, 3, 4,49, 50-61.

• Streaming Algorithms: In cases where the data sets are too large to be stored in memory, we consider streaming techniques, where computation is performed on the y. A recent line of work has been focused on developing algorithms that obtain desirable guarantees for important tasks in machine learning while using modest memory resources 5, 6, 7, 8, 9,62-68.

• Distributed Optimization: The rise of distributed computation frameworks such as MapReduce, Hadoop, and Spark, enabled unprecedented advancement in machine 1 learning. Although submodular optimization is a canonical example of computation that cannot be parallelized, there is a great deal of work on new algorithm design approaches that can utilize distributed computational resources 10, 11, 12, 13, 14, 15, 16,69-77.

2. Submodular Optimization with Imperfect Information

In many modern applications, perfect-information oracles can not assumed, and instead, we resort to approximate or imperfect ones in order to address challenges such as scalability, uncertainty in data and models, as well as dynamic and adversarial environments. We will formalize oracles with imperfect information through three main classes{Stochastic, Online, and Bandit} each of which opens a new avenue in the field of discrete (submodular) optimization and requires fundamentally novel techniques:

• The Stochastic Oracle. The stochastic oracle returns a stochastic, but unbiased estimate of the function value at any query point. Given this type of oracle access to the function values, the primary question is to develop stochastic submodular optimization techniques with minimal sample complexity (i.e. the total number of queries from the stochastic oracle) and computation complexity 17, 18. The stochastic oracle is motivated form practical and large-scale applications and covers popular instances of discrete optimization: (i) Oftentimes in practice the objective is defined in terms of an empirical risk, i.e., through a finite sum of loss functions associated to the data points. This formulation appears in submodular applications such as data summarization 19, 20, 21, recommender systems 22, 18, and sparse regression 23, 24, 25 etc. (ii) In some other cases, the objective is given as an expectation over an explicit stochastic model which is hard/intractable to compute. For example, in influence maximization in social networks 26,the objective value is defned as the expectation of a stochastic difiusion process, quantifying the expected fraction of the network influenced from a selected seed set.

• Online/Bandit Oracle. This type of oracle is the model of choice when the optimizer/learner has to interact with an unknown, evolving, or even adversarially changing environment. The oracle's outcome in this setting varies with time, and depending on how limited the oracle's outcome is, we can define two different scenarios: online, and bandit settings. The primary optimization goal in this setting is to provide no-regret mechanisms to maximize the cumulative objective over time. Online and Bandit submodular optimization, introduced in 27, 28, 29, arises naturally in discrete applications involving dynamic environments, e.g. online/dynamic resource allocation 30, 27, online ranking 31, 32, sensor placement in unknown or adversarial environments 33, in uencing dynamic social networks 34, online recommender systems 35, 36, and dynamic multi-robot coverage problems 37.

3. A Non-Convex Bridge Between Discrete and Continuous Optimization

To address discrete otimization with imperfect oracles, we will describe a recently developed framework which bridges discrete and continuous optimization. Through appropriate continuous extensions, this framework devises algorithms that succeed in finding good solutions by making a large number of small, exploratory steps using noisy estimates of the objective value, and moving toward the optimal solution. As we will discuss, solving the resulting continuous problems requires novel methods beyond the state-of-the-art, because they are highly non-convex and possess undesirable stationary points. We show how tools from discrete and continuous optimization as well as techniques that exploit the special structure (submodularity) admitted by these problems and avoid those bad stationary points 18 38, 39, 40, 41, 42, 43. Indeed, submodular optimization is inherently related to continuous optimization as many submodular optimization methods rely on continuous relaxations. This connection has recently been strengthen by introducing continuous submodular functions 44, 45, 78, 18. Such functions are not convex (nor concave) but still allow finding near-optimal solutions, thus providing a rich framework for studying non-convex optimization problems.

4. Beyond Submodularity

Finally, one can generalize the notion of submodularity and still provide approximation guarantees. Several of such generalizations, e.g., adaptive submodularity 46, 47, weak submodularity 25, 9, two-stage submodularity 48, etc, have been recently proposed. These generalizations extend the applications of submodularity to interactive settings, dictionary learning, and sparse recovery.

References

1.	AAAI	2015	Lazier Than Lazy Greedy	Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause
2.	ICML	2016	Fast Constrained Submodular Maximization: Personalized Data Summarization	Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi
3.	SODA	2014	Submodular maximization with cardinality constraints	N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz
4.	ICML	2014	Fast multi-stage submodular maximization: Extended version	K. Wei, R. Iyer, and J. Bilmes
5.	KDD	2014	Streaming submodular maximization: massive data summarization on the fly	A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause
6.	DISC	2014	On Streaming and Communication Complexity of the Set Cover Problem	Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian
7.	ICALP	2015	Streaming algorithms for submodular function maximization	C. Chekuri, S. Gupta, and K. Quanrud
8.	SODA	2015	Online Submodular Maximization with Preemption	N. Buchbinder, M. Feldman, and R. Schwartz
9.	NIPS	2017	Streaming Weak Submodularity: Interpreting Neural Networks on the Fly	E. R. Elenberg, A. G. Dimakis, M. Feldman, and A. Karbasi
10.	JMLR	2016	Distributed Submodular Maximization	Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, Andreas Krause;
11.	NIPS	2015	Distributed Submodular Cover: Succinctly Summarizing Massive Data	. Mirzasoleiman, A. Karbasi, A. Badanidiyuru, and A. Krause
12.	NIPS	2016	Fast Distributed Submodular Cover: Public-Private Data Summarization	B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi
13.	NIPS	2013	Distributed Submodular Maximization: Identifying Representative Elements in Massive Data	B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause
14.	STOC	2015	Randomized Composable Core-sets for Distributed Submodular Maximization	V. Mirrokni and M. Zadimoghaddam
15.	SPAA	2013	Fast greedy algorithms in mapreduce and streaming	R. Kumar, B. Moseley, S. Vassilvitskii, and A. Vattani
16.	FOCS	2016	A new framework for distributed submodular maximization	R. Barbosa, A. Ene, H. L. Nguyen, and J. Ward
17.	NIPS	2017	Stochastic Submodular Maximization: The Case of Coverage Functions	M. Karimi, M. Lucic, H. Hassani, and A. Krasue
18.	NIPS	2017	Gradient Methods for Submodular Maximization	H. Hassani, M. Soltanolkotabi, and A. Karbasi
19.	ACL	2011	A class of submodular functions for document summarization,	H. Lin and J. Bilmes
20.	EMNLP	2014	Submodularity for data selection in statistical machine translation	K. Kirchhofi and J. Bilmes
21.	CIKM	2012	Temporal corpus summarization using submodular word coverage	R. Sipos, A. Swaminathan, P. Shivaswamy, and T. Joachims
22.	COLT	2017	Greed is good: Near-optimal submodular maximization via greedy optimization	M. Feldman, C. Harshaw, and A. Karbasi
23.	ICML	2010	Submodular dictionary selection for sparse representation	A. Krause and V. Cevher,
24.	ICML	2016	Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection	A. Das and D. Kempe
25.	The Annals of Statistics	2018	RESTRICTED STRONG CONVEXITY IMPLIES WEAK SUBMODULARITY	E. R. Elenberg, R. Khanna, A. G. Dimakis, and S. Negahban
26.	SIGKDD	2003	Maximizing the spread of in uence through a social network	D. Kempe, J. Kleinberg, and E. Tardos
27.	NIPS	2009	An online algorithm for maximizing submodular functions,	M. Streeter and D. Golovin
28.	NIPS	2011	Linear submodular bandits and their application to diversified retrieva	Y. Yue and C. Guestrin
29.	ICML	2011	Online submodular minimization for combinatorial structures	S. Jegelka and J. A. Bilmes
30.	AAAI	2011	Dynamic resource allocation in conservation planning	D. Golovin, A. Krause, B. Gardner, S. J. Converse, and S. Morey
31.	NIPS	2011	Online submodular set cover, ranking, and repeated active learning	A. Guillory and J. A. Bilmes
32.	ICML	2010	Learning optimally diverse rankings over large document collections	A. Slivkins, F. Radlinski, and S. Gollapudi
33.	AAAI	2011	Randomized sensing in adversarial environment	A. Krause, A. Roper, and D. Golovin
34.	ICDM	2013	Influence maximization in dynamic social networks	H. Zhuang, Y. Sun, J. Tang, J. Zhang, and X. Sun
35.	arXiv	2014	Online submodular maximization under a matroid constraint with application to learning assignments	D. Golovin, A. Krause, and M. Streeter
36.	IJCAI	2015	Optimal greedy diversity for recommendation	A. Ashkan, B. Kveton, S. Berkovsky, and Z. Wen
37.	RSS	2016	Eficient online multi-robot exploration via distributed sequential greedy assignment	M. Corah and N. Michael
38.	JMLR	2018	Stochastic conditional gradient methods: From convex minimization to submodular maximization	A. Mokhtari, H. Hassani, and A. Karbasi
39.	ICML	2018	Projection-free online optimization with stochastic gradient: From convexity to submodularity,	L. Chen, C. Harshaw, H. Hassani, and A. Karbasi
40.	AISTATS	2018	Online continuous submodular maximization	L. Chen, H. Hassani, and A. Karbasi
41.	arXiv	2019	Stochastic conditional gradient++	H. Hassani, A. Karbasi, A. Mokhtari, and Z. Shen
42.	NIPS	2018	Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization	R. Niazadeh, T. Roughgarden, and J. Wang
43.	NIPS	2017	Continuous dr-submodular maximization: Structure and algorithms	A. Bian, K. Levy, A. Krause, and J. M. Buhmann
44.	Springer	2017	Submodular functions: from discrete to continuous domains	F. Bach
45.	AISTATS	2017	Guaranteed non-convex optimization: Submodular maximization over continuous domains	A. Bian, B. Mirzasoleiman, J. M. Buhmann, and A. Krause
46.	JAIR	2016	Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization	D. Golovin and A. Krause
47.	AAAI	2015	Submodular surrogates for value of information	Y. Chen, S. Javdani, A. Karbasi, J. A. Bagnell, S. S. Srinivasa, and A. Krause
48.	ICML	2016	Learning sparse combinatorial representations via two-stage submodular maximization	E. Balkanski, A. Krause, B. Mirzasoleiman, and Y. Singer
49.	Mathematical Programming	1987	An Analysis of Approximations for Maximizing Submodular Set Functions—I	G. L. Nemhauser, L. A. Wolsey & M. L. Fisher
50.	Optimization Techniques	1978	Accelerated greedy algorithms for maximizing submodular set functions	Michel Minoux
51.	SODA	2014	Submodular Maximization With Cardinality Constraints	Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
52.	ICML	2017	Differentially Private Submodular Maximization: Data Summarization in Disguise	Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi
53.	arXiv	2020	Regularized Submodular Maximization at Scale	Ehsan Kazemi, Shervin Minaee, Moran Feldman, Amin Karbasi
53.	SODA	2013	fast algorithms for maximizing submodular functions	Ashwinkumar Badanidiyuru Jan Vondrak
54.	ICML	2020	Efficient Algorithms and Lower Bound for Submodular Maximization	Wenxin Li, Ness Shroff
55.	ICML	2017	Robust Guarantees of Stochastic Greedy Algorithms	Avinatan Hassidim, Yaron Singer
56.	WINE	2010	Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms	Anupam Gupta, Aaron Roth, Grant Schoenebeck, Kunal Talwar
57.	PMLR	2017	Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization	Moran Feldman, Christopher Harshaw, Amin Karbasi
58.	PMLR	2016	Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization	Eric Balkanski, Baharan Mirzasoleiman, Andreas Krause, Yaron Singer
59.	ICML	2017	Probabilistic Submodular Maximization in Sub-Linear Time	Serban Stan, Morteza Zadimoghaddam, Andreas Krause, Amin Karbasi
60.	ICALP	2018	A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint	Alina Ene∗ Huy L. Nguyên†
61.	arXiv	2020	Submodular Maximization Through Barrier Functions	Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák
62.	ICML	2019	Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity	Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi , Amin Karbasi
63.	Mathematical Programming	2015	submodular maximization meets streaming: matching, magroids and more	Amit Chakrabarti, Sagar Kale
64.	STOC	2020	The one-way communication complexity of submodular maximization with applications to streaming and robustness	Feldman, Moran and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico
65.	arXiv	2020	Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model	Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida
66.	arXiv	2020	Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints	Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, Andrew Suh
67.	NIPS	2018	Do Less, Get More: Streaming Submodular Maximization with Subsampling	Moran Feldman, Amin Karbasi, Ehsan Kazemi
68.	ICML	2020	streaming submodular maximization under a k-system constraint	Haba, Ran and Kazemi, Ehsan and Feldman, Moran and Karbasi, Amin
69.	ICML	2015	The Power of Randomization: Distributed Submodular Maximization on Massive Datasets	Rafael Barbosa, Alina Ene, Huy Nguyen, Justin Ward
71.	NIPS	2014	Parallel Double Greedy Submodular Maximization", Pan, Jegelka, Gonzalez, Bradley, Jordan	Xinghao Pan, Stefanie Jegelka, Joseph Gonzalez, Joseph Bradley, Michael I. Jordan
72.	KDD	2018	Optimal Distributed Submodular Optimization via Sketching	Bateni, MohammadHossein, Hossein Esfandiari, and Vahab Mirrokni
73.	STOC	2018	The adaptive complexity of maximizing a submodular function	Eric Balkanskim Yaron Singer
74.	SODA	2019	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation	Eric Balkanski, Aviad Rubinstein, Yaron Singer
75.	SODA	2018	Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time	Alina Ene, Huy L. Nguyen
76.	SODA	2019	Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity	Matthew Fahrbach, Vahab Mirrokni and Morteza Zadimoghaddam
77.	STOC	2019	Unconstrained submodular maximization with constant adaptive complexity	Lin Chen, Moran Feldman, Amin Karbasi
78.	arXiv	2020	Continuous Submodular Maximization: Beyond DR-Submodularity	Moran Feldman, Amin Karbasi

funkalisome.blogspot.com

Source: http://iid.yale.edu/icml/icml-20.md/

Share this post