Two new online optimization algorithms tackle convex and submodular problems without projections or exact gradients.
problem Efficiently optimize non-convex functions like submodular functions under computational constraints.
method Meta-Frank-Wolfe and One-Shot Frank-Wolfe algorithms using stochastic gradient estimates.
result Achieve optimal adversarial regret bounds for convex and continuous submodular optimization.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. The paper tackles online optimization with continuous submodular functions, achieving sublinear regret bounds.
problem Online optimization with continuous submodular functions.
method Proposes Frank-Wolfe algorithm and online stochastic gradient ascent for continuous submodular maximization.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bounds against ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) -approximation and 1 / 2 1/2 1/2 -approximation in hindsight. An optimal algorithm maximizes submodular functions online with no-1/2 regret.
problem Maximizing submodular functions in an online setting with limited information.
method Polynomial-time no-1/2-regret algorithm for online unconstrained submodular maximization.
result Achieves 1/2 times the maximum total value of a fixed subset in hindsight, up to a sublinear error term.
Paper tackles online DR-submodular maximization with various convex sets.
problem Maximizing DR-submodular functions online over different convex sets.
method Develops online algorithms with approximation guarantees for various convex sets.
result Achieves 1 / e 1/e 1/ e -approximation ratio with O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) regret for down-closed sets. 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 ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) static regret with single gradient query per round, improving state of the art. Paper develops privacy-preserving algorithms for online submodular optimization.
problem Online submodular optimization under differential privacy constraints.
method Develops algorithms for both full information and bandit feedback settings, using Lovasz extensions and unbiased estimates.
result Achieves low expected regret with differential privacy guarantees in both settings.
Paper analyzes an algorithm for maximizing non-concave functions with budget constraints.
problem Maximizing non-concave functions with budget constraints under DR-submodularity.
method Generalized Sequential algorithm for online monotone DR-submodular function maximization.
result First competitive ratio bound matches known tight bound for linear objective functions.
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 ( d log ( d T ) ) O(d\log(dT)) O ( d log ( d T )) for 1 / 2 1/2 1/2 -approximate pseudo-regret. 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.
Paper tackles online DR-submodular maximization with stochastic constraints.
problem Maximizing utility while adhering to a cumulative resource constraint in an online setting.
method Proposes OLFW algorithm to solve the problem of online continuous DR-submodular maximization with linear stochastic constraints.
result Obtains sub-linear regret and constraint violation bounds.
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 ) (1-1/e) ( 1 − 1/ e ) -regret bounds for each algorithm. Many prediction domains, such as ad placement, recommendation, trajectory prediction, and document summarization, require predicting a set or list of options. Such lists are often evaluated using submodular reward functions that measure both quality and diversity. We propose a simple, efficient, and provably near-optim…
New algorithm for online convex minimization over integer lattice.
problem Online decision-making with nonlinear combinatorial objectives.
method Introduces online L a t u r a l \mathrm{L}^{
atural} L a t u r a l -convex minimization and proposes efficient algorithms. result Tight regret bound for full information setting algorithm.
The paper tackles online optimization with DR-submodular functions and linear budgets.
problem Optimizing points over time with long-term budget constraints and DR-submodular objectives.
method Proposes OSPHG algorithm to achieve sub-linear regret and budget violation bounds.
result Achieves sub-linear bounds for both regret and total budget violation under certain window lengths.
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 framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing ( α , β , δ , e x t t t N ) (α,β,δ, exttt{N}) ( α , β , δ , e x ttt N ) -resilience and developing a black-box framework. result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
New framework for decentralized optimization of upper-linearizable functions with improved regret and complexity.
problem Decentralized optimization of upper-linearizable functions with general constraints.
method Decentralized projection-free optimization with upper-linearizable function framework.
result Regret of O ( T 1 − θ / 2 ) O(T^{1-θ/2}) O ( T 1 − θ /2 ) with communication complexity of O ( T θ ) O(T^θ) O ( T θ ) and linear optimization calls of O ( T 2 θ ) O(T^{2θ}) O ( T 2 θ ) . Transforms offline greedy algorithms to online algorithms for combinatorial problems.
problem Online decision-making in time-varying combinatorial environments.
method General framework using Blackwell approachability and Bandit Blackwell approachability.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret in full information setting and O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) regret in bandit setting. Study on maximizing submodular functions with limited updates, achieving tight bounds and poly-time algorithms.
problem Online submodular maximization with constant recourse.
method Information-theoretic bounds and poly-time randomized algorithms.
result Achieved tight bounds of 2/3 and 3/4 for general and coverage functions, respectively, with a 0.51 approximation.
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.
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.
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 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 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.
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.
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.
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 improves submodular function optimization by directly optimizing a combination of bias and variance.
problem Optimizing submodular functions under distributional uncertainty.
method Distributionally robust optimization (DRO) for submodular functions.
result DRO improves performance on the actual underlying function compared to standard methods.
New method optimizes discrete submodular problems using stochastic gradient descent.
problem Optimizing submodular functions in discrete settings with stochastic elements.
method Projected stochastic gradient ascent for continuous optimization, followed by rounding.
result Achieves optimal approximation guarantees with significantly reduced computational cost.
The scalability of submodular optimization methods is critical for their usability in practice. In this paper, we study the reducibility of submodular functions, a property that enables us to reduce the solution space of submodular optimization problems without performance loss. We introduce the concept of reducibility…
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.
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 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.
Differentiable submodular maximization combines learning and optimization.
problem Learning and optimizing submodular functions separately.
method Interpreting greedy maximization as distributions, smoothing, and differentiating.
result The approach optimizes submodular functions with theoretical guarantees.
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.
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.
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.
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 β \beta β and α \alpha α parameters. result LDGM achieves ( 1 − e − β − ϵ ) (1-e^{-\beta}-\epsilon) ( 1 − e − β − ϵ ) -approximation guarantee with O ( 1 / ϵ ) O(1/\epsilon) O ( 1/ ϵ ) iterations. 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.
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…
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.
Apricot selects subsets from large data sets efficiently using submodular optimization.
problem Efficiently selecting representative subsets from large data sets.
method Submodular optimization with efficient greedy algorithm.
result Strong theoretical guarantees on the quality of selected subsets.
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.
New algorithm solves optimization problems without submodularity.
problem Finding efficient solutions for optimization problems when submodularity does not hold.
method Parallel quasi-concave set optimization algorithm.
result Efficient globally optimal solution to maxi-min problems.
Stochastic conditional gradient methods improve optimization for convex and submodular functions.
problem Optimization of large-scale stochastic problems with high-dimensional constraints.
method Proposes averaging technique for gradient approximations and linear programming for descent/ascent directions.
result Achieves optimal or near-optimal guarantees for various submodular maximization problems.
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.