Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

Aaron Sidford; Brian Axelrod; Yang P. Liu

REVIEW 3 major objections 6 minor 12 references

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Near-linear queries suffice to approximately minimize submodular functions

desk verdict Main theorem genuinely resolves the near-linear oracle complexity question for approximate SFM; the proof has a terse but repairable gap in Lemma 3.4, and the extensions are sketchier but sound. read the letter →

arxiv 1909.00171 v1 pith:TX2GXFPI submitted 2019-08-31 cs.DS math.OC

Brian Axelrod , Yang P. Liu , Aaron Sidford This is my paper · ORCID

classification cs.DSmath.OC

keywords submodularfunctionminimizationoraclecomplexitystochasticsubgradientdescentLovászextensioncontinuoussubmodularitynonconvexoptimizationsparseminimizernear-linearalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that approximate submodular function minimization—finding a set whose value is within $\epsilon$ of the minimum of a set function on an $n$-element universe—can be solved with only $\tilde{O}(n/\epsilon^2)$ evaluations of the function, up to logarithmic factors. That improves the previous best oracle complexity of $\tilde{O}(n^{3/2}/\epsilon^2)$ and matches the known lower bound for subgradient-based algorithms up to polylogarithmic factors. The algorithm runs projected stochastic subgradient descent on the Lovász extension of $f$ and uses a data structure that samples sparse, low-variance gradient estimates without reading all $n$ coordinates. The same machinery extends to submodular functions on $[k]^n$ and to a class of nonconvex continuous functions with nonpositive mixed partial derivatives, yielding nearly linear oracle complexity in those settings as well.

What carries the argument

The Lovász extension $\hat f$ of $f$—the convex set function obtained by ordering coordinates by size—turns set minimization into convex optimization. The load-bearing mechanism is a gradient-difference data structure (Lemma 3.4): when $y-x$ is $k$-sparse, after $O(k)$ evaluations it can sample, in $\tilde{O}(1)$ further evaluations, a 1-sparse random vector $z$ with $\mathbb{E}[z]=g(y)-g(x)$ and $\mathbb{E}[\|z\|_2^2]=O(1)$. The algorithm chains these sampled differences along a binary decomposition of the iteration counter, so the stochastic subgradient at step $t$ is an estimate of $g(x_0)+\sum_j (g(x_{k_{j+1}})-g(x_{k_j}))$, and the binary structure makes the total preprocessing cost $\tilde{O}(1)$ per iteration. A continuous analogue of the extension, defined for submodular functions on $[k]^n$, plays the same role for the nonconvex minimization results.

What would settle it

Exhaustively search all submodular functions on a small universe (say $n\le 6$) for a pair of points $x,y$ with $y-x$ 1-sparse such that the coordinate-wise difference $g(y)-g(x)$, ordered by a permutation consistent with both points, changes sign more than a constant number of times. One such example would falsify Lemma 3.4 and with it the paper's $\tilde{O}(n/\epsilon^2)$ oracle bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any submodular function $f:\{0,1\}^n \to [-1,1]$ and any $\epsilon>0$, the algorithm returns a random set $S$ with $\mathbb{E}[f(S)] \le \min_{T\subseteq [n]} f(T)+\epsilon$ while making $\tilde{O}(n/\epsilon^2)$ calls to an evaluation oracle for $f$. The argument constructs a stochastic subgradient oracle for the Lovász extension whose estimates are 1-sparse with expected squared norm $\tilde{O}(1)$, so projected stochastic subgradient descent converges in $\tilde{O}(n/\epsilon^2)$ iterations. The key is avoiding the naive $\Omega(n)$ cost of forming a full subgradient: the algorithm writes each new subgradient as a sum of differences between nearby points and samples each difference from a data structure maintained at amortized cost $\tilde{O}(1)$ per iteration. The same reduction also yields an exact $\tilde{O}(sM^2)$-query algorithm when $f$ is integer valued with range $[-M,M]$ and an $s$-sparse minimizer, and a $\tilde{O}(nL^6/\epsilon^6)$-query algorithm for nonconvex continuous functions with nonpositive mixed partial derivatives and $L^\infty$-Lipschitz constant $L$.

Load-bearing premise

The entire near-linear oracle bound rests on Lemma 3.4's assertion that when two points differ in only $k$ coordinates, the difference of their subgradients splits into $O(k)$ contiguous blocks whose entries all share a sign, so each block's sum can be evaluated in one oracle call; if that sign-partition property fails, the amortized per-iteration sampling cost stops being $\tilde{O}(1)$ and the $\tilde{O}(n/\epsilon^2)$ bound collapses.

Editorial extensions

If this is right

Oracle complexity for $\epsilon$-approximate discrete submodular function minimization drops from $\tilde{O}(n^{3/2}/\epsilon^2)$ to $\tilde{O}(n/\epsilon^2)$, matching the subgradient-oracle lower bound up to polylogarithmic factors.
For integer-valued $f$ with range $[-M,M]$ and an $s$-sparse minimizer, exact minimization uses $\tilde{O}(sM^2)$ oracle calls; this becomes the first sublinear-time algorithm when $sM^2=o(n)$.
For continuous $f$ on $[0,1]^n$ with all mixed partial derivatives $\le 0$ and Lipschitz constant $L$, an $\epsilon$-additive global minimizer can be found in $\tilde{O}(nL^6/\epsilon^6)$ evaluations, replacing a cubic dependence on $n$ with a nearly linear one.
The extension to submodular functions on $[k]^n$ runs in $\tilde{O}(nk^4/\epsilon^2)$ oracle calls, so the improvement is not tied to the Boolean lattice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The binary-counter amortization used here suggests a general recipe: any projected subgradient method whose iterates move by sparse steps and whose objective admits cheap interval-sum queries can enjoy the same near-linear amortized oracle cost; coordinate descent is a natural next test case.
The sparse-minimizer theorem has a consequence the authors leave implicit: when the optimum is small and the integer range is bounded, exact SFM need not inspect all $n$ elements, which points toward streaming or local-search versions of cut and matroid-rank minimization.
One testable reading of the continuous theorem is as a discretization lemma: functions with pairwise nonpositive mixed partials and Lipschitz constant $L$ can be minimized on a grid of step $\epsilon/(2L)$; applying that to $g(\sum_i c_i x_i)$ with concave $g$ gives a near-linear primitive for a class of nonconvex resource-allocation problems.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the paper delivers what it claims — O~(n/ε²) oracle calls for approximate SFM, improving on the n^5/3 and n^3/2 bounds — and it does so with a genuinely new binary-representation amortization. I would send this to a serious referee.

What's new: the segment decomposition using the binary representation of the iteration counter to amortize preprocessing is the real technical departure from CLSW17 and HRRS19. The proof of the main theorem is mostly coherent: unbiased stochastic gradients with O(1) second moment, and the oracle count summing Σ 2^{ν2(i)} = O~(T). The sparse-minimizer result (~O(sM²)) and the continuous result (~O(nL^6/ε^6)) are also new, though presented more sketchily.

Where I would push: Lemma 3.4's Appendix B proof asserts that g(y)-g(x) partitions into O(k) intervals of common sign based on deleting k elements. As written that is too fast: Lemma 3.2 gives the sign for coordinates where the difference is zero, but the moved coordinates need to be handled separately. The claim itself is true — take the unchanged runs as blocks plus the k changed coordinates as singletons — so this is a repairable presentation gap, not a flaw. Same for the need to fix a tie-breaking rule for consistent permutations; without it the telescoping in Algorithm 1 could pick different subgradients for the same point. A one-line deterministic tie-breaker fixes it.

The continuous sections are weaker: Lemma 5.7 and Theorem 7 are proof sketches, and the submodularity of the discretized function is asserted without proof (it does follow from the mixed-partial condition, but it should be stated). The 'near-optimal' phrasing in Section 1.1 leans on a subgradient-oracle lower bound, and the transfer to the evaluation-oracle model is not argued carefully; the result is probably optimal, but the claim is stronger than the argument. None of this changes my view that the central bound is correct.

Citation pattern is fine: the CLSW17/HRRS19 comparisons are accurate, and reliance on LSW15 and CLSW17 lemmas is legitimate.

Who this is for: anyone working on submodular optimization or oracle-efficient convex minimization. The main theorem resolves an open problem and should be cited. The paper deserves full peer review; it will need minor revisions to tighten Lemma 3.4's proof and the continuous-section sketches, but the core contribution stands.

Referee Report

3 major / 6 minor

Summary. The paper claims a randomized algorithm for ε-approximate submodular function minimization on {0,1}^n with range [-1,1] using ~O(n/ε^2) evaluation-oracle calls, improving on prior ~O(n^{5/3}/ε^2) and ~O(n^{3/2}/ε^2) algorithms. It further gives an ~O(sM^2)-call algorithm for integer-valued SFM with an s-sparse minimizer, an ~O(nk^4/ε^2)-call algorithm for submodular functions on [k]^n, and an ~O(nL^6/ε^6)-call algorithm for continuous twice-differentiable functions with nonpositive mixed partials. The method runs projected stochastic subgradient descent on the Lovász extension and uses a data structure that samples sparse unbiased estimators of gradient differences; the binary decomposition of the iteration counter is used to amortize preprocessing costs.

Significance. If the main theorem is correct, it resolves the open problem of near-linear oracle complexity for approximate SFM posed by CLSW17 and HRRS19, and it is optimal up to the ε dependence given the subgradient-oracle lower bound. The sparse pseudopolynomial result gives the first sublinear-time SFM algorithm in the sparse regime, and the continuous extension substantially improves Bach's cubic dependence on n. The paper's high-level architecture is sound: Lemma 3.1 and Lemma 3.3 provide the needed norm and interval-sum tools, and the amortization of preprocessing costs over the trajectory is a genuine contribution. The main caveat is that the proof of the key data-structure lemma is incomplete as written, so the central claim currently rests on a gap that must be repaired.

major comments (3)

[Appendix B, proof of Lemma 3.4] The proof asserts that because Px and Py differ by k deletions and insertions, there are subsets I1,...,I_{2k} that are intervals in both permutations and carry a common sign for g(y)-g(x). This is not demonstrated: Lemma 3.2 supplies a sign only for coordinates outside the support of d=y-x, while the changed coordinates can have arbitrary signs, and a common interval containing changed coordinates need not be uniform in sign. The proposed alternative of taking maximal common subsequences of unchanged coordinates also needs an argument that those blocks are contiguous in both full permutations, which is not automatic. Since the O(k) preprocessing bound and the O(1) second-moment guarantee of the lemma both depend on this partition, the proof must supply an explicit construction of the intervals and a proof of the uniform-sign property.
[Algorithm 1, lines 3, 7, 8, 12; Appendix B] Algorithm 1 uses g(x) as if it were a single-valued function, but g(x) is defined by a consistent permutation and is not unique at ties; at x0=0 every permutation is consistent. Without a deterministic tie-breaking rule, the same point can receive different subgradients in different calls to Process and Sample, and the telescoping identity used to form g⋆i can fail. The paper should fix a deterministic consistent-permutation rule, for example breaking ties by coordinate index, and prove that all invocations use the same rule.
[Section 4, proof of Theorem 7 and Theorem 2] Section 4 derives the exact-minimizer guarantee of Theorem 2 from Theorem 7, which only proves E[ˆf(x)] < min_T f(T) + 1. The step 'It is direct to see' omits the amplification argument that repeated runs, combined with Lemma 2.2 to convert each point to a set, give an exact minimizer with high probability. This should be stated because Theorem 2's contribution is exactness in the sparse regime.

minor comments (6)

[Section 1.2] There is a typo in 'weekl y polynomial' in the first sentence; it should read 'weakly polynomial.'
[Theorem 2 statement] The notation 'argminS⊆{0,1}nf(S)' should be written as 'argmin_{S⊆[n]} f(S)' for clarity.
[Algorithm 4 header] The parameter ε is not used in the stated guarantee of SparseSFM, which returns a point with E[ˆf(x)] < min_T f(T) + 1; either rename the parameter or clarify that the guarantee is additive error 1.
[Figure 1] The caption and diagram for the decomposition of [0,11] are hard to parse; adding explicit segment values such as (0,8), (8,10), (10,11) would improve readability.
[Appendix B, proof of Lemma 4.4] The phrase 'use the proof of Lemma 3.2 above' should read 'use the proof of Lemma 3.4,' and the word 'coordiantes' is misspelled. More importantly, the reduction to points x′, y′ should explicitly note that g depends only on the consistent permutation, so the data structure for x′, y′ yields the same g(y)-g(x).
[Section 5.3, proof of Theorem 3] The sentence 'We can also verify that f′ is submodular' would benefit from a one-line verification, since the discrete submodularity of f′ follows from the continuous mixed-partial condition by integrating over grid cells.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main result is a new algorithm built on prior published lemmas, with no fitted parameter or prediction that reduces to an input.

full rationale

The paper's central claim, Theorem 1, is a new oracle-complexity bound for approximate submodular function minimization obtained by projected stochastic subgradient descent on the Lovasz extension. The derivation chain is self-contained modulo standard, independently published ingredients: the stochastic subgradient descent template is attributed to Bubeck (Theorem 5), the Lovasz extension facts are classical (Lovasz, Fujishige), and the structural lemmas on subgradients (Lemmas 3.1, 3.2, 3.3) are cited to CLSW17, a prior STOC paper with independent published proofs. Those lemmas are not restatements of the target result; they are used as tools to build a new data structure and sampling procedure. Lemma 3.4, the key technical step, is proved in Appendix B from these lemmas; although the assertion that g(y)-g(x) partitions into O(k) constant-sign intervals is terse and arguably under-justified, this is a proof-presentation gap that is repairable, not a circular reduction. The continuous-domain result (Theorem 3) reduces to the discrete result through a direct discretization argument, again with no fitted parameters. No step in the paper defines an input in terms of an output, fits a parameter to data and then calls the result a prediction, or imports a uniqueness theorem from the authors' own prior work to force a choice. Self-citations occur (CLSW17, LSW15), but they are normal references to prior published algorithms and lemmas that are not equivalent to the new claims. Overall, the paper's derivation is not circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The main theorem is self-contained given standard convex optimization tools and prior SFM lemmas. No free parameters are fit. The assumptions are mostly standard math; two domain assumptions in the sparse and continuous extensions are stated without full proof, but are plausible and checkable.

assumptions (5)

standard math The Lovász extension properties: convexity, consistency on {0,1}^n, min preservation, and the subgradient formula (Theorem 4).
Cited to Lovász 1983 and Fujishige 2005; used throughout Section 3.
standard math Projected stochastic subgradient descent guarantee (Theorem 5) providing E[f(avg x_i)] ≤ min f + R B sqrt(2/T).
Imported from Bubeck 2015; this is the convergence engine for all main algorithms.
standard math The subgradient L1 norm bound ||g(x)||_1 ≤ 3M for f with range [-M,M] (Lemma 3.1), and the interval sum formula (Lemma 3.3).
These prior lemmas from CLSW17/Jegelka-Bilmes/Hazan-Kale are asserted and used without reproving in Section 3; they are necessary for the O(1) variance claim.
domain assumption For the sparse algorithm, moving a positive (resp. negative) marginal coordinate to the far left (resp. right) of the permutation preserves its nonzeroness and sign (Section 4, proof of Lemma 4.1).
Stated without proof: 'submodularity ensures that moving the coordinate to the left or right of the permutation never makes it zero'. If false, FindPerm could fail and Theorem 2 would break.
domain assumption The discretized function f'(x) = f(x/k) on [k]^n is submodular when f has all mixed partials ≤ 0 (Section 5.3, proof of Theorem 3).
Stated as 'We can also verify that f' is submodular' without proof; this is a standard fact for smooth submodular functions but is load-bearing for Theorem 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Near-optimal Approximate Discrete and Continuous Submodular Function Minimization." pith.science (2026). https://pith.science/paper/TX2GXFPI

@misc{pith2026190900171,
  author       = {Pith},
  title        = {Pith review of: Near-optimal Approximate Discrete and Continuous Submodular Function Minimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TX2GXFPI}},
  note         = {Machine review of arXiv:1909.00171}
}

abstract

In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on $n$-elements with range $[-1, 1]$, computes an $\epsilon$-additive approximate minimizer in $\tilde{O}(n/\epsilon^2)$ oracle evaluations with high probability. This improves over the $\tilde{O}(n^{5/3}/\epsilon^2)$ oracle evaluation algorithm of Chakrabarty \etal~(STOC 2017) and the $\tilde{O}(n^{3/2}/\epsilon^2)$ oracle evaluation algorithm of Hamoudi \etal. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function $f$ with domain $[0, 1]^n$ that satisfies $\frac{\partial^2f}{\partial x_i \partial x_j} \le 0$ for all $i \neq j$ and is $L$-Lipschitz with respect to the $L^\infty$-norm we give an algorithm that computes an $\epsilon$-additive approximate minimizer with $\tilde{O}(n \cdot \mathrm{poly}(L/\epsilon))$ function evaluation with high probability.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[6]

The ellipsoid method and its consequences in combinatorial optimization

[GLS84] M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Corrigendu m to our paper: “The ellipsoid method and its consequences in combinatorial optimization” [Combinatorica 1 (1981), no. 2, 169–197; MR0625550 (84a:90044)]. Combinatorica, 4(4):291–295,

work page 1981
[12]

Primal-dual accelerated gradient methods with small-dimensional relaxation oracle

[NGGD18] Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, an d Pavel Dvurechensky. Primal-dual accelerated gradient descent with line search for convex and nonc onvex optimization problems. arXiv preprint arXiv:1809.05895 ,

work page Pith review arXiv
[1954]

Provable submodular minimization using wolfe’s algorithm

[CJK14] Deeparnab Chakrabarty, Prateek Jain, and Pravesh Kot hari. Provable submodular minimization using wolfe’s algorithm. In Advances in Neural Information Processing Systems 27: Annu al Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 802–809,

work page 2014
[1983]

A faste r cutting plane method and its implications for combinatorial and convex optimization

[LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faste r cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015 , pages 1049–1065. IEEE Computer Soc., Los Alamitos, CA,

work page 2015
[1999]

Duchi, Oliver Hinder, and Aaron Sidfor d

[CDHS16] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidfor d. Accelerated methods for non- convex optimization. CoRR, abs/1611.00756,

arXiv
[2005]

Accelerated metho ds for α-weakly-quasi-convex prob- lems

[GG17] Sergey Guminov and Alexander Gasnikov. Accelerated metho ds for α-weakly-quasi-convex prob- lems. arXiv preprint arXiv:1710.00797 ,

arXiv
[2009]

[JB11] Stefanie Jegelka and Jeﬀ A. Bilmes. Online submodular minimizatio n for combinatorial struc- tures. In Proceedings of the 28th International Conference on Machin e Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011 , pages 345–352,

work page 2011
[2011]

On the global linear con vergence of frank-wolfe optimiza- tion variants

[LJ15] Simon Lacoste-Julien and Martin Jaggi. On the global linear con vergence of frank-wolfe optimiza- tion variants. In Advances in Neural Information Processing Systems 28: Annu al Conference on Neural Information Processing Systems 2015, December 7-12 , 2015, Montreal, Quebec, Canada , pages 496–504,

work page 2015

Show all 12 references

[2012]

Quantum and clas- sical algorithms for approximate submodular function minimization

20 [HRRS19] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, an d Miklos Santha. Quantum and clas- sical algorithms for approximate submodular function minimization. CoRR, abs/1907.05378,

1907 arXiv
[2016]

Theory of capacities

[Cho54] Gustave Choquet. Theory of capacities. Ann. Inst. Fourier, Grenoble , 5:131–295 (1955), 1953–

1955
[2017]

Lee, and Tengyu Ma

[GLM16] Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix completion ha s no spurious local minimum. In Advances in Neural Information Processing Systems 29: Annu al Conference on Neural In- formation Processing Systems 2016, December 5-10, 2016, Ba rcelona, Spain, pages 2973–2981,

2016
[2019]

Near- optimal methods for minimizing star-convex functions and beyond

[HSS19] Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. Near- optimal methods for minimizing star-convex functions and beyond. arXiv preprint arXiv:1906.11985 ,

1906 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [6]

The ellipsoid method and its consequences in combinatorial optimization

[GLS84] M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Corrigendu m to our paper: “The ellipsoid method and its consequences in combinatorial optimization” [Combinatorica 1 (1981), no. 2, 169–197; MR0625550 (84a:90044)]. Combinatorica, 4(4):291–295,

work page 1981

[2] [12]

Primal-dual accelerated gradient methods with small-dimensional relaxation oracle

[NGGD18] Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, an d Pavel Dvurechensky. Primal-dual accelerated gradient descent with line search for convex and nonc onvex optimization problems. arXiv preprint arXiv:1809.05895 ,

work page Pith review arXiv

[3] [1954]

Provable submodular minimization using wolfe’s algorithm

[CJK14] Deeparnab Chakrabarty, Prateek Jain, and Pravesh Kot hari. Provable submodular minimization using wolfe’s algorithm. In Advances in Neural Information Processing Systems 27: Annu al Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 802–809,

work page 2014

[4] [1983]

A faste r cutting plane method and its implications for combinatorial and convex optimization

[LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faste r cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015 , pages 1049–1065. IEEE Computer Soc., Los Alamitos, CA,

work page 2015

[5] [1999]

Duchi, Oliver Hinder, and Aaron Sidfor d

[CDHS16] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidfor d. Accelerated methods for non- convex optimization. CoRR, abs/1611.00756,

arXiv

[6] [2005]

Accelerated metho ds for α-weakly-quasi-convex prob- lems

[GG17] Sergey Guminov and Alexander Gasnikov. Accelerated metho ds for α-weakly-quasi-convex prob- lems. arXiv preprint arXiv:1710.00797 ,

arXiv

[7] [2009]

[JB11] Stefanie Jegelka and Jeﬀ A. Bilmes. Online submodular minimizatio n for combinatorial struc- tures. In Proceedings of the 28th International Conference on Machin e Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011 , pages 345–352,

work page 2011

[8] [2011]

On the global linear con vergence of frank-wolfe optimiza- tion variants

[LJ15] Simon Lacoste-Julien and Martin Jaggi. On the global linear con vergence of frank-wolfe optimiza- tion variants. In Advances in Neural Information Processing Systems 28: Annu al Conference on Neural Information Processing Systems 2015, December 7-12 , 2015, Montreal, Quebec, Canada , pages 496–504,

work page 2015