Answers.Body: <p>In interaction like this there's no theoretical reason you have to choose a fixed update scheme.</p>
  <p>In the more common synchronous update scheme, all components <span class="math-container">$x_i$</span> are updated independently using the previous values of <span class="math-container">$x_j$</span> 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.</p>
  <p>In asynchronous update scheme, you update each <span class="math-container">$x_i$</span> 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.</p>
  <p>The paper of Lian et al (2018) &quot;<em>Asynchronous Decentralized Parallel Stochastic Gradient Descent</em>&quot; studies their comparison and the case for the second update scheme.</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-07T23:24:47.863Z
Answers.Text: Thank you! So there is no right choice here. I always have used the synchronous update scheme and when the asynchronous update scheme came into my head, I was worried I performed gradient descent wrong. I'm aware I sound inexperienced and dumb but I'm glad this has been thought about before.
Answers.UserDisplayName: Darkmoon Chief
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-05T21:00:45.840Z
Answers.LastActivityDate: 2024-11-05T21:00:45.840Z
Answers.UserDisplayName: cinch
Body: <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-06T19:59:28.977Z
Comments.Text: Hi @Darkmoon Chief and welcome to AI Stack Exchange! This site allows use of LaTeX in posts. When you have time, please edit your post to display the equations and other symbols in LaTeX. Thank you for posting, and we hope to see more of your posts here soon!
Comments.UserDisplayName: DeepQZero
Tags: <objective-functions><optimization><gradient-descent><loss>
Title: Do we plug in the old values or the new values during the gradient descent update?
UserDisplayName: Darkmoon Chief
ThreadText: # Do we plug in the old values or the new values during the gradient descent update?
  
  (Asked by: username_0 on 2024-11-05)
  
  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.
  
  **Tags:** objective-functions, optimization, gradient-descent, loss
  
  > **Comments:**
  > **username_1**: Hi @username_0 and welcome to AI Stack Exchange! This site allows use of LaTeX in posts. When you have time, please edit your post to display the equations and other symbols in LaTeX. Thank you for posting, and we hope to see more of your posts here soon!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-11-05. Score: 2 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: Thank you! So there is no right choice here. I always have used the synchronous update scheme and when the asynchronous update scheme came into my head, I was worried I performed gradient descent wrong. I'm aware I sound inexperienced and dumb but I'm glad this has been thought about before.  
  
  ---
  
  