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.
Adaptive decision-making for state estimation with partial observations.
problem Stochastic state estimation with partial observations and active diagnosis.
method Weak adaptive submodularity and adaptive greedy policy.
result Adaptive greedy policy achieves near-optimal performance for weakly adaptive submodular reward functions.
New algorithm speeds up greedy feature selection for large datasets.
problem High running time for greedy feature selection in large datasets.
method Developed a new algorithm that achieves better performance by exploiting distributed computation and stochastic evaluation.
result Submodularity is not required for multiplicative approximation guarantees of these algorithms.
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.
New method improves submodular maximization for machine learning applications.
problem Inexact monotonicity in submodular functions limits traditional algorithms' performance.
method Introduces monotonicity ratio as a continuous version of monotonicity, leading to improved approximation guarantees.
result Improved approximation ratios for movie recommendation, quadratic programming, and image summarization.
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.
New algorithm explains neural network predictions in real-time.
problem Interpreting deep neural network predictions.
method Streaming algorithm for combinatorial maximization with weakly submodular objective.
result First theoretical guarantee for this class of functions.
Optimal subset selection for hypothesis testing with penalties.
problem Optimal subset selection of information sources for hypothesis testing with misclassification penalties.
method Proposes a misclassification penalty framework and studies two variants of subset selection problems under centralized Bayesian learning.
result Proves the submodularity of the objective and constraints of the subset selection problems and establishes performance guarantees for greedy algorithms.
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.
New SLC distributions enable easier control over diversity.
problem Lack of easy control over diversity in existing models.
method Developed strongly log-concave distributions and two tools for sampling and mode finding.
result Established weak log-submodularity for SLC functions and optimization guarantees for mode finding.
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.
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.
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.
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.
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.
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. 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. 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.
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.
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.
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. 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…
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.
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. A scalable approach for distributed submodular maximization under fixed machine capacity.
problem Large-scale machine learning problems constrained by limited machine capacity.
method Proposes a truly scalable approach for distributed submodular maximization.
result Achieves performance competitive with centralized greedy solution.
Paper improves greedy algorithm for non-submodular matroid constraints.
problem Maximizing non-submodular functions subject to matroid constraints.
method Developed and analyzed a greedy algorithm with approximation guarantees.
result Greedy algorithm offers approximation factors for matroid 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.
Scalable methods for maximizing regularized submodular functions with improved memory and communication complexity.
problem Maximizing submodular functions with negative values and constraints.
method Developed one-pass streaming and distributed algorithms for maximizing regularized submodular functions.
result Improved memory and communication complexity by a factor of O(1/ε) compared to existing work.
Adaptive cascade submodular maximization tackles sequential selection under uncertainty.
problem Maximizing expected utility from a set of items with unknown states and continuation probabilities.
method Proposed adaptive cascade submodular functions and a 0.12 approximation algorithm.
result Identified a class of functions (adaptive cascade submodular) that many practical applications satisfy.
IoU is not submodular, impacting machine learning applications.
problem IoU's submodularity assumption in machine learning is incorrect.
method Demonstrated through counterexamples and analysis of function properties.
result IoU is not a submodular function, invalidating its use in certain applications.
A new method learns interpretable decision rules using submodular optimization.
problem Learning interpretable decision rules from data.
method Submodular optimization approach for selecting rules from a large set.
result The method effectively learns interpretable rule sets from real datasets.
Two algorithms maximize DR-submodular functions under convex constraints.
problem Maximizing non-monotone DR-submodular functions under convex constraints.
method Developed two algorithms with provable guarantees: a two-phase algorithm with 1/4 approximation and a Frank-Wolfe variant with 1/e approximation.
result Proved strong relation between stationary points and global optimum for DR-submodular functions.
New algorithm speeds up feature selection and experimental design.
problem Designing efficient parallel algorithms for statistical subset selection.
method Differential submodularity and adaptive sampling.
result Logarithmic parallel runtime for feature selection and experimental design.
Algorithm improves recommendation subset selection in the presence of biases.
problem Maximizing submodular functions for recommendation in the presence of social biases.
method Algorithm for submodular maximization with fairness constraints.
result Algorithm provably outputs subsets with near-optimal utility and proportional representation.
Paper tackles non-monotone DR-submodular maximization with approximation and regret guarantees.
problem Maximizing non-monotone DR-submodular functions over specific sets.
method Frank-Wolfe algorithm for general convex sets, Stochastic Gradient Ascent for down-closed convex sets.
result First approximation guarantees for both offline and online settings.
New algorithms reduce regret for online submodular maximization under various conditions.
problem Online optimization of submodular functions with adversarial or random utilities.
method Characterized strongly DR-submodular functions and derived bounds for different utility classes.
result Logarithmic regret bounds for adversarial strongly DR-submodular functions and submodular functions with random order.
Issue found in proof of adaptive submodular function minimization theorem.
problem Proof of adaptive submodular function minimization theorem is incorrect.
method Example provided to show incorrectness of a critical step in a related theorem.
result Critical step in related theorem is found to be incorrect.
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.
This paper studies robust payoff allocation in submodular games, especially against replication.
problem Payoff allocation in submodular games, especially robustness against replication.
method Systematically studied replication manipulation in submodular games, introduced replication robustness metric, and validated with empirical ML data market.
result Conditions characterizing robustness of semivalues in submodular games.
Generative Flow Networks use submodular upper bounds to generate more data.
problem Generating data from unknown, complex reward functions efficiently.
method Introduce submodular upper bounds to estimate reward, use Optimism in the Face of Uncertainty principle to train GFNs.
result SUBo-GFN generates significantly more data than classical GFNs.