Diminishing-returns (DR) submodular optimization is an important field with many real-world applications in machine learning, economics and communication systems. It captures a subclass of non-convex optimization that provides both practical and theoretical guarantees. In this paper, we study the fundamental problem of…
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “DR-submodular maximization”
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.
In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guar…
Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Setscs.LG
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 static regret with single gradient query per round, improving state of the art.
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.
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…
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.
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.
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.
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…
Mean field inference in probabilistic models is generally a highly nonconvex problem. Existing optimization methods, e.g., coordinate ascent algorithms, can only generate local optima. In this work we propose provable mean filed methods for probabilistic log-submodular models and its posterior agreement (PA) with stron…
In this paper, we study the problem of monotone (weakly) DR-submodular continuous maximization. While previous methods require the gradient information of the objective function, we propose a derivative-free algorithm LDGM for the first time. We define and to characterize how close a function is to continuous D…
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the…
In this paper, we propose three online algorithms for submodular maximisation. The first one, Mono-Frank-Wolfe, reduces the number of per-function gradient evaluations from [Chen2018Online] and [chen2018projection] to 1, and achieves a -regret bound of . The second one, Bandit-F…
A dissertation on scalable projection-free optimization methods.
problem Efficient optimization algorithms for large-scale machine learning problems.
method Study of Frank-Wolfe variants and their extensions to distributed and derivative-free settings.
result Development of 1-SFW and QFW, achieving state-of-the-art complexity and efficiency.
From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Modelscs.LG
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.
This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems; however, their applicability remains limited when the problem dimension is large and the projecti…
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…
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 with communication complexity of and linear optimization calls of .
In this paper, we study a class of online optimization problems with long-term budget constraints where the objective functions are not necessarily concave (nor convex) but they instead satisfy the Diminishing Returns (DR) property. Specifically, a sequence of monotone DR-submodular objective functions $\{f_t(x)\}_{t=1…
One of the beauties of the projected gradient descent method lies in its rather simple mechanism and yet stable behavior with inexact, stochastic gradients, which has led to its wide-spread use in many machine learning applications. However, once we replace the projection operator with a simpler linear program, as is d…
Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularitystat.ML
Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scal…
Study finds Hilbert square of real surfaces can be maximal even when the surface has disconnected real locus.
problem Exploring conditions for maximality of Hilbert square of real surfaces.
method Analyzing Hilbert square of maximal real surfaces and examining specific examples.
result Hilbert square can be maximal even for surfaces with disconnected real locus.
Maximal knotless graphsmath.GT
Maximal knotless graphs have at least 74% of their vertices' edges.
problem Characterizing maximal knotless graphs and understanding their edge constraints.
method Analyzing edge maximality and constructing graphs to meet constraints.
result There exists an infinite family of maximal knotless graphs with fewer edges than previously thought.
The paper finds maximal metrics on Euclidean spaces.
problem Finding maximal elements in moduli spaces of Riemannian metrics.
method Defining a preorder on moduli space by isometry groups and identifying maximal elements.
result Constructs many examples of maximal metrics on Euclidean spaces.
Survey on geometry and topology of maximal antipodal sets.
problem Maximal antipodal sets on Riemannian manifolds.
method Comprehensive survey of existing research.
result Relation to various mathematical areas.
New bounds on maximal linkless graphs with improved edge-to-vertex ratios.
problem Finding maximal linklessly embeddable graphs with improved edge-to-vertex ratios.
method Constructing families of graphs and proving necessary and sufficient conditions for clique sums.
result Improved edge-to-vertex ratios for maximal linklessly embeddable graphs.
Study examines maximal domains of radial harmonic functions across different curvature types.
problem Understanding maximal domains of radial harmonic functions in various curvature settings.
method Analysis of harmonic spaces with positive, zero, and negative curvature.
result Characterization of maximal domains for radial harmonic functions in different curvature contexts.
We shall investigate maximal surfaces in Minkowski 3-space with singularities. Although the plane is the only complete maximal surface without singular points, there are many other complete maximal surfaces with singularities and we show that they satisfy an Osserman-type inequality.
The paper explores reflection principles for lightlike line segments on maximal surfaces.
problem Reflection property does not hold for lightlike line segments on maximal surfaces.
method Analyzes reflection properties for lightlike line segments connecting shrinking singularities.
result Shows a kind of reflection principle for lightlike line segments on maximal surfaces.
New maximal surfaces solve Bernstein problems.
problem Bernstein problems in centroaffine geometry.
method Calabi affine maximal surfaces and orthonormal frame fields.
result Complete centroaffine extremal hypersurfaces solve all Bernstein problems.
The study finds that maximizing median returns is the only viable strategy in portfolio selection.
problem Difficulties in studying optimal portfolio strategies due to discontinuity and time inconsistency in maximizing median and quantile returns.
method Used intra-personal equilibrium approach to analyze portfolio selection under median and quantile maximization.
result Median maximization is the only viable strategy, with no investment in risky assets for other quantiles.
This paper surveys AUC maximization for big data and AI.
problem Assessing classifier performance for imbalanced data.
method Maximizing AUC score directly.
result No comprehensive survey of AUC maximization exists.
Study of large group actions on surfaces, focusing on Hurwitz and handlebody groups.
problem Characterizing and understanding group actions on surfaces, especially maximal handlebody and Hurwitz groups.
method Analyzing various group actions, comparing Hurwitz and handlebody groups, and examining bounding actions.
result Relationship between Hurwitz groups and maximal handlebody groups, and insights into geometric bounding actions.
We study homologically maximizing timelike geodesics in conformally flat tori. A causal geodesic in such a torus is said to be homologically maximizing if one (hence every) lift of to the universal cover is arclength maximizing. First we prove a compactness result for homologically maximizing timelike geodesics…
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.
The ball maximizes the first biharmonic Steklov eigenvalue.
problem Maximizing the first biharmonic Steklov eigenvalue for bounded domains.
method Comparing domains with fixed measure to find the maximum eigenvalue.
result The ball maximizes the first positive biharmonic Steklov eigenvalue.
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 approximation ratio for adaptive submodular maximization and $ rac{1-1/e-ε}{4-2/e-2ε}$ for fully adaptive submodular maximization.
Study on maximal surfaces with high genus in Lorentz-Minkowski space.
problem Existence of nonorientable maximal surfaces with high genus.
method Existence results for nonorientable maximal surfaces with high genus and one end.
result Existence of maximal surfaces with high genus in Lorentz-Minkowski space.
We show that a positive braid knot has maximal topological 4-genus exactly if it has maximal signature invariant. As an application, we determine all positive braid knots with maximal topological 4-genus and compute the topological 4-genus for all positive braid knots with up to 12 crossings.
In the present paper we study two-dimensional maximal surfaces with harmonic level-sets. As a corollary we obtain a new class of one-periodic maximal surfaces.
Maximal representations in symplectic lattices proven for most cases.
problem Understanding maximal representations in symplectic lattices.
method Analyzing mapping class group orbits and continuous deformations of maximal diagonal representations.
result Proof of maximal representations in most lattices of Sp(2n,R).
The geometry and topology of complete nonorientable maximal surfaces with lightlike singularities in the Lorentz-Minkowski 3-space are studied. Some topological congruence formulae for surfaces of this kind are obtained. As a consequence, some existence and uniqueness results for maximal Moebius strips and maximal Klei…
We consider trading in a financial market with proportional transaction costs. In the frictionless case, claims are maximal if and only if they are priced by a consistent price process--the equivalent of an equivalent martingale measure. This result fails in the presence of transaction costs. A properly maximal claim i…
We study the poset of Hamiltonian tori for polygon spaces. We determine some maximal elements and give examples where maximal Hamiltonian tori are not all of the same dimension.
Lorentz meets Lipschitzmath.DG
Maximal causal curves for Lipschitz metrics are either lightlike or timelike.
problem Characterizing maximal causal curves for Lipschitz metrics.
method Analyzing the parametrization and geodesic equation for maximal causal curves in terms of Filippov solutions.
result Maximal causal curves for Lipschitz metrics are either everywhere lightlike or everywhere timelike.
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.
Maximal dilatation found on nonorientable surfaces.
problem Finding maximal dilatation on nonorientable surfaces.
method Proving irreducibility of a polynomial to show maximal dilatation.
result Maximal dilatation is achieved by the Liechti-Strenner polynomial.