EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD

Item request has been placed! ×
Item request cannot be made. ×
  Processing Request
  • Additional Information
    • Publication Date:
      2017
    • Collection:
      Computer Science
      Statistics
    • Abstract:
      We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch oracle that distributes a limited query budget over a number of stochastic gradients and aggregates them to estimate the true gradient. Since the optimal mini-batch size depends on the unknown cost-fidelity function, we propose an algorithm, {\it EE-Grad}, that sequentially explores the performance of mini-batch oracles and exploits the accumulated knowledge to estimate the one achieving the best performance in terms of cost-efficiency. We provide performance guarantees for EE-Grad with respect to the optimal mini-batch oracle, and illustrate these results in the case of strongly convex objectives. We also provide a simple numerical example that corroborates our theoretical findings.
    • Accession Number:
      edsarx.1705.07070
  • Citations
    • ABNT:
      DONMEZ, M. A.; RAGINSKY, M.; SINGER, A. C. EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD. [s. l.], 2017. Disponível em: http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428. Acesso em: 15 dez. 2019.
    • AMA:
      Donmez MA, Raginsky M, Singer AC. EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD. 2017. http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428. Accessed December 15, 2019.
    • APA:
      Donmez, M. A., Raginsky, M., & Singer, A. C. (2017). EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428
    • Chicago/Turabian: Author-Date:
      Donmez, Mehmet A., Maxim Raginsky, and Andrew C. Singer. 2017. “EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD.” http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428.
    • Harvard:
      Donmez, M. A., Raginsky, M. and Singer, A. C. (2017) ‘EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD’. Available at: http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428 (Accessed: 15 December 2019).
    • Harvard: Australian:
      Donmez, MA, Raginsky, M & Singer, AC 2017, ‘EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD’, viewed 15 December 2019, .
    • MLA:
      Donmez, Mehmet A., et al. EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD. 2017. EBSCOhost, search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428.
    • Chicago/Turabian: Humanities:
      Donmez, Mehmet A., Maxim Raginsky, and Andrew C. Singer. “EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD,” 2017. http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428.
    • Vancouver/ICMJE:
      Donmez MA, Raginsky M, Singer AC. EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD. 2017 [cited 2019 Dec 15]; Available from: http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1705.07070&custid=s8280428