Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"handle:1773/46846". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Washington

1. Raut, Prasanna Sanjay. Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints.

Degree: 2021, University of Washington

In this thesis, we consider online continuous DR-submodular maximization with linear stochastic long-term constraints. Compared to the prior work on online submodular maximization , our setting introduces the extra complication of stochastic linear constraint functions generated at each round and are independent and identically distributed (i.i.d). To be precise, at step t∈{1,\dots,T}, a DR-submodular utility function ft(∙) and a constraint vector pt, i.i.d. generated from an unknown distribution with mean p, are revealed after committing to an action xt and we aim to maximize the overall utility while the expected cumulative resource consumption ∑t=1T < p,xt> is below a fixed budget BT. Stochastic long-term constraints arise naturally in applications where there is a limited budget or resource available and resource consumption at each step is governed by stochastically time-varying environments. We propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class of online problems. We analyze the performance of the OLFW algorithm and we obtain sub-linear regret bounds as well as sub-linear cumulative constraint violation bounds, both in expectation and with high probability. Advisors/Committee Members: Fazel, Maryam (advisor).

Subjects/Keywords: regret analysis; non-convex optimization; online optimization; submodular maximization; Applied mathematics; Computer science; Operations research; Mechanical engineering

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Raut, P. S. (2021). Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints. (Thesis). University of Washington. Retrieved from http://hdl.handle.net/1773/46846

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Raut, Prasanna Sanjay. “Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints.” 2021. Thesis, University of Washington. Accessed April 22, 2021. http://hdl.handle.net/1773/46846.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Raut, Prasanna Sanjay. “Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints.” 2021. Web. 22 Apr 2021.

Vancouver:

Raut PS. Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints. [Internet] [Thesis]. University of Washington; 2021. [cited 2021 Apr 22]. Available from: http://hdl.handle.net/1773/46846.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Raut PS. Online Decision Making: DR-Submodular Objectives and Stochastic Linear Constraints. [Thesis]. University of Washington; 2021. Available from: http://hdl.handle.net/1773/46846

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.