Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization

By Lin Xiao. 2009

902 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “This formulation results in a more complicated algorithm, sub-optimal regret analysis, and failure to maintain structural properties (like sparsity) introduced by composite losses (Duchi et al., 2010; Xiao, 2010; McMahan, 2011; 2017).”
Certified Defenses for Data Poisoning Attacks (2017, methodology): “The particular algorithm depicted in Algorithm 1 is a variant of regularized dual averaging (Xiao, 2010), which is an alternative to gradient descent that often converges faster for norm-constrained optimization problems.”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, methodology): “Stochastic Dual Averaging Similarly to sub-gradient descent algorithms, one can adapt dual averaging algorithm to a stochastic setting; this was studied extensively by Xiao (2009).”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “These methods are characterized by incremental updates based on subgradients ∂(cid:96) ( w , z i ) of individual instances, and enjoy the advantages of being highly scalable and simple to implement.”
Optimal Distributed Online Prediction Using Mini-Batches (2010, methodology): “The analysis in Appendix A (and Appendix B) actually applies to a much larger class of update rules, which includes the family of mirror descent updates (Nemirovski et al., 2009; Lan, 2009) and the family of (non-Euclidean) dual averaging updates (Nesterov, 2009; Xiao, 2010).”
Adaptive Bound Optimization for Online Convex Optimization (2010, neutral): “Accordingly, we call this algorithm follow the proximally-regularized leader (FTPRL).”
Distributed delayed stochastic optimization (2011, methodology): “For the remainder of the paper, we will use the following three essentially standard assumptions [8, 9, 20] about the stochastic optimization problem (1).”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “In this section, we provide a formal statement of the distributed minimization problem, and a description of the distributed dual averaging algorithm.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “• RDA: the regularized dual averaging method in [33].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “This update is related to SDCA, as well as to stochastic methods for composite convex optimization such as the regularized dual averaging algorithm of Xiao [49].”
Optimization with Sparsity-Inducing Penalties (2011, background): “1) may also be tackled with stochastic optimization approaches, which has been the focus of much recent research [21, 23, 108, 129].”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, methodology): “[25, 24, 19]) d 2 Stochastic Coordinate Descent [20, 14] dn”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “In this MDP, we observe that the performance of both Dual Averaging methods (DA and DA-RV) is very similar, and in general slightly better than the approximate Mirror Descent variants.”
Sparse Overcomplete Word Vector Representations (2015, methodology): “We use the AdaGrad variant of one such learning algorithm, the regularized dual averaging algorithm (Xiao, 2009), which keeps track of the online average gradient at time t : ¯ g t = 1 t (cid:48) =1 g t (cid:48) Here, the subgradients do not include terms for the regularizer; they are derivatives…”
Ad click prediction: a view from the trenches (2013, methodology): “More sophisticated approaches such as FOBOS and truncated gradient do succeed in introducing sparsity [11, 20].”
Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces (2014, background): “Mirror descent has become the cornerstone of many online l1 regularization approaches such as in [37], [38] and [39].”