Back to search

University of British Columbia

Beyond submodular maximization : one-sided smoothness and meta-submodularity

Abstract

dc:description

While there are well-developed tools for maximizing a submodular function f(S) subject to a matroid constraint S ∈ ℳ, there is much less work on the corresponding supermodular maximization problems. We develop new techniques for attacking these problems inspired by the continuous greedy method applied to the multi-linear extension of a submodular function. We first adapt the continuous greedy algorithm to work for general twice-continuously differentiable functions. Our results are based on a new notion of one-sided smoothness of an objective. Reminiscent of how Lipschitz smoothness bounds convergence rates in convex optimization, one-sided smoothness controls the approximability of maximizing a monotone, non-linear function. If F : [0,1]^n → ℝ≥₀ is one-sided σ-smooth, then it yields an approximation factor depending only on σ. We apply the new algorithm to a broad class of quadratic supermodular functions arising in diversity maximization. We also develop new methods for rounding quadratics over a matroid polytope. These are based on extensions to swap rounding and approximate integer decomposition. Together with the adapted continuous greedy this leads to a O(σ³/²)-approximation. This is the best asymptotic approximation known for this class of diversity maximization and we give some evidence for why we believe it may be tight. We then consider general (non-quadratic) functions. We give a broad parameterized family of monotone functions which include submodular functions and the just-discussed supermodular family of discrete quadratics. The new family is defined by restricting the one-sided smoothness condition to the boolean hypercube; such set functions are called γ-meta-submodular. We develop local search algorithms with approximation factors that depend only on γ. We show that the γ-meta-submodular families include well-known function classes including meta-submodular functions (γ - 0), proportionally submodular (γ - 1) and diversity functions based on negative-type distances or Jensen-Shannon divergence (both γ - 2) and (semi-)metric diversity functions. We then focus on maximizing a specific 1-meta-submodular function in a distributed setting. This has applications in machine learning and recommender systems. As an application, we model the multi-label feature selection problem as such an optimization problem. This combined with our optimization algorithm leads to the first distributed multi-label feature selection method.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ghadiri, Mehrdad

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/71447

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ghadiri, Mehrdad. Beyond submodular maximization : one-sided smoothness and meta-submodularity. master's thesis, University of British Columbia, 2019. http://hdl.handle.net/2429/71447