A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
The paper studies continuous submodular functions and their optimization.
New method improves submodular maximization for machine learning applications.
New method for probabilistic modeling of integer submodular functions.
New algorithms solve DR-submodular maximization with faster convergence.
The paper introduces submodular information measures for machine learning applications.
DR-submodular continuous functions are important objectives with wide real-world applications spanning MAP inference in determinantal point processes (DPPs), and mean-field inference for probabilistic submodular models, amongst others. DR-submodularity captures a subclass of non-convex functions that enables both exact…
Submodularity is one of the most well-studied properties of problem classes in combinatorial optimization and many applications of machine learning and data mining, with strong implications for guaranteed optimization. In this thesis, we investigate the role of submodularity in provable non-convex optimization and vali…
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…
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of p…
New algorithms improve submodular minimization via DC programming.
In this paper, we consider adaptive decision-making problems for stochastic state estimation with partial observations. First, we introduce the concept of weak adaptive submodularity, a generalization of adaptive submodularity, which has found great success in solving challenging adaptive state estimation problems. The…
A new kernel for ranked data tackles computational challenges.
Submodularity is studied for convex risk measures, including Expected Shortfall.
A new algorithm ThreeSieves maximizes submodular functions efficiently in streaming data.
Submodular function minimization is well studied, and existing algorithms solve it exactly or up to arbitrary accuracy. However, in many applications, such as structured sparse learning or batch Bayesian optimization, the objective function is not exactly submodular, but close. In this case, no theoretical guarantees e…
The paper examines how sampling data affects the performance of submodular maximization.
In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approa…
We investigate upper and lower hedging prices of multivariate contingent claims from the viewpoint of game-theoretic probability and submodularity. By considering a game between "Market" and "Investor" in discrete time, the pricing problem is reduced to a backward induction of an optimization over simplexes. For Europe…
Differentially private algorithms for submodular maximization under various constraints.
The ability to integrate information in the brain is considered to be an essential property for cognition and consciousness. Integrated Information Theory (IIT) hypothesizes that the amount of integrated information () in the brain is related to the level of consciousness. IIT proposes that to quantify information i…
In this paper, we study a certain class of online optimization problems, where the goal is to maximize a function that is not necessarily concave and satisfies the Diminishing Returns (DR) property under budget constraints. We analyze a primal-dual algorithm, called the Generalized Sequential algorithm, and we obtain t…
New framework for consistent submodular maximization with insertions and deletions.
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…
We are motivated by large scale submodular optimization problems, where standard algorithms that treat the submodular functions in the \emph{value oracle model} do not scale. In this paper, we present a model called the \emph{precomputational complexity model}, along with a unifying memoization based framework, which l…
Submodular functions are set functions mapping every subset of some ground set of size into the real numbers and satisfying the diminishing returns property. Submodular minimization is an important field in discrete optimization theory due to its relevance for various branches of mathematics, computer science and e…
New algorithm maximizes non-monotone adaptive submodular functions in linear time.
Paper tackles stochastic -submodular bandits with full feedback, achieving sublinear regret.
Paper tests DPPs for diversity models, distinguishing them from other distributions.
Study private submodular maximization in streaming data.
New framework tackles submodular welfare with multi-agent combinatorial bandits.
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…
Adaptive cascade submodular maximization tackles sequential selection under uncertainty.
A new method learns interpretable decision rules using submodular optimization.
Problems of segmentation, denoising, registration and 3D reconstruction are often addressed with the graph cut algorithm. However, solving an unconstrained graph cut problem is NP-hard. For tractable optimization, pairwise potentials have to fulfill the submodularity inequality. In our learning paradigm, pairwise poten…
Algorithm improves recommendation subset selection in the presence of biases.
Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfortunately, once the function deviates from submodularity, the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaini…
New algorithms reduce regret for online submodular maximization under various conditions.
This paper studies robust payoff allocation in submodular games, especially against replication.
Generative Flow Networks use submodular upper bounds to generate more data.
Fast algorithms developed for adaptive and fully adaptive submodular maximization problems.
In this paper, we propose a new framework for designing fast parallel algorithms for fundamental statistical subset selection tasks that include feature selection and experimental design. Such tasks are known to be weakly submodular and are amenable to optimization via the standard greedy algorithm. Despite its desirab…
We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a dierence between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of ou…
In this paper, we propose scalable methods for maximizing a regularized submodular function expressed as the difference between a monotone submodular function and a modular function . Indeed, submodularity is inherently related to the notions of diversity, coverage, and representativeness. In p…
Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify the best possible extension, we show an equivalence between the submodular extensions of…
New algorithm for maximizing submodular functions in real-time data changes.
In this paper, we consider the problem of black box continuous submodular maximization where we only have access to the function values and no information about the derivatives is provided. For a monotone and continuous DR-submodular function, and subject to a bounded convex body constraint, we propose Black-box Contin…
We consider active, semi-supervised learning in an offline transductive setting. We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function. Arbitrary non-symmetric submodular functions can be…
Paper proposes DG-ETC for online submodular maximization with stochastic bandit feedback.