A stochastic gradient descent algorithm with random search directions

Firstly, we introduce some notations. Secondly, we shall formulate our new class of SGD algorithms with random search directions which includes the SCGD algorithm. Finally, we will spell out some regularity assumptions. The SCGD algorithm as given in (3), represents the practical definition by considering the vectors in the canonical basis of R d . However, we can extend this coordinate selecting rule by using more general random vectors with a possible adaptive sampling policy. Therefore, we introduce the Stochastic Coordinate Gradient Descent algorithm with Random Search Direction (SCORS) defined for all n 1, by X n +1= X n γ nD (V n +1) f U n+1( X n), (SCORS) where the initial state X 1 is a squared integrable random vector of R d which can be arbitrarily chosen, D (v) = vv T for any vector v R d, the sequence (U n) is independent from (X n) where ( U n) is independent and identically distributed with U ([ [1, N ] ])distribution and V n is a random vector of R d sampled from an underlying distribution P n satisfying certain conditions (see Assumption 1 below). Furthermore, we 3 assume that V n +1is independent from U n +1conditionally on F n, where F n = σ (X 1, . . .