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:

Submodular Optimization

Submodular Optimization with Perfect Information

• Fast Greedy Methods: The first class of methods considers cases where the size and dimension of the data is large, but data can be fully accessible and stored in memory. 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.
• Streaming Algorithms: In cases where the data sets are too large to be stored in memory, streaming techniques are used to perform computation on the fly. These algorithms achieve desirable guarantees for machine learning tasks while using modest memory resources.
• Distributed Optimization: Distributed computation frameworks like MapReduce, Hadoop, and Spark have advanced machine learning. New algorithms leverage distributed resources to address submodular optimization's inherently non-parallelizable nature.

Submodular Optimization with Imperfect Information

• The Stochastic Oracle: This oracle provides a stochastic but unbiased estimate of the function value. Techniques are developed with minimal sample and computational complexity, addressing applications like data summarization, recommender systems, and influence maximization in social networks.
• Online/Bandit Oracle: This oracle is used when interacting with an unknown, evolving, or adversarially changing environment. The goal is to create no-regret mechanisms for maximizing cumulative objectives over time, applicable in online resource allocation, dynamic multi-robot coverage, and online recommender systems.

A Non-Convex Bridge Between Discrete and Continuous Optimization

• Framework Overview: A recently developed framework bridges discrete and continuous optimization by using continuous extensions. It finds good solutions through noisy objective value estimates, addressing highly non-convex challenges.
• Tools and Techniques: These methods exploit submodularity's special structure to avoid undesirable stationary points. Continuous submodular functions provide a rich framework for tackling non-convex problems while achieving near-optimal solutions.

Beyond Submodularity

• Generalizations: Extensions such as adaptive submodularity, weak submodularity, and two-stage submodularity provide approximation guarantees beyond traditional submodular settings. These generalizations apply to interactive settings, dictionary learning, and sparse recovery.