New method for probabilistic modeling of integer submodular functions.
problem Lack of probabilistic modeling for integer submodular functions.
method Proposed Generalized Multilinear Extension and block-coordinate ascent algorithm.
result Demonstrated effectiveness and viability on real-world datasets.
Improved model capacity for graph cut algorithms by relaxing submodularity constraints.
problem Improving graph cut algorithms for complex image processing tasks.
method Enforce probably approximately submodular pairwise potentials instead of guaranteed submodular ones.
result Substantial improvement in model capacity with reduced inference error.
A new pruning method reduces submodular maximization costs.
problem Efficiently maximizing submodular functions with reduced computational cost.
method Submodular sparsification via submodularity graph pruning.
result Pruned submodularity graph reduces computational cost and memory usage.
New optimization method for graph-based learning problems.
problem Minimizing decomposable submodular functions in graph and hypergraph settings.
method Dual strategy and random coordinate descent with projections.
result RCD algorithm converges linearly and achieves significant improvements in prediction accuracy.
Paper proposes a new method to minimize submodular functions with fewer calls to simpler oracles.
problem Minimizing the sum of submodular set functions with limited information.
method Introduces a modified convex problem requiring constrained total variation oracles that can be solved with fewer calls to minimization oracles.
result Shows significant reduction in the number of calls to minimization oracles.
We consider active, semi-supervised learning in an offline transductive setting. We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function. Arbitrary non-symmetric submodular functions can be…
A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constr…
A new kernel for ranked data tackles computational challenges.
problem Complex geometric structure and partial rankings make existing algorithms infeasible for real-world applications.
method Derives a graph cut kernel that combines submodular optimization and kernel-based methods.
result The graph cut kernel efficiently handles large-scale ranked data.
Improves scalability of Bayesian optimization for combinatorial spaces.
problem Optimizing expensive functions over large combinatorial spaces.
method Parametrized Submodular Relaxation (PSR) to solve AFO problems for BOCS.
result Significant improvements in scalability and accuracy for BOCS model.
The paper introduces submodular information measures for machine learning applications.
problem Generalizing information-theoretic measures to non-random variables.
method Developing combinatorial information measures based on submodular functions.
result Submodular mutual information is submodular in one argument for certain submodular functions.
New method for efficient graph signal sampling and reconstruction.
problem Minimizing MSE in graph signal reconstruction with noisy data.
method Formulated as binary constraint minimization, approximated via SDP relaxation and greedy algorithm.
result Randomized greedy algorithm provides near-optimal subset with significant speedup.
Submodular functions have many applications. Matchings have many applications. The bitext word alignment problem can be modeled as the problem of maximizing a nonnegative, monotone, submodular function constrained to matchings in a complete bipartite graph where each vertex corresponds to a word in the two input senten…
Unified framework for robust submodular optimization with various constraints.
problem Robust optimization in machine learning applications.
method Unified framework for minimization and maximization under combinatorial constraints.
result Scalable approximation algorithms for various submodular optimization problems.
New optimization problem for graph and hypergraph learning tasks.
problem Learning tasks on graphs and hypergraphs.
method Quadratic decomposable submodular function minimization (QDSFM) via dual strategy and double-loop algorithms.
result Linear convergence rates for outer-loop optimization and effective hypergraph-based PageRank algorithm.
This paper tackles robust submodular minimization for image segmentation and correspondence.
problem Robust submodular minimization for image segmentation and correspondence.
method Constrained submodular minimization with scalable approximation algorithms for various combinatorial constraints.
result First work on robust submodular minimization under broad combinatorial constraints.
New algorithms solve DR-submodular maximization with faster convergence.
problem Maximizing monotone DR-submodular functions under convex constraints.
method Introduced strongly DR-submodular functions and proposed SDRFW and PGA algorithms.
result SDRFW achieves optimal approximation ratio after fewer iterations.
This paper proposes a submodular load clustering method for transmission-level load areas.
problem Traditional load analysis challenges with new electricity usage patterns.
method Robust Principal Component Analysis (R-PCA) and submodular cluster center selection.
result The proposed method efficiently clusters load areas and demonstrates effectiveness in PJM load data.
Study on identifying AMP chain graph models under known and unknown component decompositions.
problem Identifying AMP chain graph models with known and unknown chain component decompositions.
method Analyzes conditions for identifiability of AMP models and proposes algorithms for structure recovery.
result Conditions for DAG identifiability in AMP models extend equal variance criteria for Bayes nets.
In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approa…
We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends …
SALSA improves submodular maximization on streaming data to 0.632 approximation.
problem Maximizing submodular functions on data streams with cardinality constraints.
method SALSA, a new low-memory, single-pass algorithm for streaming submodular maximization.
result SALSA achieves a 0.632 approximation factor, improving over the 0.5 factor of previous methods.
Paper tackles BNSL with IP, improving quality of solutions.
problem Bayesian Network Structure Learning (BNSL) with IP formulations.
method Inexact column generation using difference-of-submodular optimization.
result Improved solutions quality compared to state-of-the-art approaches.
The paper studies continuous submodular functions and their optimization.
problem Maximizing continuous submodular functions in poly. time.
method Characterization of continuous submodularity, operations preserving it, and algorithms for constrained maximization.
result Continuous submodularity is equivalent to a weak DR property, leading to continuous DR-submodular functions with the full DR property.
We present an exploration of the rich theoretical connections between several classes of regularized models, network flows, and recent results in submodular function theory. This work unifies key aspects of these problems under a common theory, leading to novel methods for working with several important models of inter…
To cope with the high level of ambiguity faced in domains such as Computer Vision or Natural Language processing, robust prediction methods often search for a diverse set of high-quality candidate solutions or proposals. In structured prediction problems, this becomes a daunting task, as the solution space (image label…
New method approximates non-submodular functions, offering first guarantees.
problem Minimizing non-submodular functions without theoretical guarantees.
method Extends submodularity relations to non-submodular functions, offering approximation guarantees.
result First approximation guarantees for non-submodular minimization, optimal under noise.
Submodularity is studied for convex risk measures, including Expected Shortfall.
problem Characterizing submodularity in convex risk measures.
method Analyzing submodularity properties of law-invariant coherent risk measures, including Expected Shortfall and Value-at-Risk.
result AES is submodular only when it reduces to ES, and empirical analysis shows AES violations are less frequent than VaR and ES violations.
Differentially private algorithms for submodular maximization under various constraints.
problem Maximizing decomposable submodular functions under constraints while preserving privacy.
method Designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints.
result Improved utility guarantees and competitive performance compared to non-private algorithms.
A new framework speeds up submodular optimization for large problems.
problem Large scale submodular optimization problems are hard to solve.
method Memoization framework for submodular functions with precomputed statistics.
result Significant speedups for various submodular optimization problems.
We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a mor…
This thesis explores how submodularity aids in optimizing non-convex functions and validating algorithms.
problem Understanding which functions can be optimized efficiently in non-convex settings.
method Introducing continuous submodularity and developing algorithms for maximizing these functions.
result Characterization and optimization of continuous submodular functions with strong guarantees.
A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions,…
New algorithm maximizes non-monotone adaptive submodular functions in linear time.
problem Maximizing non-monotone adaptive submodular functions subject to a cardinality constraint.
method Developed a linear-time algorithm for non-monotone adaptive submodular maximization.
result Achieved a 1/e−ε approximation ratio with O(nε−2logε−1) value oracle queries. Submodular functions can be exactly minimized in polynomial time, and the special case that graph cuts solve with max flow \cite{KZ:PAMI04} has had significant impact in computer vision \cite{BVZ:PAMI01,Kwatra:SIGGRAPH03,Rother:GrabCut04}. In this paper we address the important class of sum-of-submodular (SoS) function…
We study how to make submodular optimization more efficient.
problem Scalability of submodular optimization methods.
method Introduce reducibility concept and perturbation-reduction optimization framework.
result Our framework significantly accelerates optimization for irreducible submodular functions.
Paper tackles stochastic k-submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k-submodular functions with full-bandit feedback. method Proposes online algorithms for various k-submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α-regret bounds for multiple k-submodular stochastic combinatorial multi-armed bandit problems. Study private submodular maximization in streaming data.
problem Private maximization of submodular functions in streaming data.
method Established differentially private baselines and derived better trade-offs for decomposable submodular functions.
result Improved trade-offs between privacy and utility for decomposable submodular functions.
Greedy policy achieves good results for adaptive submodular problems.
problem Sequential decision making with adaptive stochastic optimization.
method Adaptive submodularity ratio to analyze greedy policy performance.
result Greedy policy achieves approximation guarantees for a broader class of problems.
Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization.
problem Maximizing continuous non-monotone submodular and DR-submodular functions.
method Developed novel algorithms for both continuous submodular and DR-submodular maximization problems.
result First $ rac{1}{2}$-approximation algorithm for continuous submodular maximization.
New algorithm improves weakly submodular maximization beyond cardinality constraints.
problem Maximizing weakly submodular functions under non-cardinality constraints.
method Randomized greedy algorithm for weakly submodular maximization under matroid constraints.
result Randomized greedy achieves an approximation ratio of (1+1/γ)−2 for weakly submodular maximization under matroid constraints. New framework tackles submodular welfare with multi-agent combinatorial bandits.
problem Maximizing total welfare among agents with shared constraints and submodular utilities under bandit feedback.
method Proposes an explore-then-commit strategy with randomized assignments for multi-agent combinatorial bandits.
result Achieves ildeO(T2/3) regret, first for partition-based submodular welfare problem under bandit feedback. Optimizes experiment design for causal structure learning in linear models with cycles.
problem Causal structure learning from combined observational and interventional data in linear non-Gaussian cyclic models.
method Combinatorial characterization of equivalence classes, adaptive stochastic optimization, greedy policy with near-optimal performance guarantee, sampling-based estimator for reward function.
result Optimal experiment design reduces the equivalence class of causal graphs to a single true graph with a small number of interventions.
New algorithm improves non-submodular objective maximization in adversarial settings.
problem Maximizing non-submodular objectives under adversarial deletions.
method Oblivious-Greedy algorithm for non-submodular objectives.
result First constant-factor guarantees for non-submodular objectives.
A derivative-free algorithm improves continuous submodular maximization.
problem Maximizing monotone DR-submodular continuous functions without gradient information.
method LDGM algorithm for continuous DR-submodular maximization, with β and α parameters. result LDGM achieves (1−e−β−ϵ)-approximation guarantee with O(1/ϵ) iterations. Derives an approximation algorithm for continuous submodular maximization without derivative information.
problem Maximizing a continuous submodular function with only function values and no derivative information.
method Black-box Continuous Greedy algorithm for DR-submodular functions, extended to stochastic setting.
result Achieves a (1−1/e)OPT−ε approximation guarantee with O(d/ε3) function evaluations. Optimizes submodular extensions for efficient marginal estimation.
problem Efficiently compute approximate marginals for submodular energy functions.
method Equivalence between submodular extensions and LP relaxations for MAP estimation; worst-case optimality established.
result Worst-case optimal submodular extension for various models.
New connection between subset selection and submodular maximization.
problem Subset selection and submodular maximization in high-dimensional settings.
method Greedy algorithms and weak submodularity.
result Greedy algorithms perform within a constant factor of the best possible subset-selection solution.
Three online algorithms for submodular maximization with varying feedback types.
problem Maximizing submodular functions under different feedback models.
method Mono-Frank-Wolfe, Bandit-Frank-Wolfe, Responsive-Frank-Wolfe.
result Achieved (1−1/e)-regret bounds for each algorithm.