AI 독서 파트너

DR-submodularity (Bian et al., 2017b), i.e., ∂²Iₜ(x)/∂xᵢ∂xⱼ ≤ 0, ∀i, j. If there are N advertisers providing N schemes, let x = [x¹, …, xᴺ], where xⁱ ∈ ℝ₊ˢ. We aim to maximize the impact on the least affected customers with the influence of N advertisers, modeled as

where αᵢ > 0 denotes the weights. Obviously, (3) is a robust DR-submodular maximization problem.

1.4 Organization

The rest of our paper is organized as follows. Preliminaries, including relevant notations, definitions, zeroth-order gradient estimations and a generic zeroth-order stochastic approximation algorithm framework, are given in Section 2. In Section 3, we propose two specific zeroth-order stochastic approximation methods, CG-ZOSA and RG-ZOSA, and present their approximation analysis for smooth DR-submodular maximization problem. Section 4 introduces a novel finite-sum auxiliary function for smoothed functions, and then designs the NZOSA algorithm for non-smooth up-concave maximization. We further extend NZOSA to apply for a class of robust submodular optimization problems in Section 5. The efficiency of the proposed algorithms is validated by extensive experiments in Section 6. Finally, we present our conclusions in Section 7.

2. Preliminaries

2.1 Notations and Definitions

We denote basis vectors by eᵢ := (0, …, 1, 0, …, 0)ᵀ ∈ ℝᵈ, where the i-th component is 1, and the radius and diameter of the constraint set 𝒳 by R := max_{x∈𝒳}‖x‖ and D := max_{x,y∈𝒳}‖x − y‖ respectively, where ‖·‖ is ℓ₂-norm by default.

For x, y ∈ ℝᵈ, we denote (x ∨ y)ᵢ = max{xᵢ, yᵢ} and (x ∧ y)ᵢ = min{xᵢ, yᵢ}, and x ≤ y means xᵢ ≤ yᵢ, ∀i ∈ [d]. Given x ∈ ℝᵈ and u > 0, denote by 𝔹_d(x, u) = {y ∈ ℝᵈ | ‖x − y‖ ≤ u} the ℓ₂-norm ball of radius u centered at x, and denote 𝕊 = {x ∈ ℝᵈ : ‖x‖ = 1} as the unit sphere. Given 𝒟 ⊆ ℝᵈ, we say that f : 𝒟 → ℝ is L₀-Lipschitz continuous w.r.t. the norm ‖·‖ if |f(x) − f(y)| ≤ L₀‖x − y‖ for any x, y ∈ 𝒟, and that f is L-smooth if its gradient is L-Lipschitz continuous. A continuous function f : 𝒟 → ℝ is said to be submodular, if

holds for all x, y ∈ 𝒟. If furthermore f is twice differentiable, the submodularity is equivalent to that all off-diagonal entries of its Hessian are non-positive, i.e., ∂²f(x)/∂xᵢ∂xⱼ ≤ 0, ∀x ∈ 𝒟 and i ≠ j.

Definition 1. (DR-submodular function) Given a convex set 𝒟 ⊆ ℝᵈ, a continuous function f : ℝᵈ → ℝ is said to be DR-submodular over 𝒟, if for any x ≤ y ∈ 𝒟 and a ∈ ℝ₊ such that (aeᵢ + x) ∈ 𝒟, (aeᵢ + y) ∈ 𝒟, ∀i ∈ {1, 2, …, d}, the following diminishing return (DR) property holds: