Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
Online convex optimization with switching cost is considered under the frugal information setting where at time $t$, before action $x_t$ is taken, only a single function evaluation and a single gradient is available at the previously chosen action $x_{t-1}$ for either the current cost function $f_t$ or the most recent cost function $f_{t-1}$. When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor
In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO), in which the learner needs to minimize not o…
Online Convex Optimization with Switching Cost and Delayed Gradients
We consider the online convex optimization (OCO) problem with quadratic and linear switching cost in the limited information setting, where an online algorithm can choose its action using only gradient information about …
Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost
An online non-convex optimization problem is considered where the goal is to minimize the flow time (total delay) of a set of jobs by modulating the number of active servers, but with a switching cost associated with cha…
Online Convex Optimization with Continuous Switching Constraint
In many sequential decision making applications, the change of decision would bring an additional cost, such as the wear-and-tear cost associated with changing server status. To control the switching cost, we introduce t…
Decision MakingSequential Decision MakingRevisiting Smoothed Online Learning
In this paper, we revisit the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost, and target two performance metrics: competitive ratio and dynamic regret wi…