---
abstract: 'Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scale applications. At the same time, there is a growing trend of non-convex optimization in machine learning community and a need for online methods. Continuous DR-submodular functions, which exhibit a natural diminishing returns condition, have recently been proposed as a broad class of non-convex functions which may be efficiently optimized. Although online methods have been introduced, they suffer from similar problems. In this work, we propose , the first online projection-free algorithm that uses stochastic gradient estimates. The algorithm relies on a careful sampling of gradients in each round and achieves the optimal $O(\sqrt{T})$ adversarial regret bounds for convex and continuous submodular optimization. We also propose , a simpler algorithm which requires only a single stochastic gradient estimate in each round and achieves an $O(T^{2/3})$ stochastic regret bound for convex and continuous submodular optimization. We apply our methods to develop a novel “lifting” framework for the online discrete submodular maximization and also see that they outperform current state-of-the-art techniques on various experiments.'
author:
- |
    Lin Chen lin.chen@yale.edu\
    Yale Institute for Network Science\
    Department of Electrical Engineering\
    Yale University\
    New Haven, CT 06511, USA Christopher Harshaw christopher.harshaw@yale.edu\
    Yale Institute for Network Science\
    Department of Computer Science\
    Yale University\
    New Haven, CT 06511, USA Hamed Hassani hassani@seas.upenn.edu\
    Department of Electrical and Systems Engineering\
    University of Pennsylvania\
    Philadelphia, PA 19104, USA Amin Karbasi amin.karbasi@yale.edu\
    Yale Institute for Network Science\
    Department of Electrical Engineering\
    Yale University\
    New Haven, CT 06511, USA
bibliography:
- 'example\_paper.bib'
---

@appearing

Acknowledgments {#acknowledgments .unnumbered}
===============

AK was supported by AFOSR YIP (FA9550-18-1-0160). CH was supported in part by NSF GRFP (DGE1122492) and by ONR Award N00014-16-1-2374.
