Robust budget allocation via continuous submodular functions

DOI10.1007/S00245-019-09567-0zbMATH Open1465.90057arXiv1702.08791OpenAlexW3160894936MaRDI QIDQ2019911FDOQ2019911

Authors: Matthew Staib, Stefanie Jegelka 

Publication date: 22 April 2021

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision $epsilon$.

Full work available at URL: https://arxiv.org/abs/1702.08791

Recommendations

• Robust monotone submodular function maximization
• Robust monotone submodular function maximization
• Adaptive robust submodular optimization and beyond
• Robust submodular minimization with applications to cooperative modeling
• Generalized budgeted submodular set function maximization

zbMATH Keywords

nonconvex optimizationrobust optimizationbudget allocationsubmodular optimizationconstrained submodular optimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Robustness in mathematical programming (90C17)

Cites Work

• Templates for convex cone problems with applications to sparse signal recovery
• Active set algorithms for isotonic regression; a unifying framework
• Theory and applications of robust optimization
• Robust optimization
• Conditional gradient algorithms with open loop step size rules
• Robust discrete optimization and network flows
• Robust solutions of linear programming problems contaminated with uncertain data
• Submodular functions and optimization.
• Rings of sets
• Title not available (Why is that?)
• Minimizing a Submodular Function on a Lattice
• A tutorial on geometric programming
• Finding the nearest point in A polytope
• Submodular Function Minimization under Covering Constraints
• Geometric Programming for Communication Systems
• Approximation algorithms for reliable stochastic combinatorial optimization
• Relative entropy relaxations for signomial optimization
• Polymatroids and mean-risk minimization in discrete optimization
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Stochastic Covering and Adaptivity
• Discrete convex analysis
• New algorithms for convex cost tension problem with application to computer vision
• Geometric Programming: Methods, Computations and Applications
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Maximizing social influence in nearly optimal time
• Title not available (Why is that?)
• Robust monotone submodular function maximization
• Subquadratic submodular function minimization
• Constrained maximization of posynomials by geometric programming
• Submodular functions: from discrete to continuous domains
• Supermodular programming on finite lattices
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Exact bounds for steepest descent algorithms of $L$-convex function minimization
• Risk averse submodular utility maximization
• Submodular function maximization on the bounded integer lattice
• Submodular stochastic probing on matroids
• The limitations of optimization from samples

Cited In (3)

• A bi-criteria algorithm for online non-monotone maximization problems: DR-submodular+concave
• Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret
• Frameworks and results in distributionally robust optimization

Uses Software

• TFOCS

This page was built for publication: Robust budget allocation via continuous submodular functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019911)