# Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization

Authors: Zhigang Li; Mingchuan Zhang; Junlong Zhu; Ruijuan Zheng; Qikun Zhang; Qingtao Wu
Journal: Complexity
 (2018)

---

## Abstract

We consider a stochastic continuous submodular huge-scale optimization problem, which arises naturally in many applications such as machine learning. Due to high-dimensional data, the computation of the whole gradient vector can become prohibitively expensive. To reduce the complexity and memory requirements, we propose a stochastic block-coordinate gradient projection algorithm for maximizing continuous submodular functions, which chooses a random subset of gradient vector and updates the estimates along the positive gradient direction. We prove that the estimates of all nodes generated by the algorithm converge to some stationary points with probability 1. Moreover, we show that the proposed algorithm achieves the tight(pmin/2F⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for DR-submodular functions by choosing appropriate step sizes. Furthermore, we also show that the algorithm achieves the tight (γ2/1+γ2pminF⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for weakly DR-submodular functions with parameter γ by choosing diminishing step sizes.


---

## Body

## 1. Introduction

In this paper, we focus on the submodular function maximization, which has recently attracted significant attention in academia since submodularity is a crucial concept in combinatorial optimization. Furthermore, they have arisen in a variety of areas, such as social sciences, algorithm game theory, signal processing, machine learning, and computer vision. Furthermore, submodular functions have found many applications in the applied mathematics and computer science, such as probabilistic models [1, 2], crowd teaching [3, 4], representation learning [5], data summarization [6], document summarization [7], recommender systems [8], product recommendation [9, 10], sensor placement [11], network monitoring [12, 13], the design of structured norms [14], clustering [15], dictionary learning [16], active learning [17], and the utility maximization in sensor networks [18].In submodular optimization problems, there exist many polynomial time algorithms for exactly minimizing the submodular functions, such as combinatorial algorithms [19–21]. In addition, there also exist many polynomial time algorithms for approximately maximizing the submodular functions with approximation guarantees, such as the local search and greedy algorithms [22–25]. Despite this progress, these methods use the combinatorial techniques, which have some limitations [26]. For this reason, a new approach is proposed by using multilinear relaxation [27], which can lift the submodular functions optimization problems into the continuous domain. Thus, the continuous optimization techniques are used to minimize exactly or maximize approximately submodular functions in polynomial time. Recently, most literature is devoted to continuous submodular optimization [28–31]. The algorithms cited above need to compute all the (sub)gradients.However, the computation of all (sub)gradients can become prohibitively expensive when dealing with huge-scale optimization problems, where the decision vectors are high-dimensional. For this reason, coordinate descent method and its variants are proposed for solving efficiently convex optimization problems [32]. At each iteration, the coordinate descent methods only choose one block of variables to update their decision vectors. Thus, they can reduce the memory and complexity requirements at each iteration when dealing with high-dimensional data. Furthermore, coordinate descent methods can be applied in support vector machine [33], large-scale optimization problems [34–37], protein loop closure [38], regression [39], compressed sensing [40], etc. In coordinate descent methods, the choice of search strategy mainly include cyclic coordinate search [41–43] and the random coordinate search [44–46]. In addition, the asynchronous coordinate decent methods are also proposed in recent years [47, 48].Despite this progress, however, stochastic block-coordinate gradient projection methods for maximizing submodular functions have barely been investigated. To fill this gap, we propose the stochastic block-coordinate gradient projection algorithm to solve stochastic continuous submodular optimization problems, which are introduced in [30]. In order to reduce the complexity and memory requirements at each iteration, we incorporate the block-coordinate decomposition into the stochastic gradient projection in the proposed algorithm. The main contributions of this paper are as follows:(i)
We propose a stochastic block-coordinate gradient projection algorithm for maximizing continuous submodular functions. In the proposed algorithm, each node chooses a random subset of the whole approximation gradient vector and updates its decision vector along gradient ascent direction.(ii)
We show that each node asymptotically converges to some stationary points by the stochastic block-coordinate gradient projection algorithm; i.e., the estimates of all nodes converge to some stationary points with probability 1.(iii)
We investigate the convergence rate of stochastic block-coordinate gradient projection algorithm with approximation guarantee. When the submodular functions are DR-submodular, we prove that the convergence rate ofO(1/T) is achieved with pmin/2 approximation guarantee. More generally, we show that the convergence rate of O(1/T) is achieved with pmin(1-γ2/(1+γ2)) approximation guarantee for weakly DR-submodular functions with parameter γ.The remainder of this paper is organized as follows. We describe mathematical background in Section2. We formulate the problem of our interest and propose a stochastic block-coordinate gradient projection algorithm in Section 3. In Section 4, the main results of this paper are stated. The detailed proofs of the main results of the paper are provided in Section 5. The conclusion of the paper is presented in Section 6.


## 2. Mathematical Background

Given a ground setV, which consists of n elements. If a set function f:2V→R+ satisfies(1)fA+fB≥fA∩B+fA∪Bfor all subsets A,B⊆V, then the set function f is called submodular. The notation of submodularity is mostly used in discrete domain, but it can be extended to continuous domain [49]. Given a subset of R+n, X=∏i=1n‍Xi, where each set Xi is a subset of R+ and is compact. A continuous function F:X→R+ is called submodular continuous function if, for all x,y∈X, the following inequality(2)Fx+Fy≥Fx∨y+Fx∧yholds, where x∨y≔maxx,y (coordinate-wise) and x∧y≔minx,y (coordinate-wise). Moreover, if x⪯y, we have Fx≤Fy for all x,y∈X, and then the submodular continuous function F is called monotone on X. Furthermore, a differentiable submodular continuous function F is calledDR-submodular if, for all x,y∈X such that x⪯y, we have ∇Fx⪰∇Fy; i.e., ∇F· is an antitone mapping [29]. When the submodular continuous function F is twice differentiable, the submodular F is submodular if and only if all off-diagonal components of its Hessian matrix are nonpositive [28]; i.e., for all x∈X,(3)∂2Fx∂xi∂xj≤0,∀i≠j.Furthermore, if the submodular function F is DR-submodular, then all second-derivatives are nonpositive [29]; i.e., for all x∈X,(4)∂2Fx∂xi∂xj≤0.In addition, the twice differentiability implies that the submodular F is smooth [50]. Moreover, we say that a submodular function F is β-smooth if, ∀x,y∈X, we have(5)Fy≤Fx+∇Fx,y-x+β2y-x2.Note that the above definition is equivalent to(6)∇Fx-∇Fy≤βx-y.Furthermore, a function F is calledweakly DR-submodular function with parameter γ if(7)γ≔infx,y∈X,x≤y⁡infi∈1,…,n⁡∇Fxi∇Fyi.More details about weak DR-submodular functions are available in [29].


## 3. Problem Formulation and Algorithm Design

In this section, we first describe the problem of our interest, and then we design an algorithm to efficiently solve the problem.In this paper, we focus on the following constrained optimization problem:(8)maxx∈K⁡Fx≔Eξ~DFξx,where K denotes the constraint set, D denotes an unknown distribution, Fξ is a submodular continuous function for all ξ∈D. Moreover, we assume that the constraint set, K=∏i=1n‍Ki⊆X, is convex, where each Ki⊆R+ is convex and closed set for all i=1,…,n. The problem has recently been introduced in [30]. In addition, we use the notation F∗ to denote the optimal value of Fx for all x∈K, i.e., F∗≔maxx∈KFx. Furthermore, we can see that the function Fx is submodular function because each function Fξ is submodular continuous function for all ξ∈D [28].To solve problem (8), the projected stochastic gradient methods are a class of efficient algorithms [31]. However, we focus on the case that the decision vectors x are high-dimensional in this work; i.e., the dimensionality of vectors n is large. The full gradient computations are prohibitive expensive and become computational bottleneck. Therefore, we propose a stochastic block-coordinate gradient method by combining the great features of block-coordinate and stochastic gradient. We assume that the components of decision variables are arbitrarily chosen but fixed for each processor. Furthermore, at each iteration, each processor randomly chooses a subset of (stochastic) gradients, rather than all the (stochastic) gradients. The detailed description of the proposed algorithm is as follows. Starting from an initial value x∈K, for t=0,1,2,…, each i=1,…,n updates its decision variable as(9)xit+1=ΠKixit+qitαtgit,where αt is the step-size, ΠKix denotes the Euclidean projection of x on the set Ki, qit are independent and identically Bernoulli random variables with Pqit=1=pi for all t=0,1,2,… and i=1,…,n, and git denotes the unbiased estimate of the gradient ∇iFxt, which denotes the i-th coordinate in ∇Fxt.We introduce the following matrix.(10)Qt≔diag⁡q1t,…,qntTherefore, we can write relation (9) more compactly as(11)xt+1=ΠKxt+αtQtgt,where xt≔xit,…,xntT∈R+n, and gt≔g1t,…,gntT∈Rn. Note that the i-th coordinate of gt is missing when qit=0 at each iteration t, and then the i-th coordinate of xt is not updated. Therefore, a random subset of x∈R+n is updated at each iteration t. In addition, we use the notation P to denote a diagonal matrix with size n×n; i.e., P≔diagP11,…,Pii,…,Pnn, where Pii=pi.LetFt denote the history information of all random variables generated by the proposed algorithm (11) up to time t. In this paper, we adopt the following assumption on the random variables qit, which is stated as follows.Assumption 1.
For alli,j,t,s, the random variables qit and qjs are independent of each other. Furthermore, the random variables qit are independent of Ft-1 and gt for any decision variables x∈Ft-1.In addition, we assume that the functionF and the sets Ki satisfy the following conditions.Assumption 2.
Assume that the following properties hold:
(a) The constraint setK⊆X is convex, and each set Ki⊆R+ is convex and closed for all i∈1,…,n.
(b) The functionF:X→R+ is monotone and weakly DR-submodular with parameter γ over X.
(c) The functionF is differentiable and β-smooth with respect to norm ·.
Next, we make the following assumption about stochastic oraclegt.Assumption 3.
Assume that the stochastic oraclegt satisfies the following conditions: (12)Egt=∇Fxtand (13)Egt-∇Fxt2≤μ2.
The above assumption implies that the stochastic oraclegt is an unbiased estimate of ∇Fxt.In this section, we first formulate an optimization problem, and then design an optimization method to solve it. Moreover, we also give some standard assumptions to analyze the performance of the proposed method.


## 4. Main Results

In this section, We first provide the performance of convergence. To this end, we first introduce the definition of a stationary point, which is defined as in [31].Definition 4.
For a vectorx∈K and a function F:X→R+, if maxy∈Ky-x,∇Fx≤0, then x is a stationary point of F over K⊂X.
From Definition4, the convergence of our proposed algorithm is given in the following theorem.Theorem 5.
Let Assumptions1–3 hold. Assume that the set of stationary points is nonempty and 0<αt<2/β. Moreover, the sequence xt is generated by the stochastic block-coordinate gradient projection algorithm (11). Then, the iterative sequence xt converges to some stationary point x¯∈K with probability 1.
The proof can be found in the next section. The above result shows that the iterations converge to some local maximum with probability 1.
Furthermore, when the functionF:X→R+ is differentiable and DR-submodular, we have the following result.Theorem 6.
Let Assumptions1–3 hold. Moreover, assume γ=1 in (7) and αt=1/β+t. The sequence xt is generated by the stochastic block-coordinate gradient projection algorithm (11). Furthermore, the random decision variable xτ is picked by choosing x1, xT with probability 1/2T-1 and the other variables with probability 1/T. Then, for any random variable for τ∈1,…,T, we have(14)EFxτ≥pmin2F∗-12δ2β2T+δ22T+μ2T,where δ2≔supx,y∈Kx-y2, pmin≔mini∈1,…,npi.The proof can be found in the next section. From the above result, we can see that an objective value in expectation can be obtained afterOδ2β/ϵ+δ2+μ2/ϵ2 iterations of the stochastic block-coordinate gradient projection algorithm (11) for any initial value. Moreover, the objective value is at least pmin/2F∗-ϵ for any DR-submodular function.In addition, when the functionF:X→R+ is weakly DR-submodular function with parameter γ, we also yield the following result.Theorem 7.
Let Assumptions1–3 hold. The sequence xt is generated by the stochastic block-coordinate gradient projection algorithm (11) with αt=1/β+t. Furthermore, the random decision variable xτ is picked by choosing xt in x1,…,xT with probability 1/T. Then, for any for τ∈1,…,T, we have(15)EFxτ≥γ21+γ2pmin-1γTF∗-γ1+γ2δ2β+T2T+μ2T,where pmin≔mini∈1,…,npi, δ2≔supx,y∈Kx-y2.The proof can be found in the next section. Note that the stochastic block-coordinate gradient projection algorithm yields an objective value afterOδ2β/ϵ+δ2+μ2/ϵ2 iterations from any initial value. Furthermore, the expectation of the objective value is in at least γ2/1+γ2pminF∗ for any weakly DR-submodular function.


## 5. Performance Analysis

In this section, the detailed proofs of main results are provided. We first analyze the convergence performance of the stochastic block-coordinate gradient projection algorithm.Proof of Theorem5.
By the Projection Theorem [32], we have(16)x-ΠKx,z-ΠKx≤0for all z∈K. Therefore, let z=xt and x=xt+αtQtgt in inequality (16); we obtain(17)xt+1-xt-αtQtgt,xt+1-xt≤0,where we have used relation (11). By simple algebraic manipulations, we yield(18)xt+1-xt2≤xt+1-xt,αtQtgt.Furthermore, when qit=0 for any i∈1,…,n, xit+1=xit at each iteration t≥0. Therefore, we have(19)xt+1-xt,αtQt-Igt=0.From the above relation, we also obtain(20)xt+1-xt,Qtgt=xt+1-xt,gt.Plugging relation (20) into inequality (18), we have(21)xt+1-xt2≤xt+1-xt,αtgt.Taking conditional expectation in (21), we have(22)Ext+1-xt2∣Ft≤αt∇FxtT×Ext+1-xt∣Ft,where we have used Egt=∇Fxt in the last inequality. In addition, since the function F is β-smooth, we have(23)Fxt+1≥Fxt+xt+1-xt,∇Fxt-β2xt+1-xt2.Taking conditional expectation on Ft in (23) and using relation (22), we obtain(24)EFxt+1∣Ft≥Fxt+1αt-β2Ext+1-xt2∣Ftfor step-size αt∈0,2/β. For brevity, let κ≔1/αt-β/2. Inequality (24) implies that(25)F∗-EFxt+1∣Ft≤F∗-Fxtκ·Ext+1-xt2∣Ft.From the definition of F∗, we have F∗≥Fxt for t≥0; i.e., the sequence of random variables F∗-Fxt is nonnegative for all t≥0. Therefore, according to theSupermartingale Convergence Theorem [51], we can see that the sequence Fxt is convergent with probability 1. Furthermore, we also have(26)∑t=0∞Ext+1-xt2∣Ft<∞with probability 1. From relation (11), inequality (26) implies that(27)∑t=0∞ΠKxt+αt∇Fxt-xtP2<∞with probability 1, where P≔diagp1,p2,…,pn. Therefore, we obtain that(28)limt→∞⁡ΠKxt+αt∇Fxt-xt=0with probability 1. Thus, there exists a subsequence xtl, which converges to x¯. Then, we have(29)liml→∞⁡ΠKxtl+αt∇Fxtl=x¯.Since the gradient projection operation is continuous, we have(30)ΠKx¯+αt∇Fx¯=x¯with probability 1. The above relation implies that(31)ΠK-x¯αt∇Fx¯=0with probability 1. Then, relation (31) implies that maxz∈Kz-x¯,∇Fx¯≤0. Therefore, x¯ is a stationary point of F· over K with probability 1. The statement of the theorem is completely proved.To prove Theorem6, we first present the following lemmas. The first lemma follows from [52], which is stated as follows.Lemma 8.
For allz∈K, we have(32)x-ΠKx,z-ΠKxP≤0for any diagonal matrix P.The next lemma is due to [53], which is stated as follows.Lemma 9.
Assume that a functionF is submodular and monotone. Then, we have(33)x-y,∇Fx≤2Fx-Fx∨y-Fx∧yfor any points x,y∈K.In addition, we also have the following lemma.Lemma 10.
Let Assumptions1–3 hold. The iterative sequence xt is generated by the stochastic block-coordinate gradient projection algorithm (11) with step-size αt≤σt/1+βσt, where σ(t)>0 for t≥0. Then, we have(34)Fxt+1≥Fxt-σt2∇Fxt-gt2+pminxt+1-xt,QtgtP-1-pmin2β+1σtxt+1-xtP-12,where pmin≔mini∈1,…,npi.Proof.
In inequality (21), we let Qt=Ik, where Ik denotes the diagonal matrix with the k-th entry equal to 1 and the other entries equal to 0. Then, we have(35)1αtΠKkxkt+αtgkt-xkt2-ΠKkxkt+αtgkt-xktgkt≤0.Furthermore, the above relation implies that(36)ΠKkxkt+αtgkt-xktgkt-12αtΠKkxkt+αtgkt-xkt2≥0.Therefore, for any k, we obtain(37)ΠKkxkt+αtgkt-xktgkt-12αtΠKkxkt+αtgkt-xkt2≥pminpkΠKkxkt+αtgkt-xktgkt-pmin2αtpkΠKkxkt+αtgkt-xkt2where in the last inequality we have used pmin/pk≤1. Since 0≤pi≤1 for all i∈1,…,n, setting αt=1/β and following from relation (23), we have(38)Fxt+1-Fxt≥xt+1-xt,∇Fxt-β2xt+1-xt2=xt+1-xt,∇Fxt-gt+xt+1-xt,gt-β2xt+1-xt2≥pminxt+1-xt,QtgtP-1-pmin2β+1σtxt+1-xtP-12-σt2∇Fxt-gt2,where the last inequality is obtained by using inequality (37), Young’s inequality, and the fact that xit+1=xit when qit=0 for all i∈1,…,n. Moreover, 0≤pi≤1 for all i∈1,…,n. Rearranging the terms in (38), the lemma is obtained completely.With Lemmas8 and 10 in places, we have the following result.Lemma 11.
Let Assumptions1–3 hold. The iterative sequence xt is generated by the stochastic block-coordinate gradient projection algorithm (11) with step-size αt≤σt/1+βσt. Then, for all t≥0, we have(39)Ext-v,gt∣Ft≥1pminFxt-1pminEFxt+1∣Ft-σt2pminE∇Fxt-gt2∣Ft+12αtExt+1-vP-12-xt-vP-12∣Ft,where pmin=mini∈1,…,npi.Proof.
From the result in Lemma10, we have(40)Fxt+1≥Fxt-σt2∇Fxt-gt2+pminv-xt,QtgtP-1+pminxt+1-v,QtgtP-1-pmin2β+1σtxt+1-xtP-12.In addition, following on from Lemma 8, we also obtain(41)xt+αtQtgt-xt+1,v-xt+1P-1≤0,which implies that(42)xt+1-v,QtgtP-1≥1αtxt+1-v,xt+1-xtP-1.Combining inequalities (40) and (42), we yield(43)Fxt+1≥Fxt-σt2∇Fxt-gt2+pminv-xt,QtgtP-1+pminαtxt+1-v,xt+1-xtP-1-pmin2β+1σtxt+1-xtP-12.=Fxt-σt2∇Fxt-gt2+pminv-xt,QtgtP-1+pmin2αtxt+1-vP-12-xt-vP-12+pmin21αt-β-1σtxt+1-xtP-12≥Fxt-σt2∇Fxt-gt2+pminv-xt,QtgtP-1+pmin2αtxt+1-vP-12-xt-vP-12,where the last inequality is due to αt≤σt/1+βσt. Taking conditional expectation of the above inequality on Ft, we yield(44)EFxt+1∣Ft≥EFxt∣Ft-σt2E∇Fxt-gt2∣Ft+pminEv-xt,gt∣Ft+pmin2αtExt+1-vP-12-xt-vP-12∣Ft.Thus, by some algebraic manipulations, inequality (39) is obtained.Next, we start to prove Theorem6.Proof of Theorem6.
Settingv=x∗ in Lemma 11, where x∗ is the globally optimal solution for problem (8), i.e., x∗≔argmaxx∈KFx, we have(45)Ext-x∗,gt∣Ft≥1pminFxt-1pminEFxt+1∣Ft-σt2pminE∇Fxt-gt2∣Ft+12αtExt+1-x∗P-12-xt-x∗P-12∣Ft.Since(46)xt-x∗,gt=xt-x∗,∇Fxt+xt-x∗,gt-∇Fxt,taking conditional expectation of (46) with respect to Ft, we have(47)Ext-x∗,∇Fxt∣Ft=Ext-x∗,gt∣Ft+Ext-x∗,gt-∇Fxt∣Ft≥Ext-x∗,gt-∇Fxt∣Ft+1pminFxt-1pminEFxt+1∣Ft-σt2pminE∇Fxt-gt2∣Ft+12αtExt+1-x∗P-12-xt-x∗P-12∣Ft,which implies that(48)EFxt+1∣Ft≥Fxt-pminExt-x∗,∇Fxt∣Ft+pminExt-x∗,gt-∇Fxt∣Ft-σt2E∇Fxt-gt2∣Ft+pmin2αtExt+1-x∗P-12-xt-x∗P-12∣Ft.Setting x=xt and y=x∗ in Lemma 9 and taking condition expectation on Ft, we obtain(49)Ext-x∗,∇Fxt∣Ft≤2EFxt∣Ft-Ext∨x∗∣Ft-Ext∧x∗∣Ft.Thus, plugging inequality (49) into relation (48), we get(50)EFxt+1∣Ft+EFxt∣Ft-pminFx∗≥pminExt-x∗,gt-∇Fxt∣Ft-σt2E∇Fxt-gt2∣Ft+pmin2αtExt+1-x∗P-12-xt-x∗P-12∣Ft.Taking expectation in (50) and using some algebraic manipulations, we have(51)EFxt+1+EFxt-pminFx∗≥pmin2αtExt+1-x∗P-12-xt-x∗P-12-σt2E∇Fxt-gt2≥pmin2αtExt+1-x∗P-12-xt-x∗P-12-μ22σt,where we have used the relation Egt=∇Fxt to obtain the first inequality. Summing both sides of (51) for t=1,…,T, we obtain(52)∑t=1TEFxt+1+EFxt-pminFx∗≥pmin2αTExT+1-x∗P-12-pmin2α1Ex1-x∗P-12-μ22∑t=1Tσt+pmin2∑t=1T-11αt-1αt+1Ext+1-x∗P-12≥-δ22α1+δ22∑t=1T-11αt-1αt+1-μ22∑t=1Tσt≥-δ22αT-μ22∑t=1Tσt,where in the last inequality we have used the fact that Ext-x∗P-12≤δ2/pmin and 1/αt-1/αt+1≤0 for all t=1,…,T. On the other hand, we also have(53)∑t=1T2EFxt-pminF∗=EFx1-EFxT+1+∑t=1TEFxt+1+EFxt-pminFx∗≥-δ22αT-μ22∑t=1Tσt-EFxT+1,where F∗=maxx∈KFx and the last inequality is due to (52). Since σt=1/t, we have(54)∑t=1Tσt=∑t=1T1t≤∫0T1tdt=2T.Plugging the above inequality into (53) and dividing both sides by 2T,(55)1T∑t=1TEFxt+12TEFxT+1≥pmin2F∗-δ24Tβ+T-μ22T,where we have used the fact that αT=1/β+T in the last inequality. Furthermore, the above inequality implies that(56)1T∑t=2TEFxt+12TEFxT+1+EFx1≥pmin2F∗-δ24Tβ+T-μ22T.In addition, the sample xτ is obtained for τ∈1,…,T by choosing x1, xT+1 with probability 1/2T and the other decision vectors with probability 1/T; we have(57)EFxτ≥pmin2F∗-δ24Tβ+T-μ22T.Therefore, the theorem is completely proved.We now start to prove Theorem7.Proof of Theorem7.
From the definition of weakly DR-submodular function, for anyx,y∈K, we obtain(58)∇Fx⪰γ∇Fyfor all x⪯y. Recall that the following relation is from [31]; i.e., for any x,y∈K,(59)1γx-y,∇Fx≤1-1γ2Fx-Fy.Setting x=xt and y=x∗ in the above inequality, then, following from (48) and taking conditional expectation, we obtain(60)EFxt+1∣Ft+γ+1γ-1EFxt∣Ft-pminγFx∗≥pminExt-x∗,gt-∇Fxt∣Ft-σt2E∇Fxt-gt2∣Ft+pmin2αtExt+1-x∗P-12-xt-x∗P-12∣Ft.Taking expectation in (60) with respect to Ft, we get(61)EFxt+1+γ+1γ-1EFxt-pminγFx∗≥pmin2αtExt+1-x∗P-12-xt-x∗P-12-σt2E∇Fxt-gt2≥pmin2αtExt+1-x∗P-12-xt-x∗P-12-μ22σt,where the last inequality is due to Assumption 3.
Adding the above inequalities fort=1,…,T, we have(62)∑t=1TEFxt+1+γ+1γ-1Ext-pminγFx∗≥pmin2αTExT+1-x∗P-12-pmin2α1Ex1-x∗P-12-μ22∑t=1Tσt+pmin2∑t=1T-11αt-1αt+1Ext+1-x∗P-12≥-δ22α1+δ22∑t=1T-11αt-1αt+1-μ22∑t=1Tσt≥-δ22αT-μ22∑t=1Tσt,where the last inequality follows from Ext-x∗P-12≤δ2/pmin and 1/αt-1/αt+1≤0 for all t=1,…,T. Moreover, since σt=1/t and αt=1/β+1/σt, we obtain(63)∑t=1TEFxt+1+γ+1γ-1Ext-pminγFx∗≥-δ22β+T-μ2T,where we have used inequality (54) to obtain the last inequality. On the other hand, we have(64)∑t=1Tγ+1γEFxt-pminγF∗=EFx1+∑t=1TEFxt+1-EFxT+1+∑t=1Tγ+1γ-1Ext-pminγFx∗.Plugging inequality (63) into equality (64), we get(65)∑t=1Tγ+1γEFxt-pminγF∗≥-δ22β+T-μ2T-F∗.Dividing both sides by γ+1/γT in (65), we have(66)1T∑t=1TEFxt≥γ2pmin1+γ2F∗-γ1+γ2δ2β+T2T+μ2T+F∗T.In addition, we obtain the sample xτ by choosing xt with probability 1/T. Then, for any τ∈1,…,T, we have(67)EFxτ≥γ2pmin1+γ2F∗-γ1+γ2δ2β+T2T+μ2T+F∗T.Therefore, the theorem is obtained completely.In this section, we proved the main results of the paper in detail. The conclusion of this paper is provided in the next section.


## 6. Conclusion

In this paper, we have considered a stochastic optimization problem of continuous submodular functions, which is an important problem in many areas such as machine learning and social science. Since the data is high-dimensional, usual algorithms based on the computation of the whole approximate gradient vector, such as stochastic gradient methods, are prohibitive. For this reason, we proposed the stochastic block-coordinate gradient projection algorithm for maximizing submodular functions, which randomly chooses a subset of the approximate gradient vector. Moreover, we studied the convergence performance of the proposed algorithm. We proved that the iterations converge to some stationary points with probability 1 by using the suitable step sizes. Furthermore, we showed that the algorithm achieves a tight(pmin/2F∗-ϵ) approximation guarantee after O(1/ϵ2) when the submodular functions are DR-submodular and the suitable step sizes are used. More generally, we also showed that the algorithm achieves the tight (γ2/1+γ2pminF∗-ϵ) after O(1/ϵ2) iterations when the submodular functions are weakly DR-submodular with parameter γ and the appropriate step sizes are used.



---

*Source: 2609471-2018-12-05.xml*