Unifying Framework for Accelerated Randomized Methods in Convex Optimization
Pavel Dvurechensky Alexander Gasnikov Alexander Tiurin Vladimir Zholobov
math.OC cs.NA math.NA 90C25, 90C30, 90C06, 90C56, 68Q25, 65K05, 49M27, 68W20, 65Y20, 68W40 G.1.6


A New Framework for
Synthetic Aperture Sonar Micronavigation
    Salvatore Caporale and Yvan Petillot
S. Caporale  and Y. Petillot are with the Institute of Sensors, Signals and Systems, Heriot-Watt University, Edinburgh, Scotland, UK (e-mail: s.caporale@hw.ac.uk; y.r.petillot@hw.ac.uk).
    December 30, 2023
===================================================================================================================================================================================================================================





	In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. We focus on accelerated random block-coordinate descent, accelerated random directional search, accelerated random derivative-free method and, using our framework, provide their versions for problems with inexact oracle information. Our contribution also includes accelerated random block-coordinate descent with inexact oracle and entropy proximal setup as well as derivative-free version of this method. Moreover, we present an extension of our framework for strongly convex optimization problems.
	
	


















§ INTRODUCTION


In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as objective value, partial or directional derivatives of the objective function.
Different types of randomized optimization algorithms, such as random coordinate descent or stochastic gradient descent for empirical risk minimization problem, have been extensively studied in the past decade with the main application being large-scale convex optimization problems. Our main focus in this paper is on accelerated randomized methods: random block-coordinate descent, random directional search, random derivative-free method. As opposed to non-accelerated methods, these methods have complexity proportional to 1/√() iterations to achieve objective function residual , as opposed to 1/ for non-accelerated methods. Accelerated random block-coordinate descent method was first proposed in <cit.>, which was the starting point for active research in this direction. The idea of the method is, on each iteration, to randomly choose a block of coordinates in the decision variable and make a step using the derivative of the objective function with respect to the chosen coordinates. Accelerated random directional search and accelerated random derivative-free method were first proposed in 2011 and published recently in <cit.>, but there was no extensive research in this direction. The idea of random directional search is to use a projection of the objective's gradient onto a randomly chosen direction to make a step on each iteration. Random derivative-free method uses the same idea, but random projection of the gradient is approximated by finite-difference, i.e. the difference of values of the objective function in two close points. This also means that it is a zero-order method which uses only function values to make a step.  

Existing accelerated randomized methods have different convergence analysis. This motivated us to pose the main question, we address in this paper, as follows. Is it possible to find a crucial part of the convergence rate analysis and use it to systematically construct new accelerated randomized methods? To some extent, our answer is "yes". We determine three main assumptions and use them to prove convergence rate theorem for our generic accelerated randomized method. Our framework allows both to reproduce known and to construct new accelerated randomized methods. The latter include new accelerated random block-coordinate descent with inexact block derivatives and entropy proximal setup.




 §.§ Related Work

In the seminal paper <cit.>, the author proposed random block-coordinate descent for convex optimization problems with simple convex separable constraints and accelerated random block-coordinate descent for unconstrained convex optimization problems. In <cit.>, the authors proposed accelerated random block-coordinate descent with non-uniform probability of choosing a particular block of coordinates. They also developed an efficient implementation without full-dimensional operations on each iteration. The authors of <cit.> introduced accelerated block-coordinate descent for composite optimization problems, which include problems with separable constraints. Later, the paper <cit.> extended this method for strongly convex problems.  
The papers <cit.> (this work first appeared in May, 2015), <cit.> and <cit.> proposed an accelerated block-coordinate descent with complexity, which does not explicitly depend on the problem dimension. 

We also mention special type of accelerated block-coordinate descent developed in <cit.> for empirical risk minimization problems. All these accelerated block-coordinate descent methods work in Euclidean setup, when the norm in each block is Euclidean and is defined using some positive semidefinite matrix. Non-accelerated block-coordinate methods, but with non-euclidean setup, were considered in <cit.>. All the mentioned methods rely on exact block derivatives and exact projection on each step. Inexact projection in the context of non-accelerated random coordinate descent was considered in <cit.>.






Research on accelerated random directional search and accelerated random derivative­/free methods for smooth problems started in <cit.>, where also non-smooth problems were considered. Derivative-free methods for non-smooth problems were further developed in <cit.> for the case of exact computations and in <cit.> for the case of inexact function values. Non-accelerated gradient-free methods for smooth problems were developed in <cit.> for the case of exact objective value evaluation and in <cit.> for inexact values, see also extensive reviews <cit.>. Accelerated gradient-free methods with inexact oracle were introduced in <cit.> and later extended for the case of random directional search in <cit.>. The main difference with this work is that here we develop a unifying framework for all the three types of accelerated randomized methods including coordinate descent method.

We should also mention that there are other accelerated randomized methods in <cit.>. Most of these methods were developed deliberately for empirical risk minimization problems and do not fall in the scope of this paper. We also list the following works, which consider accelerated full-gradient methods with inexact oracle <cit.>.














 §.§ Our Approach and Contributions

Our framework has two main components, namely, Randomized Inexact Oracle and Unified Accelerated Randomized Method. The starting point for the definition of our oracle is a unified view on random directional search and random block-coordinate descent. In both these methods, on each iteration, a randomized approximation for the objective function's gradient is calculated and used, instead of the true gradient, to make a step. This approximation for the gradient is constructed by a projection on a randomly chosen subspace. For random directional search, this subspace is the line along a randomly generated direction. As a result a directional derivative in this direction is calculated. For random block-coordinate descent, this subspace is given by randomly chosen block of coordinates and block derivative is calculated. One of the key features of these approximations is that they are unbiased, i.e. their expectation is equal to the true gradient. We generalize two mentioned approaches by allowing other types of random transformations of the gradient for constructing its randomized approximation. 

The inexactness of our oracle is inspired by the relation between derivative-free method and directional search. In the framework of derivative-free methods, only the value of the objective function is available for use in an algorithm. At the same time, if the objective function is smooth, the directional derivative can be well approximated by the difference of function values at two points which are close to each other. Thus, in the context of zero-order optimization, one can calculate only an inexact directional derivative. Hence, one can construct only a biased randomized approximation for the gradient when a random direction is used. We combine previously mentioned random transformations of the gradient with possible inexactness of this transformations to construct our Randomized Inexact Oracle, which we use in our generic algorithm to make a step on each iteration. 

The basis of our generic algorithm is Similar Triangles Method of <cit.> (see also <cit.>), which is an accelerated gradient method with only one proximal mapping on each iteration, this proximal mapping being essentially the Mirror Descent step. The notable point is that, we only need to substitute the true gradient with our Randomized Inexact Oracle and slightly change one step in the Similar Triangles Method, to obtain our generic accelerated randomized algorithm, which we call Unified Accelerated Randomized Method (UARM), see Algorithm <ref>.
We prove convergence rate theorem for UARM in two cases: the inexactness of Randomized Inexact Oracle can be controlled and adjusted on each iteration of the algorithm, the inexactness can not be controlled.

We apply our framework to several particular settings: random directional search, random coordinate descent, random block-coordinate descent and their combinations with derivative-free approach. As a corollary of our main theorem, we obtain both known and new results on the convergence of different accelerated randomized methods with inexact oracle. 

To sum up, our contributions in this paper are as follows.

	
  * We introduce a general framework for constructing and analyzing different types of accelerated randomized methods, such as accelerated random directional search, accelerated block-coordinate descent, accelerated derivative-free methods. Our framework allows to obtain both known and new methods and their convergence rate guarantees as a corollary of our main Theorem <ref>. 
	
  * Using our framework, we introduce new accelerated methods with inexact oracle, namely, accelerated random directional search, accelerated random block-coordinate descent, accelerated derivative-free method. To the best of our knowledge, such methods with inexact oracle were not known before. See section <ref>.
	
  * Based on our framework, we introduce new accelerated random block­/coordinate descent with inexact oracle and non-euclidean setup, which was not done before in the literature. The main application of this method is minimization of functions on a direct product of large number of low-dimensional simplexes. See subsection <ref>.
	
  * We introduce new accelerated random derivative-free block-coordinate descent with inexact oracle and non-euclidean setup. Such method was not known before in the literature. Our method is similar to the method in the previous item, but uses only finite-difference approximations for block derivatives. See subsection <ref>.





The rest of the paper is organized as follows. In section <ref>, we provide the problem statement, motivate and make three our main assumptions, illustrate them by random directional search and random block-coordinate descent. In section <ref>, we introduce our main algorithm, called Unified Accelerated Randomized Method, and, based on stated general assumptions, prove convergence rate in Theorem  <ref>. Section <ref> is devoted to applications of our general framework for different particular settings, namely

	
  * Accelerated Random Directional Search (<ref>),
	
  * Accelerated Random Coordinate Descent (<ref>),
	
  * Accelerated Random Block-Coordinate Descent (<ref>),
	
  * Accelerated Random Derivative-Free Directional Search (<ref>),
	
  * Accelerated Random Derivative-Free Coordinate Descent (<ref>),
	
  * Accelerated Random Derivative-Free Block-Coordinate Descent 
	(<ref>).
	
  * Accelerated Random Derivative-Free Block-Coordinate Descent with Random Approximations for Block Derivatives (<ref>).





§ PRELIMINARIES





 §.§ Notation


Let finite-dimensional real vector space E be a direct product of n finite-dimensional real vector spaces E_i, i=1,...,n, i.e. E=⊗_i=1^n E_i and dim E_i = p_i, i=1,...,n. Denote also p=∑_i=1^n p_i. Let, for i=1,...,n, E_i^* denote the dual space for E_i. Then, the space dual to E is E^*=⊗_i=1^n E_i^*. Given a vector x^(i)∈ E_i for some i ∈ 1,...,n, we denote as [x^(i)]_j its j-th coordinate, where j ∈ 1,...,p_i.
To formalize the relationship between vectors in E_i, i=1,...,n and vectors in E, we define primal partition operators U_i : E_i → E, i=1,...,n, by identity

    x = (x^(1),...,x^(n)) = ∑_i=1^n U_i x^(i),    x^(i)∈ E_i,    i=1,...,n,    x ∈ E.

For any fixed i ∈ 1,...,n, U_i maps a vector x^(i)∈ E_i, to the vector (0,....,x^(i),...,0) ∈ E. The adjoint operator U_i^T: E^* → E_i^*, then, is an operator, which, maps a vector g = (g^(1),...,g^(i),..., g^(n)) ∈ E^*, to the vector g^(i)∈ E_i^*. 
Similarly, we define dual partition operators U_i : E_i^* → E^*, i=1,...,n, by identity

    g = (g^(1),...,g^(n)) = ∑_i=1^n U_i g^(i),    g^(i)∈ E_i^*,    i=1,...,n,    g ∈ E^*.

For all i=1,...,n, we denote the value of a linear function g^(i)∈ E_i^* at a point x^(i)∈ E_i by g^(i), x^(i)_i. We define 

    g, x  = ∑_i=1^n  g^(i), x^(i)_i,    x ∈ E,    g ∈ E^*.

For all i=1,...,n, let ·_i be some norm on E_i and ·_i,* be the norm on E_i^* which is dual to ·_i

    g^(i)_i,* = max_x^(i)_i ≤ 1 g^(i), x^(i)_i.

Given parameters β_i ∈^n_++, i=1,...,n, we define the norm of a vector x=(x^(1),...,x^(n)) ∈ E as 

    x_E^2 = ∑_i=1^n β_i x^(i)_i^2.
 
Then, clearly, the dual norm of a vector g=(g^(1),...,g^(n)) ∈ E^* is 

    g_E,*^2 = ∑_i=1^n β_i^-1g^(i)_i^2.
 
Throughout the paper, we consider optimization problem with feasible set Q, which is assumed to be given as Q=⊗_i=1^n Q_i ⊆ E, where Q_i ⊆ E_i, i=1,...,n are closed convex sets.  
To have more flexibility and be able to adapt algorithm to the structure of sets Q_i, i=1,...,n, we introduce proximal setup, see e.g. <cit.>.
For all i=1,...,n, we choose a prox-function d_i(x^(i)) which is continuous, convex on Q_i and

	
  * admits a continuous in x^(i)∈ Q_i^0 selection of subgradients 	∇ d_i(x^(i)), where x^(i)∈ Q_i^0 ⊆ Q_i, and Q_i^0  is the set of all x^(i), where ∇ d_i(x^(i)) exists;
	
  * is 1-strongly convex on Q_i with respect to ·_i, i.e., for any x^(i)∈ Q_i^0, y^(i)∈ Q_i, it holds that d_i(y^(i))-d_i(x^(i)) -∇ d_i(x^(i)) ,y^(i)-x^(i)_i ≥1/2y^(i)-x^(i)_i^2.
 
We define also the corresponding Bregman divergence V_i[z^(i)] (x^(i)) := d_i(x^(i)) - d_i(z^(i)) - ∇ d_i(z^(i)), x^(i) - z^(i)_i, x^(i)∈ Q_i, z^(i)∈ Q_i^0, i=1,...,n. 
It is easy to see that V_i[z^(i)] (x^(i)) ≥1/2x^(i) - z^(i)_i^2,    x^(i)∈ Q_i, z^(i)∈ Q_i^0, i=1,...,n.
Standard proximal setups, e.g. Euclidean, entropy, ℓ_1/ℓ_2, simplex can be found in <cit.>. It is easy to check that, for given parameters β_i ∈^n_++, i=1,...,n, the functions d(x) = ∑_i=1^n β_i d_i(x^(i)) and V[z] (x) = ∑_i=1^n β_i V_i[z^(i)] (x^(i)) are respectively a prox-function and a Bregman divergence corresponding to Q. 
Also, clearly,

    V[z] (x) ≥1/2x - z_E^2,    x ∈ Q,    z ∈ Q^0 := ⊗_i=1^n Q_i^0.

For a differentiable function f(x), we denote by ∇ f(x) ∈ E^* its gradient. 






 §.§ Problem Statement and Assumptions



The main problem, we consider, is as follows

    min_x∈ Q ⊆ E  f(x),

where f(x) is a smooth convex function, Q=⊗_i=1^n Q_i ⊆ E, with Q_i ⊆ E_i, i=1,...,n being closed convex sets. 

We now list our main assumptions and illustrate them by two simple examples. More detailed examples are given in section <ref>. As the first example here, we consider random directional search, in which the gradient of the function f is approximated by a vector ∇ f(x) , e  e, where ∇ f(x) , e is the directional derivative in direction e and random vector e is uniformly distributed over the Euclidean sphere of radius 1. Our second example is random block-coordinate descent, in which the gradient of the function f is approximated by a vector U_iU_i^T ∇ f(x), where U_i^T ∇ f(x) is i-th block derivative and the block number i is uniformly randomly sampled from 1,...,n. The common part in both these randomized gradient approximations is that, first, one randomly chooses a subspace which is either the line, parallel to e, or i-th block of coordinates. Then, one projects the gradient on this subspace by calculating either ∇ f(x) , e or U_i^T ∇ f(x). Finally, one lifts the obtained random projection back to the whole space E either by multiplying directional derivative by vector e, or applying dual partition operator U_i. At the same time, in both cases, if one scales the obtained randomized approximation for the gradient by multiplying it by n, one obtains an unbiased randomized approximation of the gradient

    _e n ∇ f(x) , e  e = ∇ f(x),   _i n U_iU_i^T ∇ f(x) = ∇ f(x),    x ∈ Q.

We also want our approach to allow construction of derivative-free methods. For a function f with L-Lipschitz-continuous gradient, the directional derivative can be well approximated by the difference of function values in two close points. Namely, it holds that 

    ∇ f(x) , e   = f(x+τ e) - f(x)/τ + o(τ),

where τ > 0 is a small parameter. Thus, if only the value of the function is available, one can calculate only inexact directional derivative, which leads to biased randomized approximation for the gradient if the direction is chosen randomly. These three features, namely, random projection and lifting up, unbiased part of the randomized approximation for the gradient, bias in the randomized approximation for the gradient, lead us to the following assumption about the structure of our general Randomized Inexact Oracle.

[Randomized Inexact Oracle]
	
	We access the function f only through Randomized Inexact Oracle (x), x ∈ Q, which is given by
	
    (x) = ρ(^T∇ f(x) + ξ(x)) ∈ E^*,

	where ρ> 0 is a known constant;  is a random "`projection"' operator from some auxiliary space H to E, and, hence, ^T, acting from E^* to H^*, is the adjoint to ; : H^* → E^* is also some random "`reconstruction"' operator; ξ(x) ∈ H^* is a, possibly random, vector characterizing the error of the oracle. The oracle is also assumed to satisfy the following properties
	
    ρ^T∇ f(x) = ∇ f(x),   ∀ x ∈ Q, 
    	
       ξ(x)_E,*≤δ,   ∀ x ∈ Q,
 
	where δ≥ 0 is oracle error level.
	
	
	




Let us make some comments on this assumption. The nature of the operator ^T is generalization of random projection. 
For the case of random directional search, H =, ^T: E^* → is given by ^T g =  g, e, g ∈ E^*. For the case of random block-coordinate descent, H = E_i, ^T: E^* → E_i^* is given by ^T g = U_i^T g, g ∈ E^*. We assume that there is some additive error ξ(x) in the generalized random projection ^T ∇ f(x). This error can be introduced, for example, when finite-difference approximation of the directional derivative is used. Finally, we lift the inexact random projection ^T ∇ f(x)+ξ(x) back to E by applying operator . For the case of random directional search, : → E^* is given by t = te, t ∈. For the case of random block-coordinate descent, : E_i^* → E^* is given by g^(i) = U_i g^(i), g^(i)∈ E_i^*. The number ρ is the normalizing coefficient, which allows the part ρ^T∇ f(x) to be unbiased randomized approximation for the gradient. This is expressed by equality  (<ref>). Finally, we assume that the error in our oracle is bounded, which is expressed by property  (<ref>). In our analysis, we consider two cases: the error ξ can be controlled and δ can be appropriately chosen on each iteration of the algorithm; the error ξ can not be controlled and we only know oracle error level δ.

Let us move to the next assumption. As said, our generic algorithm is based on Similar Triangles Method of <cit.> (see also <cit.>), which is an accelerated gradient method with only one proximal mapping on each iteration. This proximal mapping is essentially the Mirror Descent step. For simplicity, let us consider here an unconstrained minimization problem in the Euclidean setting. This means that Q_i = E_i = ^p_i, x^(i)_i = x^(i)_2, i=1,...,n. Then, given a point u ∈ E, a number α, and the gradient ∇ f(y) at some point y ∈ E, the Mirror Descent step is

    u_+ = min_x ∈ E{1/2x-u_2^2 + α∇ f(y),x } = u - α∇ f(y).

Now we want to substitute the gradient ∇ f(y) with our Randomized Inexact Oracle (y). Then, we see that the step u_+ = u - α(y) makes progress only in the subspace onto which the gradient is projected, while constructing the Randomized Inexact Oracle. In other words, u - u_+ lies in the same subspace as (y). In our analysis, this is a desirable property and we formalize it as follows.
[Regularity of Prox-Mapping]
	
	The set Q, norm ·_E, prox-function d(x), and Randomized Inexact Oracle (x) are chosen in such a way that, for any u,y ∈ Q, α >0, the point
	
    u_+ = min_x ∈ Q{V[u](x) + α(y),x }

	satisfies 
	
    ^T∇ f(y), u - u_+  = ∇ f(y), u - u_+ .


The interpretation is that, in terms of linear pairing with u - u_+, the unbiased part ^T∇ f(y) of the Randomized Inexact Oracle makes the same progress as the true gradient ∇ f(y).

Finally, we want to formalize the smoothness assumption for the function f. In our analysis, we use only the smoothness of f in the direction of u_+ - u, where u ∈ Q and u_+ is defined in  (<ref>). Thus, we consider two points x,y ∈ Q, which satisfy equality x = y + a (u_+ - u), where a ∈. For the random directional search, it is natural to assume that f has L-Lipschitz-continuous gradient with respect to the Euclidean norm, i.e. 

    f(x) ≤ f(y) + ∇ f(y), x-y  + L/2x-y_2^2,    x,y ∈ Q.

Then, if we define x_E^2 = L x_2^2, we obtain that, for our choice x = y + a (u_+ - u),

    f(x) ≤ f(y) + ∇ f(y), x - y  + 1/2x-y_E^2.

Usual assumption for random block-coordinate descent is that the gradient of f is block-wise Lipschitz continuous. This means that, for all i=1,...,n, block derivative f'_i(x) = U_i^T ∇ f(x) is L_i-Lipschitz continuous with respect to chosen norm ·_i, i.e.

    f'_i(x+U_ih^(i)) - f'_i(x)_i,*≤ L_i h^(i)_i,    h^(i)∈ E_i,    i=1,...,n,    x ∈ Q.

By the standard reasoning, using  (<ref>), one can prove that, for all i=1,...,n,

    f(x+U_ih^(i)) ≤ f(x) +  U_i^T∇ f(x), h^(i) + L_i/2h^(i)_i^2,    h^(i)∈ E_i,    x ∈ Q.

In block-coordinate setting, (x) has non-zero elements only in one, say i-th, block and it follows from (<ref>) that u_+ - u also has non-zero components only in the i-th block. Hence, there exists h^(i)∈ E_i, such that u_+ - u = U_i h_i and x = y + a U_i h^(i).
Then, if we define x_E^2 = ∑_i=1^n L_i x^(i)_i^2, we obtain

    f(x)  = f(y + a U_i h^(i))     (<ref>)≤  f(y) +  U_i^T∇ f(y), a h^(i) + L_i/2a h^(i)_i^2 
        = f(y) + ∇ f(y), a U_i h^(i) + 1/2a U_i h^(i)_E^2  
        = f(y) + ∇ f(y), x - y  + 1/2x-y_E^2.

We generalize these two examples and assume smoothness of f in the following sense.
[Smoothness]	
    The norm ·_E is chosen in such a way that, for any u,y ∈ Q, a ∈, if x = y + a (u_+ - u) ∈ Q, then
	
    f(x) ≤ f(y) + ∇ f(y), x - y  + 1/2x-y_E^2.








§ UNIFIED ACCELERATED RANDOMIZED METHOD


In this section, we introduce our generic Unified Accelerated Randomized Method, which is listed as algorithm <ref> below, and prove <ref>, which gives its convergence rate. The method is constructed by a modification of Similar Triangles Method (see <cit.>) and, thus, inherits part of its name. 








	Algorithm <ref> is correctly defined in the sense that, for all k≥ 0, x_k,y_k ∈ Q.
	



	The proof is a direct generalization of Lemma 2 in <cit.>. By definition  (<ref>), for all k≥ 0, u_k ∈ Q. If we prove that, for all k≥ 0, x_k ∈ Q, then, from  (<ref>), it follows that, for all k≥ 0, y_k ∈ Q. Let us prove that, for all k≥ 0, x_k is a convex combination of u_0 … u_k, namely x_k = ∑_l=0^kγ_k^l u_l, where γ_0^0 = 1, γ_1^0 = 0, γ_1^1 = 1, and for k ≥ 1,
	
    γ_k+1^l =(1 - α_k+1/A_k+1)γ_k^l,     l = 0,…,k - 1 
    α_k+1/A_k+1(1 - ρα_k/A_k) + ρ(α_k/A_k - α_k+1/A_k+1),    l = k 
    ρα_k+1/A_k+1,    l = k+1.

	Since, x_0=u_0, we have that γ_0^0 = 1. Next, by  (<ref>), we have x_1 = y_1 + ρα_1/A_1 (u_1 - u_0) = u_0 + ρα_1/A_1 (u_1 - u_0) = (1 - ρα_1/A_1) u_0 + ρα_1/A_1 u_1. Solving the equation  (<ref>) for k=0, and using the choice α_0 = 1 - 1/ρ, we obtain that α_1 = 1/ρ and
	
    α_1/A_1 (<ref>)=α_1/ρ^2 α_1^2 = 1/ρ.

	Hence, x_1=u_1 and	γ_1^0 = 0, γ_1^1 = 1. Let us now assume that x_k = ∑_l=0^kγ_k^l u_l and prove that x_k+1 is also a convex combination with coefficients, given by  (<ref>).
	From  (<ref>),  (<ref>), we have 
	
    x_k+1 = y_k+1 + ρα_k+1/A_k+1 (u_k+1 - u_k) = α_k+1u_k + A_k x_k/A_k+1 + ρα_k+1/A_k+1 (u_k+1 - u_k) 
     =
    	A_k/A_k+1x_k + (α_k+1/A_k+1 - ρα_k+1/A_k+1)u_k + ρα_k+1/A_k+1u_k+1
     = (1 - α_k+1/A_k+1) ∑_l = 0^kγ_k^l u_l + (α_k+1/A_k+1 - ρα_k+1/A_k+1)u_k + ρα_k+1/A_k+1u_k+1.

	Note that all the coefficients sum to 1.
	Next, we have 
	
    x_k+1 =   (1 - α_k+1/A_k+1) ∑_l = 0^k-1γ_k^l u_l
       + (γ_k^k (1 - α_k+1/A_k+1) + (α_k+1/A_k+1 - ρα_k+1/A_k+1))u_k + ρα_k+1/A_k+1u_k+1
       =
    	(1 - α_k+1/A_k+1) ∑_l = 0^k-1γ_k^l u_l
       + (ρα_k/A_k(1 - α_k+1/A_k+1) + (α_k+1/A_k+1 - ρα_k+1/A_k+1))u_k + ρα_k+1/A_k+1u_k+1
       =(1 - α_k+1/A_k+1) ∑_l = 0^k-1γ_k^l u_l
       + (α_k+1/A_k+1(1 - ρα_k/A_k) + ρ(α_k/A_k -α_k+1/A_k+1))u_k + ρα_k+1/A_k+1u_k+1.

	So, we see that  (<ref>) holds for k+1. It remains to show that γ_k+1^l ≥ 0, l = 0,…,k+1.
	For γ_k+1^l, l = 0,…,k-1 and γ_k+1^k+1 it is obvious. From  (<ref>), we have
	
    α_k+1 = 1+√(1+4 ρ^2 A_k)/2 ρ^2.

	Thus, since {A_k}, k≥ 0 is non-decreasing sequence, {α_k+1}, k≥ 0 is also non-decreasing. From  (<ref>), we obtain α_k+1/A_k+1 = α_k+1/ρ^2α_k+1^2, which means that this sequence is non-increasing. Thus, α_k/A_k≥α_k+1/A_k+1 and α_k/A_k≤α_1/A_1≤1/ρ for k ≥ 1. These inequalities prove that γ_k+1^k≥ 0.	




	
	Let the sequences {x_k, y_k, u_k, α_k, A_k }, k≥ 0 be generated by algorithm <ref>. Then,  for all u ∈ Q, it holds that
	
    α_k+1(y_k+1), u_k - u≤     A_k+1(f(y_k+1) - f(x_k+1)) + V[u_k](u) - V[u_k+1](u) 
        + α_k+1ρξ(y_k+1), u_k - u_k+1.
	



	Using assumptions <ref> and <ref> with α = α_k+1, y=y_k+1, u=u_k, u_+ = u_k+1, we obtain
	
    α_k+1(y_k+1), u_k - u_k+1    (<ref>)=α_k+1ρ(^T∇ f(y_k+1) + ξ(y_k+1)), u_k - u_k+1
        (<ref>)=α_k+1ρ∇ f(y_k+1), u_k - u_k+1  + α_k+1ρξ(y_k+1), u_k - u_k+1
        (<ref>)= A_k+1∇ f(y_k+1), y_k+1 - x_k+1  + α_k+1ρξ(y_k+1), u_k - u_k+1.
	
	Note that, from the optimality condition in  (<ref>), for any u ∈ Q, we have
	
    ∇ V[u_k](u_k+1) + α_k+1(y_k+1), u - u_k+1≥ 0.

	By the definition of V[u](x), we obtain, for any u ∈ Q,
	
    V[u_k](u) - V[u_k+1](u) - V[u_k](u_k+1)  =    d(u) - d(u_k) - ∇ d(u_k), u-u_k 
       - ( d(u) - d(u_k+1) - ∇ d(u_k+1), u-u_k+1) 
       - ( d(u_k+1) - d(u_k) - ∇ d(u_k), u_k+1-u_k ) 
        = ∇ d(u_k) - ∇ d(u_k+1) , u_k+1 - u 
        =  - ∇ V[u_k](u_k+1) , u_k+1 - u .

	Further, for any u ∈ Q, by assumption <ref>,
	
    α_k+1(y_k+1), u_k - u    = α_k+1(y_k+1), u_k - u_k+1 + α_k+1(y_k+1), u_k+1 - u
        (<ref>)≤α_k+1(y_k+1), u_k - u_k+1 +  -∇ V[u_k](u_k+1) , u_k+1 - u  
        (<ref>)=α_k+1(y_k+1), u_k - u_k+1 + V[u_k](u) - V[u_k+1](u) - V[u_k](u_k+1) 
        (<ref>)≤α_k+1(y_k+1), u_k - u_k+1 + V[u_k](u) - V[u_k+1](u) - 1/2u_k-u_k+1_E^2 
        (<ref>), (<ref>)= A_k+1∇ f(y_k+1), y_k+1 - x_k+1  + α_k+1ρξ(y_k+1), u_k - u_k+1 + 
        + V[u_k](u) - V[u_k+1](u) - A_k+1^2/2ρ^2 α_k+1^2y_k+1 - x_k+1_E^2 
        (<ref>)= A_k+1(∇ f(y_k+1), y_k+1 - x_k+1 - 1/2y_k+1 - x_k+1_E^2  ) + 
        + α_k+1ρξ(y_k+1), u_k - u_k+1 + V[u_k](u) - V[u_k+1](u) 
        (<ref>), (<ref>)≤ A_k+1(  f(y_k+1) - f(x_k+1)  )  + V[u_k](u) - V[u_k+1](u) +
        +α_k+1ρξ(y_k+1), u_k - u_k+1.

	In the last inequality, we used assumption <ref> with a=ρα_k+1/A_k+1, x=x_k+1, y=y_k+1, u=u_k, u_+=u_k+1.




	
	Let the sequences {x_k, y_k, u_k, α_k, A_k }, k≥ 0 be generated by Algorithm <ref>. Then,  for all u ∈ Q, it holds that
	
    α_k+1∇ f(y_k+1), u_k - u≤      A_k+1(f(y_k+1) - _k+1f(x_k+1)) + V[u_k](u) 
        - _k+1V[u_k+1](u) 
    	+ 	_k+1α_k+1ρξ(y_k+1), u - u_k+1,
	
	where _k+1 denotes the expectation conditioned on all the randomness up to step k. 



	First, for any u∈ Q, by assumption <ref>, 
	
    _k+1α_k+1(y_k+1), u_k - u    (<ref>)=_k+1α_k+1ρ(^T∇ f(y_k+1) + ξ(y_k+1)), u_k - u 
        (<ref>)=α_k+1∇ f(y_k+1), u_k - u 
       + _k+1α_k+1ρξ(y_k+1), u_k - u .
	
	Taking conditional expectation _k+1 in  (<ref>) of Lemma <ref> and using  (<ref>), we obtain the statement of the Lemma.	




	Let the sequences {x_k, y_k, u_k, α_k, A_k }, k≥ 0 be generated by Algorithm <ref>. Then,  for all u ∈ Q, it holds that
	
    A_k+1_k+1f(x_k+1) - A_kf(x_k) ≤     α_k+1( f(y_k+1) + ∇ f(y_k+1), u - y_k+1) + V[u_k](u)  
    
    	   - _k+1V[u_k+1](u) 
       + _k+1α_k+1ρξ(y_k+1), u - u_k+1.

	



	For any u ∈ Q,
	
    α_k+1∇ f(y_k+1), y_k+1 - u   = α_k+1∇ f(y_k+1), y_k+1 - u_k  + α_k+1∇ f(y_k+1), u_k - u
        (<ref>), (<ref>)= A_k∇ f(y_k+1), x_k - y_k+1 + α_k+1∇ f(y_k+1), u_k - u
       conv-ty≤ A_k(f(x_k) - f(y_k+1) ) + α_k+1∇ f(y_k+1), u_k - u
        (<ref>)≤ A_k(f(x_k) - f(y_k+1) ) + A_k+1(f(y_k+1) - _k+1f(x_k+1)) + 
        + V[u_k](u) - _k+1V[u_k+1](u) + 	_k+1α_k+1ρξ(y_k+1), u - u_k+1
    
    	
    	    (<ref>)=α_k+1 f(y_k+1) + A_kf(x_k) - A_k+1_k+1f(x_k+1) + V[u_k](u) 
       - _k+1V[u_k+1](u)  + 	_k+1α_k+1ρξ(y_k+1), u - u_k+1.

	Rearranging terms, we obtain the statement of the Lemma.



	Let the assumptions <ref>, <ref>, <ref> hold. Let the sequences {x_k, y_k, u_k, α_k, A_k }, k≥ 0 be generated by Algorithm <ref>. Let f_* be the optimal objective value and x_* be an optimal point in problem (<ref>). Denote 
	
    P_0^2 = A_0(f(x_0)-f_*) + V[u_0](x_*).

	
		
  * If the oracle error ξ(x) in  (<ref>) can be controlled and, on each iteration, the error level δ in  (<ref>) satisfies
		
    δ≤P_0/4ρ A_k,

		then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤3P_0^2/2A_k,

		where  denotes the expectation with respect to all the randomness (up to step k in this case).
		
  * If the oracle error ξ(x) in  (<ref>) can not be controlled, then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤2P_0^2/A_k + 4 A_k ρ^2 δ^2.

	
	



	Let us change the counter in Lemma <ref> from k to i, fix u=x_*, take the full expectation in each inequality for i=0,...,k-1 and sum all the inequalities for i=0,...,k-1. Then,  
	
    A_k f(x_k) - A_0f(x_0) ≤     ∑_i=0^k-1α_i+1( f(y_i+1) + ∇ f(y_i+1), x_* - y_i+1) + V[u_0](x_*) 
       -  V[u_k](x_*) + ∑_i=0^k-1α_i+1ρξ(y_i+1), x_* - u_i+1
       conv-ty, (<ref>), (<ref>)≤ (A_k-A_0)f(x_*) + V[u_0](x_*)
       -  V[u_k](x_*) + ∑_i=0^k-1α_i+1ρδx_* - u_i+1_E  .

	Rearranging terms and using  (<ref>), we obtain, for all k ≥ 1,
	
    0 ≤ A_k( f(x_k) - f_* )    ≤
    	P_0^2-  V[u_k](x_*) + ρδ∑_i=0^k-1α_i+1 R_i+1,

	where we denoted R_i = u_i-x_*_E, i≥ 0. 
	
	1. We first prove the first statement of the Theorem. 
	We have
	
    1/2 R_0^2 = 1/2x_*-u_0_E^2  (<ref>)≤ V[u_0](x_*)  (<ref>)≤ P_0^2.

	Hence, R_0 = R_0 ≤ P_0 √(2)≤ 2 P_0. Let R_i ≤ 2 P_0, for all i=0,...,k-1. Let us prove that R_k≤ 2 P_0.
	By convexity of square function, we obtain
	
    1/2( R_k)^2 ≤1/2 R_k^2  (<ref>)≤ V[u_k](x_*)     (<ref>)≤ P_0^2 + ρδ∑_i=0^k-2α_i+1 2P_0 + α_kρδ R_k
        (<ref>)= P_0^2 + 2 ρδ P_0 (A_k-1-A_0) + α_kρδ R_k
       ≤ P_0^2 + 2 ρδ P_0 A_k + α_kρδ R_k .

	Since α_k ≤ A_k, k ≥ 0, by the choice of δ  (<ref>), we have 
	2 ρδ P_0 A_k  ≤P_0^2/2 and α_kρδ≤ A_kρδ≤P_0/4.
	So, we obtain an inequality for R_k
	
    1/2( R_k)^2 ≤3P_0^2/2 +  P_0/4 R_k.

	Solving this quadratic inequality in R_k, we obtain
	
    R_k≤P_0/4 + √(P_0^2/16+3P_0^2) = 2P_0.

	Thus, by induction, we have that, for all k ≥ 0, R_k ≤ 2 P_0. Using the bounds R_i ≤ 2 P_0, for all i=0,...,k, we obtain
	
    A_k( f(x_k) - f_* )     (<ref>)≤ P_0^2 + ρδ∑_i=0^k-1α_i+1 R_i
        (<ref>), (<ref>)≤  P_0^2 + ρP_0/4ρ A_k· (A_k-A_0) ·  2 P_0 ≤3P_0^2/2.

	This finishes the proof of the first statement of the Theorem.
	
	2. Now we prove the second statement of the Theorem.
	First, from (<ref>) for k=1, we have
	
    1/2( R_1)^2 ≤1/2 R_1^2 (<ref>)≤ V[u_1](x_*)    (<ref>)≤ P_0^2 + ρδα_1 R_1.
 
	Solving this inequality in R_1, we obtain 
	
    R_1≤ρδα_1+ √((ρδα_1 )^2+2P_0^2)≤ 2  ρδα_1 +  P_0  √(2),

	where we used that, for any a,b ≥ 0, √(a^2+b^2)≤ a +b.
	
	
	
	Then,
	
    P_0^2 + ρδα_1 R_1   ≤  P_0^2  + 2 (ρδα_1)^2 +  ρδα_1 P_0√(2)≤(P_0 + ρδ√(2) (A_1-A_0) )^2.

	Thus, we have proved that the inequality
	
    P_0^2 + ρδ∑_i=0^k-2α_i+1 R_i+1≤(P_0 + ρδ√(2) (A_k-1-A_0))^2

	holds for k=2. Let us assume that it holds for some k and prove that it holds for k+1. We have
	
    1/2( R_k)^2 ≤1/2 R_k^2 (<ref>)≤ V[u_k](x_*)    (<ref>)≤ P_0^2 + ρδ∑_i=0^k-2α_i+1 R_i+1 + α_kρδ R_k
       (<ref>)≤(P_0 + ρδ√(2) (A_k-1-A_0))^2 + α_kρδ R_k.

	Solving this quadratic inequality in R_k, we obtain
	
    R_k   ≤α_kρδ + √((α_kρδ)^2+2(P_0 + ρδ√(2) (A_k-1-A_0))^2)
       ≤ 2 α_kρδ +  (P_0 + ρδ√(2) (A_k-1-A_0)) √(2),

	where we used that, for any a,b ≥ 0, √(a^2+b^2)≤ a +b. Further,
	
    P_0^2 + ρδ∑_i=0^k-1α_i+1 R_i+1   (<ref>)≤(P_0 + ρδ√(2) (A_k-1-A_0))^2 + ρδα_k  R_k
       (<ref>)≤(P_0 + ρδ√(2) (A_k-1-A_0))^2  + 2 (ρδα_k)^2 +  ρδα_k (P_0 + ρδ√(2) (A_k-1-A_0)) √(2)
       ≤(P_0 + ρδ√(2) (A_k-1-A_0) + ρδα_k √(2))^2 = (P_0 + ρδ√(2) (A_k-A_0) )^2,

	which is (<ref>) for k+1.
	Using this inequality, we obtain 
	
    A_k( f(x_k) - f_* )    (<ref>)≤ P_0^2 + ρδ∑_i=0^k-1α_i+1 R_i+1≤(P_0 + ρδ√(2) (A_k-A_0) )^2 
       ≤ 2P_0^2 + 4 ρ^2 δ^2 A_k^2,

	which finishes the proof of the Theorem.
	
	








Let us now estimate the growth rate of the sequence A_k, k ≥ 0, which will give the rate of convergence for <ref>.

	
	Let the sequence {A_k }, k≥ 0 be generated by Algorithm <ref>. Then,  for all k ≥ 1 it holds that
	
    (k-1+2ρ)^2/4ρ^2≤ A_k ≤(k-1+2ρ)^2/ρ^2.
	



	As we showed in <ref>, α_1=1/ρ and, hence, A_1=α_0+α_1=1. Thus, (<ref>) holds for k=1. Let us assume that (<ref>) holds for some k≥ 1 and prove that it holds also for k+1.
	From (<ref>),  we have a quadratic equation for α_k+1
	
    ρ^2α_k+1^2 - α_k+1 - A_k = 0.

	Since we need to take the largest root, we obtain,
	
    α_k+1    = 1 + √( 1 + 4ρ^2A_k)/2ρ^2 = 1/2ρ^2 + √(1/4ρ^4 + A_k/ρ^2)≥1/2ρ^2 + √(A_k/ρ^2)
       ≥1/2ρ^2 + k-1+2ρ/2ρ^2 =
    	k+2ρ/2ρ^2,

	where we used the induction assumption that (<ref>) holds for k.
	On the other hand, 
	
    α_k+1    = 1/2ρ^2 + √(1/4ρ^4 + A_k/ρ^2)≤1/ρ^2 + √(A_k/ρ^2)
       ≤1/ρ^2 + k-1+2ρ/ρ^2 =
    	k+2ρ/ρ^2,

	where we used inequality √(a+b)≤√(a)+√(b), a,b ≥ 0.
	Using the obtained inequalities for α_k+1, from (<ref>) and (<ref>) for k, we get
	
    A_k+1 = A_k + α_k+1≥(k-1+2ρ)^2/4ρ^2 + k+2ρ/2ρ^2≥(k+2ρ)^2/4ρ^2

	and
	
    A_k+1 = A_k + α_k+1≤(k-1+2ρ)^2/ρ^2 + k+2ρ/ρ^2≤(k+2ρ)^2/ρ^2.

	In the last inequality we used that k ≥ 1, ρ≥ 0.



	
	According to Theorem <ref>, if the desired accuracy of the solution is , i.e. the goal is to find such x̂∈ Q that f(x̂) - f_* ≤, then the Algorithm <ref> should be stopped when 3P_0^2/2A_k≤. Then 1/A_k≤2/3 P_0^2 and the oracle error level δ should satisfy δ≤P_0/4 ρ A_k≤/6 ρ P_0.
	
	From <ref>, we obtain that 3P_0^2/2A_k≤ holds when k is the smallest integer satisfying 
	
    (k-1+2ρ)^2/4ρ^2≥3P_0^2/2 .

	This means that, to obtain an -solution, it is enough to choose
	
    k = max{⌈ρ√(6P_0^2/) + 1 -2 ρ⌉,0}.

	Note that this dependence on  means that the proposed method is accelerated.
	
	
	
	
	
	
	
	
	
	
	
	




































































































































































§ EXTENSION FOR STRONGLY CONVEX FUNCTIONS


In this section, we consider strongly-convex objective functions and show how the restart technique can be used to obtain faster rates of convergence under this additional assumption. 


[Strong convexity]
	Assume that the function f(x) is strongly convex:
	
    f(x) ≥ f(y) + ⟨∇ f(y), x-y⟩ + μ/2x - y_E^2,   ∀ x, y ∈ Q,


where the constant μ > 0. We also introduce additional assumption on the Bregman divergence V[y](x):
[Prox-function bound]
	We assume that the function d(x) satisfies conditions 0 = _x∈ Q d(x) and d(0) = 0. Also for a fixed point x_* and random point y ∈ Q^0, if y - x_*^2_E ≤ R^2 then
	
    d(y - x_*/R) ≤V^2/2.

	


Some examples of prox-functions satisfying this assumption can be found in <cit.>, the simplest being the squared Euclidean norm. The following algorithm is obtained by restarting Algorithm <ref>. As in Algorithm <ref> our algorithm has two variations. For simplicity we introduce a constant Ĉ which is equal to 0 if the oracle error ξ(x) in (<ref>) can be controlled and Ĉ = 4(k+2ρ)^2 δ^2 if the oracle error ξ(x) in (<ref>) can not be controlled. Variable k is a constant which is predefined in (<ref>). 









	Let the assumptions <ref>, <ref>, <ref>, <ref>,  <ref> hold. Let the sequences {y_j, _j}, j≥ 0 be generated by Algorithm <ref>. Let f_* be the optimal objective value and x_* be an optimal point in problem (<ref>).
	
		
  * For the second statement of Theorem <ref> when the oracle error ξ(x) in (<ref>) can not be controlled for all j ≥ 0,
		
    f(y_j) - f_* ≤_j + 8(1 - 2^-j) (k+2ρ)^2 δ^2 = _0 2^-j + 8(1 - 2^-j) (k+2ρ)^2 δ^2,

		where k is defined in (<ref>).
		
  * For the first statement of Theorem <ref> when the oracle error ξ(x) in (<ref>) can be controlled for all j ≥ 0,
		
    f(y_j) - f_* ≤_j = _0 2^-j,

		where  denotes the expectation with respect to all the randomness up to step j. Also Algorithm <ref> finds an -solution of the function f(x) in the number of <ref> steps not greater than
		
    ⌈log_2(_0/) ⌉max{⌈ρ√(16(1-1/ρ + V^2/μ)) + 1 -2 ρ⌉,0}.

	
	



	Let us denote Ĉ = 4(k+2ρ)^2 δ^2. We start our proof with a remark that if d(x) is a prox-function then a^2 d(1/ax) is also a prox-function, it is enough to show that a ^2d(1/ax) is 1-strong convex function. From definition
	
    d(x) - d(y) - ⟨∇ d(y), x - y⟩≥1/2x - y_E^2,    x ∈ Q,    y ∈ Q^0 := ⊗_i=1^n Q_i^0,

	obviously, we can get
	
    a^2d(1/ax) - a^2d(1/ay) - ⟨∇( a^2d(1/ay)), x - y⟩≥1/2x - y_E^2,

	x ∈ Q, y ∈ Q^0 := ⊗_i=1^n Q_i^0.
	Let us denote P̂_0^j =√(( A_0 + V^2/μ)_j) for all j=0,...,N, we can show following equality for k:
	
    k    = max{⌈ρ√(16(1-1/ρ + V^2/μ)) + 1 -2 ρ⌉,0}
       = max{⌈ρ√(8(A_0 + V^2/μ)_j-1/_j) + 1 -2 ρ⌉,0}
       = max{⌈ρ√(8(P̂_0^j-1)^2/_j) + 1 -2 ρ⌉,0}.

	Thus we have equivalent definition of k:
	
    k = max{⌈ρ√(8(P̂_0^j-1)^2/_j) + 1 -2 ρ⌉,0}
    	.

	1. We first prove the first statement of Theorem <ref>.
	For j = 0 inequality (<ref>) follows from Algorithm <ref> input. Let us assume that this is true for j and prove that it holds
	for j+1. Let us define P_0^j-1 equal to P_0 from the j's call of Algorithm <ref>.
	From assumption <ref>, induction, and definition of Ĉ, we obtain 
	
    μ/2y_j - x_*_E^2 ≤(f(y_j) - f_*) ≤_j + 2(1 - 2^-j)Ĉ.
 
	We can write following upper bound for P_0^j:
	
    (P_0^j)^2    = A_0(f(y_j)-f_*) + V̂[y_j](x_*) 
       =A_0(f(y_j)-f_*) + (d̂(x_*) - d̂(y_j) - ⟨∇d̂(y_j), x_* - y_j⟩)

	From assumption <ref> and (<ref>), we have d̂(y_j) = 0 and ∇d̂(y_j) = 0. Therefore,
	
    (P_0^j)^2   = A_0(f(y_j)-f_*)
       + 2(_j + 2(1 - 2^-j)Ĉ)/μ d(√(μ/2(_j+ 2(1 - 2^-j)Ĉ))(y_j - x_*)).

	In assumption <ref> we can take R = √(2(_j + 2(1 - 2^-j)Ĉ)/μ) and get
	
    (P_0^j)^2   ≤ A_0(f(y_j)-f_*) + (_j+ 2(1 - 2^-j)Ĉ)V^2/μ
       ≤(A_0 + V^2/μ)(_j+ 2(1 - 2^-j)Ĉ)

	and hence (P_0^j)^2 ≤ (P̂_0^j)^2 + 2(A_0 + V^2/μ)(1 - 2^-j)Ĉ. Using Theorem <ref> we obtain:
	
	
    f(y_j+1) - f_* 
    	   ≤2 (P_0^j)^2/A_k + 4 A_kρ^2 δ^2
       (<ref>)≤2 (P_0^j)^2/A_k + Ĉ
       ≤2(P̂_0^j)^2/A_k + 2(A_0 + V^2/μ)(1 - 2^-j)Ĉ/A_k + Ĉ.

	Using the second definition (<ref>) for k
	as well as in Remark <ref> with P_0 = P̂_0^j 

	we have:
	
    2(P̂_0^j)^2/A_k≤_j+1.

	Finally, we can conclude:
	
    f(y_j+1) - f_*    ≤_j+1+2(A_0 + V^2/μ)(1 - 2^-j)Ĉ/(P̂_0^j)^2_j+1+ Ĉ
       =_j+1+2(A_0 + V^2/μ)(1 - 2^-j)Ĉ/( A_0 + V^2/μ)_j_j+1+ Ĉ
       =_j+1+2(1 - 2^-j-1)Ĉ.

	2. Obviously, the proof for the second statement of Theorem <ref> is the same. The only difference is that Ĉ = 0. It is enough to take N = ⌈log_2(_0/) ⌉ in order to find an  -solution. Due to (<ref>) we can estimate total number of Algorithm <ref> steps:
	
    K_T   = N  k
       = Nmax{⌈ρ√(16(1-1/ρ + V^2/μ)) + 1 -2 ρ⌉,0}
       =⌈log_2(_0/) ⌉max{⌈ρ√(16(1-1/ρ + V^2/μ)) + 1 -2 ρ⌉,0}.


Note that this dependence on  and μ means that the proposed method is accelerated.






§ EXAMPLES OF APPLICATIONS


In this section, we apply our general framework, which consists of assumptions <ref>, <ref>, <ref>, UARM as listed in Algorithm <ref> and convergence rate  in theorem <ref>, to obtain several particular algorithms and their convergence rate. We consider problem (<ref>) and, for each particular case, introduce a particular setup, which includes properties of the objective function f, available information about this function, properties of the feasible set Q. Based on each setup, we show how the Randomized Inexact Oracle is constructed and check that the assumptions <ref>, <ref>, <ref> hold. 
Then, we obtain convergence rate guarantee for each particular algorithm as a corollary of theorem <ref>. Our examples include accelerated random directional search with inexact directional derivative, accelerated random block-coordinate descent with inexact block derivatives, accelerated random derivative-free directional search with inexact function values, accelerated random derivative-free block-coordinate descent with inexact function values. Accelerated random directional search and accelerated random derivative-free directional search were developed in <cit.>, but for the case of exact directional derivatives and exact function values. Also, in the existing methods, a Gaussian random vector is used for randomization. Accelerated random block-coordinate descent was introduced in <cit.> and further developed in by several authors (see Introduction for the extended review). Existing methods of this type use exact information on the block derivatives and also only Euclidean proximal setup. In the contrast, our algorithm works with inexact derivatives and is able to work with entropy proximal setup. To the best of our knowledge, our accelerated random derivative-free block-coordinate descent with inexact function values is new. This method also can work with entropy proximal setup.

















































 §.§ Accelerated Random Directional Search


In this subsection, we introduce accelerated random directional search with inexact directional derivative for unconstrained problems with Euclidean proximal setup.
We assume that, for all i=1,...,n, Q_i=E_i=,  x^(i)_i^2=(x^(i))^2, x^(i)∈ E_i, d_i(x^(i))=1/2(x^(i))^2, x^(i)∈ E_i and, hence, V_i[z^(i)](x^(i)) = 1/2(x^(i)-z^(i))^2, x^(i), z^(i)∈ E_i. Thus, Q=E=^n. Further, we assume that f in (<ref>) has L-Lipschitz-continuous gradient with respect to Euclidean norm, i.e. 

    f(x) ≤ f(y) + ∇ f(y), x-y  + L/2x-y_2^2,    x,y ∈ E.

We set β_i=L, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = L x_2^2, x ∈ E, d(x) = L/2x_2^2=1/2x_E^2, x ∈ E, V[z](x)=L/2x-z_2^2=1/2x-z_E^2, x, z ∈ E. Also, we have g_E,*^2 = L^-1g_2^2, g ∈ E^*.

We assume that, at any point x ∈ E, one can calculate an inexact derivative of f in a direction e ∈ E

    f̃'(x,e) = ∇ f(x), e  + ξ(x),
 
where e is a random vector uniformly distributed on the Euclidean sphere of radius 1, i.e. _2(1):={s ∈^n: s_2=1}, and the directional derivative error ξ(x) ∈ is uniformly bounded in absolute value by error level Δ, i.e. |ξ(x)| ≤Δ, x ∈ E. Since we are in the Euclidean setting, we consider e also as an element of E^*. We use n (∇ f(x), e  + ξ(x))e as Randomized Inexact Oracle.

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
In this setting, we have ρ = n, H =, ^T: E^* → is given by ^T g =  g, e, g ∈ E^*, : → E^* is given by t = te, t ∈. Thus,

    (x) = n (∇ f(x), e  + ξ(x))e.

One can prove that _e n ∇ f(x), e  e =  n_eee^T∇ f(x) = ∇ f(x), x ∈ E, and, thus, (<ref>) holds. Also, for all x ∈ E, we have ξ(x)_E,* = 1/√(L)ξ(x)e_2 ≤Δ/√(L), which proves (<ref>) if we take δ = Δ/√(L).

Regularity of Prox-Mapping. Substituting particular choice of Q, V[u](x), (x) in (<ref>), we obtain

    u_+    = min_x ∈^n{L/2x-u_2^2+ α n (∇ f(y), e  + ξ(y))e,x }
        = u - α n/L (∇ f(y), e  + ξ(y))e.

Hence, since e, e  = 1, we have

    ^T∇ f(y), u - u_+     = ∇ f(y), e  e, α n/L (∇ f(y), e  + ξ(y))e
        =  ∇ f(y), e  e , eα n/L (∇ f(y), e  + ξ(y)) 
        = ∇ f(y),  α n/L (∇ f(y), e  + ξ(y))e
        = ∇ f(y), u - u_+ ,

which proves (<ref>).

Smoothness.
By definition of ·_E and (<ref>), we have 

    f(x) ≤ f(y) + ∇ f(y), x - y  + L/2x-y_2^2 = f(y) + ∇ f(y), x - y  + 1/2x-y_E^2,    x, y ∈ E

and (<ref>) holds.

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random directional search as a corollary of Theorem <ref> and Lemma <ref>. 

	
	Let Algorithm <ref> with (x) = n (∇ f(x), e  + ξ(x))e, where e is random and uniformly distributed over the Euclidean sphere of radius 1, be applied to Problem (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem (<ref>). Assume that directional derivative error ξ(x) satisfies |ξ(x)| ≤Δ, x ∈ E. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + L/2u_0-x_*_2^2.

	
		
  * If the directional derivative error ξ(x) can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0√(L)/4nA_k,

		then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the directional derivative error ξ(x) can not be controlled, then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 4/L (k-1+2n)^2 Δ^2.

	



	According to Remark <ref> and due to the relation δ = Δ/√(L), we obtain that the error level Δ in the directional derivative should satisfy
	
    Δ≤√(L)/6nP_0.

	At the same time, to obtain an -solution for Problem (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.






 §.§ Accelerated Random Coordinate Descent


In this subsection, we introduce accelerated random coordinate descent with inexact coordinate derivatives for problems with separable constraints and Euclidean proximal setup. We assume that, for all i=1,...,n, E_i=, Q_i ⊆ E_i are closed and convex, x^(i)_i^2=(x^(i))^2, x^(i)∈ E_i, d_i(x^(i))=1/2(x^(i))^2, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = 1/2(x^(i)-z^(i))^2, x^(i), z^(i)∈ Q_i. Thus, Q=⊗_i=1^n Q_i has separable structure. 







Let us denote e_i ∈ E the i-th coordinate vector. Then, for i=1,...,n, the i-th coordinate derivative of f is f_i'(x) = ∇ f(x), e_i.
We assume that the gradient of f in (<ref>) is coordinate-wise Lipschitz continuous with constants L_i, i=1,...,n, i.e.

    |f'_i(x+he_i) - f'_i(x)| ≤ L_i |h|,    h ∈,    i=1,...,n,    x ∈ Q.

We set β_i=L_i, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = ∑_i=1^n L_i (x^(i))^2, x ∈ E, d(x) = 1/2∑_i=1^n L_i(x^(i))^2, x ∈ Q, V[z](x)=1/2∑_i=1^n L_i (x^(i)-z^(i))^2, x, z ∈ Q. Also, we have g_E,*^2 = ∑_i=1^n L_i^-1 (g^(i))^2, g ∈ E^*. 

We assume that, at any point x ∈ Q, one can calculate an inexact coordinate derivative of f

    f̃_i'(x) = ∇ f(x), e_i  + ξ(x),
 
where the coordinate i is chosen from i=1,...,n at random with uniform probability 1/n, the coordinate derivative error ξ(x) ∈ is uniformly bounded in absolute value by Δ, i.e. |ξ(x)| ≤Δ, x ∈ Q. Since we are in the Euclidean setting, we consider e_i also as an element of E^*. We use n (∇ f(x), e_i  + ξ(x))e_i as Randomized Inexact Oracle.

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
In this setting, we have ρ = n, H = E_i =, ^T: E^* → is given by ^T g =  g, e_i, g ∈ E^*, : → E^* is given by t = te_i, t ∈. Thus,

    (x) = n (∇ f(x), e_i  + ξ(x))e_i,    x ∈ Q.

One can prove that _i n ∇ f(x), e_i  e_i =  n_ie_ie_i^T∇ f(x) = ∇ f(x), x ∈ Q, and, thus, (<ref>) holds. Also, for all x ∈ Q, we have ξ(x)_E,* = 1/√(L_i)|ξ(x)| ≤Δ/√(L_0), where L_0 = min_i=1,...,nL_i. This proves (<ref>) with δ = Δ/√(L_0).

Regularity of Prox-Mapping. Separable structure of Q and V[u](x) means that the problem (<ref>) boils down to n independent problems of the form 

    u_+^(j) = min_x^(j)∈ Q_j{L_j/2(u^(j)-x^(j))^2+ α(y), e_j  x^(j)},    j = 1,...,n.

Since (y) has only one, i-th, non-zero component, (y), e_j is zero for all j  i. Thus, u-u_+ has one, i-th, non-zero component and e_i, u - u_+  e_i = u - u_+. 
Hence, 

    ^T∇ f(y), u - u_+     = ∇ f(y), e_i  e_i, u - u_+ 
        = ∇ f(y), e_i   e_i, u - u_+ 
        = ∇ f(y),   e_i, u - u_+  e_i 
        = ∇ f(y), u - u_+ ,

which proves (<ref>).

Smoothness.
By the standard reasoning, using (<ref>), one can prove that, for all i=1,...,n,

    f(x+h e_i) ≤ f(x) + h ∇ f(x),  e_i   + L_i h^2/2,    h ∈,    x ∈ Q.

Let u,y ∈ Q, a ∈, and x = y + a (u_+-u) ∈ Q. As we have shown above, u_+-u has only one, i-th, non-zero component. Hence, there exists h ∈, such that u_+-u = he_i and x = y + a he_i.
Thus, by definition of ·_E and (<ref>), we have 

    f(x)  = f(y + a he_i )    ≤ f(y) + a h ∇ f(y), e_i    + L_i/2(a h)^2 
        = f(y) + ∇ f(y), a he_i  + 1/2a h e_i_E^2  
        = f(y) + ∇ f(y), x - y  + 1/2x-y_E^2.

This proves (<ref>).

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random coordinate descent as a corollary of <ref> and <ref>. 

	
	Let Algorithm <ref> with (x) = n (∇ f(x), e_i  + ξ(x))e_i, where i is uniformly at random chosen from 1,...,n, be applied to Problem (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem (<ref>). Assume that coordinate derivative error ξ(x) satisfies |ξ(x)| ≤Δ, x ∈ Q. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + ∑_i=1^nL_i/2(u_0^(i)-x_*^(i))^2.

	
		
  * If the coordinate derivative error ξ(x) can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0√(L_0)/4nA_k,

		then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the coordinate derivative error ξ(x) can not be controlled, then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 4/L_0 (k-1+2n)^2 Δ^2.

	



	According to Remark <ref> and due to the relation δ = Δ/√(L_0), we obtain that the error level Δ in the coordinate derivative should satisfy
	
    Δ≤√(L_0)/6nP_0 .

	At the same time, to obtain an -solution for Problem (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.







 §.§ Accelerated Random Block-Coordinate Descent


In this subsection, we consider two block-coordinate settings. The first one is the Euclidean, which is usually used in the literature for accelerated block-coordinate descent. The second one is the entropy, which, to the best of our knowledge, is analyzed in this context for the first time. We develop accelerated random block-coordinate descent with inexact block derivatives for problems with simple constraints in these two settings and their combination.

Euclidean setup. We assume that, for all i=1,...,n, E_i=^p_i; Q_i is a simple closed convex set; x^(i)_i^2= B_i x^(i), x^(i), x^(i)∈ E_i, where B_i is symmetric positive semidefinite matrix; d_i(x^(i))=1/2x^(i)_i^2, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = 1/2x^(i)-z^(i)_i^2, x^(i), z^(i)∈ Q_i.

Entropy setup. We assume that, for all i=1,...,n, E_i=^p_i; Q_i is standard simplex in ^p_i, i.e., Q_i = {x^(i)∈^p_i_+: ∑_j=1^p_i[x^(i)]_j = 1}; x^(i)_i=x^(i)_1=∑_j=1^p_i|[x^(i)]_j|, x^(i)∈ E_i; d_i(x^(i))=∑_j=1^p_i[x^(i)]_j ln [x^(i)]_j, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = ∑_j=1^p_i[x^(i)]_j ln[x^(i)]_j/[z^(i)]_j, x^(i), z^(i)∈ Q_i. 

Note that, in each block, one also can choose other proximal setups from <cit.>. Combination of different setups in different blocks is also possible, i.e., in one block it is possible to choose the Euclidean setup and in an another block one can choose the entropy setup.

Using operators U_i, i=1,...,n defined in (<ref>), for each i=1,...,n, the i-th block derivative of f can be written as f_i'(x) = U_i^T ∇ f(x).
We assume that the gradient of f in (<ref>) is block-wise Lipschitz continuous with constants L_i, i=1,...,n with respect to chosen norms ·_i, i.e.

    f'_i(x+U_ih^(i)) - f'_i(x)_i,*≤ L_i h^(i)_i,    h^(i)∈ E_i,    i=1,...,n,    x ∈ Q.

We set β_i=L_i, i=1,...,n. Then, by definitions in subsection <ref>, we have

    x_E^2 = ∑_i=1^n L_i x^(i)_i^2,    x ∈ E,


    d(x) = ∑_i=1^n L_id_i(x^(i)),    x ∈ Q,


    V[z](x)=∑_i=1^n L_i V_i[z^(i)](x^(i)),    x, z ∈ Q.

 Also, we have g_E,*^2 = ∑_i=1^n L_i^-1g^(i)_i,*^2, g ∈ E^*. 

We assume that, at any point x ∈ Q, one can calculate an inexact block derivative of f

    f̃_i'(x) = U_i^T ∇ f(x) + ξ(x),
 
where a block number i is chosen from 1,...,n randomly uniformly, the block derivative error ξ(x) ∈ E_i^* is uniformly bounded in norm by Δ, i.e. ξ(x)_i,*≤Δ, x ∈ Q, i=1,...,n. As Randomized Inexact Oracle, we use n U_i(U_i^T ∇ f(x) + ξ(x)), where U_i is defined in (<ref>).  

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
In this setting, we have ρ = n, H = E_i, ^T: E^* → E_i^* is given by ^T g = U_i^T g, g ∈ E^*, : E_i^* → E^* is given by g^(i) = U_i g^(i), g^(i)∈ E_i^*. Thus,

    (x) = n U_i(U_i^T ∇ f(x) + ξ(x)),    x ∈ Q.

Since i ∈ R[1,n], one can prove that _i n U_iU_i^T ∇ f(x) =  ∇ f(x), x ∈ Q, and, thus, (<ref>) holds. Also, for all x ∈ Q, we have ξ(x)_E,* = U_i ξ(x)_E,* = 1/√(L_i)ξ(x)_i,*≤Δ/√(L_0), where L_0 = min_i=1,...,nL_i. This proves (<ref>) with δ = Δ/√(L_0). 

Regularity of Prox-Mapping. Separable structure of Q and V[u](x) means that the problem (<ref>) boils down to n independent problems of the form 

    u_+^(j) = min_x^(j)∈ Q_j{L_jV[u^(j)](x^(j))+ α U_j^T(y),x^(j)},    j = 1,...,n.

Since (y) has non-zero components only in the block i, U_j^T(y) is zero for all j  i. Thus, u-u_+ has non-zero components only in the block i and U_iU_i^T (u - u_+) = u - u_+. 
Hence, 

    ^T∇ f(y), u - u_+     = U_iU_i^T∇ f(y), u - u_+ 
        = ∇ f(y), U_iU_i^T (u - u_+) 
        = ∇ f(y), u - u_+ ,

which proves (<ref>).

Smoothness.
By the standard reasoning, using (<ref>), one can prove that, for all i=1,...,n,

    f(x+U_ih^(i)) ≤ f(x) +  U_i^T∇ f(x), h^(i) + L_i/2h^(i)_i^2,    h^(i)∈ E_i,    x ∈ Q.

Let u,y ∈ Q, a ∈, and x = y + a (u_+-u) ∈ Q. As we have shown above, u_+-u has non-zero components only in the block i. Hence, there exists h^(i)∈ E_i, such that u_+-u = U_i h^(i) and x = y + a U_i h^(i).
Thus, by definition of ·_E and (<ref>), we have 

    f(x)  = f(y + a U_i h^(i))    ≤ f(y) +  U_i^T∇ f(y), a h^(i) + L_i/2a h^(i)_i^2 
        = f(y) + ∇ f(y), a U_i h^(i) + 1/2a U_i h^(i)_E^2  
        = f(y) + ∇ f(y), x - y  + 1/2x-y_E^2.

This proves (<ref>).

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random block-coordinate descent as a corollary of <ref> and <ref>. 

	
	Let <ref> with (x) = n U_i(U_i^T ∇ f(x) + ξ(x)), where i is uniformly at random chosen from 1,...,n, be applied to Problem (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem (<ref>). Assume that block derivative error ξ(x) satisfies |ξ(x)| ≤Δ, x ∈ Q. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + V[u_0](x_*).

	
		
  * If the block derivative error ξ(x) can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0√(L_0)/4nA_k,

		then,  for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the block derivative error ξ(x) can not be controlled, then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 4/L_0 (k-1+2n)^2 Δ^2.

	




	According to Remark <ref> and due to the relation δ = Δ/√(L_0), we obtain that the block derivative error Δ should satisfy
	
    Δ≤√(L_0)/6nP_0.

	At the same time, to obtain an -solution for Problem (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.







 §.§ Accelerated Random Derivative-Free Directional Search


In this subsection, we consider the same setting as in subsection <ref>, except for Randomized Inexact Oracle. Instead of directional derivative, we use here its finite-difference approximation.
We assume that, for all i=1,...,n, Q_i=E_i=,  x^(i)_i=(x^(i))^2, x^(i)∈ E_i, d_i(x^(i))=1/2(x^(i))^2, x^(i)∈ E_i, and, hence, V_i[z^(i)](x^(i)) = 1/2(x^(i)-z^(i))^2, x^(i), z^(i)∈ E_i. Thus, Q=E=^n. Further, we assume that f in (<ref>) has L-Lipschitz-continuous gradient with respect to Euclidean norm, i.e. 

    f(x) ≤ f(y) + ∇ f(y), x-y  + L/2x-y_2^2,    x,y ∈ E.

We set β_i=L, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = L x_2^2, x ∈ E, d(x) = L/2x_2^2=1/2x_E^2, x ∈ E, V[z](x)=L/2x-z_2^2=1/2x-z_E^2, x, z ∈ E. Also, we have g_E,*^2 = L^-1g_2^2, g ∈ E^*.

We assume that, at any point x ∈ E, one can calculate an inexact value (x) of the function f, s.t. |(x)-f(x)|≤Δ, x ∈ E. To approximate the gradient of f, we use 

    (x) = n(x+τ e)-(x)/τe,
 




where τ > 0 is small parameter, which will be chosen later, e ∈ E is a random vector uniformly distributed on the Euclidean sphere of radius 1, i.e. on _2(1):={s ∈^n: s_2=1}.
Since, we are in the Euclidean setting, we consider e also as an element of E^*. 

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
First, let us show that the finite-difference approximation for the gradient of f can be expressed in the form of (<ref>). We have

    (x)    = n(x+τ e)-(x)/τe 
        = n (⟨∇ f(x), e⟩  + 1/τ( (x+τ e)-(x) - τ⟨∇ f(x), e⟩)  )e.

Taking ρ = n, H =, ^T: E^* → be given by ^T g =  g, e, g ∈ E^*, : → E^* be given by t = te, t ∈, we obtain

    (x) = n (∇ f(x), e  + ξ(x))e,

where ξ(x) = 1/τ( (x+τ e)-(x) - τ⟨∇ f(x), e⟩).
One can prove that _e n ∇ f(x), e  e =  n_eee^T∇ f(x) = ∇ f(x), x ∈ E, and, thus, (<ref>) holds. It remains to prove (<ref>), i.e., find δ s.t. for all x ∈ E, we have ξ(x)_E,*≤δ.

    ξ(x)_E,*    =  1/√(L)ξ(x)e_2  = 1/√(L)1/τ( (x+τ e)-(x) - τ⟨∇ f(x), e⟩) e _2
        = 1/√(L)1/τ( (x+τ e) - f(x+τ e) - ((x) - f(x)) _2 
        + 1/√(L)(f(x+τ e) - f(x) - τ⟨∇ f(x), e⟩)) e _2 
       ≤2Δ/τ√(L)+ τ√(L)/2.

Here we used that |(x)-f(x)|≤Δ, x ∈ E and (<ref>). So, we have that (<ref>) holds with δ = 2Δ/τ√(L)+ τ√(L)/2. To balance both terms, we choose τ = 2 √(Δ/L), which leads to equality δ = 2 √(Δ).

Regularity of Prox-Mapping. This assumption can be checked in the same way as in subsection <ref>.

Smoothness. This assumption can be checked in the same way as in subsection <ref>.

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random derivative-free directional search as a corollary of Theorem <ref> and Lemma <ref>. 

	
	Let Algorithm <ref> with (x) = n(x+τ e)-(x)/τe, where e is random and uniformly distributed over the Euclidean sphere of radius 1, be applied to Problem (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem (<ref>). Assume that function value error (x)-f(x) satisfies |(x)-f(x)| ≤Δ, x ∈ E. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + L/2u_0-x_*_2^2.

	
		
  * If the error in the value of the objective f can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0^2/64n^2A_k^2,

		and τ = 2 √(Δ/L) then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the error in the value of the objective f can not be controlled and τ = 2 √(Δ/L), then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 16 (k-1+2n)^2 LΔ.

	



	According to Remark <ref> and due to the relation δ = 2 √(Δ), we obtain that the error level in the function value should satisfy
	
    Δ≤^2 /144 n^2P_0^2.

	The parameter τ should satisfy
	
    τ≤/6 n P_0 √(L) .

	At the same time, to obtain an -solution for Problem (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.












 §.§ Accelerated Random Derivative-Free Coordinate Descent


In this subsection, we consider the same setting as in subsection <ref>, except for Randomized Inexact Oracle. Instead of coordinate derivative, we use here its finite-difference approximation. We assume that, for all i=1,...,n, E_i=, Q_i ⊆ E_i are closed and convex, x^(i)_i=(x^(i))^2, x^(i)∈ E_i, d_i(x^(i))=1/2(x^(i))^2, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = 1/2(x^(i)-z^(i))^2, x^(i), z^(i)∈ Q_i. Thus, Q=⊗_i=1^n Q_i has separable structure. 

Let us denote e_i ∈ E the i-th coordinate vector. Then, for i=1,...,n, the i-th coordinate derivative of f is f_i'(x) = ∇ f(x), e_i.
We assume that the gradient of f in (<ref>) is coordinate-wise Lipschitz continuous with constants L_i, i=1,...,n, i.e.

    |f'_i(x+he_i) - f'_i(x)| ≤ L_i |h|,    h ∈,    i=1,...,n,    x ∈ Q.

We set β_i=L_i, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = ∑_i=1^n L_i (x^(i))^2, x ∈ E, d(x) = 1/2∑_i=1^n L_i(x^(i))^2, x ∈ Q, V[z](x)=1/2∑_i=1^n L_i (x^(i)-z^(i))^2, x, z ∈ Q. Also, we have g_E,*^2 = ∑_i=1^n L_i^-1 (g^(i))^2, g ∈ E^*.

We assume that, at any point x in a small vicinity Q̅ of the set Q, one can calculate an inexact value (x) of the function f, s.t. |(x)-f(x)|≤Δ, x ∈Q̅. To approximate the gradient of f, we use 

    (x) = n(x+τ e_i)-(x)/τe_i,
 




where τ > 0 is small parameter, which will be chosen later, and the coordinate i is chosen from i=1,...,n randomly with uniform probability 1/n. Since, we are in the Euclidean setting, we consider e_i also as an element of E^*. 

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
First, let us show that the finite-difference approximation for the gradient of f can be expressed in the form of (<ref>). We have

    (x)    = n(x+τ e_i)-(x)/τe_i
        = n (⟨∇ f(x), e_i⟩  + 1/τ( (x+τ e_i)-(x) - τ⟨∇ f(x), e_i⟩)  )e_i.

Taking ρ = n, H =, ^T: E^* → is given by ^T g =  g, e_i, g ∈ E^*, : → E^* is given by t = te_i, t ∈, we obtain

    (x) = n (∇ f(x), e_i  + ξ(x))e_i,

where ξ(x) = 1/τ( (x+τ e_i)-(x) - τ⟨∇ f(x), e_i⟩).
One can prove that 

    _i n ∇ f(x), e_i  e_i =  n_ie_ie_i^T∇ f(x) = ∇ f(x),    x ∈ Q,

 and, thus, (<ref>) holds. It remains to prove (<ref>), i.e., find δ s.t. for all x ∈ Q, we have ξ(x)_E,*≤δ.

    ξ(x)_E,*    =  1/√(L_i)|ξ(x)|  = 1/√(L_i)|1/τ( (x+τ e_i)-(x) - τ⟨∇ f(x), e_i⟩)  |
        = 1/τ√(L_i)| (x+τ e_i) - f(x+τ e_i) - ((x) - f(x))| 
        + 1/τ√(L_i)|f(x+τ e_i) - f(x) - τ⟨∇ f(x), e_i⟩| 
       ≤2Δ/√(L_i)τ+ τ√(L_i)/2.

Here we used that |(x)-f(x)|≤Δ, x ∈Q̅ and (<ref>), which follows from (<ref>). So, we obtain that (<ref>) holds with δ = 2Δ/√(L_i)τ+ √(L_i)τ/2. To balance both terms, we choose τ = 2 √(Δ/L_i)≤ 2 √(Δ/L_0), where L_0 = min_i=1,...,nL_i.  This leads to equality δ = 2 √(Δ).

Regularity of Prox-Mapping. This assumption can be checked in the same way as in subsection <ref>.

Smoothness. This assumption can be checked in the same way as in subsection <ref>.

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random derivative-free coordinate descent as a corollary of Theorem <ref> and Lemma <ref>. 

	
	Let Algorithm <ref> with (x) = n(x+τ e_i)-(x)/τe_i, where i is random and uniformly distributed in 1,...,n, be applied to Problem (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem (<ref>). Assume that function value error (x)-f(x) satisfies |(x)-f(x)| ≤Δ, x ∈Q̅. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + ∑_i=1^nL_i/2(u_0^(i)-x_*^(i))^2.

	
		
  * If the error in the value of the objective f can be controlled and, on each iteration, the error level Δ satisfies  
		
    Δ≤P_0^2/64n^2A_k^2,

		and τ = 2 √(Δ/L_0) then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the error in the value of the objective f can not be controlled and τ = 2 √(Δ/L_0), then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 16 (k-1+2n)^2 Δ.

	




	According to Remark <ref> and due to the relation δ = 2 √(Δ), we obtain that the error level in the function value should satisfy
	
    Δ≤^2 /144 n^2P_0^2.

	The parameter τ should satisfy
	
    τ≤/6 n P_0 √(L_0).

	At the same time, to obtain an -solution for Problem (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.











 §.§ Accelerated Random Derivative-Free Block-Coordinate Descent


In this subsection, we consider the same setting as in subsection <ref>, except for Randomized Inexact Oracle. Instead of block derivative, we use here its finite-difference approximation. 
As in subsection <ref>, we consider Euclidean setup and entropy setup. 

Euclidean setup. We assume that, for all i=1,...,n, E_i=^p_i; Q_i is a simple closed convex set; x^(i)_i^2= B_i x^(i), x^(i), x^(i)∈ E_i, where B_i is symmetric positive semidefinite matrix; d_i(x^(i))=1/2x^(i)_i^2, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = 1/2x^(i)-z^(i)_i^2, x^(i), z^(i)∈ Q_i.

Entropy setup. We assume that, for all i=1,...,n, E_i=^p_i; Q_i is standard simplex in ^p_i, i.e., Q_i = {x^(i)∈^p_i_+: ∑_j=1^p_i[x^(i)]_j = 1}; x^(i)_i=x^(i)_1=∑_j=1^p_i|[x^(i)]_j|, x^(i)∈ E_i; d_i(x^(i))=∑_j=1^p_i[x^(i)]_j ln [x^(i)]_j, x^(i)∈ Q_i, and, hence, V_i[z^(i)](x^(i)) = ∑_j=1^p_i[x^(i)]_j ln[x^(i)]_j/[z^(i)]_j, x^(i), z^(i)∈ Q_i. 

Note that, in each block, one also can choose other proximal setups from <cit.>. Combination of different setups in different blocks is also possible, i.e., in one block it is possible to choose the Euclidean setup and in an another block one can choose the entropy setup.

Using operators U_i, i=1,...,n defined in (<ref>), for each i=1,...,n, the i-th block derivative of f can be written as f_i'(x) = U_i^T ∇ f(x).
We assume that the gradient of f in (<ref>) is block-wise Lipschitz continuous with constants L_i, i=1,...,n with respect to chosen norms ·_i, i.e.,

    f'_i(x+U_ih^(i)) - f'_i(x)_i,*≤ L_i h^(i)_i,    h^(i)∈ E_i,    i=1,...,n    x ∈ Q.

We set β_i=L_i, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = ∑_i=1^n L_i x^(i)_2^2, x ∈ E, d(x) = 1/2∑_i=1^n L_ix^(i)_2^2, x ∈ Q, V[z](x)=1/2∑_i=1^n L_i x^(i)-z^(i)_2^2, x, z ∈ Q. Also, we have g_E,*^2 = ∑_i=1^n L_i^-1g^(i)_2^2, g ∈ E^*.

We assume that, at any point x in a small vicinity Q̅ of the set Q, one can calculate an inexact value (x) of the function f, s.t. |(x)-f(x)|≤Δ, x ∈Q̅. To approximate the gradient of f, we use 

    (x) = nU_i ( (x+τ U_ie_1)-(x)/τ,...,(x+τ U_ie_p_i)-(x)/τ)^T,





where τ > 0 is small parameter, which will be chosen later, a block number i is chosen from i=1,...,n randomly with uniform probability 1/n, e_1,...,e_p_i are coordinate vectors in E_i, U_i is defined in (<ref>), U_i is defined in (<ref>).

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
First, let us show that the random derivative-free block-coordinate approximation for the gradient of f can be expressed in the form of (<ref>). Denote g̃_i = 1/τ( (x+τ U_i e_1)-(x),...,(x+τ U_i e_p_i)-(x))^T ∈ E_i, i=1,...,n. We have

    (x)     = nU_ig̃_i  = nU_i ( U_i^T∇ f(x) + (g̃_i - U_i^T∇ f(x))  ).

Taking ρ = n, H = E_i, ^T: E^* → E_i^* be given by ^T g = U_i^T g, g ∈ E^* and : E_i^* → E^* be given by g^(i) = U_i g^(i), g^(i)∈ E_i^*, we obtain

    (x) = n U_i(U_i^T∇ f(x) + ξ(x)),

where ξ(x) = g̃_i - U_i^T∇ f(x). Since i ∈ R[1,n], one can prove that _i n U_iU_i^T ∇ f(x) =  ∇ f(x), x ∈ Q, and, thus, (<ref>) holds. 
It remains to prove (<ref>), i.e., find δ s.t. for all x ∈ Q, we have ξ(x)_E,*≤δ. 
Let us fix any i from 1,...,n and j from 1,...,p_i. Then, for any x ∈Q̅, the j-th coordinate of ξ(x) = g̃_i - U_i^T∇ f(x) can be estimated as follows

    |[ξ(x)]_j|    = |1/τ( (x+τ U_i e_j)-(x) - τ U_i^T ∇ f(x), e_j| 
        = 1/τ| (x+τ U_i e_j) - f(x+τ U_i e_j) - ((x) - f(x))| 
        + 1/τ| (f(x+τ U_i e_j) - f(x) - τ U_i^T ∇ f(x), e_j ) | 
       ≤2Δ/τ+ τ L_i/2.

Here we used that |(x)-f(x)|≤Δ, x ∈Q̅, (<ref>), which follows from (<ref>). 
In our setting, for any i = 1,...,n, ·_i,* is either max-norm (for the entropy case) or Euclidean norm (for the Euclidean case). Thus, in the worst case of Euclidean norm

    ξ(x)_E,*   =  U_i ξ(x)_E,*
         = 1/√(L_i)ξ(x) _i,*
       (<ref>)≤√(p_i)/√(L_i)(2Δ/τ+ τ L_i/2)
       ≤√(p_max)(2Δ/τ√(L_i)+ τ√(L_i)/2),

where p_max = max_i=1,...,n p_i.
So, we obtain that (<ref>) holds with 

    δ = √(p_max)(2Δ/τ√(L_i)+ τ√(L_i)/2).

 To balance both terms we choose τ =  2 √(Δ/L_i)≤ 2 √(Δ/L_0), where L_0 = min_i=1,...,nL_i. This leads to equality δ = 2  √(p_maxΔ).

Regularity of Prox-Mapping. This assumption can be checked in the same way as in subsection <ref>.

Smoothness. This assumption can be checked in the same way as in subsection <ref>.

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random derivative-free block-coordinate descent as a corollary of Theorem <ref> and Lemma <ref>. 

	
	Let Algorithm <ref> with (x) defined in (<ref>), be applied to Problem  (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem  (<ref>). Assume that function value error (x)-f(x) satisfies |(x)-f(x)| ≤Δ, x ∈Q̅. Denote 
	
    P_0^2 = (1-1/n)(f(x_0)-f_*) + V[u_0](x_*).

	
		
  * If the error in the value of the objective f can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0^2/64n^2p_maxA_k^2 ,

		and τ = 2 √(Δ/L_0) then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6n^2P_0^2/(k-1+2n)^2 ,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the error in the value of the objective f can not be controlled and τ = 2 √(Δ/L_0), then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8n^2P_0^2/(k-1+2n)^2 + 16 (k-1+2n)^2 p_maxΔ.

	



	According to Remark <ref> and due to the relation δ = 2 √(p_maxΔ), we obtain that the error level in the function value should satisfy
	
    Δ≤^2 /144 n^2p_maxP_0^2.

	The parameter τ should satisfy
	
    τ≤/6 n P_0 √(L_0).

	At the same time, to obtain an -solution for Problem  (<ref>), it is enough to choose
	
    k = max{⌈ n√(6P_0^2/) + 1 -2 n ⌉,0}.









 §.§ Accelerated Random Derivative-Free Block-Coordinate Descent with Random Approximations for Block Derivatives


In this subsection, we combine random block-coordinate descent of subsection <ref> with random derivative-free directional search described in subsection <ref> and random derivative-free coordinate descent described in <ref>. 
We construct randomized approximations for block derivatives based on finite-difference approximation of directional derivatives.
Unlike subsection <ref>, we consider only Euclidean setup. We assume that, for all i=1,...,n, E_i=^p_i; x^(i)_i^2=x^(i)_2^2, x^(i)∈ E_i;  Q_i is either E_i, or ⊗_j=1^p_iQ_ij, where Q_ij⊆ are closed convex sets; d_i(x^(i))=1/2x^(i)_i^2, x^(i)∈ Q_i and, hence, V_i[z^(i)](x^(i)) = 1/2x^(i)-z^(i)_i^2, , x^(i), z^(i)∈ Q_i. For the case, Q_i = E_i, we consider randomization on the Euclidean sphere of radius 1, as in subsection <ref>. For the case, Q_i = ⊗_j=1^p_iQ_ij, we consider coordinate-wise randomization, as in subsection <ref>. 

Using operators U_i, i=1,...,n defined in  (<ref>), for each i=1,...,n, the i-th block derivative of f can be written as f_i'(x) = U_i^T ∇ f(x).
We assume that the gradient of f in  (<ref>) is block-wise Lipschitz continuous with constants L_i, i=1,...,n with respect to chosen norms ·_i, i.e.,

    f'_i(x+U_ih^(i)) - f'_i(x)_i,*≤ L_i h^(i)_i,    h^(i)∈ E_i,    i=1,...,n    x ∈ Q.

We set β_i=L_i, i=1,...,n. Then, by definitions in subsection <ref>, we have x_E^2 = ∑_i=1^n L_i x^(i)_2^2, x ∈ E, d(x) = 1/2∑_i=1^n L_ix^(i)_2^2, x ∈ Q, V[z](x)=1/2∑_i=1^n L_i x^(i)-z^(i)_2^2, x, z ∈ Q. Also, we have g_E,*^2 = ∑_i=1^n L_i^-1g^(i)_2^2, g ∈ E^*.

We assume that, at any point x in a small vicinity Q̅ of the set Q, one can calculate an inexact value (x) of the function f, s.t. |(x)-f(x)|≤Δ, x ∈Q̅. To approximate the gradient of f, we first randomly choose a block i ∈ 1,...,n with probability p_i/p, where p=∑_i=1^np_i. Then we use one the following types of random directions e ∈ E_i to approximate the block derivative f'_i(x) by a finite-difference. 

	
  * If Q_i = E_i, we take e ∈ E_i to be random vector uniformly distributed on the Euclidean sphere of radius 1, i.e. _2(1):={s ∈^p_i: s_2=1}. We call this unconstrained case.
	
  * If Q_i = ⊗_j=1^p_iQ_ij, we take e to be random uniformly chosen from 1,...,p_i coordinate vector, i.e. e = e_j ∈ E_i with probability 1/p_i. We call this separable case.
	

Based on these randomizations and inexact function values, our randomized approximation for the gradient of f is 

    (x) = p U_i (x+τ U_i e)-(x)/τe,
 




where τ > 0 is small parameter, which will be chosen later, U_i is defined in  (<ref>) and U_i is defined in  (<ref>).

Let us check the assumptions stated in subsection <ref>.

Randomized Inexact Oracle.
First, let us show that the random derivative-free block-coordinate approximation for the gradient of f can be expressed in the form of  (<ref>). We have

    (x)     = pU_i(x+τ U_i e)-(x)/τe 
        = pU_i ( ⟨ U_i^T∇ f(x), e⟩ e + 1/τ( (x+τ U_i e)-(x) - τ⟨ U_i^T ∇ f(x), e⟩) e ).

Taking ρ = p, H = E_i, ^T: E^* → E_i^* be given by ^T g =  U_i^T g,e  e, g ∈ E^* and : E_i^* → E^* be given by g^(i) = U_i g^(i), g^(i)∈ E_i^*, we obtain

    (x) = p U_i(⟨ U_i^T∇ f(x), e⟩ e + ξ(x)),

where ξ(x) = 1/τ( (x+τ U_i e)-(x) - τ⟨ U_i^T ∇ f(x), e⟩) e. By the choice of probability distributions for i and e and their independence, we have, for all x ∈ Q, 

    _i,e p U_i⟨ U_i^T∇ f(x), e⟩ e     =  p_i,eU_ie e^T U_i^T∇ f(x) = p_iU_i (E_ee e^T) U_i^T∇ f(x) 
       = p_i1/p_iU_i U_i^T ∇ f(x) = ∇ f(x)

and, thus,  (<ref>) holds. 
It remains to prove  (<ref>), i.e., find δ s.t. for all x ∈ Q, we have ξ(x)_E,*≤δ. We have

    ξ(x)_E,*   =  U_i ξ(x)_E,*  = 1/√(L_i)1/τ( (x+τ U_i e)-(x) - τ⟨ U_i^T ∇ f(x), e⟩) e _i,*
        =e _i,*/τ√(L_i)| (x+τ U_i e) - f(x+τ U_i e) - ((x) - f(x))
        + (f(x+τ U_i e) - f(x) - τ⟨ U_i^T ∇ f(x), e⟩ ) | 
       ≤2Δe _i,*/τ√(L_i)+ τe _i,*e _i^2 √(L_i)/2
    
        = 2Δ/τ√(L_i)+ τ√(L_i)/2.

Here we used that |(x)-f(x)|≤Δ, x ∈Q̅,  (<ref>), which follows from  (<ref>), and that the norms ·_i, ·_i,* are standard Euclidean. So, we obtain that  (<ref>) holds with δ = 2Δ/τ√(L_i)+ τ√(L_i)/2. To balance both terms we choose τ =  2 √(Δ/L_i)≤ 2 √(Δ/L_0), where L_0 = min_i=1,...,nL_i. This leads to equality δ = 2  √(Δ).


Regularity of Prox-Mapping. Separable structure of Q and V[u](x) means that the problem  (<ref>) boils down to n independent problems of the form 

    u_+^(l) = min_x^(l)∈ Q_l{L_l/2u^(l)-x^(l)_2^2+ α U_l^T(y),x^(l)},    l = 1,...,n.

Since (y) has non-zero components only in the block i, U_l^T(y) is zero for all l  i. Thus, u-u_+ has non-zero components only in the block i and U_i(u^(i)-u_+^(i)) = u - u_+. 

In the unconstrained case, similarly to subsection <ref>, we obtain that u^(i)-u_+^(i)=γ e, where γ is some constant. Using these two facts, we obtain

    ^T∇ f(y), u - u_+     = U_i U_i^T∇ f(y), e  e , u - u_+ 
        =  U_i^T∇ f(y), e  e ,  U_i^T(u - u_+) 
        =  U_i^T∇ f(y), e  e ,  u^(i)-u_+^(i)
        =  U_i^T∇ f(y), e  e ,  γ e 
        =  U_i^T∇ f(y), γ e  e ,   e 
        =  U_i^T∇ f(y), u^(i)-u_+^(i)
        = ∇ f(y), U_i(u^(i)-u_+^(i)) 
        = ∇ f(y), u - u_+ ,

which proves  (<ref>) for the unconstrained case.

In the separable case, similarly to subsection <ref>, we obtain that u^(i)-u_+^(i) has only one j-th non-zero coordinate, where j ∈ 1,...,p_i. Hence, e_j, u^(i)-u_+^(i) e_j = u^(i)-u_+^(i). So, we get, 

    ^T∇ f(y), u - u_+     = U_i U_i^T∇ f(y), e_j  e_j , u - u_+ 
        =  U_i^T∇ f(y), e_j  e_j ,  U_i^T(u - u_+) 
        =  U_i^T∇ f(y), e_j  e_j ,  u^(i)-u_+^(i)
        =  U_i^T∇ f(y), e_j  e_j ,  u^(i)-u_+^(i)
        =  U_i^T∇ f(y),  e_j ,  u^(i)-u_+^(i) e_j 
        =  U_i^T∇ f(y), u^(i)-u_+^(i)
        = ∇ f(y), U_i(u^(i)-u_+^(i)) 
        = ∇ f(y), u - u_+ ,

which proves  (<ref>) for the separable case.

Smoothness. This assumption can be checked in the same way as in subsection <ref>.

We have checked that all the assumptions listed in subsection <ref> hold. Thus, we can obtain the following convergence rate result for random derivative-free block-coordinate descent with random approximations for block derivatives as a corollary of Theorem <ref> and Lemma <ref>. 

	
	Let <ref> with (x) defined in  (<ref>), be applied to Problem  (<ref>) in the setting of this subsection. Let f_* be the optimal objective value and x_* be an optimal point in Problem  (<ref>). Assume that function value error (x)-f(x) satisfies |(x)-f(x)| ≤Δ, x ∈Q̅. Denote 
	
    P_0^2 = (1-1/p)(f(x_0)-f_*) + ∑_i=1^nL_i/2u_0^(i)-x_*^(i)_2^2.

	
		
  * If the error in the value of the objective f can be controlled and, on each iteration, the error level Δ satisfies 
		
    Δ≤P_0^2/64p^2A_k^2 ,

		and τ = 2 √(Δ/L_0) then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤6p^2P_0^2/(k-1+2p)^2 ,

		where  denotes the expectation with respect to all the randomness up to step k.
		
  * If the error in the value of the objective f can not be controlled and τ = 2 √(Δ/L_0), then, for all k ≥ 1,
		
    f(x_k) - f_*  ≤8p^2P_0^2/(k-1+2p)^2 + 16 (k-1+2p)^2 Δ.

	



	According to Remark <ref> and due to the relation δ = 2 √(Δ), we obtain that the error level in the function value should satisfy
	
    Δ≤^2 /144 p^2P_0^2.

	The parameter τ should satisfy
	
    τ≤/6 p P_0 √(L_0).

	At the same time, to obtain an -solution for Problem  (<ref>), it is enough to choose
	
    k = max{⌈ p√(6P_0^2/) + 1 -2 p ⌉,0}.






§ MODEL GENERALITY IN A NON-ACCELERATED RANDOM BLOCK-COORDINATE DESCENT

Above we propose a unified view on different randomized gradient-free and (block) coordinate-wise schemes. In the last decade an interest to structural optimization has grown <cit.>. The most general results (see  <cit.>) allow to unify different structures of the problem (composite problems, max-type problems e.t.c.) in one envelop (model generality <cit.>). But this envelop deals with the first-order methods. Motivated by Random Block Coordinate Descent (RBCD)  <cit.> we try to develop RBCD in model generality. We expect that further unification of model generality conception <cit.> with the results of this paper is also possible.

Typical randomized algorithm has such kind of auxiliary problem

    x_k+1=min_x ∈ Q{V[x_k](x) + α(x_k), x - x_k },

see for example (<ref>) and (<ref>) in Algorithm <ref>. Here the term (x_k), x - x_k is a (random) linear <<model>> of target function in considered point x_k.
The idea is to replace this model (x_k), x - x_k on something more general. 
For example, if f(x):= f(x) + h(x) we may expect, that composite model (x_k), x - x_k  + h(x) - h(x_k) is
also well suited and may lead to a better results than standard model (x_k), x - x_k.




Assume that






 
 
 




    V[z](x)=1/2∑_i=1^n L_i x^(i)-z^(i)_2^2,    Q = ⊗_i=1^nQ_i.


Function ψ_i(y,x) determines i-th part of the model of target function, that corresponds to block Q^(i). For example, in composite case if h(x) = ∑_i=1^n h_i(x^(i)) we can consider 
    ψ_i(y,x) = U_i U_i^T ∇ f(x), y - x  + h_i(y^(i)) - h_i(x^(i)).


[convexity]
   Assume that for all x ∈ Q model ψ_i(y, x) is convex function of y∈ Q and there exists such γ > 0 that for any x, y ∈ Q

    _i ψ_i(y, x) ≤1/γ(f(y) - f(x)).
 


Parameter γ = n for composite case.

[smoothness]

   For any 

   x_k,x_k+1 generated by Algorithm <ref> 



    f(x_k+1) ≤ f(x_k) + ψ_i(x_k+1, x_k) + V[x_k](x_k+1).


Assumption <ref> typically holds true with additional condition that x_k,x_k+1 generated by Algorithm <ref> satisfy   x_k^(j) = x_k+1^(j) for j ≠ i. 







    Let the assumptions <ref> and <ref> hold. Let x_k be generated by Algorithm <ref>. Let f_* be the optimal objective value and x^* be an optimal point in Problem (<ref>). Then, for all N ≥ 1,
    
    f(x_N) - f(x^*) ≤γ/N(f(x_0) - f(x^*)) + γ/NV[x_0](x^*),

    where x_N = 1/N∑_k=0^N-1 x_k.


    
From (<ref>), (<ref>) follows formula (3.12)  of <cit.> 

    -ψ_i(x, x_k) ≤  f(x_k) - f(x_k+1) + V[x_k](x) - V[x_k+1](x)

for all x∈ Q.  From this formula and (<ref>)

    1/γ(f(x_k) - f(x)) ≤
    -_iψ(x, x_k)  ≤  f(x_k) -_if(x_k+1) + V[x_k](x) - _iV[x_k+1](x).



Let start the proof using (<ref>)

    _if(x_k+1) ≤_if(x_k) + _i ψ_i(x_k+1, x_k) + _iV(x_k+1, x_k)

Using optimality condition for (<ref>)

    ∃ g ∈∂ψ(x_k+1, x_k), ⟨ g + V[x_k](x_k+1), x - x_k+1⟩≥ 0, ∀ x ∈ Q.

From strongly convex ψ(x, x_k) + V[x_k](x) we obtain that

    ψ(x, x_k) + V[x_k](x) ≥ψ(x_k+1, x_k) + V[x_k](x_k+1) + ⟨ g + V[x_k](x_k+1), x - x_k+1⟩ + V[x_k+1](x)

Using inequalities for proximal operator (<ref>) and (<ref>) we obtain that 

    ψ(x_k+1, x_k) + V[x_k](x_k+1) ≤ψ(x, x_k) + V[x_k](x) - V[x_k+1](x),

From (<ref>) and (<ref>) we can get

    1/n(f(x_k) - f(x)) ≤ -_i(ψ(x, x_k)) ≤ -_if(x_k+1) + _if(x_k) + _iV[x_k](x) - _iV[x_k+1](x)

Then take the full mathematical expectation from each inequality, where k = 0, …, N-1, put x = x_* and sum all the inequalities for k = 0, …, N-1, we obtain that 

    1/γ∑_k=0^N-1 f(x_k) - N/γf(x_*) ≤(f(x_0) - f(x_N)) + V[x_0](x_*) -  V[x_N](x_*)

Since V[x_N](x_*) ≥ 0, then

    1/γ∑_k=0^N-1 f(x_k) - N/γf(x_*) ≤(f(x_0) - f(x_N)) + V[x_0](x_*)

Using Yensen inequality and the fact that f(x_N) ≥ f(x_*) we obtain final result

    f(x_N) - f(x_*) ≤γ/N(f(x_0) - f(x_*)) + γ/NV[x_0](x_*).





§ CONCLUSION

In this paper, we introduce a unifying framework, which allows to construct different types of accelerated randomized methods for smooth convex optimization problems and to prove convergence rate theorems for these methods. As we show, our framework is rather flexible and allows to reproduce known results as well as obtain new methods with convergence rate analysis. At the moment randomized methods for empirical risk minimization problems are not directly covered by our framework. It seems to be a n interesting direction for further research. Another directions, in which we actually work, include generalization of our framework for strongly convex problems based on well-known restart technique. Another direction of our work is connected to non-uniform probabilities for sampling of coordinate blocks and composite optimization problems.


Acknowledgments. The authors are very grateful to Yu. Nesterov and V. Spokoiny for fruitful discussions. Our interest to this field was initiated by the paper <cit.>.


siamplain




