Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits

• URL: http://arxiv.org/abs/2110.04844v1
• Date: Sun, 10 Oct 2021 16:17:43 GMT
• Title: Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits
• Authors: Yan Li, Dhruv Choudhary, Xiaohan Wei, Baichuan Yuan, Bhargav Bhushanam, Tuo Zhao, Guanghui Lan
• Abstract summary: We propose a large Descent (Counter-based)-aware Descent, which applies a frequency-dependent learning rate for each token, and exhibits provable speed-up compared to SGD when the token distribution is imbalanced.
• Score: 35.543124939636044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Embedding learning has found widespread applications in recommendation systems and natural language modeling, among other domains. To learn quality embeddings efficiently, adaptive learning rate algorithms have demonstrated superior empirical performance over SGD, largely accredited to their token-dependent learning rate. However, the underlying mechanism for the efficiency of token-dependent learning rate remains underexplored. We show that incorporating frequency information of tokens in the embedding learning problems leads to provably efficient algorithms, and demonstrate that common adaptive algorithms implicitly exploit the frequency information to a large extent. Specifically, we propose (Counter-based) Frequency-aware Stochastic Gradient Descent, which applies a frequency-dependent learning rate for each token, and exhibits provable speed-up compared to SGD when the token distribution is imbalanced. Empirically, we show the proposed algorithms are able to improve or match adaptive algorithms on benchmark recommendation tasks and a large-scale industrial recommendation system, closing the performance gap between SGD and adaptive algorithms. Our results are the first to show token-dependent learning rate provably improves convergence for non-convex embedding learning problems.

Related papers

• Bandit-Driven Batch Selection for Robust Learning under Label Noise [20.202806541218944]
  We introduce a novel approach for batch selection in Gradient Descent (SGD) training, leveraging bandit algorithms. Our methodology focuses on optimizing the learning process in the presence of label noise, a prevalent issue in real-world datasets.
  arXiv  Detail & Related papers  (2023-10-31T19:19:01Z)
• FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data [54.81695390763957]
  Federated learning is an emerging distributed machine learning method. We propose a heterogeneous local variant of AMSGrad, named FedLALR, in which each client adjusts its learning rate. We show that our client-specified auto-tuned learning rate scheduling can converge and achieve linear speedup with respect to the number of clients.
  arXiv  Detail & Related papers  (2023-09-18T12:35:05Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Learning Rate Perturbation: A Generic Plugin of Learning Rate Schedule towards Flatter Local Minima [40.70374106466073]
  We propose a generic learning rate schedule plugin called LEArning Rate Perturbation (LEAP) LEAP can be applied to various learning rate schedules to improve the model training by introducing a certain perturbation to the learning rate. We conduct extensive experiments which show that training with LEAP can improve the performance of various deep learning models on diverse datasets.
  arXiv  Detail & Related papers  (2022-08-25T05:05:18Z)
• CCLF: A Contrastive-Curiosity-Driven Learning Framework for Sample-Efficient Reinforcement Learning [56.20123080771364]
  We develop a model-agnostic Contrastive-Curiosity-Driven Learning Framework (CCLF) for reinforcement learning. CCLF fully exploit sample importance and improve learning efficiency in a self-supervised manner. We evaluate this approach on the DeepMind Control Suite, Atari, and MiniGrid benchmarks.
  arXiv  Detail & Related papers  (2022-05-02T14:42:05Z)
• Online Attentive Kernel-Based Temporal Difference Learning [13.94346725929798]
  Online Reinforcement Learning (RL) has been receiving increasing attention due to its fast learning capability and improving data efficiency. Online RL often suffers from complex Value Function Approximation (VFA) and catastrophic interference. We propose an Online Attentive Kernel-Based Temporal Difference (OAKTD) algorithm using two-timescale optimization.
  arXiv  Detail & Related papers  (2022-01-22T14:47:10Z)
• Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
  dataset bias is one of the prevailing causes of unfairness in machine learning. We study whether models trained with uncertainty-based ALs are fairer in their decisions with respect to a protected class. We also explore the interaction of algorithmic fairness methods such as gradient reversal (GRAD) and BALD.
  arXiv  Detail & Related papers  (2021-04-14T14:20:22Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  In imitation learning from observation IfO, a learning agent seeks to imitate a demonstrating agent using only observations of the demonstrated behavior without access to the control signals generated by the demonstrator. Recent methods based on adversarial imitation learning have led to state-of-the-art performance on IfO problems, but they typically suffer from high sample complexity due to a reliance on data-inefficient, model-free reinforcement learning algorithms. This issue makes them impractical to deploy in real-world settings, where gathering samples can incur high costs in terms of time, energy, and risk. We propose a more data-efficient IfO algorithm
  arXiv  Detail & Related papers  (2021-03-31T23:46:32Z)
• AdaS: Adaptive Scheduling of Stochastic Gradients [50.80697760166045]
  We introduce the notions of textit"knowledge gain" and textit"mapping condition" and propose a new algorithm called Adaptive Scheduling (AdaS) Experimentation reveals that, using the derived metrics, AdaS exhibits: (a) faster convergence and superior generalization over existing adaptive learning methods; and (b) lack of dependence on a validation set to determine when to stop training.
  arXiv  Detail & Related papers  (2020-06-11T16:36:31Z)
• Fase-AL -- Adaptation of Fast Adaptive Stacking of Ensembles for Supporting Active Learning [0.0]
  This work presents the FASE-AL algorithm which induces classification models with non-labeled instances using Active Learning. The algorithm achieves promising results in terms of the percentage of correctly classified instances.
  arXiv  Detail & Related papers  (2020-01-30T17:25:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.