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 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.
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.
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. 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.
Fast algorithms developed for adaptive and fully adaptive submodular maximization problems.
problem Maximizing submodular functions subject to constraints in linear time.
method Developed linear-time algorithms for two submodular maximization problems: adaptive and fully adaptive.
result Achieved (1−1/e−ε) approximation ratio for adaptive submodular maximization and $ rac{1-1/e-ε}{4-2/e-2ε}$ for fully adaptive submodular maximization. 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.
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.
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.
Paper tackles adaptive submodularity in sequential decision making.
problem Maximizing adaptive submodular functions with limited adaptive rounds.
method Proposes an efficient semi-adaptive policy with logarithmic adaptive rounds.
result Achieves an almost tight 1−1/e−ε approximation guarantee. Algorithm finds best elements for unknown submodular function with noisy evaluations.
problem Maximizing unknown submodular function with noisy user feedback.
method Adaptive sampling with lbox{} module for exploration.
result PAC-style guarantees on solution quality and sampling cost.
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.
Greedy algorithms near-optimal for adaptive optimization with budget constraint.
problem Adaptive optimization with budget constraint in AI and ML.
method Investigates two simple greedy algorithms and a combined algorithm for pointwise submodular and cost-sensitive submodular functions.
result Best greedy algorithm is near-optimal with respect to optimal algorithm using half the budget.
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.
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.
FAST algorithm maximizes submodular functions efficiently.
problem Maximizing submodular functions under cardinality constraints.
method Fast Adaptive Sequencing Technique (FAST) for submodular maximization.
result FAST achieves an approximation ratio of 1−1/e with O(log(n)log2(logk)) adaptive queries and O(nloglog(k)) total queries. Adaptive greedy policy tackles sequential decision making problems.
problem Finding optimal sequences in interactive and sequential decision making.
method Submodularity and adaptive greedy policy with theoretical guarantees.
result Strong theoretical guarantees for adaptive greedy policy.
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 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.
Paper proposes DG-ETC for online submodular maximization with stochastic bandit feedback.
problem Online unconstrained submodular maximization with stochastic bandit feedback.
method Double-Greedy - Explore-then-Commit (DG-ETC) approach.
result DG-ETC achieves logarithmic regret O(dlog(dT)) for 1/2-approximate pseudo-regret. A new algorithm tackles submodular bandit problems with multiple constraints.
problem Addressing diversified retrieval and online learning with budget constraints.
method Non-greedy algorithm focusing on upper-confidence bounds.
result High-probability upper bound of an approximation regret matching fast offline algorithm's ratio.
Paper improves submodular streaming with better approximation, less memory, and lower complexity.
problem Maximizing submodular functions in streaming with a cardinality constraint.
method Sieve-Streaming++ with one pass, O(k) memory, and (1/2)-approximation; adaptive complexity reduction. result Achieves (1/2)-approximation with O(k) memory and low adaptive complexity. 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.
New method tackles online DR-submodular maximization with improved regret guarantees.
problem Online maximization of non-monotone DR-submodular functions over down-closed convex sets.
method 1/e-linearization through exponential reparametrization, surrogate potential, and reduction to online linear optimization.
result Achieves O(T1/2) static regret with single gradient query per round, improving state of the art. 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.
A streaming algorithm for document/video summarization that performs as well as offline greedy methods.
problem Efficiently summarizing documents or videos from a stream of data.
method stream clipper algorithm that adds elements to a solution set or buffer, swapping elements based on adaptive thresholds.
result The algorithm performs as well as offline greedy methods in practice, with improved efficiency in terms of computation and memory usage.
Paper introduces a new framework for optimizing non-convex functions.
problem Optimizing non-convex functions, especially DR-submodular and concave functions.
method Developed a general meta-algorithm to convert linear/quadratic optimization to optimization of upper-linearizable/quadratizable functions.
result Unified approach to concave and DR-submodular optimization problems.
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.
Adaptive system diversifies and personalizes visual browsing for better user engagement.
problem Poor performance of search queries in ambiguous or inspirational browsing scenarios.
method Bayesian regression for scoring relevance, submodular diversification, and personalized category preferences learned from user behavior.
result Significant improvement in click-through-rate and session duration on live traffic.
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 guarantees for adaptive combinatorial maximization with various objectives.
problem Maximizing under cardinality constraints and minimum cost coverage in adaptive settings.
method Bayesian approach with comprehensive approximation guarantees for various utility functions.
result Maximal gain ratio is a new parameter that provides stronger approximation guarantees than greedy policies.
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. 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.
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…