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.
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.
Novel convex surrogate for submodular losses with tractable computation.
problem Learning with non-modular losses for set prediction.
method Proposed Lovász hinge loss function for submodular losses.
result First tractable convex surrogates for submodular losses.
Corrects a claim about IoU loss being submodular, showing it's true.
problem Clarifies the submodularity of IoU loss function.
method Analyzes the misreading of set membership in previous claims.
result Demonstrates that the previous claims about IoU loss are incorrect.
Novel convex surrogate for non-modular loss functions.
problem Computational tractability for non-modular loss functions.
method Submodular-supermodular decomposition, slack-rescaling, Lov{á}sz hinge.
result First tractable solution for non-modular loss functions.
A new convex loss function optimizes set predictions with balanced size and coverage.
problem Optimizing set predictions with balanced size and coverage.
method Proposes a convex loss function using Choquet integrals for nondecreasing subset-valued functions.
result Optimal trade-offs between conditional probabilistic coverage and set size.
New algorithms solve non-convex isotonic regression problems efficiently.
problem Minimizing submodular functions with ordering constraints.
method Discretization schemes leading to zero-th, first, or higher order oracles for efficient optimization.
result Non-convex loss functions can be robust to outliers and still lead to efficient optimization.
This work explores scalable submodular optimization for networked systems.
problem Optimal subset selection in large systems with high computational complexity.
method Leader-selection in multi-agent networks, stochastic and distributed greedy algorithms, accelerated computation oracles.
result Significant speedups with little loss of optimality compared to baseline algorithms.
The paper examines how sampling data affects the performance of submodular maximization.
problem Performance loss due to probability sampling in submodular maximization.
method Examines a simple probability sampling method where each data point is selected with probability at least r.
result The sampling gap is both upper and lower bounded by 1/r for policywise submodular utility functions.
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 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.
Study finds an efficient algorithm for measuring integrated information in large neural systems.
problem Finding the Minimum Information Partition (MIP) for measuring integrated information in large neural systems is computationally expensive.
method Developed an optimization algorithm that can find the MIP in polynomial time for non-submodular measures of integrated information.
result The algorithm accurately identifies the MIP in large systems, making it practical for real neural data.
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.
New algorithm for online convex minimization over integer lattice.
problem Online decision-making with nonlinear combinatorial objectives.
method Introduces online Latural-convex minimization and proposes efficient algorithms. result Tight regret bound for full information setting algorithm.
New method achieves small-loss regret bounds in random-order model.
problem Online learning with adversarial loss functions in random order.
method Extending batch-to-online transformation, using average sensitivity and stability.
result Small-loss regret bounds of order ildeO(φ⋆(OPTT)). 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 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 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. Meta-learning for discrete tasks using submodular optimization.
problem Improving performance on new tasks with limited data.
method Discrete submodular optimization for personalized initial solutions.
result Significant reduction in computational cost for new tasks.
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.
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. 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.