summaries: In many real world applications for RL such as medicine, there are limits on the number of policies from which we can simulate data. This paper proposes an approach that adaptively decides when to update the simulation policy, based on the difference between it and the current learned policy. Experiments on a medical treatment environment and Atari show that the approach obtains similar performance to on-policy RL with fewer changes of the simulation policy.

summaries: In the RL context, this paper aims at designing a generic solution for reducing the number of policy switches during training (called switching cost) while maintaining the performance. This study is done in the context of deep reinforcement learning. A few generic baselines solutions are provided as well as a more complex solution that empirically outperforms the baselines.

summaries: This paper studies RL with low switching cost under the deep RL setting. It points out several naive algorithms like switching after a certain number of steps and then propose a new heuristic. This heuristic learns a new policy offline using the experience replay the behavior collected and switches the behavior policy once the similarity of the feature embeddings of the current state by these two policies becomes large. The paper also makes an attempt to provide a theoretical justification for a better understanding of the heuristic. This method might outperform the naive algorithms by some margin, if any. It would be a more interesting manuscript if some stronger results could be provided from the perspective of any of theory, experiments, or applications.

abstractText: We initiate the study on deep reinforcement learning problems that require low switching cost, i.e., a small number of policy switches during training. Such a requirement is ubiquitous in many applications, such as medical domains, recommendation systems, education, robotics, dialogue agents, etc, where the deployed policy that actually interacts with the environment cannot change frequently. Our paper investigates different policy switching criteria based on deep Q-networks and further proposes an adaptive approach based on the feature distance between the deployed Q-network and the underlying learning Q-network. Through extensive experiments on a medical treatment environment and a collection of the Atari games, we find our feature-switching criterion substantially decreases the switching cost while maintains a similar sample efficiency to the case without the low-switching-cost constraint. We also complement this empirical finding with a theoretical justification from a representation learning perspective.

authors:
Ki Uhn Ahn
Cheol Soo Park

title: Application of deep q-networks for model-free optimal control balancing between different hvac systems

venue: Science and Technology for the Built Environment,

authors:
Tao Ao
Jiong Shen
Xichui Liu

title: The application of dqn in thermal process control

venue: Chinese Control Conference (CCC),

authors:
Peter Auer
Nicolo Cesa-Bianchi
Paul Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine learning,

authors:
Yu Bai
Tengyang Xie
Nan Jiang
Yu-Xiang Wang

title: Provably efficient q-learning with low switching cost

venue: In Advances in Neural Information Processing Systems,

authors:
Marc G. Bellemare
W. Dabney
R. Munos

title: A distributional perspective on reinforcement

venue: learning. ArXiv,

authors:
Nicolo Cesa-Bianchi
Ofer Dekel
Ohad Shamir

title: Online learning with switching costs and other adaptive adversaries

authors:
Shi-Yong Chen
Yang Yu
Qing Da
Jun Tan
Hai-Kuan Huang
Hai-Hong Tang

title: Stabilizing reinforcement learning in dynamic environment with application to online recommendation

venue: In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Shixiang Gu
Ethan Holly
Timothy Lillicrap
Sergey Levine

title: Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates

venue: IEEE international conference on robotics and automation (ICRA),

authors:
H.V. Hasselt
A. Guez
D. Silver

title: Deep reinforcement learning with double q-learning

venue: In AAAI,

authors:
Matteo Hessel
Joseph Modayil
Hado van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Dan Horgan
Bilal Piot
Mohammad Gheshlaghi Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning

authors:
Natasha Jaques
Asma Ghandeharioun
Judy Hanwen Shen
Craig Ferguson
Agata Lapedriza
Noah Jones
Shixiang Gu
Rosalind Picard

title: Way off-policy batch deep reinforcement learning of implicit human preferences in dialog

venue: arXiv preprint arXiv:1907.00456,

authors:
Sascha Lange
Thomas Gabel
Martin Riedmiller

title: Batch reinforcement learning

venue: In Reinforcement learning,

authors:
Sergey Levine
Aviral Kumar
George Tucker
Justin Fu

title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems

venue: arXiv preprint arXiv:2005.01643,

authors:
Travis Mandel
Yun-En Liu
Sergey Levine
Emma Brunskill
Zoran Popovic

title: Offline policy evaluation across representations with applications to educational games

venue: In AAMAS,

authors:
Tatsuya Matsushima
Hiroki Furuta
Yutaka Matsuo
Ofir Nachum
Shixiang Gu

title: Deploymentefficient reinforcement learning via model-based offline optimization

venue: arXiv preprint arXiv:2006.03647,

authors:
V. Mnih
K. Kavukcuoglu
D. Silver
Andrei A. Rusu
J. Veness
Marc G. Bellemare
A. Graves
Martin A. Riedmiller
Andreas K. Fidjeland
Georg Ostrovski
S. Petersen
C. Beattie
A. Sadik
Ioannis Antonoglou
H. King
D. Kumaran
Daan Wierstra
S. Legg
Demis Hassabis

title: Humanlevel control through deep reinforcement learning

authors:
Satinder P Singh
Tommi Jaakkola
Michael I Jordan

title: Reinforcement learning with soft state aggregation

venue: In Advances in neural information processing systems,

title: Learning to predict by the methods of temporal differences

venue: Machine Learning,

authors:
R. Sutton
A. Barto

title: Reinforcement learning: An introduction

venue: IEEE Transactions on Neural Networks,

authors:
Haoran Tang
Rein Houthooft
Davis Foote
Adam Stooke
Xi Chen
Yan Duan
John Schulman
F. Turck
P. Abbeel

title: Exploration: A study of count-based exploration for deep reinforcement

authors:
Ziyu Wang
T. Schaul
Matteo Hessel
H.V. Hasselt
Marc Lanctot
N.D. Freitas

title: Dueling network architectures for deep reinforcement learning

authors:
Zihan Zhang
Xiangyang Ji
Simon S. Du

title: Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon

venue: arXiv preprint arXiv:2009.13503,

authors:
Zihan Zhang
Yuan Zhou
Xiangyang Ji

title: Almost optimal model-free reinforcement learning via reference-advantage decomposition, 2020b

heading: 1 INTRODUCTION

text:
Reinforcement learning (RL) is often used for modeling real-world sequential decision-making problems such as medical domains, personalized recommendations, hardware placements, database optimization, etc. For these applications, oftentimes it is desirable to restrict the agent from adjusting its policy frequently. In medical domains, changing a policy requires a thorough approval process by experts. For large-scale software and hardware systems, changing a policy requires to redeploy the whole environment. Formally, we would like our RL algorithm admits a low switching cost. In this setting, it is required that the deployed policy that interacts with the environment cannot change many times.
In some real-world RL applications such as robotics, education, and dialogue system, changing the deployed policy frequently may cause high costs and risks. Gu et al. (2017) trained robotic manipulation by decoupling the training and experience collecting threads; Mandel et al. (2014) applied RL to educational games by taking a data-driven methodology for comparing and validating policies offline, and run the strongest policy online; Jaques et al. (2019) developed an off-policy batch RL algorithms for dialog system, which can effectively learn in an offline fashion, without using different policies to interact with the environment. All of these work avoid changing the deployed policy frequently as they try to train the policy offline effectively or validate the policy to determine whether to deploy it online.
For RL problem with a low switching cost constraint, the central question is how to design a criterion to decide when to change the deployed policy. Ideally, we would like this criterion to have the following four properties:
1. Low switching cost: This is the purpose of this criterion. An algorithm equipped with this policy switching criterion should have low switching cost.
2. High Reward: Since the deployed policy determines the collected samples and the agent uses fewer deployed policies, the collected data may not be informative enough to learn the optimal policy with high reward. We need this criterion to deploy policies that can collect informative samples.
3. Sample Efficiency: Since the agent only uses a few deployed policies, there may be more redundant samples, which will not be collected if the agent switches the policy frequently. We would like algorithms equipped with a criterion with similar sample efficiency as the case without the low switching cost constraint.
4. Generality: We would like this criterion to be effective not only on a specific task but also broadly effective on a wide range of tasks.
In this paper, we take a step toward this important problem. We focus on designing a principled policy switching criterion for deep Q-networks (DQN) learning algorithms, which have been widely used in applications. For example, Ahn & Park (2020) apply DQN to control balancing between different HVAC systems, Ao et al. (2019) propose a thermal process control method based on DQN, and Chen et al. (2018) try to apply it to online recommendation. Notably these applications all require low switching cost.
Our paper conducts a systematic study on DQN with low switching cost. Our contributions are summarized below.
Our Contributions
• We conduct the first systematic empirical study on benchmark environments that require modern reinforcement learning algorithms. We test two naive policy switching criteria: 1) switching the policy after a fixed number of steps and 2) switching the policy after an increasing step with a fixed rate. We find that neither criterion is a generic solution because sometimes they either cannot find the best policy or significantly decrease the sample efficiency.
• Inspired by representation learning theory, we propose a new feature-based switching criterion that uses the feature distance between the deployed Q-network and the underlying learning Q-network. Through extensive experiments, we find our proposed criterion is a generic solution – it substantially decreases the switching cost while maintains a similar performance to the case without the low-switching-cost constraint.
• Along the way, we also derive a deterministic Rainbow DQN (Hessel et al., 2018), which may be of independent interest.
Organization This paper is organized as follows. In Section 2, we review related work. In Section 3, we describe our problem setup and review necessary backgrounds. In Section 4, we describe deterministic Rainbow DQN with the low switching cost constraint. In Section 5, we introduce our feature-based policy switching criterion and its theoretical support. In Section 6, we conduct experiments to evaluate different criteria. We conclude in Section 7 and leave experiment details to appendix.

heading: 2 RELATED WORK

text:
Low switching cost algorithms were first studied in the bandit setting (Auer et al., 2002; CesaBianchi et al., 2013). Existing work on RL with low switching cost is mostly theoretical. To our knowledge, Bai et al. (2019) is the first work that studies this problem for the episodic finite-horizon tabular RL setting. Bai et al. (2019) gave a low-regret algorithm with an O ( H3SA log (K) ) local switching upper bound where S is the number of stats, A is the number of actions, H is the planning horizon and K is the number of episodes the agent plays. The upper bound was improved in Zhang et al. (2020b;a).
The only empirical study on RL with switching cost is Matsushima et al. (2020), which proposed a concept of deployment efficiency and gave a model-based algorithm. During the training process, the algorithm fixes the number of deployments, trains a dynamics model ensemble, and updates the deployed policy alternately. After each deployment, the deployed policy collects transitions in the real environment to enhance the models, and then the models optimize the policy by providing imagined trajectories. In other words, they reduce the number of deployments by training on simulated environments. Our goal is different: we design a criterion to decide when to change the deployed policy, and this criterion could be employed by model-free algorithms.
There is a line of work on offline RL (also called Batch RL) methods, where the policy does not interact with the environment directly and only learns from a fixed dataset (Lange et al., 2012; Levine et al., 2020). Some methods Interpolate offline and online methods, i.e., semi-batch RL
algorithms (Singh et al., 1995; Lange et al., 2012), which update the policy many times on a large batch of transitions. However, the switching cost is not their focus.

heading: 3 PRELIMINARIES

heading: 3.1 MARKOV DECISION PROCESS

text:
Throughout our paper, we consider the episodic Markov decision model (S,A, H, P, r). In this model, S is the state space, A is the action space, H ∈ Z+ is the planning horizon. P is the transition operator where P (x′|x, a) denotes the transition probability of taking action a from state x to state x′. r : S ×A → R is the reward function. A policy is a mapping from a state to an action, π : S → A. In this paper, we focus on deterministic policies as required by motivating applications. The dynamics of the episodic MDP can be view as the interaction of an agent with the environment periodically. We let K be the total number of episodes the agent plays. At the beginning of an episode k ∈ [K], the agent chooses a policy πk. The initial xk1 ∈ S is sampled from a distribution, and the agent is then in step 1. At each step h ∈ [H] in this episode, based on the current state xkh ∈ S the agent chooses the action akh = πk(xkh). The environment will give the reward for the step r(xkh, a k h) and move the agent to the next state xh+1 ∼ P (·|xkh, akh). The episode automatically ends when the agent reaches the step H + 1.
Q-function is used to evaluate the long-term value for the action a and subsequent decisions. The Q-function of a policy π at time step h is defined as follows:
Qπh(x, a) := rh(x, a) + E
[ H∑
i=h+1
r (xi, π (xi)) ∣∣∣∣∣xh = x, ah = a ]
(1)
The goal of this agent is to find a policy π∗ which maximizes the expected reward, π∗ = arg maxπ Eπ [∑H h=1 rh ] . Ideally, we want to use a few episodes (K) as possible to learn π∗.

heading: 3.2 SWITCHING COST

text:
The concept of switching cost is used to quantify the adaptability of RL algorithms. The switching cost is defined as the number of policy changes of deployed policies in the running of the algorithm in K episodes, namely:
Nswitch := K−1∑ k=1 I{πk 6= πk+1} (2)
The goal of this paper is to equip algorithm with a criterion that learns π∗ using a few episodes while at the same time has small Nswitch.
3.3 DEEP Q-LEARNING
If we can estimate Q-function for each state and action pair well, there is no difficulty in finding π∗. For example, we can always select a∗ = arg maxaQ(x, a). However, it is not easy to learn Q value estimates for each state and action pair, especially when the state or the action space is large.
In deep Q-learning (DQN), Mnih et al. (2015) combine deep networks and reinforcement learning successfully by using a deep neural network to approximate Q(x, a). Given the current state xh, the agent selects a action ah greedily based on the Q(xh, a), then the state move to xh+1 and a reward rt+1 is obtained. The transition (xt, at, rt+1, xt+1) is saved to the replay memory buffer. At each time, a batch of transitions is sampled from this buffer, and the parameters of neural networks are optimized by using stochastic gradient descent to minimize the loss
(rh+1 + γh+1 max a′
qθ̄(xh+1, a ′)− qθ(xh, ah))2 (3)
where γh+1 is the chosen discount of time step h + 1, θ is the parameters of the online network, and θ̄ represents the parameters of the target network. The gradient of the loss is back-propagated
only to update θ, while θ̄ is not optimized directly. DQN has been successful as it led to superhuman performance on several Atari games. Nevertheless, there are also several limitations of this algorithm and many extensions have been proposed. Rainbow (Hessel et al., 2018) combines six of these extensions and obtains an excellent and stable performance on many Atari games. In the Appendix A, we review these tricks. In this paper, we focus on Rainbow DQN with low switching cost.

heading: 3.4 COUNT-BASED EXPLORATION

text: In many real-world scenarios that require low switching cost, it is also required to use deterministic policies, especially in applications mentioned above. Exploring strategies like -greedy and noisy net make the policy stochastic, which we cannot use here. Count-based exploration algorithms are known to perform near-optimally when used in reinforcement learning for solving tabular MDPs. Tang et al. (2017) applied these algorithms into high-dimensional state spaces successfully. They discretized the state space with a hash function φ : S → Z. Then an exploration bonus r+(x) = β√ n(φ(x)) is added to the reward function and the agent is trained with the modified reward r + r+. Note that with the count-based exploration, the policy is deterministic.

heading: 4 DETERMINISTIC RAINBOW DQN WITH A POLICY SWITCHING CRITERION

text: In this section, we first introduce how to implement a deterministic Rainbow DQN with a policy switching criterion. This implementation combines six DQN tricks and the policy is always deterministic.

heading: 4.1 DETERMINISTIC RAINBOW DQN

text:
We first discuss how to make Rainbow DQN always output deterministic policies. Recall that to explore more efficiently, Rainbow adopts the Noisy Net (Fortunato et al., 2018), which makes the policy stochastic. To obtain a deterministic policy and keep exploring, we remove Noisy Net and employ the Count-Based exploration described in the previous section. When the deployed policy interacts with the environment, it selects the action which maximizes theQ-function. After obtaining the reward by taking this action, an exploration bonus r+ = β√
n(φ(x)) is added into the reward.

heading: 4.2 DQN WITH A POLICY SWITCHING CRITERION

text: Besides, Rainbow updates the policies which interacts with the environment directly. These policies usually switch millions of times during the training process (since the parameters are updated millions of times). In our implementation, we add an online policy in addition to the deployed policy that interacts with the environment. The deployed policy collects the data for the experience replay buffer, while the online policy is frequently updated when training. The deployed policy is replaced with the online policy when they meet the criterion we will discuss soon. The algorithm of deterministic switching Rainbow is shown in Algorithm 1.

heading: 4.3 POLICY SWITCHING CRITERIA

text:
Here we first introduce two straightforward policy switching criteria.
Fixed Interval Switching This is the simplest criterion, we switch the deployed policy with a fixed interval. Under the FIX n criterion, we switch the deployed policy whenever the online policy is updated n times where n is a per-specified number. We will specify n in our experiments.
Adaptive Interval Switching This criterion aims to switch the deployed policy frequently at the first and reduce the switching speed gradually. Under the Adaptive n2m criterion, we increase the deployment interval from n to m. The interval between the i-th deployment and the (i + 1)-th deployment is min((i+ 1)× n,m). We will specify n and m in our experiments.
Algorithm 1 Deterministic Switching Rainbow 1: Initialize arameters θonline, θdeployed, θtarget for online policy, deployed policy and target policy,
initialize an empty replay buffer D 2: Denote the state encoder in online policy and deployed policy as fonline and fdeployed 3: Set the step to start training Hstart, the step to end training Hmax, and the interval to update the
target policy Htarget. 4: Set n(accumulated updates) = 0, n(deployment) = 0 5: for h = 1 to Hmax do 6: Select ah = arg maxaQdeployed(sh, a) 7: Execute action at and observe reward rh and state xh+1 8: Compute the hash codes through for xh, φ(xh) = sgn(Ag(xh)) 9: . A is a fixed matrix with i.i.d. entries drawn from a standard Gaussian distributionN (0, 1)
and g is a flat function 10: Update the hash table counts, n(φ(xh)) = n(φ(xh)) + 1 11: Update the reward rh = rh + β√
n(φ(rh))
12: Store (xh, ah, rh, xh+1) in D 13: if h > Hstart then 14: Sample a minibatch of transitions from D. 15: Update θonline by stochastic gradient descent on the sampled minibatch once. 16: if h % Htarget == 0 then 17: Update θtarget = θonline 18: Set n(accumulated updates) = n(accumulated updates) + 1 19: end if 20: if J (fdeployed, fonline, D, n(accumulated updates), n(deployment)) = true then 21: Update θdeployed = θonline 22: Update n(accumulated updates) = 0 23: Update n(deployment) = n(deployment) + 1 24: end if 25: end if 26: end for
Algorithm 2 Switching Criteria (J in Algorithm 1) . Fixed interval switching FIX n input n(accumulated updates) output bool(n(accumulated updates) ≥ n)
. Adaptive interval switching Adaptive n2m input n(accumulated updates), n(deployment) output bool(n(accumulated updates) ≥ min(n(deployment) + 1)× n,m)
. Feature-based switching F a input fdeployed, fonline, D Sample minibatch B of transitions (xh) from D with probability ph Compute the the similarity sim(xh) =
fdeployed(xh)·fonline(xh) ||fdeployed(xh)||×||fonline(xh)||
Compute the average similarity in sampled batch sim(B) = ∑ x∈B sim(x) ||B|| output bool(sim(B) ≤ a)
These two criteria and our proposed new criterion are summarized in Algorithm 2. Unfortunately, as will be shown in our experiments, these two criteria do not perform well. This requires us to design new principled criterion.

heading: 5 FEATURE-BASED SWITCHING CRITERION

text:
In the section, we describe our new policy switching criterion based on feature learning. We first describe this criterion, and then we provide some theoretical justification from a representation learning point of view.
Feature-based Switching Criterion We adopt the view the DQN learns to extract informative features of the states of environments. Our proposed criterion tries to switch the deployed policy according to the extracted feature. When deciding whether to switch the deployed policy or not, we first sample a batch of states B from the experience replay buffer, and then extract the feature of all states by both the deployed deep Q-network and online deep Q-network.
For a state x, the extracted feature are denoted as fdeployed(x) and fonline(x), respectively. The similarity score between fdeployed and fonline on state x is defined as
sim(x) = 〈fdeployed(x), fonline(x)〉
||fdeployed(x)|| × ||fonline(x)||
We then compute the averaged similarity score on the batch of states B sim(B) = ∑ x∈B sim(x)
||B||
With a hyper-parameter a ∈ [0, 1], the feature-based policy switching criterion is to change the deployed policy whenever sim(B) ≤ a.
Theoretical Justification Our criterion is inspired by representation learning. To illustrate the idea, we consider the following setting. Suppose we want to learn f(·), a representation function that maps the input to a k-dimension vector. We assume we have input-output pairs (x, y) with y = 〈w, f∗(x)〉 for some underlying representation function f∗(·) and a linear predictor w ∈ Rk. For ease of presentation, let us assume we know w, and our goal is to learn the underlying representation which together with w gives us 0 prediction error.
Suppose we have data sets D1 and D2. We use D1 to train an estimator of f∗, denoted as f1, and D1 ∪ D2 to train another estimator of f∗, denoted as f1+2. The training method is empirical risk minimization, i.e.,
f1 ← min f∈F
1 |D1| ∑
(x,y)∈D1
(y − 〈w, f(x)〉)2 and f1+2 ← min f∈F
1 |D1 ∪ D2| ∑
(x,y)∈D1∪D2
(y − 〈w, f(x)〉)2
where F is some pre-specified representation function class. The following theorem suggests if the similarity score between f1 and f1+2 is small, then f1 is also far from the underlying representation f∗. Theorem 1. Suppose f1 and f1+2 are trained via aforementioned scheme. There exist dataset D1, D2, function classF andw such that if the similarity score between f1 and f1+2 onD1+2 is smaller than α, then the prediction error of f1 on D1+2 is 1− α.
The proof is deferred to Appendix B where we give explicitly constructions.
Theorem 1 suggests that in certain scenarios, if the learned representation has not converged (the similarity score is small), then it cannot be the optimal representation which in turn will hurt the prediction accuracy. Therefore, if we find the similarity score is small, we should change the deployed policy.

heading: 6 EXPERIMENTS

text: In this section, we conduct experiments to evaluate different policy switching criteria on DQN. We study several Atari game environments along and an environment for simulating sepsis treatment for ICU patients. We evaluate the efficiency among different switching criteria in these environments. Implementation details and hyper-parameters are listed in the Appendix A.

heading: 6.1 ENVIRONMENTS

text:
GYMIC GYMIC is an OpenAI gym environment for simulating sepsis treatment for ICU patients to an infection, where sepsis is caused by the body’s response to an infection and could be lifethreatening. GYMIC built an environment to simulate the MIMIC sepsis cohort, where MIMIC is an open patient EHR dataset from ICU patients. This environment generates a sparse reward, the reward is set to +15 if the patient recovered and -15 if the patient died. This environment has 46 clinical features and a 5 × 5 action space. For the GYMIC, we display the learning curve of 1.5 million steps of the environment, after which the reward converge. We choose this environment because it is simulating a real-world problem that requires low switching cost. For Atari games, all the experiments were training for the environment stepping 3.5 million times.
Atari 2600 Atari 2600 games are widely employed to evaluate the performance of DQN based agents. We also evaluate the efficiency among different switching criteria on several games, such as Pong, Road Runner, Beam Rider, etc.

heading: 6.2 RESULTS AND DISCUSSIONS

text:
For all environments, we evaluate a feature-based criterion F 0.98, three fixed interval criteria covering a vast range FIX 102, F IX 103 and FIX 104, and an adaptive criterion increasing the deploying interval from 100 to 10,000. Besides the switching criteria we discussed above, we use “None” to indicate an experiment without the low-switching-cost constraint where deployed policy kept in sync with online policy all the time, notice that this experiment is equivalent to FIX 1.
Riverraid, although FIX 104 and Adaptive lead to lower switching cost, they fail to learn how to play the games well. Therefore, they are not desired generic policy switching criterion.
Secondly, we observe that changing the policy with an adaptive interval may be better than a fixed interval. Focusing on the criteria FIX 104 andAdaptive 102to104, the adaptive criterion switches the online policy fast at first and decrease its switching speed gradually, and in the end, the adaptive criterion would have the same speed as the fixed one. Therefore, there is no significant difference
between the total switching cost of these two criteria. However, we could observe that the adaptive criterion’s performance is better than the fixed one when playing Beam Rider, Pong, Qbert, and they obtain similar performances in the rest games.
Lastly, we find our proposed feature-based criterion (F 0.98) is the desired on that satisfy all four properties we discussed in Section 1. It significantly reduces the switching cost compared to “None”, and is smaller than FIX 102. While it incurs higher switching cost than FIX 103, FIX 104, and Adaptive 102to104, on all environments feature-based criterion consistently perform as well as “None” in the sense that 1) it finds the optimal policy eventually, 2) it has the same sample efficiency as “None”. On the other hand, other criteria sometime have significantly worse performance compared to “None”, so none of them is a generic solution.

heading: 7 CONCLUSION

text:
In this paper, we focus on the concept of switching cost and take a step toward designing a generic solution for reducing the switching cost while maintaining the performance. Inspired by representation learning theory, we proposed a new feature-based policy switching criterion for deep Q-learning methods. Through experiment on one medical simulation environment and six Atari games, we find our proposed criterion significantly reduces the switching cost and at the same time enjoys the same performance as the case where there is no switching cost constraint.
We believe our paper is just the first step on this important problem. One interesting question is how to design principled policy switching criteria for policy-based and model-based methods. Another direction is to give provable guarantees for these policy switching criteria that work for methods dealing with large state space in contrast to existing analyses are all about tabular RL (Bai et al., 2019; Zhang et al., 2020b;a).

heading: A DETAILS OF EXPERIMENTS

text:
A.1 DETAILED ALGORITHM
For completeness, we introduce the extensions of DQN and display our detailed algorithm.
Double Q-learning Conventional Q-learning is affected by an overestimation bias, due to the maximization step in Equation 3, Double Q-learning (Hasselt et al., 2016) address this problem by decoupling. They use the loss
(rh+1 + γh+1qθ̄(xh+1, arg max a′
qθ(xh+1, a ′))− qθ(xh, ah))2 (4)
This change reduce harmful overestimations that were present for DQN, which leads to a improvement.
Multi-step learning Q-learning accumulates a single reward, Sutton (2005) use a forward-view multi-step accumulated reward long ago, where a n-step accumulated reward is defined as
r (n) h := n−1∑ k=0 γ (n) h rh+k+1 (5)
and the final loss is (r
(n) h + γ (n) h maxa′ qθ̄(xh+1, a ′)− qθ(xh, ah))2 (6)
Multi-step targets often lead to faster learning (Sutton & Barto, 2005)
Dueling networks Wang et al. (2016) splits the DQN network into two streams called value stream V and advantage stream A, these two strems share the convolutional encoder f , and action value Q(x, a) could be computed as:
Q(x, a) = V (f(x)) +A(f(x), a)− ∑ a′ A(f(x), a ′)
Nactions (7)
Prioritized replay DQN samples uniformly from the replay buffer, to sample more frequently from those transitions from which the policy can learn more and quickly, Schaul et al. (2016) samples transitions with probability ph relative to the last encountered absolute TD error
ph ∝ |rh+1 + γh+1 max a′ qθ̄(xh+1, a ′)− qθ(xh, ah)|ω (8)
where ω is a hyper-parameter, and new transitions always have the maximum priority when they enter the buffer to ensure a bias towards unseen transitions.
Distributional RL Instead of approximating the expected return as DQN, Bellemare et al. (2017) proposed a method to approximate the distribution of returns on a a discrete support z, z is a vector with Natoms atoms and is defined as
zi = Vmin + (i− 1) Vmax − Vmin Natoms − 1 , i ∈ 1, 2, ..., Natoms (9)
where Vmin and Vmax is the minimal and maximal value in this support. The approximating distribution dh is defined on this support and the probability piθ(xh, ah) on each atom i as dh = (z, pθ(xh, ah)) .The goal is to update the trainable parameters θ to match this distribution with the actual distribution of returns. To learn the probability piθ for each i with a variant of Bellman’s equation, they minimize the Kullbeck-Leibler divergence DKL(Φzd′h||dh) between the distribution dh and the target distribution d′h := (rh+1+γh+1z, pθ̄(xh+1, arg maxa′ qθ̄(xh+1, a
′))), where Φz is a L2-projection from the target distribution to the fixed support z and qθ̄(xh+1, a) = z T pθ̄(xh+1, a)
Nosiy Net To address the limitations of exploring using -greedy policies, Fortunato et al. (2018) propose a noisy linear layer
y = b+Wx+ (bnoisy b + (Wnoisy w)x) (10) to replace the standard linear y = b + Wx, where b and w are random variables, denotes the element-wise product.
Rainbow combines all of these 6 extensions, To make the policy deterministic but still keep exploring during training, we remove the Noisy Net and adopt Count-Based exploration. The detailed algorithm is as follows.
Algorithm 3 Detailed algorithm 1: . Hyper-parameters for extensions 2: Distributional RL: Number of atoms Natoms, min/max values Vmin/Vmax 3: Prioritization replay memory: exponent ω, capacity N 4: Multi-step: number of steps n 5: . Initialization 6: Initialize prioritization replay memory D, state encoder fonline, value stream Vonline and advan-
tage stream Aonline for online policy Ponline 7: Initialize deployed policy Pdeployed and target policy Ptarget with parameters in Ponline 8: . Definition of Q-function 9: zi = Vmin + (i− 1) vmax−vminNatoms−1
10: Āionline(x) = 1
Nactions
∑ aA i online(fonline(x), a)
11: pionline(x, a) = softmax(V i online(fonline(x)) +A i online(fonline(x), a)− Āionline(x)) 12: Qonline(x, a) = ∑ i zip i online(x, a)
13: Similarly, Qdeployed(x, a) = ∑ i zip i deployed(x, a), Qtarget(x, a) = ∑ i zip i target(x, a) 14: 15: . Training process 16: set up environment 17: n(accumulated updates) = 0, n(deployment) = 0 18: for h = 1 to Hmax do 19: if Termination then 20: reset environment 21: end if 22: select ah = arg maxaQdeployed(xh, a) 23: Execute action ah in emulator and observe reward rh and state xh+1 24: compute the hash codes through for xh, φ(xh) = sgn(Ag(xh)) 25: . A is a matrix with i.i.d. entries drawn from a standard Gaussian distribution N (0, 1) and
g is a flat function 26: update the hash table counts, n(φ(xh)) = n(φ(xh)) + 1 27: update the reward rh = rh + β√
n(φ(xh))
28: store (xh, ah, rh, xh+1) in D 29: if h > Hstart then 30: sample minibatch of transitions (xh′ , ah′ , wh′ , rh′ , rh′+1 ..., rh′+n−1, xh′+n) from D
with probability ph′ 31: . wh′ is the importance-sampling weight for transitions at h′
32: compute the multi-step reward r(n)h′ = ∑n−1 k=0 γ
nrh′+k 33: a∗ = arg maxaQonline(xh′+n, a),mi = 0, i ∈ 1, 2, ..., Natoms 34: for j = 1 to Natoms do 35: T̂ zj = [r(n)h′ + γnzj ].clip(Vmin, Vmax) 36: ∆z = (Vmax − Vmin)/(Natoms − 1) 37: bj = (T̂ zj − Vmin)/∆z, l = bbjc, u = dbje 38: ml = ml + p j target(xh′+n, a
∗)(u− bj),mu = mu + pjtarget(xh′+n, a∗)(bj − l) 39: end for 40: DKLh′ = − ∑ imi log p i online(xh′ , ah′) 41: update ph′ by ||DKLh′ ||ω 42: update parameters in Ponline by a gradient descent step on DKLh′ × wh′
43: n(accumulated updates) = n(accumulated updates) + 1 44: if h % Htarget then 45: update Ptarget by the parameters of Ponline 46: end if 47: if J (fd, fo, D, n(accumulated updates),n(deployment)) = true then 48: update Pdeployed by the parameters of Ponline 49: n(accumulated updates) = 0, n(deployment) = n(deployment) + 1 50: end if 51: end if 52: end for
A.2 HYPE-PARAMETERS
Table 1 lists the basic hyper-parameters of the algorithm, all of our experiments share these hyperparameters except the experiments on GYMIC adopt the Htarget as 1K. Most of these parameter are the same with raw Rainbow algorithm. For the count base exploration, the bonus is β set to 0.01.
Table 2 lists the rest hyper-parameters for experiments on GYMIC. Since there are 46 clinical features in this environment, we stack 4 consecutive states to compose a 184-dimensional vector as the input for the state encoder fonline(fdeployed or ftarget). The state encoder is a 2-layer MLP with hidden size 128.
Table 3 shows the additional hyper-parameters for experiments on Atari games. The observations are grey-scaled and resized to 84× 84 tensor, and 4 consecutive frames are concatenated as a single state, each action selected by the agent is repeated for 4 times. The state encoder is composed of 3 convolutional layers with 32, 64 and 64 channels, which use 8x8, 4x4, 3x3 filters and strides of 4, 2, 1 respectively.
A.3 REWARD AND SWITCHING COST
In the end, we list the value of the switching cost and reward of different criteria when the environment take 1.5 million steps and 3 million steps in Table 4.

heading: B PROOF FOR SECTION 5

text:
Proof of Theorem 1. We let w = (1, 1, . . . , 1) ∈ Rk be a k-dimensional all one vector. We let
F = {f : f(x) = (2σ(〈v1, x〉)− 1, 2σ(〈v2, x〉)− 1, . . . , 2σ(〈vk, x〉)− 1)} ⊂ {Rk → Rk}
with σ(·) being the ReLU activation function1 and vi ∈ {ei,−ei} where ei ∈ Rk denotes the vector that only the i-th coordinate is 1 and others are 0. We assume k is an even number and αk is an integer for simplicity. We let the underlying f∗ be the vector correspond to (e1, e2, . . . , ek). We let D1 = {(e1, 1), (e2, 1), . . . , (e(1−α)k, 1)} and D2 = {(e(1−α)k+1, 1), . . . , (ek, 1)}. Because we use the ERM training scheme, it is clear that the training on D1 ∪ D2 will recover f∗, i.e., f1+2 = f∗ because if it is not f∗ is better solution (f∗ has 0 error ) for the empirical risk. Now if the similarity score between f1 and f1+2 is smaller than α, it means for f1, its corresponding {v(1−α)k+1, . . . , vk} are not correct. In this case, f1’s prediction error is at least 1−α onD1∪D2, because it will predict 0 on all inputs of D2.
1We define σ(0) = 0.5
1, 50
0, 00
0 st
ep s
en vi
ro nm
en t
cr ite
ri a
N on
e FI
X 1 02
FI X
1 0
3 FI
X 1 0
4 A
da pt
iv e
F 0.
98
ba ttl
e zo
ne Sw
itc hi
ng co
st 36
87 50
.0 36
87 .5
36 9.
0 36
.5 84
.5 52
9. 2
R ew
ar d
26 90
0 .0 ±
94 45 .1
2 3 0 7 0.
0 ±
7 6 9 1 .9
1 7 9 3 0 .0 ±
4 4 7 2.
7 1 8 8 7 0 .0 ±
4 4 1 7.
4 1 4 3 3 0 .0 ±
4 3 9 7.
9 1 6 9 7 0 .0 ±
5 7 6 6. 2 G ap N /A -3 83 0. 0 -8 97 0. 0 -8 03 0. 0 -1 25 70 .0 -9 93 0. 0
be am
ri de
r Sw
itc hi
ng co
st 36
87 50
.0 36
87 .5
36 9.
0 36
.5 84
.5 11
9. 6
R ew
ar d
76 55 .9 ±
20 21 .2
7 5 5 4.
2 6 ±
2 2 8 3 .4
7 4 9 3.
7 6 ±
2 3 7 6.
4 4 0 6 8.
2 6 ±
1 3 4 0.
2 4 0 7 8.
5 6 ±
1 8 1 9.
8 6 7 5 9.
7 4 ±
2 1 3 6. 3 G ap N /A -1 01 .6 -1 62 .1 -3 58 7. 6 -3 57 7. 3 -8 96 .2
po ng
Sw itc
hi ng
co st
36 87
50 .0
36 87
.5 36
9. 0
36 .5
84 .5
16 81 .4 R ew ar d − 12 .8 7 ± 8. 1 − 2. 5 ± 9 .2 − 1 3. 6 9 ± 4. 0 − 1 2. 9 7 ± 5. 2 − 7. 1 4 ± 1 0. 2 0. 0 8 ±
6. 7
G ap
N /A
10 .4
-0 .8
-0 .1
5. 7
12 .9
qb er
t Sw
itc hi
ng co
st 36
87 50
.0 36
87 .5
36 9.
0 36
.5 84
.5 12
68 .5
R ew
ar d
60 50 .2
5 ±
21 89 .2
5 0 7 3 .7
5 ±
6 2 4 .7
4 3 5 9.
7 5 ±
5 3 4 .2
6 4 9 .2
5 ±
2 4 5 .3
2 6 8 1.
0 ±
1 6 9 6 .1
3 9 4 7.
5 ±
1 4 3 8. 0 G ap N /A -9 76 .5 -1 69 0. 5 -5 40 1. 0 -3 36 9. 2 -2 10 2. 8
riv er
ra id
Sw itc
hi ng
co st
36 87
50 .0
36 87
.5 36
9. 0
36 .5
84 .5
89 9. 5 R ew ar d 54 53 .2 ± 78 7 .6 4 6 0 2. 8 ± 6 9 3 .8 4 1 7 7 .0 ± 8 7 0 .0 3 1 5 2 .6 ± 6 5 8 .6 3 2 6 7 .6 ± 7 0 5 .2 4 1 8 2 .2 ±
9 2 5 .8
G ap
N /A
-8 50
.4 -1
27 6.
2 -2
30 0.
6 -2
18 5.
6 -1
27 1.
0
ro ad
ru nn
er Sw
itc hi
ng co
st 36
87 50
.0 36
87 .5
36 9.
0 36
.5 84
.5 13
09 .0
R ew
ar d
13 26
6 .0 ±
15 13 .4
2 6 0 3 9.
0 ±
4 6 0 5 .4
1 4 9 4 7 .0 ±
2 0 0 0.
3 3 0 6 2 0 .0 ±
6 9 4 6.
2 1 9 5 1 3 .0 ±
4 7 5 1.
0 2 8 9 6 8 .0 ±
4 8 2 7. 2 G ap N /A 12 77 3. 0 16 81 .0 17 35 4. 0 62 47 .0 15 70 2. 0 3, 00 0, 00 0 st ep s
ba ttl
e zo
ne Sw
itc hi
ng co
st 74
37 50
.0 74
37 .5
74 4.
0 73
.5 12
2. 5
42 40 .3 R ew ar d 32 25 0 .0 ± 81 19 .6 2 3 9 1 0. 0 ± 6 2 8 9 .8 2 1 2 9 0 .0 ± 8 1 9 1. 8 1 7 8 3 0 .0 ± 4 3 8 4. 2 1 2 5 3 0 .0 ± 5 0 9 6. 0 2 6 1 8 0 .0 ±
7 1 6 1. 5 G ap N /A -8 34 0. 0 -1 09 60 .0 -1 44 20 .0 -1 97 20 .0 -6 07 0. 0
be am
ri de
r Sw
itc hi
ng co
st 74
37 50
.0 74
37 .5
74 4.
0 73
.5 12
2. 5
12 33 .4 R ew ar d 13 75 1 .2 ± 65 30 .9 1 1 3 9 3 .2 4 ± 4 8 0 2. 1 1 2 2 3 6 .6 2 ± 5 6 6 9. 9 5 6 5 4. 1 6 ± 2 1 2 0. 0 8 8 5 7. 9 4 ± 3 1 7 3. 9 1 2 3 1 1 .3 4 ±
6 7 3 1 .4
G ap
N /A
-2 35
8. 0
-1 51
4. 6
-8 09
7. 0
-4 89
3. 3
-1 43
9. 9
po ng
Sw itc
hi ng
co st
74 37
50 .0
74 37
.5 74
4. 0
73 .5
12 2.
5 26
87 .0
R ew
ar d
17 .9
6 ±
6. 8
1 7 .9
2 ±
4. 4
2 0 .3
5 ±
2. 3
1 7 .0 ±
5. 0
1 9 .0
2 ±
2. 2
1 7 .4
3 ±
5 .4
G ap
N /A
-0 .0
2. 4
-1 .0
1. 1
-0 .5
qb er
t Sw
itc hi
ng co
st 74
37 50
.0 74
37 .5
74 4.
0 73
.5 12
2. 5
19 80 .5 R ew ar d 17 68 5 .2 5 ± 24 86 .0 1 7 0 3 8. 5 ± 2 7 1 0 .1 1 3 8 3 6 .0 ± 4 0 3 2. 8 2 1 9 3. 7 5 ± 1 6 2 9. 5 3 8 3 8. 0 ± 1 7 1 6 .6 1 3 7 9 1 .0 ±
3 3 7 2. 0 G ap N /A -6 46 .8 -3 84 9. 2 -1 54 91 .5 -1 38 47 .2 -3 89 4. 2
riv er
ra id
Sw itc
hi ng
co st
74 37
50 .0
74 37
.5 74
4. 0
73 .5
12 2.
5 23
25 .5
R ew
ar d
78 08 .6 ±
30 8 .6
7 8 4 0.
3 ±
3 5 1 .4
7 8 7 2 .9 ±
9 3 9 .1
3 3 9 1 .1 ±
8 2 1 .2
4 0 1 3 .5 ±
9 3 8 .3
7 0 5 2 .3 ±
8 6 2 .7
G ap
N /A
31 .7
64 .3
-4 41
7. 5
-3 79
5. 1
-7 56
.3
ro ad
ru nn
er Sw
itc hi
ng co
st 74
37 50
.0 74
37 .5
74 4.
0 73
.5 12
2. 5
27 36 .6 R ew ar d 37 48 0 .0 ± 84 29 .9 3 6 1 1 8. 0 ± 6 3 6 6 .6 3 6 7 2 2 .0 ± 7 1 1 9. 7 3 5 0 5 5 .0 ± 7 0 9 5. 8 4 5 7 0 6 .0 ± 8 4 7 3. 7 4 5 9 4 0 .0 ±
8 2 3 4. 1 G ap N /A -1 36 2. 0 -7 58 .0 -2 42 5. 0 82 26 .0 84 60 .0
Ta bl
e 4:
W e
lis t
th e
va lu
e of
th e
sw itc
hi ng
co st
an d
re w
ar d
of di
ff er
en t
cr ite
ri a
w he
n th
e en
vi ro
nm en
t ta
ke s
1. 5
m ill
io n
st ep
s an
d 3
m ill
io n
st ep
s. “R
ew ar d” co rr es po nd s to th e ab so lu te va lu e of th e re w ar d, an d “G ap ” de no te s th e di ff er en ce be tw ee n th e re w ar d un de ra sp ec ifi c cr ite ri on an d “N on e. ” A nd “S w itc hi ng C os t” co rr es po nd s to th e sw itc hi ng co st un de ra cr ite ri on at th is tim e st ep .


summaries: This paper proposes homotopy SGD (H-SGD) which solves a sequence of unconstrained problems with a homotopy map and homotopy parameter. The authors analyze the algorithm for solving nonconvex problems satisfying PL condition. The analysis works with a generic homotopy map and homotopy parameter satisfying certain conditions (given in Sec 3.1). The authors show linear convergence to a neighborhood of the minimizer. The theoretical results are validated with experiments with clear explanations.

summaries: This paper proposed a Homotopy-Stochastic Gradient Descent (H-SGD) algorithm by applying homotopy strategy to explore the nice local structures of problems. H-SGD can gradually approximate to the target objective function and enjoys a global linear convergence to reach a neighborhood of a minimizer. As verified by the author, the assumption of this paper is weaker than its predecessors, Karimi et al., 2016; Vaswani et al., 2019. Further, the numerical experiments verified the effectiveness of H-SGD on regression and classification tasks.

summaries: 1. It seems to me the proposed Homotopy-SGD is not a practical algorithm, as in each iteration the algorithm has to solve a nontrivial (possibly nonconvex) subproblem. In other words, each subproblem can be as difficult as the original problem. This leads to an essential question that what is the practical motivation of this algorithm?

abstractText: First-order stochastic methods for solving large-scale non-convex optimization problems are widely used in many big-data applications, e.g. training deep neural networks as well as other complex and potentially non-convex machine learning models. Their inexpensive iterations generally come together with slow global convergence rate (mostly sublinear), leading to the necessity of carrying out a very high number of iterations before the iterates reach a neighborhood of a minimizer. In this work, we present a first-order stochastic algorithm based on a combination of homotopy methods and SGD, called Homotopy-Stochastic Gradient Descent (H-SGD), which finds interesting connections with some proposed heuristics in the literature, e.g. optimization by Gaussian continuation, training by diffusion, mollifying networks. Under some mild assumptions on the problem structure, we conduct a theoretical analysis of the proposed algorithm. Our analysis shows that, with a specifically designed scheme for the homotopy parameter, H-SGD enjoys a global linear rate of convergence to a neighborhood of a minimum while maintaining fast and inexpensive iterations. Experimental evaluations confirm the theoretical results and show that H-SGD can outperform standard SGD.

authors:
E.L. Allgower
Kurt Georg

title: Introduction to Numerical Continuation Methods

venue: Society for Industrial and Applied Mathematics,

authors:
Yoshua Bengio
Pascal Lamblin
Dan Popovici
Hugo Larochelle

title: Greedy layer-wise training of deep networks

venue: In Proceedings of the 19th International Conference on Neural Information Processing Systems,

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In Proceedings of the 26th Annual International Conference on Machine Learning,

authors:
Andrew Blake
Andrew Zisserman

title: Visual Reconstruction

authors:
Léon Bottou
Frank E. Curtis
Jorge Nocedal

title: Optimization methods for large-scale machine learning

venue: SIAM Review,

authors:
Thomas Brox
Jitendra Malik

title: Large displacement optical flow: descriptor matching in variational motion estimation

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
O. Chapelle
B. Schölkopf
A. Zien

title: Semi-Supervised Learning. Adaptive computation and machine learning

authors:
Yann N Dauphin
Razvan Pascanu
Caglar Gulcehre
Kyunghyun Cho
Surya Ganguli
Yoshua Bengio

title: Identifying and attacking the saddle point problem in highdimensional non-convex optimization

venue: Advances in Neural Information Processing Systems

title: Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of Machine Learning Research,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In Proceedings of the 34th International Conference on Machine Learning Volume 70,

authors:
Matilde Gargiani
Andrea Zanelli
Quoc Tran Dinh
Moritz Diehl
Frank Hutter

title: Transferring optimality across data distributions via homotopy methods

venue: In International Conference on Learning Representations (ICLR),

authors:
Michael Gashler
Dan Ventura
Tony Martinez

title: Iterative non-linear dimensionality reduction with manifold sculpting

authors:
Saeed Ghadimi
Guanghui Lan

title: Stochastic first- and zeroth-order methods for nonconvex stochastic programming

venue: SIAM Journal on Optimization,

authors:
Elad Hazan
Kfir Yehuda Levy
Shai Shalev-Shwartz

title: On graduated optimization for stochastic non-convex problems

venue: Proceedings of the 33nd International Conference on Machine Learning,

authors:
Geoffrey E. Hinton
Nitish Srivastava
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Improving neural networks by preventing co-adaptation of feature detectors

venue: arXiv e-prints,

authors:
Hamed Karimi
Julie Nutini
Mark Schmidt

title: Linear convergence of gradient and proximalgradient methods under the polyak-undefinedojasiewicz condition. In European Conference on Machine Learning and Knowledge Discovery in Databases - Volume 9851

venue: ECML PKDD

title: Linear convergence under the Polyak-Łojasiewicz inequality, February 2017

title: Deep learning without poor local minima

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations,

authors:
S. Kirkpatrick
C.D. Gelatt
M.P. Vecchi

title: Optimization by simulated annealing

venue: Science,

title: Homotopy Analysis Method in Nonlinear Differential Equations

authors:
Qihang Lin
Lin Xiao

title: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization

venue: Proceedings of the 31st International Conference on Machine Learning,

title: Training recurrent neural networks by diffusion

authors:
Hossein Mobahi
John W. Fisher III

title: On the link between gaussian homotopy continuation and convex envelopes

venue: URL https://doi.org/10.1007/

authors:
Hossein Mobahi
C.L. Zitnick
Yi Ma

title: Seeing through the blur

venue: In Proceedings / CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1736–1743,

authors:
Arkadi Nemirovski
Anatoli Juditsky
Guanghui Lan
Alexander Shapiro

title: Robust stochastic approximation approach to stochastic programming

authors:
Sinno Jialin Pan
Qiang Yang

title: A survey on transfer learning

venue: IEEE Trans. on Knowl. and Data Eng.,

title: Math 4565 topology homotopy, Spring 2016

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

venue: In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume

venue: Proceedings of the 30th International Conference on Machine Learning,

authors:
Shinya Suzumura
Kohei Ogawa
Masashi Sugiyama
Ichiro Takeuchi

title: Outlier path: A homotopy algorithm for robust svm

authors:
Sharan Vaswani
Francis Bach
Mark Schmidt

title: Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron

venue: Proceedings of Machine Learning Research,

authors:
Lin Xiao
Tong Zhang

title: A proximal-gradient homotopy method for the sparse least-squares problem

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

heading: 1 INTRODUCTION

text:
This paper focuses on the theoretical development and analysis of a stochastic optimization algorithm, called Homotopy-Stochastic Gradient Descent (H-SGD), based on the combination of homotopy methods and stochastic gradient descent (SGD). The algorithm we propose is specifically designed to solve finite-sum problems of the following form
w∗ ∈ arg min w∈Rd f(w) := 1N N∑ j=1 fj(w)  , (1) where f : Rd → R is continuously differentiable, bounded below and not necessarily convex. In particular, we assume that we only have access to noisy function values and gradients of the objective function in equation 1 via a stochastic first-order oracle, as in (Nemirovski et al., 2009) and (Ghadimi & Lan, 2013). Problems of this form typically arise in machine learning and deep learning applications, where the dimensionality of the datasets makes the full function and gradient evaluations too expensive. This class of problems is generally approximately solved by stochastic first-order iterative algorithms, e.g. SGD (Bottou et al., 2018), Adagrad (Duchi et al., 2011), Adam (Kingma & Ba, 2015). At the iteration t, the algorithms of this class acquire a stochastic estimate of the function value f(wt, ξt) and the gradient g(wt, ξt) by calling the oracle with input wt, where ξt is a random variable, i.e. when the noise comes from subsampling as in the mini-batch scenarios, then ξt ∈ {0, 1}N with ‖ξt‖1 = M and g(wt, ξt) = 1 M ∑N j=1 ξt,j · ∇fj(wt). In the case of SGD, for a given w0 ∈ Rd and α > 0, the iterates are generated as follows
wt+1 := wt − αg(wt, ξt) . (2)
Consequently, the iterate wt+1 = wt+1(ξ[t]) is a function of the history ξ[t] := (ξ0, . . . , ξt) (also w0 should be included in case it is a random initial point) of the generated random process and hence is itself random.
In general, stochastic first-order methods enjoy fast convergence when the problem is characterized by a certain structure. In particular, when the Polyak-Łojasiewicz (PL) condition (see Karimi et al., 2016, for more details on the PL condition) holds for the objective function in Problem 1, then, with a “small enough” value for the step-size, the SGD iterates converge linearly to a minimizer’s neighborhood (Karimi et al., 2016; Vaswani et al., 2019). Unfortunately, in many machine learning applications, the PL condition is not a realistic assumption as the landscape is generally characterized by the presence of multiple local minima and saddle points (Dauphin et al., 2014; Kawaguchi, 2016; Karimi et al., 2017). At the same time, in the vicinity of the minimizers the problems generally show stronger structures, i.e. PL or even strong convexity, allowing for a faster local convergence (Karimi et al., 2017). In such a scenario, a smart initialization hence becomes crucial for the numerical performance of the method (Sutskever et al., 2013b). Unfortunately, the power of the existing smart initialization heuristics is often quite limited given the small knowledge of the problem’s landscape which we generally dispose of. In addition, these heuristics typically can not guarantee that the SGD iterates start “close enough” to a minimizer, i.e. in the region where the PL condition holds, such that the method enjoys a linear rate of convergence. Therefore, the ideal scenario would be to be able to exploit the stronger local structure while the method’s iterates gradually approach a minimizer and independently from the starting point. In this regard, homotopy methods are a general strategy for tackling difficult optimization problems by gradually transforming a simplified version of a target problem, or a version with a known minimizer, back to its original form while following a solution along the way. Consequently, they preserve in each step the vicinity to a minimizer of the currently tackled problem, allowing the solver to always work in regions where the problems exhibit stronger structures. In general terms, homotopy methods (Allgower & Georg, 2003) are a widely and successfully used mathematical tool to efficiently solve various problems in numerical analysis, e.g. (Deuflhard, 2011), (Liao, 2012). Such methods are also suitable to solve complex non-convex optimization problems where no or only little prior knowledge regarding the localization of the solutions is available, allowing for the exploitation of the stronger local structures of the problems in order to achieve fast global convergence, e.g. (Xiao & Zhang, 2012; Lin & Xiao, 2014; Suzumura et al., 2014; Gargiani et al., 2020).
In this work, we propose a stochastic first-order numerical method to solve Problem 1, called Homotopy-Stochastic Gradient Descent (H-SGD), which is based on the combination of the homotopy method and SGD. After introducing the method and discussing the related work (Section 2), our contributions are as follows
1. In Section 3, we provide a general theoretical analysis of H-SGD under some mild assumptions, showing that, if the increments in the homotopy parameter are “small enough”, the proposed method tracks in expectation an r-optimal solution across homotopy iterations. We then show that, in the same setting, H-SGD can achieve a global linear rate of convergence to a minimizer’s neighborhood when used in combination with a specific schedule for the homotopy parameter, i.e. ∆λi decreases exponentially across homotopy iterations.
2. In Section 4, we empirically evaluate the performance of H-SGD. Our experiments not only confirm the theoretical results derived in Section 3 but also show that H-SGD with a smartly designed homotopy map can outperform SGD.

heading: 2 HOMOTOPY-SGD

text:
Homotopy-Stochastic Gradient Descent (H-SGD) is based on the combination of the homotopy method and SGD, in the hope of combining the best of both worlds. In particular, the goal is that of maintaining the advantageous properties of SGD, such as its cheap iterations and fast local convergence under PL condition, while maximally exploiting the stronger local structures via the homotopy scheme. Therefore, H-SGD relies on the definition of a homotopy map f(w, λ) : Rd × [0, 1]→ R, such that, when λ = 0 we recover a well-behaved function, e.g. convex, or a function with a known minimizer’s localization, and by increasing the λ parameter, also called homotopy parameter, we gradually morph it in order to finally end up with our target objective function f(w, 1) = f(w) (see Suciu, 2016, for more details on homotopy functions). By using such a homotopy map, H-SGD finds an approximate solution of Problem 1 by approximately solving a series of parametric problems that gradually leads to the target one. In particular, in each homotopy
iteration i, H-SGD tackles a parametric problem of the form
w∗i ∈ arg min w∈Rd f(w, λi) , (3)
where the homotopy parameter λi is slightly increased at each homotopy iteration. As confirmed by our theoretical analysis, if the variations of the homotopy parameter, i.e. ∆λi, are “small enough” across homotopy iterations, the method is able to track in expectation an r-optimal solution from source to target problem. As shown in Algorithm 1, H-SGD takes as input an approximate solution for the problem associated with f(w, 0), i.e. w0, and is then characterized by two loops: in the outer loop (homotopy iterations) the method defines a new objective function by increasing the homotopy parameter (line 5 in Algorithm 1), and in the inner loop (warm-started SGD iterations) the current homotopy problem is approximately solved with k iterations of SGD starting from the previously derived approximate solution, i.e. wi−1 (line 6 in Algorithm 1). Different functions h : N→ (0, 1] to determine the increment ∆λi in the homotopy parameter at each homotopy iteration can be used. As shown in our analysis, this function greatly impacts on the method’s properties and convergence rate. In particular, our theoretical analysis confirms that, when a specifically designed scheme for ∆λi is deployed, i.e. exponentially decreasing schedule, H-SGD is effective in guaranteeing a global linear rate of convergence to a neighborhood of a minimizer of our target problem, while, given the same setting, vanilla SGD can only ensure a global sublinear rate of convergence.
Algorithm 1 Homotopy-Stochastic Gradient Descent (H-SGD) 1: input: w0 ∈ Rd, n ∈ N, k ∈ N, h : N→ (0, 1] with ∑n i=1 h(i) = 1 and α > 0
2: initialization: i = 0, λ0 = 0 3: for i = 1, . . . , n do 4: ∆λi ← h(i) 5: λi ← λi−1 + ∆λi 6: wi ←SGD(wi−1, α, k, f(·, λi)) 7: output: wi

heading: 2.1 RELATED WORK

text:
Finding a solution of Problem 1 when the objective function is non-convex is often quite challenging. Different heuristics hence have been proposed to speed up and improve the optimization of such problems, many of which to be used in combination with stochastic first-order methods such as SGD. In this regard, the proposed method, despite being new in its general formulation and analysis, finds many interesting similarities and connections with existing heuristics in the machine learning literature, e.g. (Bengio et al., 2009; Hinton et al., 2012; Sutskever et al., 2013a). We now briefly discuss some of the state-of-the-art optimization techniques and initialization strategies for solving Problem 1 that are most related to H-SGD, drawing connections with existing and ongoing research works and in the hope that our analysis can also lead to a new interpretation of some widely used techniques which so far lack a more rigorous theoretical description and analysis.
Graduated Optimization. The graduated optimization approach (Blake & Zisserman, 1987), also known as coarse-to-grained optimization method, is a general heuristic to solve complex non-convex problems that relies on the basic principles of the homotopy method. As the name suggests, at first a coarse-grained and “easy-to-solve” version of the target problem is generated via a smoothing operation. The method then proceeds by gradually refining the problem versions, using the previous solution as initial point. Graduated optimization has been utilized explicitly and implicitly as heuristic in many machine learning and computer vision applications, e.g. object localization (Mobahi et al., 2012), manifold learning (Gashler et al., 2007), optical flow (Brox & Malik, 2011). Unfortunately, many of these techniques have practical and/or theoretical gaps, as they generally lack a rigorous running time and convergence analysis, and/or, as in (Mobahi & Fisher III, 2014) and (Hazan et al., 2016), they rely on an expensive method, i.e. Gaussian smoothing, to construct coarsegrained versions of the original target problem. Regarding theoretical contributions on graduated optimization methods for solving Problem 1, Hazan et al. (2016) are the first and only, to the best of our knowledge, to provide a theoretical analysis for the running time and convergence rate of a graduated optimization method based on an approximate, yet still expensive, type of Gaussian smoothing and SGD. Unfortunately, their analysis shows two major limitations. First, it relies on their
Gaussian smoothing approximation as homotopy map, which limits the generality of the conducted analysis, while our analysis is independent from the specific formulation of the homotopy map used. Second, the analysis is based on the assumption of local strong convexity, which is a quite strong requirement and hence might lead to considerably smaller local regions than those considered in our analysis (Karimi et al., 2017). To conclude this short overview on graduated optimization, many successful optimization heuristics proposed in the machine learning literature are implicitly related to graduated optimization and, consequently, to homotopy methods, such as curriculum learning (Bengio et al., 2009), simulated annealing (Kirkpatrick et al., 1983), noise injection techniques (Hinton et al., 2012), smart initialization (Sutskever et al., 2013a) and layer-wise pretraining (Bengio et al., 2006).
Transfer Learning. Due to the massive amount of computational resources required by the development of modern machine learning applications, the community has started to explore the possibility of re-using learned parameters across different tasks, leading to the development of many new transfer-learning algorithms, e.g. (Torrey & Shavlik, 2010; Pan & Yang, 2010; Yosinski et al., 2014; Gargiani et al., 2020). A simple yet often effective way to transfer knowledge across different tasks consists in using warm-start initialization. In this perspective, transfer-learning boils down to a sort of smart initialization heuristic. A first connection between homotopy methods and transfer-learning was underlined in (Gargiani et al., 2020). The authors propose a transfer-learning algorithm based on the homotopy method and SGD via the definition of a homotopy map that transforms a source task into a target task. The method comes together with a general theoretical analysis that is independent from the specific homotopy map adopted and shows that, under some assumptions, the algorithm can track in expectation an approximate solution from source to target task, i.e. optimality-tracking. Unfortunately, the method’s analysis is limited as it only considers constant increments of the homotopy parameter, which automatically degrades the linear rate of the local solver to a sublinear one for the homotopy-based method. In addition, as in (Hazan et al., 2016), the analysis relies on the assumption of local strong convexity, which might hold in a significantly smaller neighborhood of the minimizers than the PL condition (Karimi et al., 2017).

heading: 3 THEORETICAL ANALYSIS

text:
In this section, we provide a general theoretical analysis of H-SGD as described in Algorithm 1. In particular, after discussing the required underlying assumptions (Section 3.1), and the fundamental theoretical preliminaries (Section 3.2), first we analyze the optimality tracking properties of the proposed method (Section 3.3), and then we show that, with a specifically designed scheme for the homotopy parameter, H-SGD enjoys linear convergence to a minimizer’s neighborhood (Section 3.4). The analysis we conduct is independent from the specific type of homotopy map adopted and it applies to any scenario where the assumptions listed in Section 3.1 hold.
Recall that the proposed method is based on sequentially and approximately solving a series of n unconstrained parametric problems of the form
arg min w∈Rd
f(w, λi) , ∀i = 1, . . . , n , (4)
where λi < λi+1, λn = 1, λi ∈ (0, 1]. In addition, H-SGD relies on the availability of an approximate solution w0 for the source problem with λ0 = 0 as starting point. We use wi to denote the derived approximate solution for the problem associated with parameter λi that is obtained by applying k > 0 iterations of SGD starting from the previously derived approximate solution for the problem with parameter λi−1, ∀i = 1, . . . , n. Notice that wi−1,t = wi−1,t(ξ[i−1,t−1]) for t = 1, . . . , k with wi−1,k = wi(ξ[i]) is used to refer to the random vector generated at the i-th homotopy iteration after t iterations of SGD, where ξ[i−1,t−1] = (w0, ξ10 , . . . , ξ 1 k−1, . . . , ξ i−1 0 , . . . , ξ i−1 k−1, ξ i 0, . . . , ξ i t−1) and ξ[i] = (w0, ξ 1 0 , . . . , ξ 1 k−1, . . . , ξ i−1 0 , . . . , ξ i−1 k−1, ξ i 0, . . . , ξ i k−1) with ξ[0] = w0 are used to refer to the collection of all random sources up to the current iteration. We use U∗(λ) to denote the set of local (and global) minimizers of the parametric Problem 1.

heading: 3.1 ASSUMPTIONS

text:
We now list and discuss the assumptions that we consider throughout our analysis. Together with the standard smoothness and bounded variance assumptions, we also introduce three regularity
assumptions, which describe the localization of the solution map and how the objective function f changes by varying the homotopy parameter across iterations. In addition to these assumptions, we also consider a more general and local version of the standard PL condition.Consequently, unlike the settings considered in (Karimi et al., 2016) and (Vaswani et al., 2019), where the standard PL condition is unrealistically required to hold globally, ours is often encountered in many different non-convex scenarios (see Karimi et al., 2017, for more details).
Assumption 3.1 (existence of a regular localization of the solution map). Assume there exists a set Ω ⊆ Rd × [0, 1]z such that W ∗(λ) := Ω ∩ U∗(λ) and Σ := { (y, λ) ∈ Rd × [0, 1]z | y ∈W ∗(λ) } are both non-empty and connected. Moreover, we assume that for a given λ all the points in W ∗(λ) are associated with the same objective function value, which we denote as f∗(λ) := f(y, λ) for all y ∈W ∗(λ).
Notice that Assumption 3.1 does not imply vector-valued solutions of the parametric Problem 1.
Assumption 3.2 (regularity 1). Assume there exists δ > 0 such that
|f(w, λ̃)− f(w, λ̂)| ≤ δ‖λ̃− λ̂‖, ∀w ∈ Rd, ∀λ̃, λ̂ ∈ [0, 1]z . (5)
Assumption 3.3 (regularity 2). Assume there exists γ > 0 such that
|f∗(λ̃)− f∗(λ̂)| ≤ γ‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (6)
Assumption 3.4 (L-smoothness). Assume there exists L > 0 such that
‖∇wf(w̃, λ)−∇wf(ŵ, λ)‖ ≤ L ‖w̃ − ŵ‖, ∀w̃, ŵ ∈ Rd, ∀λ ∈ [0, 1]z . (7)
See Remark C.1 in Section C of the Appendix for more details on Assumptions 3.2 and 3.3.
Assumption 3.5 (bounded “variance”). Consider f(w, λ) with λ ∈ [0, 1]z and let g(w, ξ, λ) be the stochastic estimate of the true gradient∇wf(w, λ) used in SGD with noise ξ. Assume that
Eξ [g(w, ξ, λ)] = ∇wf(w, λ), ∀w ∈ Rd, ∀λ ∈ [0, 1]z. (8)
and that there exists σ2 ≥ 0 such that Eξ [ ‖g(w, ξ, λ)−∇wf(w, λ)‖2 ] ≤ σ2, ∀w ∈ Rd, ∀λ ∈ [0, 1]z. (9)
Assumption 3.6 (“expected” PL condition). Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate that is obtained at the i-th homotopy iteration after t iterations of SGD with t ≤ k. Assume that there exist B > σ 2
2µ and µ > 0 such that, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f∗(λi) ≤ B, then
Eξ[i−1,t−1] [ ‖∇wf(wi−1,t, λi)‖2 ] ≥ 2µ · [ Eξ[i−1,t−1] [f(wi−1,t, λi)]− f ∗(λi) ] . (10)
See Remark C.2 for additional details on Assumption 3.6.

heading: 3.2 FUNDAMENTAL THEORETICAL PRELIMINARIES

text:
Before proceeding with the main theoretical contributions, we revise and adjust the existing results in the literature on global error bounds of SGD, i.e. (Vaswani et al., 2019), to also hold in the considered setting. The extended results are then used for the derivations in Section 3.3 and 3.4.
Proposition 3.7. Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate obtained at the i-th homotopy iteration by applying t iterations of SGD with t ≤ k − 1 and α ≤ 1L . Under Assumptions 3.1 and 3.4-3.6, if Eξ[i−1,t−1] [f(wi−1,t, λi)] − f
∗(λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.
Proof. See Section D in the Appendix for a proof.
Theorem 3.8. Consider the minimization of f(w, λi) with λi ∈ [0, 1]z via SGD. Let wi−1 = wi−1(ξ[i−1]) be the random initial point associated with the i-th homotopy iteration with
Eξ[i−1] [f(wi−1, λi)] − f∗(λi) ≤ B and wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the t-th SGD iterate with t ≤ k. Under Assumptions 3.1 and 3.4-3.6, SGD with a constant step-size α ≤ 1L attains the following convergence rate to a minimizer’s neighborhood
Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤ ρtEξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
2µ , (11)
with ρ := (1− αµ). With α = 1L , we obtain ρ = ( 1− µL ) .
Proof. See Section E in the Appendix for a proof.

heading: 3.3 OPTIMALITY TRACKING

text:
In the following, we define the function φv(λi) := Ev [f(v, λi)]− f∗(λi) where v is d-dimensional real random vector. As in (Gargiani et al., 2020) but in a more relaxed setting, i.e. local PL in place of local strong-convexity, we study the optimality tracking properties of H-SGD. In particular, under the considered assumptions and by exploiting the previously introduced results on the convergence of SGD, with Theorem 3.10 we characterize the maximum allowed variation of the homotopy parameter across homotopy iterations of H-SGD such that, if φwi(λi) ≤ r, then also φwi+1(λi+1) ≤ r. The upper bound that we derive depends on the number of iterations k performed with SGD as well as on the convergence characteristics of SGD and the structural properties of the parametric problems. This result applied recursively across homotopy iterations leads to conclude that, if we adopt a “small enough” increasing step for the homotopy parameter, H-SGD can track in expectation an r-optimal solution from source to target problem.
Before proceeding with the actual optimality tracking analysis (Theorem 3.10), we study the conditions on wi and ∆λi+1 such that φwi(λi+1) ≤ B, where wi is the approximate solution of the problem associated with parameter λi that is also used as starting point for the next parametric problem. Lemma 3.9. Assume ‖λi+1 − λi‖ ≤ , 0 ≤ < Bδ+γ and let wi denote the i-th iterate of Algorithm 1 with α ≤ 1L . Under Assumptions 3.1- 3.3 and 3.4- 3.6, if φwi(λi) ≤ B − (δ + γ) ,
then φwi(λi+1) ≤ B. In addition, let kmax := ⌈ logρ ( 1− 2µ(δ+γ) +σ 2
2µB
)⌉ . If φwi(λi+1) ≤ B,
0 ≤ < 1δ+γ ( B − σ 2 2µ ) and k ≥ kmax, then φwi+1(λi+1) ≤ B − (δ + γ) .
Proof. See Section F in the Appendix for a proof.
Theorem 3.10. Assume there exists σ 2
2µ < r ≤ B and ̃ := min { 1, 2} with
1 := 1
(δ + γ) (B − r), 2 := (1− ρk) r − σ2/2µ ρk (δ + γ) . (12)
In addition, let kmax := ⌈ logρ ( 1− σ 2
2µr )⌉ . Consider Algorithm 1 with α ≤ 1L , k ≥ kmax and
‖λi+1 − λi‖ ≤ , where 0 ≤ ≤ ̃. Under Assumptions 3.1- 3.3 and 3.4- 3.6, if φwi(λi) ≤ r, then φwi+1(λi+1) ≤ r.
Proof. See Section G in the Appendix for a proof.
See Figure 2 in Section B of the Appendix for a graphical representation of the derived results.

heading: 3.4 LINEAR CONVERGENCE RATE

text:
We now study the convergence rate of H-SGD and, in particular, if it is possible to recover a global linear rate of convergence to a minimizer’s neighborhood. The results derived in Theorem 3.11 confirm that, in the considered setting and with a specifically designed schedule for the homotopy parameter, H-SGD achieves the desired rate of convergence.
Theorem 3.11. Let ρ̃ ∈ ( 1− σ 2
2µ 1 B , 1 ) and consider Algorithm 1 with α ≤ 1L , φw0(λ0) ≤ r with
σ2 2µ 1 (1−ρ̃) ≤ r ≤ B and k ≥ logρ(ρ̃). In addition, let 1 := 1 (δ+γ) (B − r) and
Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
(13)
with ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). Under Assumptions 3.1- 3.3 and 3.4- 3.6, if ‖λi+1 − λi‖ ≤ min { e−η i, 1 } with η ≥ ln (Cρ̃ ρ̃), then
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
2µ i∑ j=0 ρ̃j . (14)
Proof. See Section H in the Appendix for a proof.

heading: 4 EXPERIMENTAL EVALUATION

text: In this section, we empirically validate the theoretical results derived in Theorem 3.11. First, we consider a 1-dimensional toy regression problem to illustrate and visualize some of the basic properties of H-SGD. In this easy scenario, the introduced assumptions can be trivially verified by inspection (see the Figures 3- 4 in the Appendix). We then move to more complex and high-dimensional scenarios where the assumptions can not be verified. Inspired by Finn et al. (2017) and Gargiani et al. (2020), we consider the task of regressing with a neural network from input to output of a sinusoidal wave. Finally, we also consider a non-convex classification task based on the combination of logistic regression with a non-linear model for moon-shaped binary data (Chapelle et al., 2006). In all the considered scenarios, we compare the numerical performance of H-SGD with those of SGD and tune the step-size based on the performance of the latter.

heading: 4.1 TOY-PROBLEM

text:
We start with an easy regression problem motivated by Mobahi (2016): a 1-dimensional neural network with erf as activation function (see Figure 9 in Section B of the Appendix for a graphical representation). We generate a synthetic dataset of N = 100 samples, where xj ∈ [−1, 1], yj = 3 · xj + j and j ∼ N (0, 1). Regarding the choice of a value for the step-size, we use an estimate L̃ of the smoothness constant L and set α = 1/L̃. As loss, we use the mean squared error, which, composed with the regressing model, leads to the following non-convex optimization problem
w∗ = arg min w∈R
1
N N∑ j=1 (yj − erf(w · xj))2 . (15)
By plotting the objective function with respect to w (see Fig. 3 in Section B of the Appendix), it is easy to observe that the PL condition holds globally, with the value of µ increasing by approaching the minimizer and µ→ 0 for w → ±∞ (see Fig. 4 in the Appendix). Consequently, SGD enjoys a global linear convergence rate as proved in (Vaswani et al., 2019) but the rate itself, which depends on the value of µ, will dramatically worsen the further the iterates are from the minimizer, leading to a great overall sensitivity of the method in terms of convergence rate to the initialization. On the other side, H-SGD, thanks to the homotopy principle, goes around that issue by preserving the vicinity to the minimizer of the current homotopy problem at each homotopy iteration (see Figures 7 and 8 in Section B of the Appendix). In order to achieve that, given w0 as initial value, we set yj,0 = w0 · xj for all j = 1, . . . , N and define the following homotopy transformation
yj, λ = λ yj + (1− λ) yj, 0 . (16) As suggested by the theory (see Theorem 3.11), we select an exponentially decreasing scheme for the increment ∆λi in order to achieve linear convergence. As shown in Figure 5 in the Appendix, both H-SGD and SGD enjoy a linear rate of convergence, but H-SGD shows a superior numerical performance. This is due to the fact that the method is designed such that its iterates always lie in the neighborhood of the minimizers where more favorable values of µ lead to a faster convergence. This fact allows H-SGD to enjoy a faster global convergence rate than that of SGD.

heading: 4.2 REGRESSION WITH DEEP NEURAL NETWORKS

text: Our second experiment is inspired by Finn et al. (2017) and Gargiani et al. (2020) and focuses on studying the numerical performance of H-SGD on the task of regressing from input to output of a sinusoidal function corrupted by Gaussian noise. In particular, the input data are sampled uniformly from the interval [−1, 1] and yj = sin(10 · xj) + j with j ∼ N (0, 0.1) for all j = 1, . . . , 500. The regressor is a feedforward neural network with two hidden layers, each of 10 units, and hyperbolic tangent as activation function. As for the previous benchmark, we use the mean squared error as loss. We employ the same values of step-size α and mini-batch M for both H-SGD and SGD, where the step-size value is tuned based on the numerical performance of SGD for the selected mini-batch size (M = 5). Regarding H-SGD, we set yj,0 = x2j + j with j ∼ N (0, 0.01) and employ the same homotopy mapping as in Equation 16. As shown in Figure 6 in the Appendix, also in this scenario H-SGD shows a superior numerical performance than SGD, i.e. H-SGD reaches a loss of 10−1 roughly 4 times faster and achieves convergence more than 2 times faster than SGD. The superior numerical performance of H-SGD can be attributed to its ability of tracking a solution across homotopy iterations (see Figure 10 in the Appendix) which ensures the method to always work in the vicinity of a minimizer.

heading: 4.3 NON-LINEAR BINARY CLASSIFICATION WITH LOGISTIC REGRESSION

text:
Finally, we test H-SGD also on a classification benchmark with a logistic regression task. In particular, we use a 2-dimensional binary moon-shaped dataset (Chapelle et al., 2006) with 1000 samples corrupted by Gaussian noise. As the dataset is clearly not linearly separable, we opt for a cubic model, which, used in combination with the logistic regression framework, leads to a non-convex objective function where the optimization variable w is the collection of the model’s coefficients. For both H-SGD and SGD we use a mini-batch size of 20 and tune the value of the step-size on the SGD’s performance for that mini-batch size. Regarding H-SGD, we use as source task the one obtained considering a linear instead of a cubic model, which results in a convex and hence “easy” optimization problem. We then gradually increase the non-linearity of the model, i.e. non-convexity of the problem, until reaching in the final homotopy iteration the target problem with the desired cubic model. This homotopy map is obtained by multiplying the coefficients of the non-linear terms in the model by λ as follows
λ(c1 x 3 j,1 + c2 x 3 j,2 + c3 x 2 j,1 + c4 x 2 j,2 + c5 x 2 j,1 xj,2 + c6 xj,1 x 2 j,2) + c7 xj,1 + c8 xj,2 + c9 . (17)
For the homotopy parameter we adopt the increasing schedule that is suggested in Theorem 3.11. H-SGD outperforms SGD by reaching an error of 0.1 more than two times faster than SGD (see Figure 11 in the Appendix).

heading: 5 CONCLUSIONS AND FUTURE WORK

text: In this paper we propose a new first-order stochastic method for non-convex large-scale problems, called Homotopy-SGD (H-SGD), based on the combination of homotopy methods and SGD. This new homotopy-based optimization method allows one to exploit easy-to-solve or already-solved problems to solve new and complex ones. This is achieved by approximately and sequentially solving a sequence of optimization problems where the source problem is gradually morphed via a homotopy map into the target one. We conduct a theoretical analysis of the optimality tracking properties and convergence rate of H-SGD under some realistic and mild assumptions. The theoretical results are confirmed by some empirical evaluations, which also show the great potential in terms of performance of combining SGD with an homotopy strategy. In addition, H-SGD shows interesting connections with many practical existing heuristics proposed in the machine learning literature to speed up the convergence of first-order methods, allowing for a new and more rigorous interpretation of the latter. The current major limitation of the method relies in the design of the homotopy map. Future work should focus on exploiting the specific problem structure to design optimal homotopy maps. Moreover, under additional assumptions, more theoretical results concerning the quality of the tracked solutions could be derived.

heading: ACKNOWLEDGMENTS

heading: B ADDITIONAL FIGURES

heading: A APPENDIX

heading: C ADDITIONAL REMARKS

text:
Remark C.1. Assumption 3.2 can be read as a local Lipschitz continuity of f with respect to its second argument. Regarding the second regularity assumption (Assumption 3.3), equation 6 relates the variation of the optimal objective function value for the subset of solutions introduced in Assumption 3.1 across homotopy iterations with the variations of the homotopy parameter. When the solution localization of the solution map is vector-valued, i.e. w∗(λ) ≡W ∗(λ) (this is the case for instance when the Hessian of the objective function is positive definite at those points), this assumption can also be derived directly by combining Assumption 3.2 with the following Lipschitz continuity requirements:
• Let κ1 > 0, we assume that
|f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ κ1‖w∗(λ̃)− w∗(λ̂)‖, ∀λ̃, λ̂ ∈ [0, 1]z . (18)
• Let κ2 > 0, we assume that
‖w∗(λ̃)− w∗(λ̂)‖ ≤ κ2‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (19)
In particular, by combining Inequalities equation 18 and equation 19, we obtain
|f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ κ2 κ1‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (20) To recover Inequality equation 6 where γ := δ+κ1 κ2, we use Inequalities equation 5 and equation 20 together with the triangle inequality as follows
|f(w∗(λ̃), λ̃)− f(w∗(λ̂), λ̂)| = |f(w∗(λ̃), λ̃)− f(w∗(λ̃), λ̂) + f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ |f(w∗(λ̃), λ̃)− f(w∗(λ̃), λ̂)|+ |f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ (δ + κ1κ2)‖λ̃− λ̂‖ .
(21)
Notice that the Assumption in equation 18 is a less restrictive condition of the following general Lipschitz continuity requirement
|f(v, λ̂)− f(w, λ̂)| ≤ C‖v − w‖, ∀v, w ∈ Rd, ∀λ̂ ∈ [0, 1]z , (22)
where C > 0. Remark C.2. Assumption 3.6 is a more general version of the classical PL condition (see Section 2 Karimi et al., 2016, for more details on the classical PL condition). In particular, it is straightforward to observe that the classical PL condition implies Assumption 3.6, but not vice versa. See Figure 1 in Section B of the Appendix for a graphical representation of a one dimensional example with wi−1,t ∼ N (0, 1) where Assumption 3.6 holds, while the classical PL condition does not. The expected value operates a smoothing of the function landscape resulting in convexity, while the original function shows many bumps that make it non-convex.

heading: D PROOF OF PROPOSITION 3.7

text:
Proposition D.1. Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate obtained at the i-th homotopy iteration by applying t iterations of SGD with t ≤ k − 1 and α ≤ 1L . Under Assumptions 3.4, 3.5 and 3.6, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f
∗(λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.
Proof. For ease of notation, we use the shorthands wi−1,t = wi−1,t(ξ[i−1,t−1]) and gt = g(wi−1,t, ξ i t, λi).
Considering Assumption 3.4 together with the definition of SGD iterate and using Assumptions 3.5 and 3.6, we obtain the following inequalities
Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t] [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2
2 ‖gt‖2 ] Law of Iterated Exp.
= Eξ[i−1,t−1] [ Eξit [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2 2 ‖gt‖2 ∣∣∣ξ[i−1,t−1]]] Assumption 3.5
≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α+ Lα 2
2
) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
2 .
If α ≤ 1L , then
Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α
2
) ‖∇f(wi−1,t λi)‖2 ] + Lα2σ2
2 .
(23)
We now make use of the “expected” PL condition and derive the following inequalities
Eξ[i−1,t] [f(wi−1,t+1, λi)− f(wi−1,t, λi)] ≤ − α
2 Eξ[i−1,t−1]
[ ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
2 Assumption 3.6 ≤ −αµ [ Eξ[i−1,t−1] [f(wi−1,t, λi)]− f ∗(λi) ] + Lα2σ2
2 .
(24)
From Inequality equation 24 it follows that, whenever Eξ[i−1,t−1] [f(wi−1,t, λi)] − f∗(λi) ≥ σ 2
2µ , the objective function decreases in expectation, i.e. Eξ[i−1,t] [f(wi−1,t+1, λi)− f(wi−1,t, λi)] ≤ 0. Given that by assumptionB > σ 2
2µ , we can consequently conclude that, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f(w∗i , λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.

heading: E PROOF OF THEOREM 3.8

text:
Theorem E.1. Consider the minimization of f(w, λi) with λi ∈ [0, 1]z via SGD. Let wi−1 = wi−1(ξ[i−1]) be the random initial point associated with the i-th homotopy iteration with
Eξ[i−1] [f(wi−1, λi)] − f∗(λi) ≤ B and wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the t-th SGD iterate with t ≤ k. Under Assumptions 3.4, 3.5 and 3.6, SGD with a constant step-size α ≤ 1L attains the following convergence rate to a minimizer’s neighborhood
Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤ ρtEξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
2µ , (25)
with ρ := (1− αµ). With α = 1L , we obtain ρ = ( 1− µL ) .
Proof. For ease of notation, we use the shorthands wi−1,t = wi−1,t(ξ[i−1,t−1]) and gt = g(wi−1,t, ξ i t, λi).
By combining Assumption 3.4 with the definition of SGD iterate, for all t = 1, . . . , k − 1, we obtain the following bound on f(wt+1, λi)
f(wi−1,t+1, λi) ≤ f(wi−1,t, λi) + 〈∇f(wi−1,t, λi), wi−1,t+1 − wi−1,t〉+ L
2 ‖wi−1,t+1 − wi−1,t‖2
wi−1,t+1:=wi−1,t−αgt = f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+
Lα2
2 ‖gt‖2 .
We now take the expectation with respect to all the sources of randomness involved and then we apply the law of iterated expectations, together with Assumption 3.5
Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t] [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2
2 ‖gt‖2 ] Law of Iterated Exp.
= Eξ[i−1,t−1] [ Eξit [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2 2 ‖gt‖2 ∣∣∣ξ[i−1,t−1]]] Assumption 3.5 ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α+ Lα 2
2
) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
2 .
If α ≤ 1L , then
Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α
2
) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
2 .
(26)
We now apply the PL condition to Inequality equation 26, and we obtain
Eξ[i−1,t] [f(wi−1,t+1, λi)] Assumption 3.6 ≤ Eξ[i−1,t−1] [f(wi−1,t, λi)
−αµ( f(wi−1,t, λi)− f∗(λi) )] + Lα2σ2
2 .
(27)
By subtracting f∗(λi) on both sides and setting α = 1L , we obtain the following inequality
Eξ[i−1,t] [f(wi−1,t+1, λi)− f ∗(λi)] ≤
( 1− µ
L
) Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] + σ2
2L .
(28)
By applying Inequality equation 28 recursively, we derive the following bound
Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤
( 1− µ
L
)k Eξ[i−1] [f(wi−1, λi)− f ∗(λi)]
+ σ2
2L k−1∑ j=0 ( 1− µ L )j .
(29)
Finally, by using the limit of geometric series, we obtain
Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤
( 1− µ
L
)k Eξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
2µ . (30)

heading: F PROOF OF LEMMA 3.9

text:
Lemma F.1. Assume ‖λi+1−λi‖ ≤ , 0 ≤ < Bδ+γ and let wi denote the i-th iterate of Algorithm 1 with α ≤ 1L . Under Assumptions 3.4- 3.3 and 3.5- 3.6, if φwi(λi) ≤ B− (δ+γ) , then φwi(λi+1) ≤ B. In addition, let
kmax := ⌈ logρ ( 1− 2µ(δ + γ) + σ 2
2µB
)⌉ . (31)
If φwi(λi+1) ≤ B, 0 ≤ < 1δ+γ ( B − σ 2 2µ ) and k ≥ kmax, then φwi+1(λi+1) ≤ B − (δ + γ) .
Proof. We start by deriving an upper bound on Eξ[i] [f(wi, λi+1)] − f∗(λi+1) with φwi(λi) ≤ B and ‖λi+1 − λi‖ ≤ . For that we use the regularity Assumptions 3.2 and 3.3 together with the triangle and Jensen inequalities as follows
Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) = |Eξ[i] [f(wi, λi+1)]− f ∗(λi+1)|
= |Eξ[i] [f(wi, λi+1) + f(wi, λi)− f(wi, λi)]− f ∗(λi+1)
+ f∗(λi)− f∗(λi)| Triangle and Jensen Ineq.
≤ |Eξ[i] [f(wi, λi)]− f ∗(λi)|+ Eξ[i] [|f(wi, λi+1)− f(wi, λi)|]
+ |f∗(λi)− f∗(λi+1)| Assumptions 3.2 and 3.3
≤ |Eξ[i] [f(wi, λi)]− f ∗(λi)|+ (δ + γ) .
(32)
From Inequality equation 32 it follows that, if φwi(λi) ≤ B − (δ + γ) with < B(δ+γ) , then φwi(λi+1) ≤ B. We now use the results of Theorem 3.8 to derive a lower bound on the number of SGD-steps such that, if φwi(λi+1) ≤ B, then φwi+1(λi+1) ≤ B − (δ + γ) . We start considering the following inequality
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) ] + σ2
2µ
≤ ρkB + σ 2
2µ .
(33)
From Inequality equation 33 it follows that, if φwi(λi+1) ≤ B, then φwi+1(λi+1) ≤ B − (δ + γ) with < 1δ+γ ( B − σ 2 2µ ) whenever
k ≥ ⌈ logρ ( 1− 2µ(δ + γ) + σ 2
2µB
)⌉ . (34)

heading: G PROOF OF THEOREM 3.10

text:
Theorem G.1. Assume there exists σ 2
2µ < r ≤ B and ̃ := min { 1, 2} with
1 := 1
(δ + γ) (B − r), 2 := (1− ρk) r − σ2/2µ ρk (δ + γ) . (35)
In addition, let
kmax := ⌈ logρ ( 1− σ 2
2µr
)⌉ . (36)
Consider Algorithm 1 with α ≤ 1L , k ≥ kmax and ‖λi+1 − λi‖ ≤ , where 0 ≤ ≤ ̃. Under Assumptions 3.4- 3.3 and 3.5- 3.6, if φwi(λi) ≤ r, then φwi+1(λi+1) ≤ r.
Proof. We consider φwi(λi) ≤ r. If ≤ 1(δ+γ) (B − r) with r ≤ B, then φwi(λi) ≤ B − (δ + γ) and, as shown in Lemma 3.9, φwi(λi+1) ≤ B. This allows us to use the results of Theorem 3.8. We now derive an upper bound on Eξ[i+1] [f(wi+1, λi+1)] − f∗(λi+1) by considering the results of Theorem 3.8 together with the regularity Assumptions 3.2 and 3.3, and the triangle and Jensen inequalities as follows
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) ] + σ2
2µ = ρk ∣∣∣Eξ[i] [f(wi, λi+1) + f(wi, λi)− f(wi, λi)]− f∗(λi+1)
+ f∗(λi)− f∗(λi) ∣∣∣+ σ2
2µ Triangle and Jensen Ineq. ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρkEξ[i] [|f(wi, λi+1)− f(wi, λi)|]
+ ρk|f∗(λi)− f∗(λi+1)|+ σ2
2µ Assumptions 3.2 and 3.3 ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρk(δ + γ)‖λi+1 − λi‖+ σ2
2µ .
(37)
Using the fact that φwi(λi) ≤ r and that ‖λi+1−λi‖ ≤ , we now solve the following inequality for in order to find an upper bound on the variation of the homotopy parameter such that φwi+1(λi+1) ≤ r
ρk r + ρk (δ + γ) + σ2
2µ ≤ r . (38)
Inequality equation 38 holds whenever
k ≥ ⌈ logρ ( 1− σ 2
2µr
)⌉ , (39)
and
≤ (1− ρ k) r − σ2/2µ
ρk (δ + γ) , (40)
with r > σ 2
2µ .

heading: H PROOF OF THEOREM 3.11

text:
Theorem H.1. Let ρ̃ ∈ ( 1− σ 2
2µ 1 B , 1 ) and consider Algorithm 1 with α ≤ 1L , φw0(λ0) ≤ r with
σ2 2µ 1 (1−ρ̃) ≤ r ≤ B and k ≥ logρ(ρ̃). In addition, let 1 := 1 (δ+γ) (B − r) and
Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
(41)
with ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). Under Assumptions 3.4- 3.3 and 3.5- 3.6, if ‖λi+1 − λi‖ ≤ min { e−η i, 1 } with η ≥ ln (Cρ̃ ρ̃), then
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
2µ i∑ j=0 ρ̃j . (42)
Proof. We start assuming that φwi(λi) ≤ r, with 0 ≤ r ≤ B and ‖λi+1 − λi‖ ≤ 1 with 1 := 1 (δ+γ) (B − r) such that φwi(λi+1) ≤ B.
In particular, we consider the following upper bound on Eξ[i+1] [f(wi+1, λi+1)]− f∗(λi+1),
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ]
+ ρk (δ + γ) ∆λi+1 + σ2
2µ .
(43)
See the the proof of Theorem 3.10 for a derivation.
We then proceed by induction. Therefore, we assume
Eξ[i] [f(wi, λi)]− f ∗(λi) ≤ ρ̃i [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
2µ i−1∑ j=0 ρ̃j , (44)
and derive the conditions on ∆λi+1 such that
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
2µ i∑ j=0 ρ̃j . (45)
In order to achieve that, we consider the upper bound on Eξ[i+1] [f(wi+1, λi+1)]− f∗(λi+1) given by Inequality equation 43 and solve the following inequality for ∆λi+1
ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρk (δ + γ) ∆λi+1 + σ2
2µ
≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
2µ i∑ j=0 ρ̃j .
(46)
We obtain that Inequality equation 46 is satisfied whenever
∆λi+1 ≤ ρ̃i+1
[ Eξ[0] [f(w0, λ0)] − f ∗(λ0) ] − ρk [ Eξ[i] [f(wi, λi)] − f ∗(λi) ] + σ 2 2µ ∑i j=1 ρ̃ j
ρk(δ + γ)︸ ︷︷ ︸ RHS
. (47)
We derive a lower bound on the right-had side of equation 47 by considering the induction assumption, i.e. Inequality equation 44, and we obtain
RHS ≥ ρ̃i ( ρ̃− ρk ) [ Eξ[0] [f(w0, λ0)]− f∗(λ0) ] − σ 2 2µρ k ∑i−1 j=0 ρ̃ j + σ 2 2µ ∑i j=1 ρ̃ j
ρk(δ + γ) . (48)
Considering that k ≥ logρ(ρ̃) then
− σ 2
2µ ρk i−1∑ j=0 ρ̃j + σ2 2µ i∑ j=1 ρ̃j = σ2 2µ ( 1− ρ k ρ̃ ) i−1∑ j=0 ρ̃j ≥ 0 . (49)
Consequently, Inequality equation 47 is satisfied whenever ∆λi+1 ≤ ( ρ̃− ρk ) ρk ε0 (δ + γ) ρ̃i , (50)
where ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). To conclude this first part of derivations, we obtain that, whenever Inequality equation 50 is satisfied, then
Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 ( Eξ[0] [f(w0, λ0)]− f ∗(λ0) ) + σ2
2µ i∑ j=0 ρ̃j . (51)
In order to ensure that φwi+1(λi+1) ≤ r we consider Inequality equation 51 and use the fact that φw0(λ0) ≤ r, i.e. Eξ[0] [f(w0, λ0)] − f∗(λ0) ≤ r, to upper bound the right-hand side of Inequality equation 51. We then solve the resulting inequality for r
ρ̃i+1r + σ2
2µ i∑ j=0 ρ̃j ≤ r . (52)
Considering that ∑i j=0 ρ̃ j = (1−ρ̃i+1) (1−ρ̃) , we obtain that Inequality equation 52 is satisfied whenever
r ≥ σ 2
2µ
1
(1− ρ̃) . (53)
By combining Inequality equation 53 with the fact that r ≤ B, we obtain the following upper bound on ρ̃
ρ̃ ≤ 1− σ 2
2µ
1 B . (54)
To further simplify the bound in equation 50, we define the following constant
Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
(55)
and obtain that Inequality equation 50 holds whenever ∆λi+1 ≤ e−η i with η ≥ − ln (Cρ̃ ρ̃).