A stochastic gradient descent algorithm with random search directions
Authors: Eméric Gbaguidi
Venue: Accepted by TMLR ()

Abstract: Stochastic coordinate descent algorithms are efficient methods in which each iterate is obtained by fixing most coordinates at their values from the current iteration, and approximately minimizing the objective with respect to the remaining coordinates. However, this approach is usually restricted to canonical basis vectors of $\mathbb{R}^d$. In this paper, we develop the class of stochastic gradient descent algorithms with random search directions. These methods use the directional derivative of the gradient estimate following more general random vectors. We establish the almost sure convergence of these algorithms with decreasing step. We further investigate their central limit theorem and pay particular attention to analyze the impact of the search distributions on the asymptotic covariance matrix. We also provide non-asymptotic $\mathbb{L}^p$ rates of convergence.

Published in Transactions on Machine Learning Research (07 (07/2025)
A stochastic gradient descent algorithm with random search directions
Eméric Gbaguidi
Institut de Mathématiques de Bordeaux
Université de Bordeaur
Reviewed on OpenReview: https: openreview. net/ farum? .d=nnEEBAa..S5
Abstract
Stochastic coordinate descent algorithms are efficient methods in which each iterate is ob- tained by fixing most coordinates at their values from the current iteration, and approxi- mately minimizing the objective with respect to the remaining coordinates. However, this approach is usually restricted to canonical basis vectors of R this paper, we develop the class of stochastic gradient descent algorithms with random search directions. These meth- ods the directional derivative of the gradient estimate following vectors. We establish the almost sure convergence of these algorithms with docreasing step. We further investigate their central limit theorem and pay particular al tention to analyze the impact of the search distributions on the asymptotic covariance matrix. We also provide non-asymptotic L rates of convergence.
general random
1 Introduction
Consider the unconstrained optimization problem in Rd which can written as
min f(x), zER
(P)
where f is the average of many functions,
N Σ fx()). k=1
f(x) N
(1)
Many computational problems in varions disciplincs can be formulated as above and the stochastic algorithms are now a common approach solve (P) since the seminal works of Robbins Monro [195]] and Kiefer Wolfowitz (1952). The most famous of them is the standard Stochastic Gradient Descent (SGD) algorithm given, for all 1, by
X Xn, Yne V funnr (Xn),
(SGD)
where the initial state X1 is a squared integrable random vector of Rd which can be arbitrarily chosen, V)(X,) is the gradient of the function f caleulated at the value X,, (U,) is a sequence of independent and identically distributed random variables with uniform distribution on (1,,,...,NN) which is also independent from the sequence (X,). Moreover, (ra) is positive deterministic sequence decreasing towards zero and satisfying the standard conditions
Yn = +00 and
+00.
(2)
Despite its computational efficiency provided by using a random gradient estimate, the SGD algorithm still requires the computation of vector of size d at each iteration. However, in large-scale machine

---

Published in Transactions on Machine Learning Research (07 (07/2025)
learning problems, the reduction of the calculation cost remains one of the main challenges. Moreover. the vast majority of SGD algorithms update all coordinates in the same way (Robbins & Monro 1951
Gower et al. 2021b Leluc & Portier 2022). These issues led to the development of Stochastic Coordinate
Gradient Descent (SCGD) algorithms which are very casy to implement and have become unavoidable in
high-dimensional framework (Nesterov
2012
Shalev-Shwariz & Zhang 2013: Wright, 2015). This class of
methods have received great deal of attention in recent years due to their potential for solving largo-scale
optimization problems (Lin et al., 2014
Leluc & Portier 2022).
The SCGD algorithm modifies the SGD algorithm in the sense that its update rule is given, for all > 1, by
{
x = =x(²) x -x(²)
if j + Ea+1,
(3)
()
-n9ntt
if j Ent1s
where x stands for the j-th component of vector Xns In+1 = Vi (Xn) and (En) a sequence of random variables with values in {1.2....,d d} used to select coordinate of the gradient estimate and follows distribution called the coordinale sampling policy.
Hence, the SCGD algorithm selects and updates one coordinate at each iteration in order to sufficiently reduce the objective value while keeping other coordinates fixed. In fact, this approach can also be seen as the SGD algorithm applied just on one random coordinate. There are many strategies for the choice of the coordinate sampling policy. Our goal is to go further in the analysis of the SCGD algorithms with docrcasing step. Firstly, we develop the class of stochastic gradient descent algorithms with random search directions. These methods include the SCGD algorithms and use the directional derivative of the gradient estimate following more general random vectors. Thus, beyond the SCGD algorithms, we consider the random directions sampled from gaussian and spherical distributions (sce Section 3j. Based on weak hypotheses associated to the objective function, we establish the almost, sure convergence of these algorithms with decreasing step (see Section 4.1]. Secondly, we investigate their central limit theorem and we obtain that the asymptotic covariance matrix depends on the choice of the search dircction distributions (sce Section 4.2p. Thorefore, we provide an introductory analysis on the asymplotic performances for different choices of random directions. Lastly, we provide non-asymptotic LP rates of convergence for the SGD algorithms with random search directions (see Section 4.3
Organization of the paper.
The rest of the paper is organized as follows. Section 2 summarizes the state of art on the SCGD algorithms. In Section 3 introduce the thcoretical framework of our paper. Section is devoted to main results. Finally, in Section 5 we illustrate the good performances of the algorithms with decreasing step through numerical experiments on simulated data. All technical proofs are postponed in appendices.
2 Related work
Several stochastic coordinate descent algorithms and their variants were proposed and analyzed over years
in (Shale--Swwartz & Tewari 2009: Nesterov 2012 Richtárik & Takée 2016 Gorbunov et al. 2020 Leluc & Portier 2022 Ramesh et al.) 2023 They are recursive stochastic algorithms in which each iterate is obtained by fixing most coordinates at their values from the current iteration, and approximately minimizing the objective with respect the remaining coordinates (Wright 2015). For Nesterov (2012), the main advantage of the coordinate descent. methods is the simplicity of each iteration, both in generating the descent direction and in updating of the variables. Hence, many questions have been addressed in the literature on these algorithms due to their considerable interest.
On the one hand, the choice of the coordinate sampling policy is clearly a major issue. From that, we can distinguish two main classes of coordinate selection rules: deterministic and stochastic. However, [Sun et al.) (2017) considered that the stochastic block rule casier to analyze because taking expectation will yield good approximation to the full gradient and ensures that every coordinate updated at the specified frequency. Richtárík & Takád (0066) also obtained that the scheme of updating single randomly selected
2

---

Published in Transactions on Machine Learning Research (07/2025)
coordinate per iteration with optimal probabilities may require less iterations to converge, than all coordi- nates updating rule at every iteration. For its part, Needell et al.
(2014) suggested a non-uniform sampling
for the stochastic gradient descent. Moreover, (Chang et al. 2008 Shalev-Shwartz & Zhang 2013) proved
that the randomized strategics are more efficient than the simple rule of cycling through the coordinates
(Luo & Tseng 1992 Beck & Tetruashvili 2013 Saha & Tewari 2013 Nevertheless, Nutini el al. (2015)
compared and showed that the deterministic Gauss-Southwell rule faster than the random coordinate (aaha
selection rule in some empirical cases. However, Saha & Tewari (2013) remember us that Gauss Southwell
rule typically takes O(d) time to implement instead of just [(1) for the uniform randomized rule. This was
the main motivation for the choice of uniform probabilities in Shalev-Shwartz & Tewari (2009) which can
also justify a good performance of the SCGD algorithmss
On the other hand, Tao et al. 2012) proposed and showed the convergence rates of stochastic coordinate descent methods adapted for the regularized smooth and non-smooth losses. Likewise, [Beck & Tetruashvili (2013) established a global sublinear rate of convergence of the block coordinate gradient projection method with constant stepsize which depends on the Lipschitz parameters. Later, Lin et al. (2014) developed an accelerated randomized proximal coordinate gradient method which achieves faster linear convergence rates for minimizing strongly convex functions than existing randomized proximal coordinate gradient methods. Moreover, Konečný et al. (2017) introduced the semi-stochastic coordinate descent algorithm with constant stepsize which picks a random function and a random coordinate both using non-uniform distributions at each step. They proved the convergence of f(X,) towards the minimum of f in IL2 under the strong convexity assumption on f. There exist many others contributions on the stochastic coordinate descent variants. For instance, RRchtáriik & Takáč (016) investigated the parallel coordinate descent method in which a random subset of coordinates is chosen and updated at cach itcration. Allen-Zhu et al. (2016) also studied the accelerated coordinate descent algorithm using non-uniform sampling. Kozak et al. (2019) and
Hanzely et al. (2018) studied the projected gradient algorithms onto a random subspace at each iteration with constant stepsize. [Hanzely et al. (2018) established the convergence only in expectation by assuming that f is p-strongly convex. We also highlight that Kozak et al. (2019) proved the almost sure convergence of (Xn) under the same restrictive assumption of strong-convexityy However, both of these papers compute and use the full gradient (X,,)) at each iteration. This will not be the case at all here, since we use a uniformly chosen random estimate of the gradient. Morcover, in our paper, we consider decreasing stepsize % to avoid dependence on j--troong convexity and I-smoothness constants.
More recently, Leluc& & Portier (2022) provided the almost sure convergence as well as non-asymptotic bounds of the SCGD algorithm with decreasing step in a non-convex setting and including zeroth-order gradient estimate. They proved the convergence of the SCGD iterates towards stationary points in the sense that f((x,) converges to almost surely. They also proposed non-asymptotic bounds on the optimality gap (X)( - ["] where f* is a lower bound of f. These results have been established by assuming that f is L-smooth and under the growth condition (Lelue & Portier 2022; Gower et al. 2021b). The non-asymptotic bounds required the additional
(PI.) condition (Polyak] 1963 Gower et al. 2021a).
Although the assumptions used in Leluc & Portier (0022) are relatively weak, one can still try to relax them and provide the algorithm convergence directly on the sequence (X,). Furthermore, one can also be interested by non-asymptotic L" rates of convergence for any integer p. To our best knowledge, the central limit theorem for the SCGD algorithm was not previously establishod.
3 Preliminaries
In this section, present the mathematical background of the paper. Firstly, we introduce some notations. Secondly, we shall formulate our class of SGD algorithms with random search directions which includes the SCGD algorithm. Finally, we will spell out some regularity assumptions. In order to avoid any ambiguity, every vector norm is the l2 norm
The SCGD algorithm as given in (3 represents the practical definition by considering the vectors in the canonical basis of Rd. However, we can extend this coordinate selecting rule by using more general random vectors with possible adaptive sampling policy. Therefore, we introduce the Stochastic Coordinate Gradient.
3

---

Published in Transactions on Machine Learning Research (07/2025)
Descent algorithm with Random Search Direction (SCORS) defined for all n b by
Xn+1 = X,, 7n (U (Xn):
(SCORS)
where the initial state X1 is a squared integrable random vector of R2 which can be arbitrarily chosen, for any vector v E R2 the sequence (Un) independent from (Xx) where (Un) is independent and identically distributed with 4 ([I,N] distribution and V, a random vector of R sampled from an underlying distribution Pn satisfying certain conditions (see Assumption [ below). Furthermore, we assume that Va+1 is independent from Un+1 conditionally on Fn, where Fn a (X1, Xn)) is the o-field associated to the sequence of iterates (X,). In the same way before, (7,) is positive deterministic sequence decrcasing towards zero and satisfying the standard conditions
D(u)= =vv""""" vv"
Moreover, we will consider the random direction Vn+1 that satisfies the distributional constraint [) = La in order to reduce the bias in the SCORS gradient estimate.
Assumption 1. For all n 2 1, we assume that the random direction vector Vn is sampled from indepen- dent and possibly adaptive distribution Pn, such that
=(D(V Ls
a.s.
(4)
In addition, we suppose that the 4-th conditional moment of Vn+1 is bounded, i.e. there erists a positive constant my such that E| & my for all n > 1.
Choices of the direction distribution. We conduct here comprehensive analysis different choices of distributions Pn, satisfying Assumption 1 Several popular choices were proposed in (Chen el. al. 2024 and are listed as follows.
(U) Uniform in the canonical basis: Vn is sampled from (ydei..... vdea) with equal probability 1/d, where (e1....,ed) is the canonical basis of Rd.
(NU) Non-uniform in the canonical basis with probabilities (r.d): Vn is sampled such that for all n > 1 and j E [1.d],
1
VA
Prien Egni
(5)
where (Ex) is sequence of independent random variables defined on [1, such that
Pl = j|Fn-il= Pn.j
(6)
with Pa.j > 0 for all j E [1,d] and Ej=1 Pn.j = 1.
(G) Gaussian: (Vx) is sampled from the normal distribution WN Ia).
(S) Spherical: we sample (Vx) from the uniform distribution on the sphere with Euclidean norm 2 d.
It is easy to see that in all above choices, the search distribution P,, satisfies the equality 4 Moreover, in the particular uniform sampling case, the random coordinate is uniformly chosen at each iteration. In others words, the coordinate along which the descent shall proceed, is selected in [1,4] with the same probability equal to 1/d. Furthermore, we can consider many procedures to compute the probabilities (Pm.1....,PP.. in the non-uniform case. We will spell out different strategies the numerical experiments.
However, one can remark that the [U] and [NU] direction distribution choices correspond to the standard SCGD algorithms (3). Thus, the most interesting contribution here lies in the cases (G) and (S) by taking into account random directions of descent other than those of the canonical basis vectors of Rd. The SCORS algorithm can also be interpreted as the use of the dircctional derivative of the gradient estimate following given random vectors. Malladi et al. (2023) explored a memory-efficient zeroth-order algorithm with projected gradient for fine-tuning large language models. The directional derivative can be computed in forward-mode and this requires far less memory than backward passes. Therefore, the SCORS algorithm proposed here, may also find an interest for such applications in fine-tuning. In the sequel, we state the others general assumptions required for our analysis and used throughout the paper.
4

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Assumption 2. Assume that the function f is continuously differentiable with unique equilibrium point x² in Rd such that -f(=")=0.
Assumption 3. Suppose that for all Rd with x²,
(r x- x² Vf(x)) 00
Assumption 4. Assume there erists positive constant L such that, for all E RR,
VSL(2) Vfa(=")11 & L|le - x²112.
N 1=
Assumption 2 is standard hypothesis for the study of SGD algorithms. Furthermore, Assumption B does not impose restrictive strong convexity hypothesis on f. We need to note though that this condition is much weaker than saying that f is strictly convex. Moreover, our Assumption is of key importance and essential in general non-convex setting. This condition states that at the optimal point, the gradient of all functions fk for any 1 & k & N, does not change arbitrarily with respect to the vector our assumption with Lipschitz condition for the gradient of the objective function. It is obvious that if each function fü has Lipschitz continuous gradient with constant VLg, then Assumption 4 is satisfied by taking L as the average value of all Lę- Assumption 4 is also less restrictive than the growth conditions with the VT-smoothness of ʃ, which are classical assumptions among the literature. We point out that both Assumptions and are enough suitable obtain the almost sure convergence of the SCORS algorithm.
R Let us link
4
Main results
We first present the almost sure convergence of the SCORS algorithm. Then, we focus on the central limit theorem for the SCORS algorithm, and finally we propose non-asymptotic L rates of convergence.
4.1 Almost sure convergence
Theorem 1. Consider that (Xn) the sequence generaled by the SCORS algoritho with decreasing slep In addition, suppose that Assumptions and 4 are satisfied. Then, we
sequence (mn) satisfying ? have
lim Xn xx" a.S.,
(7)
and
lim f(Xx) = f(x²) a.s. n=000
(8)
Proof. Recall that for all n >
X = Xn. - 7n D(v++1) V (Xp).
(9)
Let us consider the Lyapunov function Tn defined for all 1, by
T, = 1x, x ==1
Hence, it follows that almost surely,
Tat1 = | - x2
Xnn - =x" Vn DVV VI,,,,
To -27 (Xn, - -x" D(V.+)
DVV( V (Xn))(X()) DVV
(10)
However, have from Assumption 1 that almost surely
B(D(V Ia-
(11)
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Moreover, obtain from and the fact that Un+1 is uniformly distributed on [1 that
E EV (X.) (X),.) 0.8.
(12)
By putting together that
12 and the conditional independence of Vn+1 and Un41, it immediately follows
B)D(V++1) (X.)) =VV(X=))=V((A))) 0.s.
(13)
Furthermore, we recall by definition that,
D(v++1) = Vn+1 VV
(14)
which implies that
fu 2x || VT V fu (x,))l
= ((V,41, Vfrnr (xn))) |V++1
(15)
By using the Cauchy-Schwarz inequality, we deduce from 15 that
(X,)] < VI (Xx))1
(16)
Once again, from the conditional independence of Vn+1 and Un+1 combined with the inequality obtain that almost surely
we
I(V. 1 (x.))11 < E
(17)
It implies via Assumption
! that there exists a positive constant my such that
Ell (X,1), < m4 (x.))
(18)
However, we have that almost surely
IV (X,))1 (( V Fui..(""")
11 fe (x 11)
(19)
Define for all x E Rd
N 7xxx) = N Σ
- -
As Un41 is uniformly distributed on [1, NI, we clearly have
E| funes (Xx) v fu + (X(n)
a.s.,
(20)
and
N V La (x*)
1
Pull (x')
(21)
N
Then, by using the four inequalities
18
19
20
and
21
we obtain that
ElII((Y++)
(xx) 2F < 2ma + 0*) a.s.,
(22)
where
0" = N (x')11
Furthermore, from the three contributions
10
13
and
22
one deduces that
P[Tn+ilJr Tn 2%, (Xn
(Xx)) (7 + 0*) 0.8.
(23)

---

Published in Transactions on Machine Learning Research (07 (075))
However, Assumption implics that r² LT, almost surely. Consequently, obtain from 23 that
1 < (1 2Lm44 In (n x², V((x,)) 2mp40 0.S.,
(24)
which can be rewritten as
TT < + + An Bn
0.s.
where on 2L n An 2m40" and B, 27n (X, xx, Vf(Xx)). The four sequences (Tn), (an), (An)
and (B,)) are positive sequences of random variables adapted to (Fx). We clearly have from that
Σ an +o0 and Σ An < to0.
Hence, we deduce from the Robbins-Siegmund Theorem (Robbins & Siegmund 1971 given by Theorem D.1 that (In) converges a.s. towards finite random variable T and the series
Bn < +00
a.8.
(25)
#=1
It only remains to show that T = 0 almost surely. Assume by contradiction that T >> 0. For some positive constants a < b, denote by the annulus Rd,
Ω = fxr IRd,
0 - x²112 b}.
Let F' be the function defined, for all æ E Rd. by
- = (r x V)(x)).
We have from Assumption that F is a continuous function in Ω compact. It implies that there exists a positive constant e such that F(x) > e for all æ E Ω. However, for n large enough, X,, E Ω which ensures that In (X, - x., vx(xx)) > cyn. Therefore, it follows from 25 that
8
Σ
In +00.
This is of course in contradiction with the left side of conditions 2 Consequently, we conclude that T 0 almost surely, leading to
lim Xn =
a.s.
By continuity of the function f, we also have which completes the proof of Theorem
4.2 Central Limit Theorem
We carry on with the central limit theorem for the SCORS algorithm. In this subsection, we assumee that f is twice differentiable. Then, we denote by ==(²((x") the Hessian matrix of f at x".
Assumption 5. Suppose that J is twice differentiable with unique equilibrium point x² in Id such that ff(=*) = 0. Denote by p= (M)in(H) the minimum eigenvalue of H. We assume that > 1/2.
The central limit theorem for the SCORS algorithm is as follows.
Theorem 2. Consider that (Xn) the sequence generated by the SCORS algorithm with decreasing step "/n 1/n and i.i.d. random direction vectors (Vn) sharing the same distribution P. satisfying Assumption Moreover, suppose that Assumption g is satisfied and
lim X, x²
a.s.
(26)
n +
7

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Then, we have the asymptotic normality
Vn(Xa- x2)
N)(
(27)
+
where the asymptotic covariance matrir is given by
Σ = / (e (e-(H-1a/2hlu71 (H-Ta/2)"
with
-=E[VV"
(28)
V. is random vector with the same distribution P and
1 N
V[l(=")
(29)
Proof. The proof of Theorem 2 can be found Appendix
We provide below the expressions of I according to the direction distribution choice P. The following result can be found in (Chen al. 2024 p. 6).
Proposition 3. Considering the matrix Q defined in 29 and under the direction distribution P listed in Section we have the following results,
Uniform in the canonical basis: I(V) d (ddiag()))
NNU
Non-uniform in the canonicol basis: ((NU) diog (Qu1 huu//p...... Qua/pa).
G
Gaussian: P(G) (2Q + tr())
d
S
Spherical: ((S)
d + (2Q + tT)))aa)
The central limit theorem is very useful and provides the theoretical guarantees necessary for building asymptotic confidence intervals based on the normal distribution. This result therefore makes it possible to address questions related to statistical inference such as the hypothesis lesting while controlling the variability of algorithms. The point that seems difficult to us here lies on the computation of the asymptotic covariance matrix in a high-dimensional context. However, the standard Monte Carlo methods can useful obtain an estimation.
Furthermore, from Proposition the spherical random directions are always more efficient than the gaussian one. However, Chen et al. (2024) remark that there is no general domination relationship among the other choices. Nevertheless, in the particular case where Q = La, we have (S) = ((U) = dII which means that the spherical and the uniform choices achieve the same asymptotic performances for the central limit thcorem. Thus, one can obtain different optimal choices of P according lo the experimental design and the data used.
can draw other interesting conclusions. In fact, one observes that
4.3 Non-asymptotic L rates of convergence
In this subsection, we are interesting by the non-asymptotic L rates of convergence the SCORS algorithm. Hence, our goal to investigate, for integer p > 1, the convergence rate of Bl||X,, - xx [|p] for the SCORS algorithm where the docreasing step is defined, for all by.
7/
(30)
for some positive constant and 1/2 &
8

---

Published in Transactions on Machine Learning Research (07/2025)
Assumption 6. Assume there erists positive constant μ such that for all R with x²,
x - x", Vf(z)) > ul =x11|
This assumption sometimes known as the Restricted Secant Inequality (RST) in the literature Karimi et al. 2016 Yi et al. 2020 Guille-Escuret et al. 2022 For instance, Theorem in Karimi et al. (2016), established that when f function with sipschitz-contimmon gradient, the RSI implies the Polyak- Lojrak-Lojssewiizz (PL) condition. However, the PT condition is not sufficient in our analysis to obtain the bound of [ xx [1=]
In this case, propose use the RST minimal condition. We highlight that unlike the strong convexity, Assumption 0 alone does not even imply the convexity of f. The RSI is also weaker than the Weak Strong Convexity (Karimi et al., 2016 Yi et al. 2020). First of all, we focus on the case Theorem
in Theorem before extending this result for any integer p 2 1 in
Theorem 4. Consider that (X,) is the sequence generated by the SCORS algorithm with decreasing step and 2 are salisfied with op & 20-1 and
sequence (7m) defined by (30). Suppose that Assumplions 2cp > 1 if a 1. Then, there erists positive constant K such that for all > 1,
K
F|II,, - x x01
(31)
n
Proof. The proof of Theorem 1 can found Appendix B
Assumption 7. Assume that for some integer p 2 1, there exists a positive constant Tpp such that for all
x Rd,
1
Σ (V - < Lp 111
N
Moreover, suppose that there exists a positive constant map such that for all n 3 1,
E[I i [( & map-
(32)
Theorem 5. Consider that (Xn) is the sequence generated by the SCORS algorithm with decreasing step
sequence (Qn) defined by (30) and such that the initial state X, belongs 1.2p. Suppose that Assumptions 2 and 7 are satisfied with pep & 2 and ep a=== = Then, there exists a positive constant K, such that for all > 1,
K PP
E [ x 11
(33)
The proof of Theorem 5 is left to the reader as it follows the same lines as the proof of Theorem 4 in Bercu et al. 2024).
5 Numerical Experiments
The purpose of this section is to show the behavior of the SCORS algorithm on simulated data. For that goal, we consider the logistic regression model (Bach 2014 Bercu et al. 2020 associated with the classical minimization problem P of the convex function f given, for all x R by
N fa(2) = Σ (log(1 + exp((a, wx))) yu (x, wx)),
f(x) = N
where E Rd is a vector of unknown parameters, wy E Rd is vector of features and the binary output yk E {0, 1). One can casily see that the gradient of f is given by
N Σ
(1
Vf(x)= fx) = N R=1
1 exppeppeee wk)) 8k wk-
(34)

---

Published in Transactions on Machine Learning Research (07 (025)
In the same way as Chen et al. (2024). carry out the experiments simulated data in order to illustrate the almost sure convergence (Theorem D the central limit theorem (Theorem 2 and the non-asymplotic L rate of convergence (Theorem Therefore, we consider an independent and identically distributed collection (ww1.3)).... such that
where the covariate w ~ Na(O, Ia) and the response E {0, 13 sampled
P(y = 1/w) + e-w,a")
(35)
The true model parameter E R is selected uniformly from the unit sphere. Furthermore, we set the sample size N 50000 and the parameter dimension d = 50. The stepsize 7n
1/n used where > 1
stands for the iterations. Here, we will compare the four methods
(
NU
G and (S) described in
Section 3 Let us define the initial value d1,k given, for any k = I....... N, by 91,6
fu (X Moreover, the
sequence kgn,k) is updated, for all n e and < k
& N, as
(Xn) if Un+1=k;
1,+11k
(36)
In.k
otherwise.
For the non-uniform search distribution
[NU) the probabilities Pv,j are computed for all n > and j e
[1. d], follows
1
if j=
Σ Ei=1 9 4
Pnj
(37)
1 pn.j"
otherwise,
1
where j" = argmax j=l,...d
o and 91 = -E 91.k-
The idea behind this choice is to select with the highest probability, the coordinate of recursive estimate of the gradient which has the highest norm, since the goal is to reduce the gradient at each iteration in order to make it converge towards
Figure I illustrates the almost sure convergence of the algorithms. This graph represents the relative opti- mality gap function < ||x -|,,-=" x"1 computed. This criterion is chosen in order to make an honest comparison of the algorithms in competition. For instance, the SGD algorithm computes all d coordinates of the gradient at each iteration, while the SCORS algorithm with uniform search distribution (U) uses just single coordinate. Thus, we made this choice to better take this principle into account.
X 1-1 where stands for the number of the gradient coordinates
0.975
0.830
Relative optimality gap
0.950
(NU)
Relative optimality gap
0.825
0.925
(5)
0.820
0.875
0.815
0.850
0.810
0.825
0.805
0.800
0.800
2
5
0
2
3
5
#Queries of gradient coordinates
#Queries of gradient coordinates
(a) All methods
(b) (U), (S) and SGD
Figure 1: Almost sure convergence of the algorithms with nn 1/n.
10

---

Published in Transactions on Machine Learning Research (07 (07/2025)
As shown from the previous graph, the SCORS algorithm with uniform search distribution U is the best for this decreasing step. It is therefore interesting to see that the SCORS algorithm can achieve better performance than the SGD algorithm in terms of almost sure convergence. Moreover, we observe that the spherical distribution choice and the SGD algorithm are close. However, the gaussian choice is clearly the worst among the methods in compelition. Furthermore, the results concerning the central limit theorem of the (U) (NU), [) and (S) algorithms are illustrated by Figure 2 We consider the same distributional convergence as Bercu al. (2024) and use the standard Monte Carlo method to estimate the asymptotic standard deviation of each algorithm. We therefore observe that these simulations confirm the asymptotic normal distribution of the SCORS algorithms with all the search distribution choices considered. Note also that the U method has the smallest asymptotic standard deviation for the large dimension d = 50.
0.012
N(0.05)
N:0,03)
(U)
(NU)
0.010
0.010
0.008
0.008
Density
Density
0.006
0.004
0.004
0.002
0.002
-150
-100
-50
50
100
150
-150
-100
-50
100
150
(a)
( where 0n R2 41.792
(b) (NU)
where 6, RJ 43.325
0.016
N(O.0E)
0.014
N(o.6g)
(G)
(5)
0.012
0.012
0.010
Density
0.010
Density
0.008
0.008
0.006
0.006
0.004
0.004
0.002
0.002
0.000
0.000
-300
-200
-100
(c)
G where on 43.193
(d) (S) where 6n 43.054
Figure 2: We used 1000 samples, where each one was obtained by running the associated algorithm for n = 500000 iterations.
In Table D report a comparison of the algorithm performances based on the computational cost. This criterion is estimated here by the average CPU time per iteration after running 5000000 iterations.
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 1: CPU time per iteration (s).
Algorithms
SGD
NU
G
CPU time
5.05 x 10 4.98 x 10-6 12.01 x 10
6.48 x 10
8.92 x 10-6
As expected, the SCORS algorithm with uniform search distribution tional time per iteration. Next come respectively the SGD, (G) difference between the CPU times per iteration of the SGD and (U) algorithms is not very significant here, which is explained by the particular form of the gradient in this specific case the logistic regression (34).
U is the fastest in terms of computa- [S] and (NU) methods. Nevertheless, the
Lastly, Figure provides approximate results on the non-asymptotic L rate of convergence. This graph just gives idea on how the mcan squared error of the algorithms decreases when goes to infinity. Each epoch consists of rumning 1000 iterations.
12400
(NU)
(G)
Mean squared error
12300
(S)
12200
12100
12000
11900
11800
11700
100
300
epochs
Figure 3: Mean squared error with respect to epochs. We confirm the decreasing order of the mean squared error of Xn - x² with respect to n.
Acknowledgments
We would like to thank François Portier for fruitful discussions on preliminary version of the manuscript. This project has benefited from state support managed by the Agence Nationale de Recherche (French National Research Agency) under the reference ANR-20-SFRI-0001
References
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárík, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning, pp. 1110-1119. PMI.R, 2016.
Francis Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic re- gression. The Journal of Machine Learning Research, 15(1):595-66 627, 2014.
Francis Bach and Eric Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
12

---

Published in Transactions on Machine Learning Research (07/2025)
Amir Beck and Luba Tetruashvili. On the convergence of block coordinate descent type methods. SIAM journal on Oplimization, (3(4):2337-206) 2013.
Bernard Bercu and Jérémie Bigot. Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measurcs. The Annals of Statistics, 49(2):968-9)) -987, 2021.
Bernard Bercu, Antoine Godichon, and Bruno Portier. An efficient stochastic newlon algorithm for parameter estimation in logistic regressions. SIAM Journal on Control and Optimization, 58(1):348 367, 2020.
Bernard Bercu, Luis Fredes, and Eméric Gbaguidi. On the saga algorithm with decreasing step. arXiv preprint ar arXit:2410.0976/ 2024.
Kai-Wei Chang, Cho-Jui Hsieh, and Chib-Jen Lin. Coordinate descent method for large-scale 12-loss linear support vector machines. Journal of Machine Learning Research, 9(7), 2008.
Chen, Zehua Lai, He Li, and Yichen Zhang. Online statistical inference for stochastic optimization via kicfor-wolfowitz methods. Journal of the American Statistical Association, 119(548):2972-225) 2024.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent. International Conference on Artificial Intelligence and Statistics, pp. 680-690. PMLR, 2020.
Robert Gower, Othmanc Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: rales, minibatching and interpolation. In International Conference Arlificial Intelligence and Statislics, pp. 1315-13511 1323. PMLR, 2021a.
Learning
Robert M Gower, Peter Richtárík, and Francis Bach. Stochastic quasi-gradient methods: Variance reduction via jacobian sketching. Mathematical Programming, 188(1):135-192, 2021b.
Charles Guille-Escuret, Adam Ibrahim, Baptiste Goujaud, and Ioannis Mitliagkas. Gradient descent is optimal under lower restricted secant inequality and upper error bound. Advances in Neural Information Processing Systems, 35:24893-24900 2022.
Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. Sega: Variance reduction via gradient sketching. Advances in Newral Information Processing Systems, 31, 2018.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradee gradient methods under the polyak-lojasiewicz condition. Tn Joint European conference on machine learning and knowledge discovery in databases, pp. 795-811. Springer, 2016.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, pp. 462-466, 1952.
Jakub Konečný, Zheng Qu, and Peter Richtárik. Semi-stochastic coordinate descent. optimization Methods and Software, 32(5):993-1005, 2017.
David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. Stochastic subspace descent. an preprint arXio:1904.01143. 2019.
Rémi Lelue and François Portier. Sgd with coordinate sampling: Theory and practice. Journal of Machine Learning Research, (3(22)): 2022.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. Advances in Neural Information Processing Systems, 27, 2014.
Zhi- Quan Luo and Paul Tseng. On the convergence of the coordinate descent method for convex differentiable minimization. Journal of Optimization Theory and Applications, 72(1):7-35, 1992.
13

---

Published in Transactions on Machine Learning Research (07 (225))
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Aduances in Neural Information Processing Systems, 36:53038 53075, 2023.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27, 2014.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization. 22(2):341-362, 2012.
Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke. Coordinate descent converges faster with the gauss-southwell rule than random selection. In International Conference on Machine Learning, pp. 1632-1641. PMLR, 2015.
Boris Teodorovich Polyak. Gradient methods for minimixing functionals. Zhurnal vychislitel 'no malemaliki i matematicheskoi fiziki, 3(4):643- 653, 1963.
Amrutha Varshini Ramesh, Aaron Mishkin, Mark Schmidt, Yihan Zhou, Jonathan Wilder Lavington, and Jennifer She. Analyzing and improving greedy 2-coordinate updates for equality-constraindd optimization via steepest descent in the 1-norm. arXiv preprinl arXiv:2307.01 169, 2023.
Peter Richtárik and Martin Takáč. On optimal probabilities in stochastic coordinate descent methods.
Optimization Letters, 10:1233- 11213-113,,, 1243, 2016.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemalical statistics, pp. 400-407, 1951.
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing methods in statistics, pp. 233-257. Elsevier, 1971.
Ankan Saha and Ambuj Tewari. On the nonasymptotic convergence of cyclic coordinate descent methods. SIAM Journal Optimization, (311)5676-601, 2013.
Shai Shalev-Shwartz and Ambuj Tewari. Stochastic methods for 1 regularized loss minimization. Proceedings of the 26th Araual International Conference on Machine Learning, pp. 929 936, 2009.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss mini- mization. Journal of Machine Learning Research, 14(1), 2013.
Tao Sun, Robert Hannah, and Wotao Yin. Asynchronous coordinate descent under more realistic assump- tions. Advonces in Neural Information Processing Systems, 30, 2017.
Qing Tao, Kang Kong, Dejun Chu, and Gaowei Wu. Stochastic coordinate descent methods for regularized smooth and nonsmooth losses. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part I 23, pp. 537 552. Springer, 2012.
Stephen J Wright. Coordinate descent algorithms. Matheraatiaal progremmiing 151(1):3 34, 2015.
Xinlei Yi, Shengjun Zhang, Tao Yang, Tianyou Chai, and Karl H Johansson. Exponential convergence for distributed optimization under the restricted secant incquality condition. IFAC-PPpersOnLine, 53(2); 2672 2677, 2020.
Li-Xin Zhang. Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs. The Annals of Applied Probability, 26(6):3630 3658, 2016.
14

---

Published in Transactions on Machine Learning Research (07 (075)
A Proof of Theorem 2
Proof. Let us reformulate the SCORS iterates for all n > 1, as follows
Xn+1 = Xn (Vf(X,) + En+1),
(38)
with
En41 = - VV((x))
(39)
and
2x+1 D(V++1) fun4s (Xn).
(40)
Moreover, we recall from
13 in the proof of Theorem that
F[ = (X,,) 0.8.
(41)
Then, it follows from 39 and 41 that
Elen+1
a.S8;
(42)
which means that (Ex) is a martingale difference sequence adapted to the filtration (Fr).
Therefore, we can also deduce that almost surely
Bleat16 = ED VX(x,)) (VS(X.))" (V((X))
(43)
Since Xn converges towards xt almost surely, obtain from Assumption that
lim vS(X,) a.8.,
(44)
n-++00
which implies that
lim 1 lim to
DD
0.8.
(45)
However, we recall by definition 40 that
ID [F] =
(X.) (D(V++1) V (Xn)) T [Fn]
= =F[[v++1 V V Su (Xa) (V (Xn)) Vn+ V [
(46)
Hercafter, we define In+1 = ( Xn, Vn+1). It is obvions that F, C In+1- Therefore, by the tower property of the conditional expectation and since Va+1 is meas-beasur,ble, we obtain from (46) that
E n+I Fr. = Vv ViT E V ferne (Xn) (X,,),)),)) 19 Vn+ VoT Fi]
(47)
Furthermore, we have that
E V funai (Xn) (V (X.)) 19
1
Σ
(X,) (VF((.))
(48)
N
km
Thus, it follows from
47 and
48 that
D n+t
[Fl = E Vv+1 VIT QnV VT ViT1FFa]
(49)
where
On N (X,, (V)(
(50)
15

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Let consider the symmetric matrix Q defined by
1 N
(51)
In fact, we have from the Jensen inequality that
E V
VIT n+1 11 Vn+ V 1 - E Vn+ VT QV V
a+1
E Vn++1
V n+1
Qn Vn V2r 1F
E Vn+1 V QU QV QV
E Vu+ V n+1 Q)V 1
Va++1 V2r x+1 (Qn - -Q)V n+1 V2' 1 FR]
E [| |1Q F1
(22)
However, Qn is -e-msuuurable and Vn+1 is independent from Fn. Therefore, Assumption with the in- oquality 52 imply that there exists a positive constant my such that almost surely
E [v++ VI+ On v [T.] - E [V++1 V QV Q & mmllQn QII-
(53)
Once again from the almost sure convergence of X, towards x² and Assumption 5 we obtain that
lim 1r - Q11 = a.s. +++000
(54)
Hence, we deduce from
and 54 that
lim n +00
F Vu+i V
Qn VT
[Va1 VV VT
a.8.
(55)
which leads to
lim +=
E VV VT Qn Vu VT 11 =
a.s.;
(56)
where
r= F. [VVV QVV*]
(57)
Thus, combining the three contributions
and 56
it follows that
lim 2+0
E( 187
F
a.8.
(58)
Therefore, we deduce from Toeplitz's lemuna that
n Blaus [Fx-1]=1
lim n-+
a.s.
(59)
T A=1
Furthermore, we have for all n > 1
||entill |entill=&2(1) [| Cn.
(60)
where
C = max (X,)))
(61)
j=I,..,N
Therefore, we define for all 0 and some positive constant M,
An
E
||E
(62)
16

---

Published in Transactions on Machine Learning Research (07 (07/2025)
and
Bn
IE
(63)
We obtain from 60 that
An
E
(lle (ee
| 2
E [||E*||
2n k=1
4(1 + 2
[
2n
4(1 + 22
sup (C.) n²l
(64)
2n
Since X, converges towards xt, it follows with Assumption 5 that
lim n+0
Cn = [Vf)(>")] too
(65)
Then, we have that almost surely
sup [ < +00, n>l
(66)
which immediately implies with 64 that
A, =
a.s.
(67)
n n-+00
Moreover, obtain with the same inequality
60 that almost surely
Bn
π
2
E [[1 [1++l*))
n
2
E [11 [[Vall Muival/>- Fa-1] Ck-1
n
E [1 [(Meiia Ck-1
(68)
By using Tocplitz's lemma and the contribution
65 we deduce that
lim
Ca-1)
max [[]](=")] to0 a.s. J=.....N
(69)
It follows from 68 and 69 that for any positive constant M,
lim sup Bn <
[[++||VI+)) max [ff(=")))3 E [[1 + [[V])*) 1 [
a.s.
(70)
+
j=l....N
Nevertheless, obtain from the Lebesgue dominated convergence theorem that
lim 00000
E (1 +|[[[* 1 (iv [>M) 0.
(71)
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Hence, it implies with 70 that
lim n-+0c
B, =
0.88
(72)
Consequently, by putting together the contributions
67 and
72
we immediately deduce that for all > 0,
lim +-0
EE |||ex||
m F = 0
a.8.
Finally, it follows from the central limit theorem for stochastic algorithms given by Theorem 2.3 in ZZang 2016) that
Vn(Xn, x²) n Na(0, E)
where
Σ
(e (e- -((--a//2)) du,
which completes the proof of Theorem 2
B Proof of Theorem 4
Proof. We already proved in 23 that for all n 2 1,
1[ T, 2% (Xn x², fx(,)) 2m + +0)
a.s.
(73)
Therefore, follows from Assumption that (X, - x,, V Vf(x,)) 3 pTm: which leads to 2pmm) Tr, 2m -2 (T (X,) + 0")
E[Tn+1 [F.] <
(74)
By taking the expectation on both side of this inoquality, we obtain that for all n 2 1,
E[Ta+1]] < (1 - 2pm)) E[T.. + 2m (E]+"(X,,)) + +
(75)
Hence, we deduce from Corollary in Appendix C below that there exists positive constant b such that, for all n > 1, (X,)) & by Consequently, the incquality
75 immediately implics, for all n > 1, that
E[Tn+i]
E
(76)
(n + 1)e
(n + 1)20
where a = 2pc and = 2220+ (m + 8*). Finally, we can conclude from Lemma D.1 that there exists a positive constant K such that for any n > 1,
K
E X x 2=11 < n
which achieves the proof of Theorem
C Additional asymptotic result on the convergence in 1_2p
The purpose of this appendix is provide additional asymplotic properties of the SCORS algorithm that will be useful in the proofs of our main results. First of all, we recall for some integer p > that T || x= 1|22,
Theorem 6. Consider that (X,) is the sequence generated by the SCORS algorithm with decrensing step 7/n satisfying Suppose that Assumptions
6 and 7 are satisfied. Then, have that
To To < +x
0.S.,
(77)
and
7n E[T < +00.
(78)
18

---

Published in Transactions on Machine Learning Research (07 (07/2025)
The proof of Theorem is very analogous to that of Theorem 8 in Bercu al. 2024 A direct consequence
of Theorem 6 using the left-hand side of (2) is as follows.
Corollary 7. Assume that the conditions of Theorem 0 hold. Then, for all p 2 we have
lim T 0 a.S.., +00
and
lim E[ 0.
D Some useful existing results
We first recall the well-known Robbins-Siogmund Theorem (Robbins & Siegmund, 1971).
Theorem D.1 (Robbins-Siegmund theorem). Let (Tn), (an), (An), (B.) be four positive sequences of random variables adapted a filtration (Fr) such that
B [F) & (1 an) + An Ba.
where
Σ On < +00 and Σ An +00 a.8.
Then, (Tx) converges almost surely lowards fimile vandom variable T and
Σ Bn +00 a.s.
The next lemma provide very useful inequality for non-asymptotic convergence rates. This result is given
Lemma A.3 in supplementary material of Bercu & Bigof (021) also Theorem in Bach & Moulines 2011
Lemma D.1. [Brreu & Bigot 2021). Let (Za) be a sequence of positive real numbers satisfying, for all 1, the recursive inequality
7at1 & (1-
a (n + 1)
2n + 1 11
(79)
where a, b, a and 3 are positive constants satisfying < 2", & 1, 1 B < 2 and B < 2a with 8 < a + 1 in the special case where a 1. Then, there erists a positive constant such that, for any n 2 1,
C Zn & nア-a
(80)
19


Reviews:
[{"review_id": "YCH2sHTikT", "reviewer": "Reviewer_evch", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a complete study of the proposed class of algorithms from almost sure convergence to asymptotic normality and non-asymptotic convergence rates. It also presents numerical experiments on a logistic regression problem to illustrate the effectiveness of the algorithms.\n\nThere are two obvious shortcomings of the paper. \n\nFirst, the paper heavily relies on other papers, for example, (Bercu et al., 2024) and (Chen et al., 2024). The idea of using different directions sampled from underlying distributions is from (Chen et al., 2024). The choices of direction distributions were proposed in Subsection 3.1 of (Chen et al., 2024). In addition, many proofs in this paper rely on results from (Bercu et al., 2024) and other related papers. See the detailed comment in the \"Requested Changes.\" This severely undermines the contribution of this paper.\n\nSecond, from all figures and tables presented in Section 5, it seems that the choice (U), i.e., uniform in the canonical basis, is the best among all choices of direction distributions. This is the well-studied and very common choice. This greatly diminishes the relevance of alternative direction distributions, since in practice they offer no advantage over SGD in terms of performance and running time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a class of stochastic gradient coordinate descent-type algorithms with random search directions beyond the standard basis vectors. It presents three types of theoretical results: 1) almost sure convergence; 2) asymptotic normality; and 3) non-asymptotic convergence rates.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In the end of the proof of Theorem 1, it is said the proof follows that of Theorem 1 in (Bercu et al., 2024).\" Can the authors provide a self-contained proof and also acknowledge which part is an analogue of (Bercu et al., 2024)?\n\nPlease also explain the last step in the proof of Theorem 2. What is used from Theorem 2.3 in (Zhang, 2016)?\n\nThe same request applies to other theorems in the paper. It would be helpful if the authors could state the technical results from other papers in the appendix. Then the paper would be more readable.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qIcrJYkmjB", "reviewer": "Reviewer_T6L8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#Major Concerns\n1) Although the proposed algorithm seems more general than the existing SCD algorithm, from both theories and experiments, I cannot find benefits of this generalization. Specifically, the proposed algorithm provides different choices of the coordinated sampling policy, but the uniform sampling (which reduces to the naive SCD) achieves the best experimental results. Moreover, from Proposition 3, it is unclear whether other choices of sampling policy can achieve a better central limit theorem than uniform sampling.\n2) Although the almost sure convergence, the central limit theorem, and the non-asymptotic convergence for the proposed algorithm have been proved, the value of these theoretical results for the (optimization and machine learning) community is unclear. It would be better if the authors could highlight their theoretical contributions.\n3) Although the authors claim that \"our Assumption 4 is of key importance and essential in general non-convex setting\", some assumptions (e.g., Assumptions 3, 5, and 6) used in this paper actually make the analysis easier than the general non-convex case. Specifically, it seems that Assumption 5 implies the loss function is strongly convex.\n4) In the experiments, it seems that the step size of all algorithms is set to be $\\gamma_n=1/n$. However, for the convex loss function utilized in the experiments, the commonly utilized step size of SGD should be $O(1/\\sqrt{n})$. It is unclear whether such a choice of step size affects the comparison of these algorithms, especially the mean squared error shown in Figure 3.\n\n#Minor Concerns\n1) I am not sure whether the frequent use of \"almost surely\" is necessary.\n2) The authors have referred the readers to learn some proofs from Bercu et al. (2024). It would be better if a sketch of such proofs could be provided in this paper.\n3) I prefer \"the assumptions used in Leluc & Portier (2022)\" to \"the assumptions used in (Leluc & Portier, 2022)\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "#Summary\n\nIn this paper, the authors consider the problem of stochastic optimization and propose the stochastic coordinate gradient descent algorithm with random search direction (SCORS).  The main motivation of the proposed algorithm is to address the limitation of the existing stochastic coordinate descent (SCD) algorithm. More specifically, SCD actually could be viewed as an efficient variant of the classical stochastic gradient descent (SGD) algorithm in some cases. However, as the authors pointed out, the coordinated sampling policy of SCD is limited. Moreover, the authors have proved the almost sure convergence, the central limit theorem, and the non-asymptotic convergence for the proposed algorithm. Experimental results have also been provided to verify these theoretical guarantees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see Strengths And Weaknesses", "broader_impact_concerns": "This is a theoretical paper, and I do not find any ethical issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GdUVB3MjM6", "reviewer": "Reviewer_NNts", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper introduces novel and interesting results—for example, a central limit theorem for stochastic coordinate gradient descent—which are likely to be of broad interest to the optimization community.\n2. The technical exposition is clear and well-organized. Even readers who are not specialists in this area will find the presentation straightforward and easy to follow.\n\nWeakness:\n1. I think there could be more discussion on related works, especially works in the past two years. For example, this paper (https://arxiv.org/abs/2307.01169) by Ramesh et. al. studied greedy block coordinate gradient descent and may be relevant.\n2. The latter sections of the paper are overly terse: they state theorems and definitions without sufficient commentary on their implications or on the necessity and reasonableness of the underlying assumptions. A deeper discussion of how these results connect to or extend prior work would strengthen the manuscript.\n3. The experimental section adds limited value. Since the theoretical results are straightforward and convincing, it is unclear what additional insight the current experiments provide—and they may not even adequately demonstrate the theorems’ claims.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper extends stochastic coordinate gradient descent by allowing each iteration to select an arbitrary direction vector—rather than a single coordinate—and perform the update along that direction. Under mild regularity conditions and a suitably chosen step-size schedule, the authors prove almost-sure convergence of the method. They further establish both asymptotic convergence rates and non-asymptotic $\\mathbb{L}^p$ convergence bounds under additional standard assumptions on the step sizes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here’re some changes I would like to see from the revision of the paper.  \n1. More related works and discussions on the theorems as I mentioned before in the \"Weakness\" section.  \n2. For the experiments confirming the central limit theorem, compute the theoretical variance and compare it with the empirical variance. Similarly, for the non-asymptotic experiments, ideally show a comparison between theoretical and empirical rates, but it may be hard to compute the theoretical rates here (and it's only an upper bound).\n\nHere're some suggestions I think could make this paper better.\n1. In the abstract and introduction, the sentence  \n   > “In this paper, we develop a new class of stochastic gradient descent algorithms with random search directions which uses the directional derivative of the gradient estimate following more general random vectors.” \n\n   is too long and confusing. Consider rewriting it for clarity and brevity.  \n2. Use an enumeration in the introduction to emphasize your contributions; this will make them stand out more clearly.  \n3. Assumption 1 combines unbiasedness and boundedness; since these are used separately in the proofs, split them into two distinct assumptions. Also, clarify “the 4th conditional moment of $V_n$ is bounded” by providing the exact mathematical expression, noting that $V_n$ is vector-valued.  \n4. Specify that every vector norm is the $\\ell_2$ norm, to avoid any ambiguity.  \n5. Instead of stating “the rest of the proof follows as in …”, either include the full proof or add intermediate lemmas to make the paper more self-contained.  \n\nHere're some questions I hope the authors could address in the revision of the paper:\n1. In the proof of Theorem 1, you mentioned $T_n$ is a Lyapunov function, but where did you use this property. Is it omitted at the end of the proof?\n2. In Assumption 5, why is the minimum eigenvalue should be greater than $\\frac{1}{2}$? This $\\frac{1}{2}$ seems to be quite arbitrary here and I couldn't find where it is used.\n3. What's $V$ in (27)? It's actually not defined. Since each $V_n$ is i.i.d. you may want to simplify your notation.\n4. Why is Assumption 3 needed for Theorem 1 but not for Theorem 4 and 5? This is a bit surprising to me.\n5. In your experiments, why are $\\\\{(w_1,y_1),\\cdots,(w_N,y_N)\\\\}$ chosen i.i.d. with Gaussian distribution? I don't think in your theorem there isn't much restrictions on $f_k$.\n6. I don't understand your relative optimality gap function. Isn't the initial point $X_1$ the same for different methods? If so, how is this different from just using $\\lVert X_t-x^*\\rVert$? Why does this metric make the comparison fair?\n7. All of your experiments shows uniform is the best, so what's the point of using other distributions?", "broader_impact_concerns": "I don't think there're any ethical concerns of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)