prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Sparse SGD + momentum  = cuda memory issue.
  When using classic SGD optimizer with momentum with sparse embeddings the memory keeps garbage collecting / allocating leading to slow down and out of memory error eventually. [Here is a minimal exemple to reproduce the issue](https://gist.github.com/cedias/946a380807b7e1bf92d738268b71415a)
  
  ![slowing](https://user-images.githubusercontent.com/1705336/31611730-87b2ccbc-b27d-11e7-8826-12023e848a77.png)
  
  ![memoryerror](https://user-images.githubusercontent.com/1705336/31612140-0fea1080-b27f-11e7-99b7-8dae06d931b1.gif)
  
  The issue dissapears when momentum is not used
  ![nomomentum](https://user-images.githubusercontent.com/1705336/31611728-86c7a9f8-b27d-11e7-85b3-979ce180ec3d.png)
  
  or when embeddings are not sparse
  ![notsparse](https://user-images.githubusercontent.com/1705336/31611729-872bb416-b27d-11e7-8ca1-65629cfae6bc.png)
  
  
  I'm using the last pytorch version on conda: `'0.2.0_4'`
  
  
  </issue>
  <code>
  [start of torch/optim/sgd.py]
  1 from .optimizer import Optimizer, required
  2 
  3 
  4 class SGD(Optimizer):
  5     r"""Implements stochastic gradient descent (optionally with momentum).
  6 
  7     Nesterov momentum is based on the formula from
  8     `On the importance of initialization and momentum in deep learning`__.
  9 
  10     Args:
  11         params (iterable): iterable of parameters to optimize or dicts defining
  12             parameter groups
  13         lr (float): learning rate
  14         momentum (float, optional): momentum factor (default: 0)
  15         weight_decay (float, optional): weight decay (L2 penalty) (default: 0)
  16         dampening (float, optional): dampening for momentum (default: 0)
  17         nesterov (bool, optional): enables Nesterov momentum (default: False)
  18 
  19     Example:
  20         >>> optimizer = torch.optim.SGD(model.parameters(), lr=0.1, momentum=0.9)
  21         >>> optimizer.zero_grad()
  22         >>> loss_fn(model(input), target).backward()
  23         >>> optimizer.step()
  24 
  25     __ http://www.cs.toronto.edu/%7Ehinton/absps/momentum.pdf
  26 
  27     .. note::
  28         The implementation of SGD with Momentum/Nesterov subtly differs from
  29         Sutskever et. al. and implementations in some other frameworks.
  30 
  31         Considering the specific case of Momentum, the update can be written as
  32 
  33         .. math::
  34                   v = \rho * v + g \\
  35                   p = p - lr * v
  36 
  37         where p, g, v and :math:`\rho` denote the parameters, gradient,
  38         velocity, and momentum respectively.
  39 
  40         This is in contrast to Sutskever et. al. and
  41         other frameworks which employ an update of the form
  42 
  43         .. math::
  44              v = \rho * v + lr * g \\
  45              p = p - v
  46 
  47         The Nesterov version is analogously modified.
  48     """
  49 
  50     def __init__(self, params, lr=required, momentum=0, dampening=0,
  51                  weight_decay=0, nesterov=False):
  52         defaults = dict(lr=lr, momentum=momentum, dampening=dampening,
  53                         weight_decay=weight_decay, nesterov=nesterov)
  54         if nesterov and (momentum <= 0 or dampening != 0):
  55             raise ValueError("Nesterov momentum requires a momentum and zero dampening")
  56         super(SGD, self).__init__(params, defaults)
  57 
  58     def __setstate__(self, state):
  59         super(SGD, self).__setstate__(state)
  60         for group in self.param_groups:
  61             group.setdefault('nesterov', False)
  62 
  63     def step(self, closure=None):
  64         """Performs a single optimization step.
  65 
  66         Arguments:
  67             closure (callable, optional): A closure that reevaluates the model
  68                 and returns the loss.
  69         """
  70         loss = None
  71         if closure is not None:
  72             loss = closure()
  73 
  74         for group in self.param_groups:
  75             weight_decay = group['weight_decay']
  76             momentum = group['momentum']
  77             dampening = group['dampening']
  78             nesterov = group['nesterov']
  79 
  80             for p in group['params']:
  81                 if p.grad is None:
  82                     continue
  83                 d_p = p.grad.data
  84                 if weight_decay != 0:
  85                     d_p.add_(weight_decay, p.data)
  86                 if momentum != 0:
  87                     param_state = self.state[p]
  88                     if 'momentum_buffer' not in param_state:
  89                         buf = param_state['momentum_buffer'] = d_p.clone()
  90                     else:
  91                         buf = param_state['momentum_buffer']
  92                         buf.mul_(momentum).add_(1 - dampening, d_p)
  93                     if nesterov:
  94                         d_p = d_p.add(momentum, buf)
  95                     else:
  96                         d_p = buf
  97 
  98                 p.data.add_(-group['lr'], d_p)
  99 
  100         return loss
  101
  [end of torch/optim/sgd.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/torch/optim/sgd.py b/torch/optim/sgd.py
  --- a/torch/optim/sgd.py
  +++ b/torch/optim/sgd.py
  @@ -86,7 +86,8 @@
                   if momentum != 0:
                       param_state = self.state[p]
                       if 'momentum_buffer' not in param_state:
  -                        buf = param_state['momentum_buffer'] = d_p.clone()
  +                        buf = param_state['momentum_buffer'] = p.data.new().resize_as_(p.data).zero_()
  +                        buf.mul_(momentum).add_(d_p)
                       else:
                           buf = param_state['momentum_buffer']
                           buf.mul_(momentum).add_(1 - dampening, d_p)
  
verification_info: {"golden_diff": "diff --git a/torch/optim/sgd.py b/torch/optim/sgd.py\n--- a/torch/optim/sgd.py\n+++ b/torch/optim/sgd.py\n@@ -86,7 +86,8 @@\n                 if momentum != 0:\n                     param_state = self.state[p]\n                     if 'momentum_buffer' not in param_state:\n-                        buf = param_state['momentum_buffer'] = d_p.clone()\n+                        buf = param_state['momentum_buffer'] = p.data.new().resize_as_(p.data).zero_()\n+                        buf.mul_(momentum).add_(d_p)\n                     else:\n                         buf = param_state['momentum_buffer']\n                         buf.mul_(momentum).add_(1 - dampening, d_p)\n", "issue": "Sparse SGD + momentum  = cuda memory issue.\nWhen using classic SGD optimizer with momentum with sparse embeddings the memory keeps garbage collecting / allocating leading to slow down and out of memory error eventually. [Here is a minimal exemple to reproduce the issue](https://gist.github.com/cedias/946a380807b7e1bf92d738268b71415a)\r\n\r\n![slowing](https://user-images.githubusercontent.com/1705336/31611730-87b2ccbc-b27d-11e7-8826-12023e848a77.png)\r\n\r\n![memoryerror](https://user-images.githubusercontent.com/1705336/31612140-0fea1080-b27f-11e7-99b7-8dae06d931b1.gif)\r\n\r\nThe issue dissapears when momentum is not used\r\n![nomomentum](https://user-images.githubusercontent.com/1705336/31611728-86c7a9f8-b27d-11e7-85b3-979ce180ec3d.png)\r\n\r\nor when embeddings are not sparse\r\n![notsparse](https://user-images.githubusercontent.com/1705336/31611729-872bb416-b27d-11e7-8ca1-65629cfae6bc.png)\r\n\r\n\r\nI'm using the last pytorch version on conda: `'0.2.0_4'`\r\n\n", "before_files": [{"content": "from .optimizer import Optimizer, required\n\n\nclass SGD(Optimizer):\n    r\"\"\"Implements stochastic gradient descent (optionally with momentum).\n\n    Nesterov momentum is based on the formula from\n    `On the importance of initialization and momentum in deep learning`__.\n\n    Args:\n        params (iterable): iterable of parameters to optimize or dicts defining\n            parameter groups\n        lr (float): learning rate\n        momentum (float, optional): momentum factor (default: 0)\n        weight_decay (float, optional): weight decay (L2 penalty) (default: 0)\n        dampening (float, optional): dampening for momentum (default: 0)\n        nesterov (bool, optional): enables Nesterov momentum (default: False)\n\n    Example:\n        >>> optimizer = torch.optim.SGD(model.parameters(), lr=0.1, momentum=0.9)\n        >>> optimizer.zero_grad()\n        >>> loss_fn(model(input), target).backward()\n        >>> optimizer.step()\n\n    __ http://www.cs.toronto.edu/%7Ehinton/absps/momentum.pdf\n\n    .. note::\n        The implementation of SGD with Momentum/Nesterov subtly differs from\n        Sutskever et. al. and implementations in some other frameworks.\n\n        Considering the specific case of Momentum, the update can be written as\n\n        .. math::\n                  v = \\rho * v + g \\\\\n                  p = p - lr * v\n\n        where p, g, v and :math:`\\rho` denote the parameters, gradient,\n        velocity, and momentum respectively.\n\n        This is in contrast to Sutskever et. al. and\n        other frameworks which employ an update of the form\n\n        .. math::\n             v = \\rho * v + lr * g \\\\\n             p = p - v\n\n        The Nesterov version is analogously modified.\n    \"\"\"\n\n    def __init__(self, params, lr=required, momentum=0, dampening=0,\n                 weight_decay=0, nesterov=False):\n        defaults = dict(lr=lr, momentum=momentum, dampening=dampening,\n                        weight_decay=weight_decay, nesterov=nesterov)\n        if nesterov and (momentum <= 0 or dampening != 0):\n            raise ValueError(\"Nesterov momentum requires a momentum and zero dampening\")\n        super(SGD, self).__init__(params, defaults)\n\n    def __setstate__(self, state):\n        super(SGD, self).__setstate__(state)\n        for group in self.param_groups:\n            group.setdefault('nesterov', False)\n\n    def step(self, closure=None):\n        \"\"\"Performs a single optimization step.\n\n        Arguments:\n            closure (callable, optional): A closure that reevaluates the model\n                and returns the loss.\n        \"\"\"\n        loss = None\n        if closure is not None:\n            loss = closure()\n\n        for group in self.param_groups:\n            weight_decay = group['weight_decay']\n            momentum = group['momentum']\n            dampening = group['dampening']\n            nesterov = group['nesterov']\n\n            for p in group['params']:\n                if p.grad is None:\n                    continue\n                d_p = p.grad.data\n                if weight_decay != 0:\n                    d_p.add_(weight_decay, p.data)\n                if momentum != 0:\n                    param_state = self.state[p]\n                    if 'momentum_buffer' not in param_state:\n                        buf = param_state['momentum_buffer'] = d_p.clone()\n                    else:\n                        buf = param_state['momentum_buffer']\n                        buf.mul_(momentum).add_(1 - dampening, d_p)\n                    if nesterov:\n                        d_p = d_p.add(momentum, buf)\n                    else:\n                        d_p = buf\n\n                p.data.add_(-group['lr'], d_p)\n\n        return loss\n", "path": "torch/optim/sgd.py"}]}