2019/06/30 by Omid Sadeghi, Maryam Fazel, Sadeghi, Omid +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1907.00316
openalex publication_date 2019/06/30 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
In this paper, we study a class of online optimization problems with\nlong-term budget constraints where the objective functions are not necessarily\nconcave (nor convex) but they instead satisfy the Diminishing Returns (DR)\nproperty. Specifically, a sequence of monotone DR-submodular objective\nfunctions ft(x) t=1T and monotone linear budget functions \⟨\npt,x \⟩ t=1T arrive over time and assuming a total targeted budget\nBT, the goal is to choose points xt at each time t\∈ 1,\…,T ,\nwithout knowing ft and pt on that step, to achieve sub-linear regret\nbound while the total budget violation \∑t=1T \⟨ pt,xt \⟩\n-BT is sub-linear as well. Prior work has shown that achieving sub-linear\nregret is impossible if the budget functions are chosen adversarially.\nTherefore, we modify the notion of regret by comparing the agent against a\n(1-\(1)/(e))-approximation to the best fixed decision in hindsight which\nsatisfies the budget constraint proportionally over any window of length W.\nWe propose the Online Saddle Point Hybrid Gradient (OSPHG) algorithm to solve\nthis class of online problems. For W=T, we recover the aforementioned\nimpossibility result. However, when W=o(T), we show that it is possible to\nobtain sub-linear bounds for both the (1-\(1)/(e))-regret and the total\nbudget violation.\n