Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization

1. Introduction

• Conditional gradient methods replace costly projections onto a convex set with linear programs that can have lower implementation complexity.The paper presents this as an alternative to stochastic proximal gradient methods when projection is expensive or intractable.Source: §1 · p. 2
• Prior stochastic conditional gradient methods faced unresolved small-batch convergence in convex minimization and lacked a constant-factor guarantee for stochastic submodular maximization.The paper notes that small-batch stochastic continuous greedy methods failed to achieve a constant-factor approximation.Source: §1 · p. 2
• The proposed stochastic conditional gradient method averages stochastic gradients to reduce approximation noise while requiring only one stochastic gradient computation per iteration.It is presented as a stochastic variant of Frank-Wolfe for convex minimization and of continuous greedy for continuous submodular maximization.Source: §1 · p. 3
• O(1/t^1/3) convergence and O(1/ε^3) stochastic gradient evaluations give SFW an ε-suboptimal objective value in stochastic convex minimization.The paper also reports almost-sure convergence of the objective values to the optimum.Source: §1 · p. 3
• (1−1/e) and 1/e approximation guarantees cover monotone and non-monotone continuous submodular maximization, respectively.For monotone weakly DR-submodular objectives, SCG achieves a (1−e^−γ) guarantee.Source: §1 · p. 3
• For stochastic discrete submodular maximization, the method obtains (1−1/e) and 1/e guarantees for monotone and non-monotone cases, respectively.The paper extends continuous results through the multilinear extension; for monotone objectives with curvature c, it gives a (1−e^−c)/c guarantee.Source: §1 · pp. 3–4

Convex minimization

• For stochastic convex minimization, the proposed method achieves O(1/ϵ3) stochastic-gradient complexity under expected-function smoothness and fixed batch size, improving on cited methods with stronger assumptions or growing batches.The text contrasts its result with O(1/ϵ4) for Hazan and Kale (2012) and O(1/ϵ3) for Hazan and Luo (2016), which requires an increasing batch size.Source: §2 · p. 4

Submodular maximization

• Prior deterministic continuous greedy obtains (1 −1/e) for monotone submodular functions under matroid constraints, while stochastic gradient variants had failed to achieve a constant-factor approximation with small batches.The cited deterministic result is from Calinescu et al. (2011); the stochastic difficulty is described in the related-work discussion.Source: §2 · p. 5
• For monotone continuous DR-submodular maximization, Stochastic Continuous Greedy reaches (1 −1/e)OPT −ϵ in O(1/ϵ3) iterations under general convex constraints; the non-monotone guarantee is (1/e)OPT −ϵ for down-closed constraints.The expected function must be monotone and DR-submodular in the monotone case; the stochastic functions need not be. For the non-monotone case, the feasible set must be down-closed.Source: §2 · p. 6
• Earlier stochastic continuous-submodular gradient ascent achieved (1/2 −ϵ), whereas this paper's monotone method reaches the (1 −1/e) guarantee and applies to any convex constraint.The prior result is attributed to Hassani et al. (2017), and the comparison is stated for the monotone case.Source: §2 · p. 6
• For stochastic submodular set-function maximization under a matroid constraint, continuous relaxation and rounding yield expected (1 −1/e) and (1/e) guarantees for monotone and non-monotone cases, respectively.For monotone functions with curvature c < 1, the factor improves to ((1−1/ec)/c).Source: §2 · p. 6

3. Stochastic Convex Minimization

• When the distribution is unknown or expected gradients are computationally costly, the section seeks a stochastic Frank-Wolfe method using one stochastic gradient per iteration.Only the expected function is assumed convex and smooth; the stochastic functions need not be convex or smooth.Source: §3 · p. 7

3.1 Stochastic Frank-Wolfe Method

• Stochastic Frank-Wolfe averages the previous estimate with a new unbiased stochastic gradient to reduce gradient noise that can make naive stochastic Frank-Wolfe diverge.The estimate uses a diminishing stepsize, and the method initializes it at the null vector.Source: §3.1 · p. 7
• At each iteration, the method minimizes the averaged-gradient linear objective over the feasible set, then updates the iterate as a convex combination of its current point and the selected point.Each iteration requires one stochastic-gradient computation, unlike cited methods with growing gradient-evaluation batches.Source: §3.1 · p. 7

3.2 Convergence Analysis

• Under bounded-set, convexity, smoothness, and bounded-variance assumptions, expected suboptimality decreases at least as O(1/t1/3), requiring O(1/ϵ3) stochastic gradients for ϵ accuracy.The theorem uses γt = 2/(t + 8) and ρt = 4/(t + 8)2/3.Source: §3.2 · pp. 8–9
• With stepsizes satisfying the stated summability conditions, the objective values converge to the optimum almost surely; γt = O(1/t) and ρt = O(1/t2/3) are valid choices.The convergence is with probability 1.Source: §3.2 · pp. 9–10

4.1 Preliminaries

• DR-submodularity is the diminishing-returns condition expressed by antitone gradients; for twice-differentiable functions, it implies non-positive second derivatives.The section studies stochastic objectives whose expectation is DR-submodular, even when individual stochastic functions need not be.Source: §4.1 · p. 11, §4.2 · p. 11

4.2 Stochastic Continuous Greedy

• SCG averages stochastic gradients and uses a linear maximization over C to choose its ascent direction.It updates the iterate toward that direction with step size 1/T, keeping the final iterate feasible even when C is not down-closed or does not contain 0.Source: §4.2 · p. 11
• Under Assumptions 4-6, SCG using noisy unbiased gradient estimates achieves the optimal approximation bound (1 −1/e), with the error term vanishing at a sublinear rate of O(T^-1/3).Source: §4.2 · pp. 12–13

4.3 Weak Submodularity

• For monotone γ-weakly DR-submodular objectives, SCG achieves a (1−e^-γ) approximation under the stated assumptions.The bound applies with the same gradient-averaging schedule used for SCG.Source: §4.3 · p. 13

4.4 Non-monotone Continuous Submodular Maximization

• For non-monotone DR-submodular objectives on a down-closed convex set, NMSCG achieves a ((1/e)OPT −ϵ) guarantee using O(1/ϵ3) stochastic gradients.Its ascent-direction linear program adds v ≤ ¯u − xt to limit growth.Source: §4.4 · pp. 13–14

5. Stochastic Discrete Submodular Maximization

• SCG gives the first tight (1 −1/e) guarantee for general monotone stochastic submodular set functions under a matroid constraint; NMSCG gives a (1/e) guarantee for the non-monotone case.The paper also states a ((1 −e−c)/c) guarantee for monotone functions with curvature c.Source: §5 · pp. 15, 17
• The method solves a continuous problem over the matroid polytope using the multilinear extension, then rounds the fractional solution without expected objective loss.Randomized pipage rounding is stated to require O(n) complexity for uniform matroids and O(n2) for general matroids.Source: §5 · p. 15
• An unbiased gradient estimate for the multilinear extension can be constructed from stochastic function evaluations, avoiding the full expectation over random functions.The passage describes sampling a set and using stochastic marginal values to estimate partial derivatives.Source: §5 · p. 15
• For the monotone case, SCG reaches a (1 −1/e)OPT −ϵ solution in O(n3/2/ϵ3) iterations and O(n5/2/ϵ3) stochastic set-function evaluations.Each iteration's gradient estimate can be computed using n samples from the stochastic set function.Source: §5 · p. 17

5.1 Convergence Bounds Based on Curvature

• For monotone functions with curvature c, SCG reaches a ((1 −e−c)/c)OPT −ϵ solution using O(n3/2/ϵ3) iterations and O(n5/2/ϵ3) function evaluations.The paper relates lower curvature to a tighter approximation bound.Source: §5.1 · p. 18

6.1 Convex Setting

• With variance σ = 100 and σ = 300, SFW using one stochastic gradient per iteration performs close to deterministic FW and outperforms mini-batch FW, including larger batches.At the larger variance, mini-batch FW with b = 100 is significantly worse than SFW; increasing its batch size improves convergence but its suboptimality eventually saturates.Source: §6.1 · p. 19, Figure 1 · p. 19
• After 10,000 iterations, matrix-completion SFW reaches normalized error 0.25 with b = 10 and 2.3×10^-3 with b = 1000; mini-batch FW with b = 1000 remains above 0.55.Even with b = 1000, SFW uses less than 3.2% of the 31,884 observed elements per iteration.Source: §6.1 · p. 20
• By iteration count, growing-batch FW is fastest using b = O(t^2), but it uses 10^8 samples at t = 10^4; by processed samples, SFW outperforms both growing-batch and mini-batch FW.The comparison passage reports O(T^3) samples for growing-batch FW versus Tb for SFW with constant b.Source: §6.1 · p. 21
• Among the tested averaging schedules, ρ_t = O(t^-2/3) performs best, although the experiment does not establish it as optimal.The schedules compared were O(t^-1/3), O(t^-1/2), O(t^-2/3), and O(t^-1).Source: §6.1 · p. 21

6.2 Submodular Setting

• For the continuous movie-selection formulation, SCG's linear-program step takes O(n) time, and randomized Pipage rounding yields a set with at least 1 − 1/e of the optimal size-k utility.The rounding procedure does not require access to f.Source: §6.2 · p. 22
• The movie-recommendation tests use facility-location and concave-over-modular objectives, with a cardinality constraint on the selected movies.The data are 1 million MovieLens ratings from 6,041 users for 4,000 movies; the facility-location utility uses each user's highest-rated selected movie.Source: §6.2 · pp. 22–23
• In the movie-recommendation comparisons, FW needs a larger mini-batch to be comparable to SCG, and SCG requires fewer function evaluations than SGA and Greedy.The evaluation-count comparison uses facility-location value versus simple-function evaluations at fixed k = 40; the other objective is concave-over-modular.Source: §6.2 · p. 23, Figure 4 · p. 23

7. Conclusion

• For smooth expected objectives, SFW reaches an ϵ-suboptimal value within O(1/ϵ^3) iterations and can use batch size one, unlike state-of-the-art stochastic conditional-gradient methods requiring growing batches.The method uses a momentum term in the stochastic-gradient approximation to reduce noise.Source: §7 · p. 24
• For monotone stochastic DR-submodular maximization, SCG gives a ((1 − 1/e)OPT − ϵ) guarantee with O(1/ϵ^3) stochastic gradients; the non-monotone method gives a 1/e approximation.The conclusion also reports 1 − 1/e and 1/e guarantees, respectively, for monotone and non-monotone stochastic submodular set maximization under a general matroid constraint.Source: §7 · p. 24

Appendix A. Proof of Lemma 1

• The proof starts from the running-estimate update and adds and subtracts the previous expected gradient to decompose the squared tracking error.This yields terms for the preceding estimation error, stochastic-gradient noise, and gradient change.Source: Appendix A · p. 24
• Conditional expectation, the noise bound, gradient smoothness, and the step-size bound control the noise and gradient-change terms in the error recursion.Young's inequality bounds the cross term; the proof then uses ρ_t ≤ 1 and sets β = ρ_t/2.Source: Appendix A · pp. 24–25
• The proof applies two inequalities involving ρ_t to obtain the bound that establishes claim (9).The inequalities bound (1 − ρ_t)(1 + 2/ρ_t) by 2/ρ_t and (1 − ρ_t)(1 + ρ_t/2) by 1 − ρ_t/2.Source: Appendix A · p. 25

Appendix B. Proof of Lemma 2

• Smoothness bounds the next objective value; substituting the conditional-gradient update and adding and subtracting the estimate-based linear term prepares the bound.The proof then compares the linear-oracle choice with the optimum and adds and subtracts the true-gradient term.Source: Appendix B · pp. 25–26
• Cauchy–Schwarz bounds the gradient-estimation error term, convexity bounds the true-gradient term, and the diameter assumption yields the inequality for claim (10).The convexity step uses ∇F(x_t)^T(x* − x_t) ≤ F(x*) − F(x_t).Source: Appendix B · p. 26

Appendix C. Proof of Theorem 3

• The expected suboptimality recursion combines the previous gap, expected gradient-estimation error, and a smoothness term proportional to γ².The proof applies the recurrence lemma with α = 2/3 and t0 = 8 to bound the error sequence.Source: Appendix C · pp. 26–27
• Lemma 17 bounds a nonnegative sequence satisfying the stated recurrence and gives a rate at which the sequence converges to zero.The proof proceeds by induction and extends Lemma 8 of Mokhtari and Ribeiro (2015).Source: Appendix C · p. 26
• The induction is complete, so inequality (75) holds for every t ≥ 0; its proof establishes the base case at t = 0 and proceeds by assuming (75) at t = k.Source: Appendix C · p. 28

Appendix D. Proof of Theorem 4

• The proof concludes that F(x_t) − F(x*) converges to zero almost surely.A supermartingale argument gives a finite limit and a zero limit inferior, establishing convergence to zero.Source: Appendix D · p. 29

Appendix E. Proof of Lemma 5

• The Lemma 5 proof bounds gradient-estimation error using the variance assumption, smoothness, bounded iterates, and Young’s inequality.It then applies Lemma 17 to obtain the resulting error bound.Source: Appendix E · p. 30

Appendix F. Proof of Theorem 6

• Theorem 6’s proof uses monotonicity and concavity along positive directions to relate the gradient to the optimality gap.The argument also bounds the gradient-estimation error and invokes smoothness before concluding the claim.Source: Appendix F · p. 31

Appendix G. Proof of Theorem 7

• Theorem 7’s proof replaces the gradient-to-gap relation with a weak DR-submodularity bound scaled by γ.Young’s inequality controls the gradient-estimation inner product before the proof derives its final bound.Source: Appendix G · p. 32

Appendix H. Proof of Theorem 8

• Theorem 8’s proof relies on the down-closed constraint to bound feasible directions and then applies concavity in positive directions.The argument uses the NMSCG update and bounds the gradient-estimation term before deriving the claim.Source: Appendix H · pp. 33–34

Appendix I. Proof of Lemma 10

• Lemma 10’s proof uses that each linear-optimization direction is an extreme-point indicator with at most r ones.This property supports the ensuing bound and the claim in (36).Source: Appendix I · p. 35

Appendix J. Proof of Theorem 11

• Lemma 19 gives a coordinate-wise error bound for Stochastic Continuous Greedy with ρ_t = 4/(t + 8)^(2/3).Its proof adapts Lemma 5 using the maximum marginal value and rank-dependent bound from Lemma 10.Source: Appendix J · pp. 35–36
• Theorem 11’s proof follows Theorem 6’s steps, replacing σ² with n max_j E[ f̃({j}, z)²] in the bound.The coordinate-wise analysis uses the Hessian bound based on the maximum marginal value and the rank r.Source: Appendix J · pp. 35–36

Appendix K. Proof of Theorem 13

• Theorem 13’s proof derives the claim in (40) by following the preceding bounds, using Lemma 19 for both monotone and non-monotone functions.The proof then follows the steps from (118) to (121).Source: Appendix K · p. 36

• Using an inequality and result (129), the proof takes expectations, applies Lemma 19, then subtracts F* and regroups terms.Source: Appendix L · pp. 36–37
• The proof recursively applies expression (139) for t = 0, . . . , T −1.Source: Appendix L · p. 37
• The final regrouping uses (1 −c/T) ≤1, result (101), and F(x0) ≥0 to obtain claim (42).Source: Appendix L · p. 37