Do we plug in the old values or the new values during the gradient descent update?

Question

I have a scenario when I am trying to optimize a vector of D dimensions. Every component of the vector is dependent on other components according to a function such as: summation over (i,j): (1-e(x_i)(x_j))/2 where e is constant and x are embeddings of i and j Lets say the update rule is be: x_i=x_i-lr0.5(e)(x_j) where lr is the learning rate. Do we use old value of x_j or the updated value? What I mean is x_j might get a new embedding during the update and x_i in the same iteration might get updated too.

Answer 1

In interaction like this there's no theoretical reason you have to choose a fixed update scheme.

In the more common synchronous update scheme, all components $x_i$ are updated independently using the previous values of $x_j$ where all updates are effectively based on the frozen values from the previous iteration. This is often simpler to implement, particularly when you want to control the dependency dynamics explicitly, as it avoids circular dependencies that could cause instability.

In asynchronous update scheme, you update each $x_i$ with the latest updated values of its all other relevant components. While intuitively this can sometimes accelerate convergence especially for high dimensional problems in a distributed computing cluster, it can also lead to instability especially if the dependency structure is dense across many components and there's communication bottleneck at parameter servers in a distributed cluster.

The paper of Lian et al (2018) "Asynchronous Decentralized Parallel Stochastic Gradient Descent" studies their comparison and the case for the second update scheme.

Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when workers are many, and 2) significantly worse convergence when the traffic to parameter server is congested... we propose an asynchronous decentralized stochastic gradient decent algorithm (AD-PSGD) satisfying all above expectations... Empirically, AD-PSGD outperforms the best of decentralized parallel SGD (D-PSGD), asynchronous parallel SGD (A-PSGD), and standard data parallel SGD (AllReduce-SGD), often by orders of magnitude in a heterogeneous environment.