Stochastic Continuous Greedy ++: When Upper and Lower Bounds Match
Authors: Amin Karbasi, Hamed Hassani, Aryan Mokhtari, Zebang Shen
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we develop Stochastic Continuous Greedy++ (SCG++), the first efficient variant of a conditional gradient method for maximizing a continuous submodular function subject to a convex constraint. Concretely, for a monotone and continuous DR-submodular function, SCG++ achieves a tight [(1 1/e)OPT ϵ] solution while using O(1/ϵ2) stochastic gradients and O(1/ϵ) calls to the linear optimization oracle. We further provide an information-theoretic lower bound to showcase the necessity of O(1/ϵ2) stochastic oracle queries in order to achieve [(1 1/e)OPT ϵ] for monotone and DR-submodular functions. In this section, we analyze the convergence of Algorithm 1 using (18) as the gradient-difference estimation. In this section, we show that reaching a (1 1/e ϵ)-optimal solution of Problem (1) requires at least O(1/ϵ2) calls to an oracle which provides stochastic first-order information. |
| Researcher Affiliation | Academia | Hamed Hassani ESE Department University of Pennsylvania Philadelphia, PA hassani@seas.upenn.edu; Amin Karbasi ECE Department Yale University New Haven, CT amin.karbasi@yale.edu; Aryan Mokhtari ECE Department The University of Texas at Austin Austin, TX mokhtari@austin.utexas.edu; Zebang Shen ESE Department University of Pennsylvania Philadelphia, PA zebang@seas.upenn.edu |
| Pseudocode | Yes | Algorithm 1 Stochastic Continuous Greedy++ (SCG++) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments performed on any dataset, thus no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments performed on any dataset, thus no information about dataset splits for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs; it does not describe any empirical experiments that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments or their implementation details, thus no software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments, therefore no experimental setup details such as hyperparameters or training settings are provided. |