Minimizing Adaptive Regret with One Gradient per Iteration

1 Introduction

Online convex optimization is a powerful framework for modeling sequential decision making [Hazan, 2016]. It can be deemed as a repeated game where a learner competes against an adversary: In every iteration t, firstly the learner selects an action xt from a convex set D ⊆ Rd , at the same time, the adversary reveals a convex function ft(·) : D ↦→ R, and the learner incurs a loss ft(xt). The goal is to minimize the cumulative loss over T iterations. The standard performance metric is regret, defined as the difference between the cumulative loss of the learner and that of the optimal action in hindsight [Shalev-Shwartz, 2012]:

which is typically referred to as static regret since the comparator is time-invariant. Despite that static regret is a reasonable benchmark in many contexts and has led to plentiful online algorithms [Hazan, 2016], it fails to capture the hardness of real-world applications where the environments are nonstationary and no single fixed action performs well in general (e.g., portfolio management, ad recommendation). As a consequence, a more stringent performance metric termed adaptive regret [Hazan and Seshadhri, 2007] was proposed and received significant interest recently. Given a parameter τ, the Strongly version of Adaptive Regret (SAR) is defined as the algorithm's maximum static regret over any time interval of length τ [Daniely et al., 2015]:

where [T] is the shorthand of {1, ..., T}. Minimizing SAR forces the algorithm to keep a low static regret in any time interval of length τ.

In the past decade, a wide variety of algorithms that guarantee low SAR have been proposed for different types of convex functions [Hazan and Seshadhri, 2007; Hazan and Seshadhri, 2009; Daniely et al., 2015; Jun et al., 2017; Zhang et al., 2017]. However, different from traditional algorithms under the static setting that only query the gradient once in each iteration, existing approaches under the adaptive setting query the gradient at least O(log t) times in the t-th round. The price paid for adaptivity impedes them to many applications, especially when the evaluation of gradients is expensive. For example, in nuclear normminimization [Ji and Ye, 2009], we have to perform SVD to compute the gradient, which is a costly step for large-scale matrices; another example is the mini-batch optimization [Li et al., 2014], where the gradient is obtained by averaging the gradients of all samples inside a batch.

Contribution. In this paper, we propose a series of algorithms for minimizing adaptive regret that only query the gradient once in each iteration. Similar to previous approaches for adaptive regret, our algorithms follow the Learning with Expert Advice (LEA) framework [Cesa-Bianchi and Lugosi, 2006]. The basic idea is to maintain many algorithms for minimizing static regret as experts to output a set of actions, and employ a weighting method to combine these actions and select xt. In order to output an action, each expert needs to compute its own gradient. In contrast to previous algorithms where each expert queries the gradient of ft(·) directly, the expert kept in our algorithm queries the gradient of a surrogate loss [van Erven and Koolen, 2016]. It can be considered as a conversion from the original learning problem to a new one, where the loss revealed by the adversary in each iteration is the surrogate loss, rather than ft(·). The surrogate losses are carefully designed to satisfy the following properties.

• Their gradients can be computed efficiently by exploiting ∇ft(xt), which is shared among all experts, without further querying ∇ft(·) at different points;
• The SAR of any algorithm on the new problem is an upper bound of that on the original problem.

Equipped with surrogate losses, our algorithms only need to query the gradient once in each round, and achieve O(√τ logT), O(log2 T) and O(d log2 T) SAR bounds for general convex, strongly convex and exponentially concave functions respectively. These upper bounds match the theoretical guarantees of the optimal SAR methods.

2 RelatedWork

In the literature, most studies are devoted to the minimization of static regret [Hazan, 2016]. For general convex and strongly convex functions, the classic algorithm Online Gradient Descent (OGD) enjoys O(√T) and O(logT) static regret bounds respectively [Zinkevich, 2003; Hazan et al., 2007]. Both bounds are known to be minimax optimal [Abernethy et al., 2009]. For exponentially concave functions, the state-of-the-art algorithm is Online Newton Step (ONS), which achieves an O(d logT) static regret bound [Hazan et al., 2007].

To handle changing environments, the seminal work of Hazan and Seshadhri [2007] proposed adaptive regret (referred to as Weakly Adaptive Regret, WAR), which is defined as the maximum static regret of an algorithm over any time interval:

To minimize this performance metric, Hazan and Seshadhri [2007] developed an algorithm called Following the Leading History (FLH), achieving O(√T log T ) and O(dlog T ) WAR for general convex and exponentially concave functions respectively. The essential idea of FLH is to maintain many low static regret algorithms (e.g., OGD or ONS) simultaneously as experts, and employ a meta algorithm to combine the outputs of experts and decide the final action. Each expert attains good static regret in a different time interval, and the meta algorithm can track the best expert by dynamically assigning weights to different experts according to their historical performances. Specifically, in the t-th round, FLH maintains t low static regret algorithms (OGD or ONS), and each algorithm needs to query the gradient of ft(·) once. Thus, the number of gradient evaluations in FLH is linear with respect to t. To reduce the computational cost, Hazan and Seshadhri [2007] then proposed an enhanced version of FLH named Advanced Following the Leading History (AFLH). By removing some old experts according to a data streaming method, AFLH reduces the number of experts and gradient queries down to O(log t) per round, at a cost of an additional logT in its regret.

A major drawback of WAR is that it does not respect short time intervals well. For instance, an O(√T) type of static regret bound is meaningless for intervals of length O(√T). To address this limitation, Daniely et al. [2015] proposed strongly adaptive regret, which is defined in (1). Furthermore, Daniely et al. [2015] introduced the following definition:

Definition 1. For any static learning problem, let R(τ) be its minimax static regret bound over τ iterations. An algorithm is said to be strongly adaptive, if

It can be proved that AFLH algorithm in Hazan and Seshadhri [2007] is in fact strongly adaptive for strongly convex and exponentially concave functions, but not for general convex functions. Daniely et al. [2015] then developed a strongly adaptive algorithm named Strongly Adaptive Online Learner (SAOL), which improves AFLH by introducing a new meta algorithm as well as a new expert removing policy. This algorithm achieves O(√τ log T ) SAR for general convex functions with O(log t) experts and gradient queries in round t. Later, Jun et al. [2017] proposed an algorithm named Coin Betting for Changing Environment (CBCE) that improves the SAR for convex functions to O(√τ log T) with O(log t) experts and gradient queries as well.

From the above discussions, we observe that all the previous methods for adaptive regret need to query the gradient at least O(log t) times in the t-th round. Our goal is to reduce the number of gradient evaluation to 1 per iteration.

3 Algorithms

In this section, we introduce our efficient low SAR algorithms for exponentially concave, strongly convex, as well as general convex functions respectively, and present their theoretical guarantees. We put the detailed analysis in the supplementary material due to the limitation of space.

Through out the paper, we use ‖ · ‖ to denote ℓ2 norm, and ΠAD (·) the projection induced by a positive semi-definite matrix A, i.e.,

Before proceeding to specific algorithms, following previous studies [Hazan and Seshadhri, 2007; Jun et al., 2017], we introduce the following assumptions and definitions [Boyd and Vandenberghe, 2004]:

Assumption 1. The gradients of all loss functions are bounded by G, i.e., maxx∈D ‖∇ft(x)‖ ≤ G for all t.

Assumption 2. The diameter of the decision set is bounded by D, i.e., maxx1,x2∈D ‖x1 -x2‖ ≤D.

Definition 2. A function f : D ↦→ R is convex if ∀x1, x2 ∈ D,

Definition 3. A function f : D ↦→ R is λ-strongly convex if ∀x1, x2 ∈ D,

Algorithm 1 The meta algorithm for exp-concave and strongly convex functions

1: Initialize S1 = {E1}, q1 = 1 2: for t = 1, ..., T do 3: for Ei ∈ St do 4: if qi ̸= t then 5: Pass ∇ft-1(xt-1) to expert Ei 6: end if 7: Get action xi,t from expert Ei 8: end for 9: Choose xt by (3) 10: Observe ∇ft(xt) 11: Remove experts whose ei are less than t 12: ˆn = |St| +1 13: Initialize Eˆn, set pˆn,t+1 = 1 t+1 , qˆn = t, compute eˆn 14: St+1 ←St ∪ {Eˆn} 15: for Ei ∈ St+1 and qi ̸= t do 16: ˆ pi,t+1 = {pi,t exp(-αecLec t (xi,t)), exp-concave pi,t exp(-αscLsc t (xi,t)), strongly convex 17: end for 18: for Ei ∈ St+1 and qi ̸= t do 19: pi,t+1 = (1 - 1 t+1 ) ˆ pi,t+1 ∑Ej∈St+1,qj̸=t ˆ pj,t+1 20: end for 21: end for

Algorithm 2 The algorithm for expert Ei (exp-concave version)

Definition 4. A function f : D ↦→ R is α-exponentially concave (abbreviated to α-exp-concave), if exp(-αf(·)) is concave over domain D.

Finally, we introduce the following lemma for exp-concave functions [Hazan et al., 2007]:

Lemma 1. If Assumptions 1 and 2 hold, and ft : D ↦→ R is α-exp-concave, we have ∀ x1, x2 ∈ D,

where γ = 12 min{ 1 4GD , α}.

3.1 Exp-Concave Functions

Our algorithm named MARSL-ec (Minimizing Adaptive Regret with Surrogate Losses for exp-concave functions) is a two-level hierarchical construction, summarized in Algorithm 1 (the meta algorithm) and Algorithm 2 (the expert algorithm). In each round t, we maintain a set of experts St = {E1, ...,En}. We use qi to denote the round in which Ei is added to the expert set. At the beginning of every round, each expert Ei ∈ St runs the expert algorithm once to output an action xi,t, and passes it to the meta algorithm (Algorithm 1, steps 3-8). Since we are dealing with exp-concave functions, we choose ONS as the expert algorithm. Next, a linear weighting method is applied to combine the outputs of experts and select xt (Algorithm 1, step 9):

In step 11, following the data streaming rule in Hazan and Seshadhri [2007], we remove some experts from St to keep the number of experts |St| = O(log t). Specifically, expert Ei will be removed in round ei, defined as

where u(qi) is a number such that 2u(qi) is the largest power of 2 that divides qi. After the experts are removed, we initialize a new expert Eˆn with ˆn = |St| + 1, and add it to St to get St+1 (steps 12-14). In steps 15-17, the weights of experts are updated by their own losses through the exponential weighting method. Finally, in steps 18-20, the weights are normalized to keep the sum to be 1.

The major difference between AFLH [Hazan and Seshadhri, 2007] and our algorithm is the loss function revealed to experts. While AFLH directly reveals ft(·) to all experts in round t, we use a surrogate loss Lec t (·). Specifically, consider an expert Ei ∈ St. As mentioned above, in round t, Ei has to performONS to output xi,t. Let xi,t-1 be its output in round t - 1. In AFLH, xi,t is computed as:

Clearly, to compute xi,t, expert Ei has to query ∇ft-1(·) at xi,t-1. Because |St| = O(log t), it leads to an O(log t) number of gradient evaluations in round t. Inspired by Metagrad [van Erven and Koolen, 2016], we introduce surrogate loss to tackle this drawback. According to Lemma 1, we construct a lower bound for ft(·), i.e., ∀u ∈ D,

where ∇t := ∇ft(xt). Then, we define

and take Lec t (·) as the loss for all experts in St. Lec t (·) enjoys the following property:

Lemma 2. If Assumptions 1 and 2 hold, ft(·) is α-expconcave, then Lec t (·) is αec -exp-concave, where αec = γ/ (1 + 2γDG + γ 2D2G2 ) . Besides, we have ∀ u1, u2 ∈ D,

Algorithm 3 The algorithm for expert Ei (strongly convex version)

• 1: if qi = t then
• 2: xi,t = 0
• 3: else
• 4: yi,t = xi,t-1 - 1 t-qi ∇Lsc t-1 (xi,t-1)
• 5: xi,t = ∏Id D (yi,t )
• 6: end if
• 7: Output xi,t

By Lemma 2, Lec t (·) is exp-concave, therefore ONS can still be applied. Specifically, for expert Ei, its updating rule can be rewritten as:

where

Because

∇Lec t-1 (xi,t-1) =γ∇t-1∇⊤t-1 (xi,t-1 -xt-1) +∇t-1, (11) expert Ei only needs to use ∇t-1 = ∇ft-1(xt-1), instead of querying ∇ft-1(xi,t-1). In this way, our algorithm only queries the gradient once in each round.

As we have replaced ft(·) with Lec t (·), after the gradient is revealed, we use Lec t (xi,t) to update ˆ pi,t:

For α-exp-concave functions, MARSL-ec achieves the following SAR bound, which matches the optimal result in Hazan and Seshadhri [2007] up to a constant factor:

Theorem1. Suppose Assumptions 1 and 2 hold and all functions f1, . . . , fT are α-exp-concave, MARSL-ec achieves

We note that the concept of surrogate loss was used by van Erven and Koolen [2016]. Their work aims to develop an universal algorithm that can automatically adapt to different type of loss functions under the static setting. In contrast, this paper aims to minimize the adaptive regret in the dynamic setting.

3.2 Strongly Convex Functions

For strongly convex functions, we proposed an algorithm named MARSL-sc (Minimizing Adaptive Regret with Surrogate Losses for strongly convex functions), which uses the same meta algorithm as MARSL-ec, but employs a different surrogate loss and expert algorithm (Algorithm 3). Before proceeding to the algorithm, firstly we introduce the following lemma [Hazan et al., 2007], which implies that strongly convex function is also exp-concave when the gradient is bounded:

Lemma 3. If ft : D → R is λ-strongly convex and Assumption 1 holds, then ft(·) is λ/G2 -exp-concave.

By Lemma 3, we can directly apply MARSL-ec to this learning scenario. However, it will lead to a linear dependence on d in the upper bound (Theorem 1). As an alternative, we introduce a new surrogate loss which suits the problem better. Following the same spirit as in Section 3.1, we first give a lower bound for ft(·) based on Definition 3, i.e., ∀u ∈ D,

Then, the surrogate loss Lsc t (·) is defined as:

and we use Lsc t (·) in place of ft(·) for all experts in round t. Because the Hessian matrix of Lsc t (·) is positive definite with parameter λ, Lsc t (·) is λ-strongly convex, and therefore we can adopt OGD for strongly convex functions as the expert algorithm. Specifically, each expert Ei ∈ St uses the following rule to compute xi,t:

where ηi,t = 1/(t - qi) is the step size, and

Again, each expert can output its action by only using ∇t-1, instead of querying ∇ft-1(xi,t-1). Correspondingly, we use Lsc t (xi,t) to update ˆ pi,t at each round t:

where αsc is the parameter of exp-convexity of Lsc t (·). Since Lsc t (·) is λ-strongly convex, and ∀u ∈ D,

Lemma 3 implies Lsc t (·) is λ/(λD+G)2 -exp-concave. Consequently, we set αsc = λ/(λD + G)2 .

For λ-strongly convex functions, we prove a similar SAR bound as Theorem 1, but independent from d:

Theorem 2. Suppose Assumptions 1 and 2 hold, and all functions f1, . . . , fT are λ-strongly convex, MARSL-sc achieves

3.3 General Convex Functions

For general convex functions, we can still employ Algorithm 1 as the meta algorithm, and take OGD for general convex functions as its subroutine. However, it will only lead to a weakly adaptive algorithm, as indicated in Section 2. Alternatively, we build our meta algorithm based on the Coin Betting for Changing Environment (CBCE) algorithm of Jun et al. [2017]. The algorithm, named Minimizing Adaptive Regret with Surrogate Losses for general convex functions (MARSL-gc), is summarized in Algorithm 4 (the Algorithm 4 The meta algorithm for general convex functions

1: Initialize S1 = {E1}, qi = 1 2: for t = 1, ..., T do 3: for Ei ∈ St do 4: if qi ̸= t then 5: Pass ∇ft-1(xt-1) to expert Ei 6: end if 7: Get action xi,t of expert Ei (Algorithm 5) 8: end for 9: Choose xt by (3), observe ∇ft(xt) and ft(xt) 10: Remove experts whose ei are less than t 11: for Ei ∈ St do 12: Compute ˜ gi,t by (21) 13: end for 14: ˆn = |St| +1 15: Initialize Eˆn, set qˆn = t and compute eˆn 16: St+1 ←St ∪ {En} 17: for Ei ∈ St+1 do 18: Compute wi,t+1 and ˆ pi,t+1 by (17) and (18) 19: end for 20: pt+1 = {ˆpt+1 /‖ˆpt+1 ‖1, ‖ˆpt+1 ‖1 > 0 [πEi ]Ei∈St , otherwise 21: end for

Algorithm 5 The algorithm for expert Ei (general convex version)

• 1: if qi = t then
• 2: xi,t = 0
• 3: else

• 5: xi,t = ∏Id D (yi,t )
• 6: end if
• 7: Output xi,t

meta algorithm) and Algorithm 5 (the expert algorithm). Similar to AFLH, CBCE follows the LEA framework with a data streaming method. In each round t, the meta algorithm receives xi,t, i = 1, ..., n, and selects xt as in (3). Next, old experts are removed from St according to the same data streaming method as in Section 3.1, and a new expert Eˆn is initialized and added to St to get St+1. Finally, the weights of experts are updated and normalized. However, instead of applying exponential weighting scheme, CBCE employs Sleeping Coin Betting method [Blum, 1997; Orabona and P´al, 2016] as the weight updating policy. In round t, after St+1 is obtained, ˆ pi,t+1 is obtained as:

where

˜ gi,t is computed as:

and πi = 1/q2 i (1 + ⌊log qi⌋) is the prior of Ei.

Our algorithm and CBCE differ in the loss functions revealed to experts. By Definition 2, a first attempt is to define the surrogate loss as:

However, because CBCE requires the loss function to lie in [0,1], we scale and redefine the surrogate loss function as:

We replace ft(·) with (20) as the loss function in round t. It can be easily verified that ∀u ∈ D, Lgc t (u) ∈ [0, 1]. Note that the gradient of Lgc t (u) is ∇Lgc t (u) = ∇t/2GD, which implies that every expert in our algorithm shares the same gradient, instead of computing their own gradients respectively. Correspondingly, the update rule of ˜ gi,t is rewritten as

For general convex functions, MARSL-gc achieves the following SAR bound, which is on the same order as the optimal result in Jun et al. [2017]:

Theorem3. Suppose Assumptions 1 and 2 hold and all functions f1, . . . , fT are convex, MARSL-gc achieves

4 Experiments

In this section, we present empirical results on different data sets to evaluate the proposed algorithms.

4.1 Synthetic Data

We consider the problem of matrix regression with a nuclear norm regularizer [Bach, 2008]. In each round t, firstly a data point (Mt, yt) arrives, where Mt ∈ Rp×q is a feature matrix and yt ∈ R is the target value. Then, the algorithm predicts a parameter matrix Wt ∈ Rp×m without knowing the data point and incurs a loss, defined as:

where a and b are constant parameters, and ‖ · ‖∗ is the nuclear norm. Inspired by Jun et al. [2017], we create a scenario where the optimal parameter matrix is drifting over time. Specifically, we sample Mt, ∀t = 1, ..., 30000 and Wi, ∀i = 1, 2, 3 uniformly at random from [-1, 1]100×100 . For t ∈ [1, 10000], we assign yt = tr(W ⊤ 1 Mt) + ϵ, where ϵ is a Gaussian distributed noise. For t ∈ [10001, 20000] ([20001, 30000]), we use the same assignment but with parameter matrix W2 (W3). In this way, the optimal parameter matrix will change every 10000 rounds. Since the loss function is convex, CBCE and MARSL-gc can be applied. As discussed in Section 3.3, our surrogate loss takes the following form:

where · denotes the element-wise product, Wt is the matrix chosen by the meta algorithm, and ∂ft(Wt) is a subgradient of ft(Wt), computed by SVD [Watson, 1992].

Following Jun et al. [2017], we scale both loss and surrogate loss by assigning a = 500 and capping them above at 1. The value of b is empirically set as 10-4 . We repeat the experiment 50 times, and the losses of the two algorithms are averaged by a moving time window of length 50, as shown in Figure 1(a). The cumulative running time is reported in Figure 1(b). As can be seen, MARSL-gc performs very closely to CBCE, and MARSL-gc is much more efficient. In fact, it achieves 15.9 times speed-up (1733.9s vs. 110.5s). Although in each round t the number of experts of MARSL-gc and CBCE are the same (i.e., O(log t)), the computations differ dramatically. Namely, in CBCE, each expert has to perform SVD twice to compute its loss and gradient, while in MARSL-gc the SVD operations are only performed in the meta algorithm. Note that the speed ratio will grow if we increase the number of iterations or the size of the matrix.

4.2 Real-World Data with a Synthetic Component

Next, we consider the problem of mini-batch logistic regression [Shalev-Shwartz and Zhang, 2013]. In each round t, a batch of training examples {(xt,1, yt,1), . . . , (xt,n, yt,n)} arrives, where (xt,i, yt,i) ∈ [-1, 1]d × {-1, 1}, i = 1, . . . , n.

Simultaneously, the learner makes a prediction of the unknown parameter w, denoted as wt, and suffers a loss, defined as:

Following the same spirit as in Section 4.1., We build a dynamic scenario based on real-world binary classification data set IJCNN01 [Prokhorov, 2001; Chang and Lin, 2011]. Let the number of iterations be 9000. In the first and last 3000 iterations, the algorithm receives a batch of training data which is randomly sampled from the original data set; in iterations 3001-6000, the labels of samples are flipped by multiplying -1. In this way, the optimal parameter will change every 3000 iterations. To make Assumption 2 is satisfied, we also add a domain constraint such that the optimal parameters are inside a d-dimensional ball with radius 10. Since the loss function is exp-concave, AFLH and MARSL-ec can be applied. As discussed in Section 3.1, the surrogate loss takes the following form:

where

(25) implies that MARSL-ec can directly compute the averaged gradient in the meta algorithm, and thus it is more efficient. We set n = 256 for both algorithms. the experiment is repeated 10 times, and the losses are averaged by a moving time window of length 20, as shown in Figure 2(a). The cumulative running time is reported in Figure 2(b). It can be seen that MARSL-ec performs nearly as well as AFLH, and achieves 10.6 times speed-up (2010.7s vs. 189.5s). The speed ratio will also grow if we increase the number of iterations or the size of the batch.

5 Conclusion

In this paper, we propose a series of efficient algorithms for minimizing the adaptive regret of exp-concave, strongly convex and general convex functions respectively. The main advantage of our algorithms is that they only require one gradient query per round, and attain the same theoretical guarantees as previous optimal algorithms. Empirical results on different data sets demonstrate the efficiency and effectiveness of our methods.

Acknowledgements

This work was partially supported by the National Key R&D Program of China (2018YFB1004300), NSFC (61603177), JiangsuSF (BK20160658), YESS (2017QNRC001), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.