summaries: This work develops an analog to Thompson sampling by upper-bounding the expected regret in sequential decision-making problems. The two terms in the upper bound loosely resemble the evidence lower bound of variational inference: the first term encourages selecting arms with high expected reward; the second term depends on the inverse of the rate function and penalizes heavy tails and encourages exploration. The resulting variational Thompson sampling algorithm is evaluated on a random game and a constrained bandit problem.

summaries: This paper introduces Variational Thompson Sampling, where rather than sampling from the posterior, which can be infeasible, a computationally tractable upper bound is optimized.  In the stochastic multi-armed bandit setting with subgaussian noise, they provide a general analysis for any algorithm that plays a "stochastically optimistic" policy, which includes vanilla TS and the new method.  The VTS algorithm is shown to have sublinear regret for the more challenging bilinear saddle point problems where it can be shown that TS fails.

summaries: This paper proposes a novel class of policies for online learning, named variational Thompson sampling (VTS). VTS is derived from a family of stochastically optimistic policies, which includes standard TS as a special case. VTS is amenable to some interesting interpretations when compared with difference existing policies such as UCB and K-learning, and is shown to outperform TS consistently in two classes of problems, i.e., zero-sum two player games and constrained bandits.

summaries: This paper presents and establishes regret bounds for a new heuristic, inspired by Thompson sampling, for selecting actions in stochastic multi-arm bandit and bilinear saddle-point problems. As in Thompson sampling, a belief state is maintained over the values of each arm. However, instead of selecting an action according to its probability of optimality, one instead computes a policy (distribution over actions) that maximizes a novel objective. The objective can be understood as combining a "pure exploitation" term (the expected reward of the policy, under the current belief distribution), and an "exploration" term that depends only on the relative concentrations (and not the expected values) of the posteriors for each arm.

abstractText: We consider online sequential decision problems where an agent must balance exploration and exploitation. We derive a set of Bayesian ‘optimistic’ policies which, in the stochastic multi-armed bandit case, includes the Thompson sampling policy. We provide a new analysis showing that any algorithm producing policies in the optimistic set enjoys Õ( √ AT ) Bayesian regret for a problem with A actions after T rounds. We extend the regret analysis for optimistic policies to bilinear saddle-point problems which include zero-sum matrix games and constrained bandits as special cases. In this case we show that Thompson sampling can produce policies outside of the optimistic set and suffer linear regret in some instances. Finding a policy inside the optimistic set amounts to solving a convex optimization problem and we call the resulting algorithm ‘variational Bayesian optimistic sampling’ (VBOS). The procedure works for any posteriors, i.e., it does not require the posterior to have any special properties, such as log-concavity, unimodality, or smoothness. The variational view of the problem has many useful properties, including the ability to tune the exploration-exploitation tradeoff, add regularization, incorporate constraints, and linearly parameterize the policy.

authors:
S. Agrawal
N. Goyal

title: Analysis of Thompson sampling for the multi-armed bandit problem

venue: Conference on learning theory, pages 39–1,

authors:
P. Auer
N. Cesa-Bianchi
P. Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine learning, 47(2-3):235–256,

authors:
P. Auer
N. Cesa-Bianchi
Y. Freund
R.E. Schapire

title: The nonstochastic multiarmed bandit problem

venue: SIAM journal on computing, 32(1):48–77,

authors:
S. Boyd
L. Vandenberghe

title: Convex optimization

venue: Cambridge university press,

authors:
N. Cesa-Bianchi
G. Lugosi

title: Prediction, learning, and games

authors:
O. Chapelle
L. Li

title: An empirical evaluation of Thompson sampling

venue: Advances in neural information processing systems, pages 2249–2257,

title: The theory of max-min and its application to weapons allocation problems, volume 5

venue: Springer Science & Business Media,

authors:
A. Fuchs
G. Letta

title: L’inégalité de Kullback

venue: application à la théorie de l’estimation. Séminaire de probabilités de Strasbourg, 4:108–131,

authors:
A. Garivier
O. Cappé

title: The kl-ucb algorithm for bounded stochastic bandits and beyond

venue: Proceedings of the 24th annual conference on learning theory, pages 359–376. JMLR Workshop and Conference Proceedings,

authors:
M. Ghavamzadeh
S. Mannor
J. Pineau
A. Tamar

title: Bayesian reinforcement learning: A survey

venue: Foundations and Trends R © in Machine Learning, 8(5-6):359–483,

title: Entropy and information theory

authors:
T. Haarnoja
H. Tang
P. Abbeel
S. Levine

title: Reinforcement learning with deep energybased policies

venue: International Conference on Machine Learning, pages 1352–1361. PMLR,

title: python-ternary: Ternary plots in python

title: A note on KL-UCB+ policy for the stochastic bandit

venue: arXiv preprint arXiv:1903.07839,

title: The theory of dispersion models

venue: CRC Press,

authors:
E. Kaufmann
O. Cappé
A. Garivier

title: On Bayesian upper confidence bounds for bandit problems

venue: Artificial Intelligence and Statistics, pages 592–600,

title: Adaptive treatment allocation and the multi-armed bandit problem

venue: The Annals of Statistics, pages 1091–1114,

authors:
T.L. Lai
H. Robbins

title: Asymptotically efficient adaptive allocation rules

venue: Advances in applied mathematics, 6(1):4–22,

authors:
T. Lattimore
C. Szepesvári

title: Bandit algorithms

venue: Cambridge University Press,

title: Reinforcement learning and control as probabilistic inference: Tutorial and review

venue: arXiv preprint arXiv:1805.00909,

authors:
J.T. Lewis
R. Russell

title: An introduction to large deviations for teletraffic engineers

authors:
E. Mazumdar
A. Pacchiano
Y.-a. Ma
P.L. Bartlett
M.I. Jordan

title: On Thompson sampling with Langevin algorithms

venue: arXiv preprint arXiv:2002.10002,

title: Variational Bayesian reinforcement learning with regret bounds

venue: arXiv preprint arXiv:1807.09647,

title: Operator splitting for a homogeneous embedding of the linear complementarity problem

venue: SIAM Journal on Optimization,

authors:
B. O’Donoghue
E. Chu
N. Parikh
S. Boyd

title: Conic optimization via operator splitting and homogeneous self-dual embedding

venue: Journal of Optimization Theory and Applications,

title: SCS: Splitting conic solver, version 2.1.0

authors:
B. O’Donoghue
T. Lattimore
I. Osband

title: Stochastic matrix games with bandit feedback

venue: arXiv preprint arXiv:2006.05145,

authors:
B. O’Donoghue
R. Munos
K. Kavukcuoglu
V. Mnih

title: Combining policy gradient and Q-learning

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

authors:
B. O’Donoghue
I. Osband
C. Ionescu

title: Making sense of reinforcement learning and probabilistic inference

authors:
I. Osband
D. Russo
B. Van Roy

title: More) efficient reinforcement learning via posterior sampling

venue: Advances in Neural Information Processing Systems, pages 3003–3011,

authors:
I. Osband
B. Van Roy

title: Why is posterior sampling better than optimism for reinforcement learning

venue: Proceedings of the 34th International Conference on Machine Learning (ICML),

authors:
M. Phan
Y.A. Yadkori
J. Domke

title: Thompson sampling and approximate inference

venue: Advances in Neural Information Processing Systems, pages 8801–8811,

authors:
P.H. Richemond
B. Maginnis

title: A short variational proof of equivalence between policy gradients and soft Q-learning

venue: arXiv preprint arXiv:1712.08650,

authors:
D. Russo
B. Van Roy

title: An information-theoretic analysis of Thompson sampling

venue: The Journal of Machine Learning Research, 17(1):2442–2471,

authors:
D.J. Russo
B. Van Roy
A. Kazerouni
I. Osband
Z. Wen

title: A tutorial on Thompson sampling

venue: Foundations and Trends R © in Machine Learning, 11(1):1–96,

title: Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone

venue: PhD thesis, Stanford University,

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

title: Asymptotic statistics, volume 3

title: Large deviations and applications

venue: SIAM,

authors:
J. Von Neumann
O. Morgenstern

title: Theory of games and economic behavior (commemorative edition)

venue: Princeton university press,

heading: 1 Introduction

text:
In this manuscript we consider online learning, in particular the multi-armed stochastic bandit problem [19] and its extension to bilinear saddle-point problems. Thompson sampling (TS) is a wellknown Bayesian algorithm to tackle this problem [37, 35]. At each iteration TS samples an action according to the posterior probability that it is the optimal action. However, it never computes these probabilities, instead TS samples from the posterior of each arm and then acts greedily with respect to that sample, which is an implicit sample from the posterior probability of optimality. TS enjoys strong theoretical guarantees [1, 35] as well as excellent practical performance [6]. Moreover, it has an elegant information-theoretic interpretation of an agent that is making a tradeoff between information accumulation and regret [34]. That being said it does have several weaknesses. Firstly, TS requires samples from the true posterior, which may be intractable for some problems. It is known that TS with even small error in its posterior samples can suffer linear regret [32]. In many cases of interest the posterior distribution is highly intractable to sample from and running MCMC chains, one for each arm, can be wasteful and slow and still not yield precise enough samples for good performance, though recent work has attempted to improve this situation [22]. Moreover, TS is unable to take into account other preferences, such as constraints or the presence of other agents. In particular, it was recently shown that TS can suffer linear regret in two-player zero sum games [27] and we shall demonstrate the same phenomenon in this work empirically for constrained bandits. Finally, when performing TS the user never has direct access to the posterior probability of optimality, only samples from that distribution (though the distribution can be estimated by taking many samples). In some practical applications having access to the policy is desirable, for example to ensure safety constraints or to allocate budgets.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this paper we present ‘variational Bayesian optimistic sampling’ (VBOS), a new Bayesian approach to online learning. At every step the VBOS algorithm solves a convex optimization problem over the simplex. The solution to this problem is a policy that satisfies a particular ‘optimism’ condition. The problem is always convex, no matter what form the posteriors take. The only requirement is the ability to compute or estimate the cumulant generating function of the posteriors. VBOS and TS can be considered as part of the same family of algorithms since, in the bandit case, they both produce policies inside the optimistic set. That being said, VBOS has several advantages over TS. First, in some cases estimating or bounding the cumulant generating function may be easier than sampling from the posterior. Second, incorporating additional requirements such as constraints, opponents or tuning the exploration exploitation tradeoff is easy in VBOS - just change the optimization problem. Finally, when using VBOS we always have direct access to the policy, rather than just implicit samples from it, as well as an explicit upper bound on the expected value of the problem, which TS does not give us. Here we list the contributions of this work.

heading: 1.1 Contributions

text:
1. We derive a set of ‘optimistic’ Bayesian policies for the stochastic multi-armed bandit that satisfy a particular optimism inequality and which includes the TS policy. 2. We present a new, simple proof of a Õ( √ AT ) regret-bound for a bandit with A arms after
T timesteps that covers any policy in the optimistic set (Õ ignores logarithmic factors).
3. We derive variational Bayesian optimistic sampling (VBOS), which is a policy in the optimistic set that can be computed by solving a convex optimization problem.
4. We show that, unlike TS, the variational formulation easily handles more complicated problems, such as bilinear saddle-point problems which include as special cases zero-sum two player games and constrained bandits.

heading: 1.2 Preliminaries

text:
A stochastic multi-armed bandit problem is a sequential learning problem in which an agent interacts with an environment in order to maximize its total cumulative reward. Initially the agent does not know how the rewards are distributed and must learn about them from experience. In each round t ∈ N the agent selects an action at ∈ {1, . . . , A} and receives a reward rt = µat + ηtat where η t at ∈ R is zero-mean noise associated with action at at time t. We define Ft = (a1, r1, . . . , at−1, rt−1) to be the sequence of actions and rewards observed by the agent prior to round t, and as shorthand we shall use the notation Et(·) = E( · | Ft). An algorithm alg is a measurable mapping that takes the entire history at time t and produces a probability distribution, the policy, from which the agent samples its action. In order to assess the quality of an algorithm alg we consider the regret, or shortfall in cumulative rewards relative to the optimal value,
Regret(µ, alg, T ) = Eη,alg [ T∑ t=1 max i µi − rt ] , (1)
where Eη,alg denotes the expectation with respect to the noise process η and any randomness in the algorithm. This quantity (1) depends on the unknown expected reward µ ∈ RA, which is fixed at the start of play and kept the same throughout. To assess the quality of learning algorithms designed to work across some familyM of problems we define
BayesRegret(φ, alg, T ) = Eµ∼φRegret(µ, alg, T ) (2)
where φ is a prior probability measure over µ ∈M that assigns relative importance to each problem instance and which we assume is known to the algorithm.

heading: 2 Thompson sampling and a variational approach

text:
The algorithm that minimizes the Bayesian regret (2) is called the Bayes-optimal policy, but it is believed to be intractable to compute in most cases [10]. With that in mind we would like an algorithm that is computationally tractable and still guarantees a good bound on the Bayesian regret.
TS is a Bayesian algorithm that at each time step samples possible values of each arm from their respective posteriors and acts greedily with respect to those samples; see Algorithm 1. This simple strategy provides a principled approach to the exploration-exploitation tradeoff in the stochastic multi-armed bandit problem. In this section we derive a set of ‘optimistic’ policies, which includes the TS policy, and we shall show that any algorithm that produces policies in this set satisfies a guaranteed Bayesian regret bound. For brevity we defer all proofs to the appendices.

heading: 2.1 Bounding the conditional expectation

text:
The Bayesian regret (2) depends on the expectation of the maximum over a collection of random variables. Here we shall derive an upper bound on this quantity, starting with a generic upper bound on the conditional expectation.
If X : Ω → Rd is a random variable in Ld1 (i.e., E|Xi| < ∞ for each i = 1, . . . , d) then we denote by ΨX : Rd → R ∪ {∞} the cumulant generating function of X − EX , i.e.,
ΨX(β) = logE exp(β>(X − EX)).
This function is always convex, and we shall assume throughout this manuscript that it is also closed and proper for any random variables we encounter. With this definition we can present a bound on the conditional expectation.
Lemma 1. Let X : Ω → R be a random variable on (Ω,F ,P) satisfying X ∈ L1, and let A ∈ F be an event with P(A) > 0. Then, for any τ ≥ 0
E[X|A] ≤ EX + τΨX(1/τ)− τ logP(A). (3)
The right hand side of (3) involves the perspective of ΨX and so is convex in τ [4] and we can minimize over τ ≥ 0 to find the tightest bound, which we do next. Recall that the convex conjugate of function f : Rd → R is denoted f∗ : Rd → R and is given by f∗(y) = supx ( x>y − f(x) ) [4].
Theorem 1. Let X : Ω → R be a random variable such that the interior of the domain of ΨX is non-empty, then under the same assumptions as Lemma 1 we have 1
E[X|A] ≤ EX + (Ψ∗X)−1(− logP(A)).
For example, if X ∼ N (0, σ2), then for any event A we can bound the conditional expectation as E[X|A] ≤ σ √ −2 logP(A), no matter how X and A are related. This inequality has clear connections to Kullback’s inequality [8] and the Donsker-Varadhan variational representation of KL-divergence [11, Thm. 3.2]. The function Ψ∗ is referred to as the Cramér function or the rate function in large deviations theory [39]. The inverse of the rate function comes up in several contexts, such as queuing theory and calculating optimal insurance premiums [21]. Cramér’s theorem tells us that the probability of a large deviation of the empirical average of a collection of IID random variables decays exponentially with more data, and that the decay constant is the rate function. It is no surprise then that the regret bound we derive will depend on the inverse of the rate function, i.e., when the tails decay faster we incur less regret.

heading: 2.2 The optimistic set

text:
Using Theorem 1 we next derive the maximal inequality we shall use to bound the regret.
Lemma 2. Let µ : Ω → RA, µ ∈ LA1 , be a random variable, let i? = argmaxi µi (ties broken arbitrarily) and denote by Ψi := Ψµi , then
Emax i µi ≤ A∑ i=1 P(i? = i) ( Eµi + (Ψ∗i )−1(− logP(i? = i)) ) .
Note that Lemma 2 makes no assumption of independence of each entry of µ, the bound holds even in the case of dependency.
1If ΨX = 0, then we take (Ψ∗X) −1 = 0.
In the context of online learning πTSi = P(i? = i) is exactly the TS policy when µi have the laws of the posterior. For ease of notation we introduce the ‘optimism’ map Gtφ : ∆A → R which for a random variable µ : Ω→ RA distributed according to φ(· | Ft) is given by
Gtφ(π) := A∑ i=1 πi ( Etµi + (Ψt∗i )−1(− log πi) ) , (4)
where ∆A denotes the probability simplex of dimension A − 1 and Ψti := Ψµi|Ft . Note that Gtφ is concave since Ψti is convex [4]. Moreover, if the random variables are non-degenerate then Gtφ is differentiable and the gradient can be computed using Danskin’s theorem [7].
With this notation we can write Et maxi µi ≤ Gtφ(πTS). This brings us to the ‘optimistic’ set of probability distributions, which corresponds to the set of policies that satisfy that same inequality. Definition 1. Let µ : Ω → RA be a random variable distributed according to φ(· | Ft), then we define the optimistic set as
Ptφ := {π ∈ ∆A | Et max i µi ≤ Gtφ(π)}.
Immediately we have two facts about the set Ptφ. First, it is non-empty since πTS ∈ Ptφ, and second, it is a convex set since the optimism map Gtφ is concave.

heading: 2.3 Variational Bayesian optimistic sampling

text:
Since the TS policy is in Ptφ, it implies that we can maximize the bound and also obtain a policy in Ptφ, since
Et max i µi ≤ Gtφ(πTS) ≤ max π∈∆A Gtφ(π). (5)
We refer to the policy that maximizes Gtφ as the ‘variational Bayesian optimistic sampling’ policy (VBOS) and present the VBOS procedure as Algorithm 2. VBOS produces a policy πt ∈ Ptφ at each round by construction. The maximum is guaranteed to exist since ∆A is compact and Gtφ is continuous. The problem of maximizing Gtφ is a concave maximization problem, and is thus computationally tractable so long as each Ψti is readily accessible. This holds no matter what form the posterior distribution takes. This means we don’t rely on any properties like log-concavity, unimodality, or smoothness of the distribution for tractability of the optimization problem.
As an example, consider the case where each µi ∼ N (0, σ2) independently. In this instance we recover the familiar bound of Emaxi µi ≤ Gφ(πTS) = maxπ∈∆A Gφ(π) = σ √ 2 logA. The variational form allows us to compute a bound in the case of differently distributed random variables.
Algorithm 1 TS for bandits for round t = 1, 2, . . . , T do
sample µ̂t ∼ φ(· | Ft) choose at ∈ argmaxi µ̂ti
end for
Algorithm 2 VBOS for bandits for round t = 1, 2, . . . , T do
compute πt = argmaxπ∈∆A G t φ(π)
sample at ∼ πt end for

heading: 2.4 Regret analysis

text:
Now we shall present regret bounds for algorithms that produce policies in the optimistic set. These bounds cover both TS and VBOS. Lemma 3. Let alg produce any sequence of policies πt, t = 1, . . . , T , that satisfy πt ∈ Ptφ, then
BayesRegret(φ, alg, T ) ≤ E T∑ t=1 A∑ i=1 πti(Ψ t∗ i ) −1(− log πti).
This bound is generic in that it holds for any set of posteriors and any algorithm producing policies in Ptφ. The regret depends on the inverse rate functions of the posteriors, no matter how complicated
those posteriors may be, and faster concentrating posteriors, i.e., larger rate functions, will have lower regret. Loosely speaking, as more data accumulates the posteriors concentrate towards the true value (under benign conditions [38, Ch. 10.2]), implying (Ψt∗i )
−1 → 0. By carefully examining the rate of concentration of the posteriors we can derive concrete regret bounds in specific cases, such as the standard sub-Gaussian reward noise case, which we do next.
Theorem 2. Let alg produce any sequence of policies πt, t = 1, . . . , T , that satisfy πt ∈ Ptφ and assume that both the prior and reward noise are 1-sub-Gaussian for each arm, then
BayesRegret(φ, alg, T ) ≤ √ 2AT logA(1 + log T ) = Õ( √ AT ).
The assumption that the prior is 1-sub-Gaussian is not really necessary and can be removed if, for example, we assume the algorithm pulls each arm once at the start of the procedure. Theorem 2 bounds the regret of both TS and VBOS, as well as any other algorithm producing optimistic policies. The point of this theorem is not to provide the tightest regret bound but to provide some insight into the question of how close to the true TS policy another policy has to be in order to achieve similar (in particular sub-linear) regret. We have provided one answer - any policy in the optimistic set Ptφ for all t, is close enough. However, this set contracts as more data accumulates (as the posteriors concentrate) so it becomes harder to find good approximating policies. That being said, the VBOS policy is always sufficiently close because it is always in the optimistic set. In Figure 1 we show the progression of a single realization of the set Ptφ over time for a three-armed Gaussian bandit with Gaussian prior and where the policy being followed is TS [13]. Initially, Ptφ is quite wide, but gradually as more data accrues it concentrates toward the optimal arm vertex of the simplex.

heading: 3 Connections and interpretations of VBOS

text:
Exploration-exploitation tradeoff. Examining the problem that is solved to determine the VBOS policy we can break it into two components
Gtφ(π) = A∑ i=1
πiEtµi︸ ︷︷ ︸ exploit +
A∑ i=1
πi(Ψ t∗ i ) −1(− log πi)︸ ︷︷ ︸
explore
,
the first term of which includes the expected reward (under the posterior) from pulling each arm and is the agent’s current understanding of the world, and the second term consists only of the uncertainty in each arm. The policy that maximizes this function is balancing this exploration and exploitation tradeoff, with a tradeoff parameter of one. In some practical instances it may be beneficial to use a different tradeoff parameter other than one, e.g., when there are a larger number of arms than the total number of rounds to play. In this case VBOS can easily be tuned to be more or less exploring as needed.
Upper confidence bounds. Here we show a connection between VBOS and upper confidence bound (UCB) methods [18, 2]. The Chernoff inequality tells us that the tail probability of random variable µ : Ω → R can be bounded as P(µ − Eµ > ) ≤ exp(−Ψ∗µ( )), for any ≥ 0. UCB algorithms build upper confidence intervals which contain the true value of the random variable with high-probability [18, 2, 16]. If we want the interval to contain the true value of µ with probability at least 1− δ it requires setting = (Ψ∗µ)−1(− log δ), yielding Eµ+ (Ψ∗µ)−1(− log δ) ≥ µ with high probability. UCB approaches to the stochastic multi-armed bandit typically choose the largest upper confidence bound (the ‘optimism in the face of uncertainty’ approach), that is, at time t they select action
at ∈ argmax i (Etµi + (Ψt∗i )−1(− log δt)),
for some schedule δt. A lot of work goes into tuning δt for various applications. By contrast, VBOS samples from policy
at ∼ argmax π∈∆A A∑ i=1 πi ( Etµi + (Ψt∗i )−1(− log πi) ) .
It is clear that VBOS is building upper confidence bounds on the values of each arm that depend on the value of the policy, since if we denote π? the maximizer to the above problem, then Pt(Etµi + (Ψt∗i )
−1(− log π?i ) < µi) ≤ π?i . This procedure gives higher ‘bonuses’ to arms that end up with lower probability of being pulled, and lower bonuses to arms with high probability of being pulled, which is similar to what is done in more sophisticated UCB algorithms such as KL-UCB+ [17, 9, 14]. This is desirable because if the mean of an arm is low then there is a chance this is simply because we have under-estimated it and perhaps we should pay more attention to that arm. In this light VBOS can be interpreted as a stochastic Bayesian UCB approach [16]. One advantage is that we do not have to tune a schedule δt, like TS our algorithm is randomized and stationary, i.e., it does not depend on how many time-steps have elapsed other than implicitly through the posteriors.
K-learning. K-learning is an algorithm originally developed for efficient reinforcement learning in MDPs where it enjoys a similar regret bound to TS [23, 30, 31]. For bandits, the agent policy at time t is given by
τ?t = argmin τ≥0
( τ log
A∑ i=1 exp(Etµi/τ + Ψti(1/τ)) ) , πti ∝ exp(Etµi/τ?t + Ψti(1/τ?t )). (6)
It can be shown that this is equivalent to VBOS when the ‘temperature’ parameters τi that we optimize over are constrained to be equal for each arm. Although K-learning and VBOS have essentially the same regret bound, this can make a large difference in practice. This connection also suggests that recent reinforcement learning algorithms that rely on the log-sum-exp operator, the ‘soft’ max family [12, 20, 28, 33], are also in some sense approximating the VBOS policy, although as made clear in [29] these approaches do not correctly model the uncertainty and so will suffer linear regret in general.

heading: 4 Bilinear saddle-point problems

text:
In this section we extend the above analysis to constrained bilinear saddle-point problems, which include as special cases zero-sum two player games and constrained multi-armed bandits, as well as standard stochastic multi-armed bandits. Equipped with the tools from the previous sections we shall formulate a convex optimization problem that when solved yields the VBOS policy at each round, and prove that in two special cases this strategy yields a sub-linear regret bound. It is known, and we shall demonstrate empirically, that TS (Algorithm 3) can fail, i.e., suffer linear regret for some instances in this more general regime [27, §3.2]. Consequently, this is the first setting where the variational approach is substantially more powerful than TS.
A finite dimensional, constrained, bilinear saddle-point problem is defined by a matrix R ∈ Rm×A and two non-empty convex sets Π ⊆ RA, Λ ⊆ Rm which are the feasible sets for the maximizer and minimizer respectively. Here we shall assume that the agent is the maximizer, i.e., that Π = ∆A, and that the agent is uncertain about the entries of R and must learn about them from experience. The saddle-point problem has optimal value given by
V ?R,Λ := min λ∈Λ max π∈∆A λ>Rπ = max π∈∆A min λ∈Λ λ>Rπ (7)
where we can swap the order of the min-max due to the minimax theorem [40]. Unlike the stochastic multi-armed bandit case the maximizing policy in the bilinear saddle-point is typically stochastic, and as such the agent will return a policy rather than a single action at each time-step. This is to allow the case, for example, an opponent who gets to know the agent policy in advance of selecting their own action. We shall consider the case where at each time period the agent produces policy πt ∈ ∆A over columns of R from which action at ∈ {1, . . . , A} is sampled, and receives reward rt ∈ R and observation ot ∈ O where either the reward, observation, or both are corrupted by noise ηt. The exact reward, noise, observation, and opponent space Λ will depend on the problem setup. For instance, the vanilla stochastic multi-armed bandit is a special case of this problem where Λ is a singleton and the agent receives bandit feedback associated with the action sampled from its policy (i.e., ot = rt = Rat + η t at ). The information available to the agent at the start of round t is given by Ft = {a1, o1, . . . , at−1, ot−1}. In this setup we define the Bayesian regret to be
BayesRegret(φ, alg, T ) = ER∼φ ( Eη,alg
T∑ t=1 (V ?R,Λ − rt)
) .
Analogously to the stochastic multi-armed bandit case we can define the optimism map and the optimistic set. Let Rj : Ω → Rm, j = 1, . . . , A, denote the random variable corresponding to the jth column of R, denote by Ψtj : Rm → R the cumulant generating function of Rj − EtRj , then assuming that Rj ∈ Lm1 we define the optimism map in this case to be
Gtφ,Λ(π) := min λ∈Λ,τ≥0 A∑ j=1 πj(λ >EtRj + τjΨtj(λ/τj)− τj log πj) (8)
and the optimistic set to be
Ptφ,Λ := {π ∈ ∆A | EtV ?R,Λ ≤ Gtφ,Λ(π)}. (9)
With these we can bound EtV ?R,Λ using the techniques we have previously developed.
Lemma 4. Assuming that R ∈ Lm×A1 we have EtV ?R,Λ ≤ max
π∈∆A Gtφ,Λ(π). (10)
This lemma motivates the VBOS algorithm for bilinear saddle-points, presented as Algorithm 4. VBOS produces policies πt ∈ Ptφ,Λ for all t by construction. On the other hand, in some cases TS can produce policies πt 6∈ Ptφ,Λ, which we shall show by counter-example in the sequel.
At first glance maximizing Gtφ,Λ might seem challenging, but we can convert it into a convex minimization problem by maximizing over π to yield dual convex optimization problem:
minimize V + ∑A j=1 τj exp(sj/τj) subject to sj ≥ λ>EtRj + τjΨtj(λ/τj)− V − τj , j = 1, . . . , A τ ≥ 0, λ ∈ Λ,
(11)
over variables τ ∈ RA, λ ∈ Rm, s ∈ RA, V ∈ R. The VBOS distribution can be recovered using π?i = exp(s ? i /τ ? i ). Problem (11) is an exponential cone program and can be solved efficiently using modern methods [25, 26, 36, 24].
Algorithm 3 TS for saddle-points for round t = 1, 2, . . . , T do
sample R̂t ∼ φ(· | Ft) set πt = argmax
π∈∆A min λ∈Λ
λ>R̂tπ
end for
Algorithm 4 VBOS for saddle-points for round t = 1, 2, . . . , T do
set πt = argmaxGtφ,Λ(π) end for

heading: 4.1 Zero-sum two-player games

text:
Consider the problem of an agent playing a two-player zero-sum matrix game against an opponent. In this setting the agent ‘column player’ selects a column index j ∈ {1, . . . , A} and the ‘row player’
selects a row index i ∈ {1, . . . ,m}, possibly with knowledge about the policy the agent is using to select the column. Note that in this case Λ = ∆m. These choices are revealed to the players and the row player makes a payment of rt = Rij + ηtij to the column player, where η t ij is a zero-mean noise term associated with actions i, j at time t, and the observation the agents receive is the reward and the actions of both players. The optimal strategies (π?, λ?) are a Nash equilibrium for the game [40, 5]. We shall assume that the agent we control is the column player, and that we have no control over the actions of the opponent. It was recently shown that both K-learning and UCB variants enjoy sub-linear regret bounds in this context [27]. Here we prove a regret bound for policies in the optimistic set under a sub-Gaussian assumption. Theorem 3. Let alg produce any sequence of policies πt, t = 1, . . . , T , that satisfy πt ∈ Ptφ,Λ and let the opponent produce any policies λt, t = 1, . . . , T , adapted to Ft. Assuming that the prior over each entry of R and reward noise are 1-sub-Gaussian we have
BayesRegret(φ, alg, T ) ≤ √ 2AmT logA(1 + log T ) = Õ( √ mAT ).
In Figure 2 we show how five agents perform on a 50 × 50 randomly generated game in self-play and against a best-response opponent. The entries of R were sampled from prior N (0, 1) and the noise term ηt at each time-period was also sampled fromN (0, 1). In self-play the opponent has the same knowledge and is applying the same algorithm to generate the policy at each time-step. The best-response opponent knows the matrix M exactly as well as the policy that the agent produces and picks the action that minimizes the reward to the agent. The matrix is the same in both cases. We compare the K-learning and UCB algorithms as described in [27] as well as EXP3 [3], a generic adversarial bandit algorithm, VBOS Algorithm 4, and TS Algorithm 3 over 8 seeds. As can be seen VBOS is the best performing algorithm in both cases, followed closely by K-learning. Although performing moderately well in self-play, it is no surprise that TS does very poorly against the bestresponse opponent since it is sometimes susceptible to exploitation, as we show next.
Consider the two-player zero-sum game counter-example presented in [27]. Here Λ = ∆2, and
R =
[ r 0
0 −1
] , r = { 1 with probability 1/2 −1 with probability 1/2.
(12)
In this case TS will play one of two policies: πTS,1 = [1, 0] or πTS,2 = [1/2, 1/2], each with probability 1/2. A quick calculation yields EV ?R,Λ = −1/4 and Gφ,Λ(πTS,2) = −1/2, so with probability 1/2 TS will produce a policy not in the optimistic set, since Gφ,Λ(πTS,2) < EV ?R,Λ. Now, consider the case where r = 1 and the opponent plays the strategy [0, 1] in every round. Then every time TS produces πTS,2 it will incur expected regret of 1/4. Since the value of r is never revealed the uncertainty is never resolved and so this pattern continues forever. This manifests as linear regret for TS in this instance. By contrast VBOS always produces πVBOS = [1, 0] and so suffers no regret.
In Figure 3 we show a realization of Ptφ,Λ over time for an agent following the VBOS policy in a randomly generated 3× 3 zero-sum two-player game. Observe that the TS algorithm has produced policies outside the optimistic set, but VBOS remains inside at all times. Note that this does not prove that TS will suffer linear regret, since membership of the optimistic set is only a sufficient, not necessary, condition.

heading: 4.2 Constrained bandits

text:
In constrained bandits we want to find the policy that maximizes expected reward subject to a set of constraints. The constraints specify that the expected value of other reward functions associated with the same arms, which are also initially unknown, are larger than zero. Formally, we have the usual unknown reward vector µ1 ∈ RA we want to maximize as well as m − 1 other unknown reward vectors µ2, . . . , µm ∈ RA that define the constraints. When there is zero uncertainty we want to solve the following primal-dual linear-programming pair
maximize µ>1 π subject to µ>i π ≥ 0, i = 2, . . . ,m
π ∈ ∆A
minimize V subject to ∑m i=1 µiλi ≤ V 1
λ ≥ 0, λ1 = 1,
over primal variable π ∈ ∆A and dual variables V ∈ R and λ ∈ Rm, and where 1 denotes the vector of all ones. We denote by (π?, λ?) any optimal primal-dual points.
When there is uncertainty in the reward vectors, then we must be careful to ensure that the Bayesian regret is well-defined. If the support of the prior includes infeasible problems, which have optimal value −∞, then the expectation of the regret under that prior is unbounded below. However, if we make the assumption that ‖λ?‖2 ≤ C for some C > 0 φ-almost surely, which implies that the problem is feasible almost surely, then the Bayesian regret is well-defined and we can derive a regret bound that will depend on C. With this in mind we define the set Λ = {λ ∈ Rm | λ1 = 1, λ ≥ 0, ‖λ‖2 ≤ C}. Let R ∈ Rm×A be the matrix with the reward vectors µ1, . . . , µm stacked row-wise, then we can write the Lagrangian for the above primal-dual pair as Equation (7), i.e., this problem is a constrained bilinear saddle-point problem in terms of the primal-dual variables π and λ.
At each round t the agent produces a policy πt from which a column is sampled and the agent receives observation vector ot = (µ1j + ηt1j , µ2j + η t 2j , . . . , µmj + η t mj) where j is the index of the sampled column and ηtij is zero-mean noise for entry i, j. We define the reward at each timeperiod to be rt = minλ∈Λ λ>Rπt. We choose this reward for two reasons, firstly the regret with this reward is always non-negative, and secondly if the regret is zero then the corresponding policy πt is optimal for the linear program since it is a maximizer of the saddle-point problem [4]. Unlike the previous examples the agent never observes this reward since it depends on exact knowledge of R to compute, the reward is only used to measure regret. Nevertheless, we have the following Bayesian regret bound for policies in the optimistic set. Theorem 4. Let alg produce any sequence of policies πt, t = 1, . . . , T , that satisfy πt ∈ Ptφ,Λ and assume that the prior over each entry of R and reward noise are 1-sub-Gaussian and that ‖λ?‖2 ≤ C φ-almost surely, then
BayesRegret(φ, alg, T ) ≤ C (√ 2 logA(1 + log T ) + 2 √ m )√ AT = Õ( √ mAT ).
Next we present a numerical experiment with n = 50 variables and m = 25 constraints. The entries of R were sampled from prior N (−0.15, 1), and we repeatedly sampled from this distribution until
a feasible problem was found. We chose a slightly negative bias in the prior for R in order to make the problem of finding a feasible policy more challenging. All noise was sampled from N (0, 1). For this experiment we set C = 10; the true optimal dual variable satisfied ‖λ?‖ ≈ 7. In Figure 4 we compare the performance of TS Algorithm 3, VBOS Algorithm 4, and K-learning [23] over 8 seeds. We also plot how much the policy produced by each algorithm violated the constraints at each time-period, as measured by `∞ norm. As can be seen both VBOS and K-learning enjoy sub-linear regret and have their constraint violation converging to zero, with VBOS slightly outperforming Klearning on both metrics. TS on the other hand appears to suffer from linear regret, and the constraint violation decreases up to a point after which it saturates at a non-zero value. It is clear that TS is unable to adequately trade off exploration and exploitation in this problem.

heading: 5 Conclusion

text:
In this manuscript we introduced variational Bayesian optimistic sampling (VBOS), which is an algorithm that produces policies by solving an optimization problem in each round of a sequential decision problem. The optimization problem that must be solved is always convex, no matter how complicated the posteriors are. We showed that VBOS enjoys low regret for several problem families, including the well-known multi-armed bandit problem as well as more exotic problems like constrained bandits where TS can fail.
We conclude with some discussion about future directions for this work. First, in follow-up work we intend to show that VBOS is applicable in structured and multi-period problems like Markov decision processes, and again prove Bayesian regret guarantees. Second, an avenue we did not explore in this work was to parameterize the policy to be in a certain family, e.g., linear in some basis. The variational formulation naturally extends to this case, where the optimization problem is in terms of the basis coefficients (which maintains convexity in the linear case). Combining these two suggests using the variational formulation to find the linearly parameterized VBOS policy in an MDP, which amounts to solving a convex optimization problem that may be much smaller than solving the corresponding problem without the parameterization. We expect that a regret bound is possible in this case under certain assumptions on the basis. Finally, since the VBOS objective is differentiable this opens the door to using differentiable computing architectures, such as deep neural networks trained using backpropagation. We speculate that it may be possible to apply VBOS in deep reinforcement learning to tackle the challenging exploration-exploitation tradeoff in those domains.
Acknowledgments and Disclosure of Funding
The authors would like to thank Ben Van Roy, Satinder Singh, and Zheng Wen for discussions and feedback. The authors received no specific funding for this work.

title: Variational Bayesian Optimistic Sampling


summaries: In this paper, the authors study a stochastic variance reduced method under sampling rules that are without replacement for smooth and non-smooth, convex and strongly convex objectives. More precisely : - they develop a proximal method call Prox-DFinito for which they study convergence rates for random reshuffling, cyclic and shuffling once samplings - in the cyclic sampling, they derive an optimal fixed ordering (and a practical adaptive variant which do not require the knowledge of $z^*$ - Finally, the authors highlight the fact that, when assuming data heterogeneity, their study lead to a convergence rate independent of the number of data samples. This was up until now just known for iid sampling.

summaries: The paper proposes a new method called Prox-DFinito based on the proximal Finito with without-replacement sampling. The authors derive complexity bounds for the proposed method in convex (for making the squared norm of the gradient small) and strongly convex cases (for making the squared distance to the solution small) that match under some additional assumptions the rate of Gradient Descent. Moreover, under additional assumptions on the objective function, the authors show sample-size independent bound in the convex case. The proofs are non-standard but clean and easy to follow. However, the paper has several strong weaknesses.

summaries: This paper develops a proximal damped version of the Finito algorithm. The algorithm is proved to achieve the same convergence rate as proximal GD, for cyclic sampling, random reshuffling and shuffling-once versions of the algorithm. Further, the authors claim that this is the first* shuffling based variance reduction algorithm to achieve the convergence rate. The paper also gives a new norm that captures the optimality of sampling orders and provides a heuristic based on that for importance based reshuffling.  Besides the theoretical results, the empirical results seem to suggest that the proposed algorithm is indeed faster than other variance reduction algorithms.   *: The authors cite a concurrent work (Malinovsky et al.) that also achieves the same convergence rates for general convex functions, but the algorithms in the two papers are different.

summaries: This paper proposes a new first-order algorithm using without-replacement strategy to solve a class of composite convex minimization problems. The main idea is to modify the well-known scheme, called Finito/MISO method by applying a without-replacement strategy and a damping step. Under the convexity and L-smoothness of f, the proposed algorithm achieves O(1/k) rate in epoch on the optimality residual. When f is additionally strongly convex, the rate is improved to linear as in standard proximal gradient methods. The analysis relies on a weight norm defined through the order of the underlying shuffling strategy. The authors also compare their method with other schemes such as a coordinate descent method with cyclic rule, and standard GD. Next, the authors also investigate the optimal cyclic rule for sampling and propose an adaptive variant. Numerical examples on standard logistic regression problem are presented to illustrate the performance of the proposed methods.

abstractText: When applying a stochastic algorithm, one must choose an order to draw samples. The practical choices are without-replacement sampling orders, which are empirically faster and more cache-friendly than uniform-iid-sampling but often have inferior theoretical guarantees. Without-replacement sampling is well understood only for SGD without variance reduction. In this paper, we will improve the convergence analysis and rates of variance reduction under without-replacement sampling orders for composite finite-sum minimization. Our results are in two-folds. First, we develop a damped variant of Finito called Prox-DFinito and establish its convergence rates with random reshuffling, cyclic sampling, and shuffling-once, under both convex and strongly convex scenarios. These rates match full-batch gradient descent and are state-of-the-art compared to the existing results for without-replacement sampling with variance-reduction. Second, our analysis can gauge how the cyclic order will influence the rate of cyclic sampling and, thus, allows us to derive the optimal fixed ordering. In the highly data-heterogeneous scenario, Prox-DFinito with optimal cyclic sampling can attain a sample-size-independent convergence rate, which, to our knowledge, is the first result that can match with uniform-iid-sampling with variance reduction. We also propose a practical method to discover the optimal cyclic ordering numerically.

title: Curiously fast convergence of some stochastic gradient descent algorithms

venue: In Proceedings of the symposium on learning and data science, Paris,

authors:
L. Bottou
F.E. Curtis
J. Nocedal

title: Optimization methods for large-scale machine learning

venue: Siam Review,

authors:
S. Boyd
N. Parikh
E. Chu

title: Distributed optimization and statistical learning via the alternating direction method of multipliers

venue: Now Publishers Inc,

authors:
S.S. Chen
D.L. Donoho
M.A. Saunders

title: Atomic decomposition by basis pursuit

venue: SIAM review,

authors:
Y.T. Chow
T. Wu
W. Yin

title: Cyclic coordinate-update algorithms for fixed-point problems: Analysis and applications

venue: SIAM Journal on Scientific Computing,

authors:
A. Defazio
F. Bach
S. Lacoste-Julien

title: SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives

venue: arXiv preprint arXiv:1407.0202,

authors:
A. Defazio
J. Domke

title: Finito: A faster, permutable incremental gradient method for big data problems

venue: In International Conference on Machine Learning,

title: The mnist database of handwritten digit images for machine learning research

venue: IEEE Signal Processing Magazine,

title: Compressed sensing

venue: IEEE Transactions on information theory,

authors:
M. Gurbuzbalaban
A. Ozdaglar
P.A. Parrilo

title: On the convergence rate of incremental aggregated gradient algorithms

title: Why random reshuffling beats stochastic gradient descent

venue: Mathematical Programming,

authors:
J. Haochen
S. Sra

title: Random shuffling beats sgd after finite epochs

authors:
X. Huang
E.K. Ryu
W. Yin

title: Tight coefficients of averaged operators via scaled relative graph

venue: Journal of Mathematical Analysis and Applications,

authors:
R. Johnson
T. Zhang

title: Accelerating stochastic gradient descent using predictive variance reduction

venue: Advances in neural information processing systems,

title: Learning multiple layers of features from tiny images

authors:
S. Ma
Y. Zhou

title: Understanding the impact of model incoherence on convergence of incremental sgd with random reshuffle

title: Incremental majorization-minimization optimization with application to large-scale machine learning

authors:
G. Malinovsky
A. Sailanbayev
P. Richtárik

title: Random reshuffling with variance reduction: New analysis and better rates

venue: arXiv preprint arXiv:2104.09342,

authors:
X. Mao
Y. Gu
W. Yin

title: Walk proximal gradient: An energy-efficient algorithm for consensus optimization

venue: IEEE Internet of Things Journal,

authors:
G. Mateos
J.A. Bazerque
G.B. Giannakis

title: Distributed sparse linear regression

venue: IEEE Transactions on Signal Processing,

authors:
K. Mishchenko
A. Khaled
P. Richtárik

title: Proximal and federated random reshuffling

venue: arXiv preprint arXiv:2102.06704,

authors:
K. Mishchenko
A. Khaled Ragab Bayoumi
P. Richtárik

title: Random reshuffling: Simple analysis with vast improvements

venue: Advances in Neural Information Processing Systems,

authors:
A. Mokhtari
M. Gurbuzbalaban
A. Ribeiro

title: Surpassing gradient descent provably: A cyclic incremental method with linear convergence rate

authors:
D. Nagaraj
P. Jain
P. Netrapalli

title: Sgd without replacement: Sharper rates for general smooth convex functions

authors:
Y. Park
E.K. Ryu

title: Linear convergence of cyclic saga

venue: Optimization Letters,

authors:
X. Qian
A. Sailanbayev
K. Mishchenko
P. Richtárik

title: Miso is making a comeback with better proofs and rates

authors:
S. Rajput
A. Gupta
D. Papailiopoulos

title: Closing the convergence gap of sgd without replacement

authors:
H. Robbins
S. Monro

title: A stochastic approximation method

venue: The annals of mathematical statistics,

authors:
R.A. Rossi
N.K. Ahmed

title: The network data repository with interactive graph analytics and visualization

venue: In AAAI,

authors:
E.K. Ryu
R. Hannah
W. Yin

title: Scaled relative graph: Nonexpansive operators via 2d euclidean geometry. arXiv: Optimization and Control, 2019

authors:
I. Safran
O. Shamir

title: How good is sgd with random shuffling

venue: In Conference on Learning Theory,

authors:
M. Schmidt
N. Le Roux
F. Bach

title: Minimizing finite sums with the stochastic average gradient

authors:
T. Sun
Y. Sun
D. Li
Q. Liao

title: General proximal incremental aggregated gradient algorithms: Better and novel results under general scheme

title: Regression shrinkage and selection via the lasso

venue: Journal of the Royal Statistical Society: Series B (Methodological),

authors:
N.D. Vanli
M. Gürbüzbalaban
A. Ozdaglar

title: A stronger convergence result on the proximal incremental aggregated gradient method

venue: arXiv: Optimization and Control,

authors:
N.D. Vanli
M. Gurbuzbalaban
A. Ozdaglar

title: Global convergence rate of proximal incremental aggregated gradient methods

authors:
B. Ying
K. Yuan
A.H. Sayed

title: Variance-reduced stochastic learning under random reshuffling

authors:
B. Ying
K. Yuan
S. Vlaski
A.H. Sayed

title: Stochastic learning under random reshuffling with constant step-sizes

authors:
H.-F. Yu
F.-L. Huang
C.-J. Lin

title: Dual coordinate descent methods for logistic regression and maximum entropy models

venue: Machine Learning,

authors:
K. Yuan
B. Ying
S. Vlaski
A. Sayed

title: Stochastic gradient descent with finite samples sizes. 2016

venue: IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP),

authors:
P. Zhao
T. Zhang

title: Stochastic optimization with importance sampling for regularized loss minimization

venue: In international conference on machine learning,

heading: 1 Introduction

text:
We study the finite-sum composite optimization problem
min x∈Rd
F (x) + r(x) and F (x) = 1
n n∑ i=1 fi(x). (1)
where each fi(x) is differentiable and convex, and the regularization function r(x) is convex but not necessarily differentiable. This formulation arises in many problems in machine learning [34, 39, 14], distributed optimization [20, 3, 19], and signal processing [4, 9].
The leading methods to solve (1) are first-order algorithms such as stochastic gradient descent (SGD) [28, 2] and stochastic variance-reduced methods [14, 6, 7, 17, 10, 32]. In the implementation of ∗Equal Contribution. Correspondence to: Kun Yuan
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
these methods, each fi(x) can be sampled either with or without replacement. Without-replacement sampling draws each fi(x) exactly once during an epoch, which is numerically faster than withreplacement sampling and more cache-friendly; see the experiments in [1, 38, 11, 7, 37, 5]. This has triggered significant interests in understanding the theory behind without-replacement sampling.
Among the most popular without-replacement approaches are cyclic sampling, random reshuffling, and shuffling-once. Cyclic sampling draws the samples in a cyclic order. Random reshuffling reorders the samples at the beginning of each sample epoch. The third approach, however, shuffles data only once before the training begins. Without-replacement sampling have been extensively studied for SGD. It was established in [1, 38, 11, 22, 24] that without-replacement sampling enables SGD with faster convergence For example, it was proved that without-replacement sampling can speed up uniform-iid-sampling SGD from Õ(1/k) to Õ(1/k2) (where k is the iteration) for strongly-convex costs in [11, 12], and O(1/k1/2) to O(1/k) for the convex costs in [24, 22]. [31] establishes a tight lower bound for random reshuffling SGD. Recent works [27, 22] close the gap between upper and lower bounds. Authors of [22] also analyzes without-replacement SGD with non-convex costs.
In contrast to the mature results in SGD, variance-reduction under without-replacement sampling are less understood. Variance reduction strategies construct stochastic gradient estimators with vanishing gradient variance, which allows for much larger learning rate and hence speed up training process. Variance reduction under without-replacement sampling is difficult to analyze. In the strongly convex scenario, [37, 33] provide linear convergence guarantees for SVRG/SAGA with random reshuffling, but the rates are worse than full-batch gradient descent (GD). Authors of [35, 23] improved the rate so that it can match with GD. In convex scenario, existing rates for without-replacement sampling with variance reduction, except for the rate established in an independent and concurrent work [18],
are still far worse than GD [33, 5], see Table 1. Furthermore, no existing rates for variance reduction under without-replacement sampling orders, in either convex or strongly convex scenarios, can match those under uniform-iid-sampling which are essentially sample-size independent. There is a clear gap between the known convergence rates and superior practical performance for without-replacement sampling with variance reduction.

heading: 1.1 Main results

text:
This paper narrows such gap by providing convergence analysis and rates for proximal DFinito, a proximal damped variant of Finito/MISO [7, 17, 26], which is a well-known variance reduction algorithm, under without-replacement sampling orders. Our main achieved results are:
• We develop a proximal damped variant of Finito/MISO called Prox-DFinito and establish its gradient complexities with random reshuffling, cyclic sampling, and shuffling-once, under both convex and strongly convex scenarios. All these rates match with gradient descent, and are state-of-the-art (up to logarithm factors) compared to existing results for without-replacement sampling with variance-reduction, see Table 1.
• Our novel analysis can gauge how a cyclic order will influence the rate of Prox-DFinito with cyclic sampling. This allows us to identify the optimal cyclic sampling ordering. ProxDFinito with optimal cyclic sampling, in the highly data-heterogeneous scenario, can attain a sample-size-independent convergence rate, which is the first result, to our knowledge, that can match with uniform-iid-sampling with variance reduction in certain scenarios. We also propose a numerical method to discover the optimal cyclic ordering cheaply.

heading: 1.2 Other related works

text:
Our analysis on cyclic sampling is novel. Most existing analyses unify random reshuffling and cyclic sampling into the same framework; see the SGD analysis in [11], the variance-reduction analysis in [10, 36, 23, 37], and the coordinate-update analysis in [5]. These analyses are primarily based on the “sampled-once-per-epoch” property and do not analyze the orders within each epoch, so they do not distinguish cyclic sampling from random reshuffling in analysis. [16] finds that random reshuffling SGD is basically the average over all cyclic sampling trials. This implies cyclic sampling can outperform random reshuffling with a well-designed sampling order. However, [16] does not discuss how much better cyclic sampling can outperform random reshuffling and how to achieve such cyclic order. Different from existing literatures, our analysis introduces an order-specific norm to gauge how cyclic sampling performs with different fixed orders. With such norm, we are able to clarify the worst-case and best-case performance of variance reduction with cyclic sampling.
Simultaneously and independently, a recent work [18] also provided an improved rates for variance reduction under without-replacement sampling orders that can match with gradient descent. However, [18] does not discuss whether and when variance reduction with replacement sampling can match with uniform sampling. In addition, [18] studies SVRG while this paper studies Finito/MISO. The convergence analyses in these two works are very different. The detailed comparison between this work and [18] can be referred to Sec. 3.3.

heading: 1.3 Notations

text:
Throughout the paper we let col{x1, · · · , xn} denote a column vector formed by stacking x1, · · · , xn. We let [n] := {1, · · · , n} and define the proximal operator as
proxαr(x) := arg min y∈Rd {α r(y) + 1 2 ‖y − x‖2} (2)
which is single-valued when r is convex, closed and proper. In general, we say A is an operator and write A : X → Y if A maps each point in space X to another space Y . So A(x) ∈ Y for all x ∈ X . For simplicity, we write Ax = A(x) and A ◦ Bx = A(B(x)) for operator composition. Cyclic sampling. We define π := (π(1), π(2), . . . , π(n)) as an arbitrary determined permutation of sample indexes. The order π is fixed throughout the entire learning process under cyclic sampling.
Random reshuffling. When starting each epoch, a random permutation τ := (τ(1), τ(2), ..., τ(n)) is generated to specify the order to take samples. Let τk denote the permutation of the k-th epoch.
Algorithm 1 Prox-DFinito Input: z̄0 = 1n n∑ i=1 z0i , step-size α, and θ ∈ (0, 1);
for epoch k = 0, 1, 2, · · · do for iteration t = kn+ 1, kn+ 2, · · · , (k + 1)n do xt−1 = proxαr(z̄
t−1); Pick it with some rule; Update ztit and z̄
t according to (4a) and (5); end for z (k+1)n i ← (1− θ)zkni + θz (k+1)n i for any i ∈ [n]; . a damping step
z̄(k+1)n ← (1− θ)z̄kn + θz̄(k+1)n; . a damping step end for

heading: 2 Proximal Finito/MISO with Damping

text:
The proximal gradient method to solve problem (1) is
zti = x t−1 − α∇fi(xt−1), ∀ i ∈ [n] (3a)
xt = proxαr ( 1 n n∑ i=1 zti )
(3b)
To avoid the global average that passes over all samples, we propose to update one zi per iteration:
zti = { xt−1 − α∇fi(xt−1), i = it zt−1i , i 6= it
(4a)
xt = proxαr ( 1 n n∑ i=1 zti ) . (4b)
When it is invoked with uniform-iid-sampling and r(x) = 0, algorithm (4a)–(4b) reduces to Finito/MISO [7, 17]. When it is invoked with cyclic sampling and r(x) = 0, algorithm (4a)–(4b) reduces to DIAG [23] and WPG [19]. We let z̄t := 1n ∑n i=1 z t i . The update (4a) yields
z̄t = z̄t−1 + (ztit − z t−1 it )/n. (5)
This update can be finished with O(d) operations if {zti}ni=1 are stored with O(nd) memory. Furthermore, to increase robustness and simplify the convergence analysis, we impose a damping step to zi and z̄ when each epoch finishes. The proximal damped Finito/MISO method is listed in Algorithm 1. Note that the damping step does not incur additional memory requirements. A more practical implementation of Algorithm 1 is referred to Algorithm 3 in Appendix A.

heading: 2.1 Fixed-point recursion reformulation

text:
Algorithm (4a)–(4b) can be reformulated into a fixed-point recursion in {zi}ni=1. Such a fixed-point recursion will be utilized throughout the paper. To proceed, we define z = col{z1, · · · , zn} ∈ Rnd and introduce the average operator A : Rnd → Rd as Az = 1n ∑n i=1 zi. We further define the i-th block coordinate operator Ti : Rnd → Rnd as Tiz=col{z1, · · · , (I−α∇fi) ◦ proxαr(Az), · · · , zn}
where I denotes the identity mapping. When applying Ti, it is noted that the i-th block coordinate in z is updated while the others remain unchanged. Proposition 1. Prox-DFinito with fixed cyclic sampling order π is equivalent to the following fixed-point recursion (see proof in Appendix B.1.)
z(k+1)n = (1− θ)zkn + θTπzkn (6)
where Tπ = Tπ(n) ◦ · · · ◦ Tπ(1). Furthermore, variable xt can be recovered by
xt = proxαr ◦ Azt, t = 0, 1, 2, · · · (7)
Similar result also hold for random reshuffling scenario. Proposition 2. Prox-DFinito with random reshuffling is equivalent to
z(k+1)n = (1− θ)zkn + θTτkzkn (8) where Tτk = Tτk(n) ◦ · · · ◦ Tτk(1). Furthermore, variable xt can be recovered by following (7).

heading: 2.2 Optimality condition

text:
Assume there exists x? that minimizes F (x) + r(x), i.e., 0 ∈ ∇F (x?) + ∂ r(x?). Then the relation between the minimizer x? and the fixed-point z? of recursion (6) and (8) can be characterized as: Proposition 3. x? minimizes F (x)+r(x) if and only if there is z? so that (proof in Appendix B.2)
z? = Tiz?, ∀ i ∈ [n], (9) x? = proxαr ◦ Az?. (10)
Remark 1. If x? minimizes F (x) + r(x), it holds from (9) and (10) that z?i = (I−α∇fi) ◦ proxαr(Az?) = x? − α∇fi(x?) for any i ∈ [n].

heading: 2.3 An order-specific norm

text:
To gauge the influence of different sampling orders, we now introduce an order-specific norm. Definition 1. Given z = col{z1, · · · , zn} ∈ Rnd and a fixed cyclic order π, we define
‖z‖2π = n∑ i=1 i n ‖zπ(i)‖2 = 1 n ‖zπ(1)‖2 + 2 n ‖zπ(2)‖2 + · · ·+ ‖zπ(n)‖2
as the π-specific norm.
For two different cyclic orders π and π′, it generally holds that ‖z‖2π 6= ‖z‖2π′ . Note that the coefficients in ‖z‖2π are delicately designed for technical reasons (see Lemma 1 and its proof in the appendix). The order-specific norm facilitates the performance comparison between two orderings.

heading: 3 Convergence Analysis

text: In this section we establish the convergence rate of Prox-DFinito with cyclic sampling and random reshuffling in convex and strongly convex scenarios, respectively.

heading: 3.1 The convex scenario

text:
We first study the convex scenario under the following assumption: Assumption 1 (Convex). Each function fi(x) is convex and L-smooth.
It is worth noting that the convergence results on cyclic sampling and random reshuffling for the convex scenario are quite limited except for [22, 33, 5, 18].
Cyclic sampling and shuffling-once. We first introduce the following lemma showing that Tπ is non-expansive with respect to ‖ · ‖π , which is fundamental to the convergence analysis. Lemma 1. Under Assumption 1, if step-size 0 < α ≤ 2L and the data is sampled with a fixed cyclic order π, it holds that (see proof in Appendix C.1)
‖Tπu− Tπv‖2π ≤ ‖u− v‖2π, ∀u,v ∈ Rnd. (11)
Recall (6) that the sequence zkn is generated through z(k+1)n = Sπz(kn). Since Sπ = (1−θ)I+θTπ and Tπ is non-expansive, we can prove the distance ‖z(k+1)n−z(kn)‖2 will converge to 0 sublinearly: Lemma 2. Under Assumption 1, if step-size 0 < α ≤ 2L and the data is sampled with a fixed cyclic order π, it holds for any k = 0, 1, · · · that (see proof in Appendix
‖z(k+1)n − zkn‖2π ≤ θ
(k + 1)(1− θ) ‖z0 − z?‖2π (12)
where θ ∈ (0, 1) is the damping parameter.
With Lemma 2 and the relation between xt and zt in (7), we can establish the convergence rate: Theorem 1. Under Assumption 1, if step-size 0 < α ≤ 2L and the data is sampled with a fixed cyclic order π, it holds that (see proof in Appendix C.3)
min g∈∂ r(xkn)
‖∇F (xkn)+g‖2≤ CL 2
(k+1)θ(1−θ) (13)
where θ ∈ (0, 1) and C = (
2 αL )2 log(n)+1 n ‖z
0 − z?‖2π . Remark 2. Inspired by reference [16], one can take expectation over cyclic order π in (13) to obtain the convergence rate of Prox-DFinito shuffled once before training begins (with C =(
2 αL )2 (n+1)(log(n)+1) 2n2 ‖z 0 − z?‖2):
E min g∈∂ r(xkn)
‖∇F (xkn)+g‖2≤ CL 2
(k+1)θ(1−θ) (14)
Random reshuffling. We let τk denote the sampling order used in the k-th epoch. Apparently, τk is a uniformly distributed random variable with n! realizations. With the similar analysis technique, we can also establish the convergence rate under random reshuffling in the expectation sense. Theorem 2. Under Assumption 1, if step-size 0 < α ≤ 2L and data is sampled with random reshuffling, it holds that (see proof in Appendix D.2)
E min g∈∂ r(xkn)
‖∇F (xkn)+g‖2≤ CL 2
(k+1)θ(1−θ) (15)
where θ ∈ (0, 1) and C = (
5 3αL )2 1 n‖z 0 − z?‖2.
Comparing (15) with (13), it is observed that random reshuffling replaces the constant ‖z0 − z?‖2π by ‖z0 − z?‖2 and removes the log(n) term in the upper bound.

heading: 3.2 The strongly convex scenario

text:
In this subsection, we study the convergence rate of Prox-DFinito under the following assumption: Assumption 2 (Strongly Convex). Each function fi(x) is µ-strongly convex and L-smooth. Theorem 3. Under Assumption 2, if step-size 0 < α ≤ 2µ+L , it holds that (see proof in Appendix E)
(E) ‖xkn − x?‖2 ≤ ( 1− 2θαµL
µ+ L
)k C (16)
where θ ∈ (0, 1) and
C=
{ log(n)+1
n ‖z 0−z?‖2π with π-order cyclic sampling,
1 n‖z 0 − z?‖2 with random reshuffling.
Remark 3. Note when θ → 1, Prox-DFinito actually reaches the best performance, so damping is essentially not necessary in strongly convex scenario.

heading: 3.3 Comparison with the existing results

text:
Recalling ‖z‖2π = ∑n i=1 i n‖zπ(i)‖ 2, it holds that
1 n ‖z‖2 ≤ ‖z‖2π ≤ ‖z‖2, ∀z, π. (17)
For a fair comparison with existing works, we consider the worst case performance of cyclic sampling by relaxing ‖z0−z?‖2π to its upper bound ‖z0−z?‖2. Letting α = O(1/L), θ = 1/2 and assuming 1 n‖z 0 − z?‖2 = O(1), the convergence rates derived in Theorems 1–3 reduce to
C-Cyclic = Õ ( L2/k ) , C-RR = O ( L2/k ) SC-Cyclic = Õ ( (1− 1/κ)k ) , SC-RR = O ( (1− 1/κ)k ) .
where “C” denotes “convex” and “SC” denotes “strongly convex”, κ = L/µ, and Õ(·) hides the log(n) factor. Note that all rates are in the epoch-wise sense. These rates can be translated into the the gradient complexity (equivalent to sample complexity) of Prox-DFinito to reach an -accurate solution. The comparison with existing works are listed in Table 1.
Different metrics. Except for [5] and our Prox-DFinito algorithm whose convergence analyses are based on the gradient norm in the convex and smooth scenario, results in other references are based on function value metric (i.e., objective error F (xkn)− F (x?)). The function value metric can imply the gradient norm metric, but not always vice versa. To comapre Prox-DFinito with other established results in the same metric, we have to transform the rates in other references into the gradient norm metric. The comparison is listed in Table 1. When the gradient norm metric is used, we observe that the rates of Prox-DFinito match that with gradient descent, and are state-of-the-art compared to the existing results. However, the rate of Prox-DFinito in terms of the function value is not known yet (this unknown rate may end up being worse than those of the other methods).
For the non-smooth scenario, our metric ming∈∂r(x) ‖∇F (x) + ∂r(x)‖2 may not be bounded by the functional suboptimality F (x) + r(x)− F (x?)− r(x?), and hence Prox-DFinito results are not comparable with those in [21, 35, 37, 33, 18]. The results listed in Table 1 are all for the smooth scenario of [21, 35, 37, 33, 18], and we use “Support Prox” to indicate whether the results cover the non-smooth scenario or not.
Assumption scope. Except for references [18, 35] and Proximal GD algorithm whose convergence analyses are conducted by assuming the average of each function to be L̄-smooth (and perhaps µ̄-strongly convex), results in other references are based on a stronger assumption that each summand function to be L-smooth (and perhaps µ-strongly convex). Note that L̄ can be much smaller than L sometimes. To compare [18, 35] and Proximal GD with other references under the same assumption, we let each L = L̄ in Table 1. However, it is worth noting that when each Li is drastically different from each other and can be evaluated precisely, the results relying on L̄ (e.g., [35] and [18]) can be much better than the results established in this work.
Comparison with GD. It is observed from Table 1 that Prox-DFinito with cyclic sampling or random reshuffling is no-worse than Proximal GD. It is the first no-worse-than-GD result, besides the independent and concurrent work [18], that covers both the non-smooth and the convex scenarios for variance-reduction methods under without-replacement sampling orders. The pioneering work DIAG [23] established a similar result only for smooth and strongly-convex problems2.
Comparison with RR/CS methods. Prox-DFinito achieves the nearly state-of-the-art gradient complexity in both convex and strongly convex scenarios (except for the convex and smooth case due to the weaker metric adopted) among known without-replacement stochastic approaches to solving the finite-sum optimization problem (1), see Table 1. In addition, it is worth noting that in Table 1, algorithms of [33, 35, 23] and our Prox-DFinito have an O(nd) memory requirement while others only need O(d) memory. In other words, Prox-DFinito is memory-costly in spite of its superior theoretical convergence rate and sample complexity.
Comparison with uniform-iid-sampling methods. It is known that uniform-sampling variancereduction can achieve anO(max{n,L/µ} log(1/ )) sample complexity for strongly convex problems [14, 26, 6] and O(L2/ ) (when using metric E‖∇F (x)‖2) for convex problems [26]. In other words, these uniform-sampling methods have sample complexities that are independent of sample size n. Our achieved results (and other existing results listed in Table 1 and [18]) for random reshuffling or worstcase cyclic sampling cannot match with uniform-sampling yet. However, this paper establishes that Prox-DFinito with the optimal cyclic order, in the highly data-heterogeneous scenario, can achieve an Õ(L2/ ) sample complexity in the convex scenario, which matches with uniform-sampling up to a log(n) factor, see the detailed discussion in Sec. 4. To our best knowledge, it is the first result, at least in certain scenarios, that variance reduction under without-replacement sampling orders can match with its uniform-sampling counterpart in terms of their sample complexity upper bound. Nevertheless, it still remains unclear how to close the gap in sample complexity between variance reduction under without-replacement sampling and uniform sampling in the more general settings (i.e., settings other than highly data-heterogeneous scenario).
2While DIAG is established to outperform gradient descent in [23], we find its convergence rate is still on the same order of GD. Its superiority to GD comes from the constant improvement, not order improvement.

heading: 4 Optimal Cyclic Sampling Order

text: Sec.3.3 examines the worst case gradient complexity of Prox-DFinito with cyclic sampling, which is worse than random reshuffling by a factor of log(n) in both convex and strongly convex scenarios. In this section we examine how Prox-DFinito performs with optimal cyclic sampling.

heading: 4.1 Optimal cyclic sampling

text:
Given sample size n, step-size α, epoch index k, and constants L, µ and θ, it is derived from Theorem 1 that the rate of π-order cyclic sampling is determined by constant
‖z0 − z?‖2π = n∑ i=1 i n ‖z0π(i) − z ? π(i)‖ 2. (18)
We define the corresponding optimal cyclic order as follows. Definition 2. An optimal cyclic sampling order π? of Prox-DFinito is defined as
π? := arg min π {‖z0 − z?‖2π}. (19)
Such an optimal cyclic order can be identified as follows (see proof in Appendix F). Proposition 4. The optimal cyclic order for Prox-DFinito is the reverse order of {‖z0i − z?i ‖2}ni=1. Remark 4 (IMPORTANCE INDICATOR). Proposition 4 implies that ‖z0i − z?i ‖2 can be used as an importance indicator of sample i. Recall z?i = x
? − α∇fi(x?) from Remark 1. If z0i is initialized as 0, the importance indicator of sample i reduces to ‖x? − α∇fi(x?)‖2, which is determined by both x? and∇fi(x?). If z0i is initialized close to x?, we then have ‖z0i − z?i ‖2 ≈ α2‖∇fi(x?)‖2. In other words, the importance of sample i can be measured by ‖∇fi(x?)‖, which is consistent with the importance indicator in uniform-iid-sampling [41, 40].

heading: 4.2 Optimal cyclic sampling can achieve sample-size-independent complexity

text:
Recall from Theorem 1 that the sample complexity of Prox-DFinito with cyclic sampling in the convex scenario is determined by (log(n)/n)‖z0 − z?‖2π . From (17) we have
1 n ‖z0 − z?‖2 ≤ ‖z0 − z?‖2π ≤ ‖z0 − z?‖2, ∀z, π. (20)
In Sec. 3.3 we considered the worst case performance of cyclic sampling, i.e., we bound ‖z0 − z?‖2π with its upper bound ‖z0 − z?‖2. In this section, we will examine the best case performance using the lower bound ‖z0 − z?‖2/n, and provide a scenario in which such best case performance is achievable. We assume ‖z0 − z?‖2/n = O(1) as in previous sections. Proposition 5. Given fixed constants n, α, k, θ, L, and optimal cyclic order π?, if the condition
ρ := ‖z0 − z?‖2π? ‖z0 − z?‖2 = O ( 1 n ) (21)
holds, then Prox-DFinito with optimal cyclic sampling achieves sample complexity Õ(L2/ ).
The above proposition can be proved by directly substituting (21) into Theorem 1. In the following, we discuss a data-heterogeneous scenario in which relation (21) holds.
A data-heterogeneous scenario. To this end, we let x? = col{x?, · · · , x?} and ∇f(x?) = col{∇f1(x?), · · · ,∇fn(x?)}, it follows from Remark 1 that z? = x? − α∇f(x?). If we set z0 = 0 (which is common in the implementation) and α = 1/L (the theoretically suggested step-size), it then holds that ‖z0i − z?i ‖2 = ‖x? − ∇fi(x?)/L‖2. Next, we assume ‖z0i − z?i ‖2 = ‖x? − ∇fi(x?)/L‖2 = nβi−1 (0 < β < 1) holds. Under such assumption, the optimal cyclic order will be π? = (1, 2, · · · , n). Now we examine ‖z0 − z?‖2π? and ‖z0 − z?‖2:
n∑ i=1 ‖z0i − z?i ‖2 = n n∑ i=1 βi−1 ≈ n 1− β , n∑ i=1 i n ‖z0i − z?i ‖2 = n∑ i=1 iβi−1 ≈ 1 (1− β)2
when n is large, which implies that ρ = ‖z0 − z?‖2π?/‖z0 − z?‖2 = O(1/n) since β is a constant independent of n. With Proposition 5, we know Prox-DFinito with optimal cyclic sampling can achieve Õ(L2/ ), which is independent of sample size n. Note that ‖∇fi(x?)‖2 = nβi−1 implies a data-heterogeneous scenario where β can roughly gauge the variety of data samples.

heading: 4.3 Adaptive importance reshuffling

text:
Algorithm 2 Adaptive Importance Reshuffling Initialize: w0(i) = ‖z0i − z̄0‖2 for i ∈ [n]; for epoch k = 0, 1, 2, · · · do
Reshuffle [n] based on the vector wk; Update a Prox-DFinito epoch; Update wk+1 according to (22);
end for
The optimal cyclic order decided by Proposition 4 is not practical since the importance indicator of each sample depends on the unknown z?i = x?−α∇fi(x?). This problem can be overcome by replacing z?i by its estimate z kn i , which leads to an adaptive importance reshuffling strategy.
We introduce w ∈ Rn as an importance indicating vector with each element wi indicating the importance of sample i and initialized as w0(i) = ‖z0i − z̄0‖2, ∀ i ∈ [n]. In the k-th epoch, we draw sample i earlier if wk(i) is larger. After the k-th epoch, w will be updated as
wk+1(i) = (1− γ)wk(i) + γ‖z0i − z (k+1)n i ‖ 2, (22)
where i ∈ [n] and γ ∈ (0, 1) is a fixed damping parameter. Suppose zkni → z?i , the above recursion will guarantee wk(i)→ ‖z0i − z?i ‖2. In other words, the order decided by wk will gradually adapt to the optimal cyclic order as k increases. Since the order decided by importance changes from epoch to epoch, we call this approach adaptive importance reshuffling and list it in Algorithm 2. We provide the convergence guarantees of the adaptive importance reshuffling method in Appendix G.

heading: 5 Numerical Experiments

heading: 5.1 Comparison with SVRG and SAGA under without-replacement sampling orders

text:
In this experiment, we compare DFinito with SVRG [14] and SAGA [7] under without-replacement sampling (RR, cyclic sampling). We consider a similar setting as in [18, Figure 2], where all step sizes are chosen as the theoretically optimal one, see Table 2 in Appendix H. We run experiments for the regularized logistic regression problem, i.e. problem (1) with fi(x) = log (1 + exp(−yi〈wi, x〉)) + λ 2 ‖x‖
2 with three widely-used datasets: CIFAR-10 [15], MNIST [8], and COVTYPE [29]. This problem is L-smooth and µ-strongly convex with L = 14nλmax(W
TW )+λ and µ = λ. From Figure 1, it is observed that DFinito outperforms SVRG and SAGA in terms of gradient complexity under without-replacement sampling orders with their best-known theoretical rates. The comparison with SVRG and SAGA with the practically optimal step sizes is in Appendix J.

heading: 5.2 DFinito with cyclic sampling

text:
Justification of the optimal cyclic sampling order. To justify the optimal cyclic sampling order π? suggested in Proposition 4, we test DFinito with eight arbitrarily-selected cyclic orders, and compare them with the optimal cyclic ordering π? as well as the adaptive importance reshuffling method (Algorithm 2). To make the comparison distinguishable, we construct a least square problem with heterogeneous data samples with n = 200, d = 50, L = 100, µ = 10−2 (see Appendix I for the constructed problem). The constructed problem is with ρ = ‖z0−z?‖2π∗/‖z0−z?‖22 = 0.006 when z0i = 0, x
0 = 0, and α = 13L , which is close to 1/n = 0.005. In the left plot in Fig. 2, it is observed that the optimal cyclic sampling achieves the fastest convergence rate. Furthermore, the adaptive
shuffling method can match with the optimal cyclic ordering. These observations are consistent with our theoretical results derived in Sec. 4.2 and 4.3.
Optimal cyclic sampling can achieve sample-size-independent complexity. It is established in [26] that Finito with uniform-iid-sampling can achieve n-independent gradient complexity with α = n8L . In this experiment, we compare DFinito (α = 2 L ) with Finito under uniform sampling (8 runs, α = n8L ) in a convex and highly heterogeneous scenario (ρ = O( 1 n )). The constructed problem is with n = 500, d = 20, L = 0.3, θ = 0.5 and ‖z0i −z?i ‖ = 10000∗0.1i−1, 1 ≤ i ≤ n (see detailed initialization in Appendix J). We also depict DFinito with random-reshuffling (8 runs) as another baseline. In the right plot of Figure 2, it is observed that the convergence curve of DFinito with π?-cyclic sampling matches with Finito with uniform sampling. This implies DFinito can achieve the same n-independent gradient complexity as Finito with uniform sampling.

heading: 5.3 More experiments

text: We conduct more experiments in Appendix J. First, we compare DFinito with GD/SGD to justify its empirical superiority to these methods. Second, we validate how different data heterogeneity will influence optimal cyclic sampling. Third, we examine the performance of SVRG, SAGA, and DFinito under without/with-replacement sampling using grid-search (not theoretical) step sizes.

heading: 6 Conclusion and Discussion

text: This paper develops Prox-DFinito and analyzes its convergence rate under without-replacement sampling in both convex and strongly convex scenarios. Our derived rates are state-of-the-art compared to existing results. In particular, this paper derives the best-case convergence rate for ProxDFinito with cyclic sampling, which can be sample-size-independent in the highly data-heterogeneous scenario. A future direction is to close the gap in gradient complexity between variance reduction under without-replacement and uniform-iid-sampling in the more general setting.

title: Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders