Efficient Online and Batch Learning Using Forward Backward Splitting

By John C. Duchi, Yoram Singer. 2009

663 citations recorded by the source corpus.

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

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

Citations in the corpus

An Analysis of the Adaptation Speed of Causal Models (2020, methodology): “When we set h(x) = 1/2‖x‖2, we recover something called the proximal stochastic gradient method (Duchi and Singer, 2009), also known as Perturbed proximal gradient algorithm (Atchadé et al.”
Optimal Distributed Online Prediction Using Mini-Batches (2010, methodology): “To extend the dual averaging method, we can use the following update rule in Xiao (2010): Similar extensions to the mirror descent method can be found in, for example, Duchi and Singer (2009).”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “1(a) is recorded when ψ(x) is Lipschitz or smooth [13], but we would not like to impose such assumptions.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “On the other hand, with a diminishing step size ηk = 1/(μk), the Prox-SG method converges at a sublinear rate [8, 17]:”
EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples (2017, background): “Since the L 1 penalty is a non-differentiable yet smooth function, the failure of the COV approach in solving (7) can be explained by its inefﬁciency in subgradient-based optimization problems (Duchi and Singer 2009).”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “Speciﬁcally, this paper focues on importance sampling techniques for Proximal Stochastic Gradient Descent (prox-SGD) [4] and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA) [13].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “In the last few years, stochastic optimization techniques have become very popular in machine learning for their empirical ability to deal with a large number T of training points [9, 22, 51, 55].”
On the linear convergence of the stochastic gradient method with constant step-size (2017, methodology): “, [3, 5, 2], and the references therein) is an elementary method for solving Problem 1.”
Auto-Sizing Neural Networks: With Applications to n-gram Language Models (2015, methodology): “The methods we use are discussed in detail elsewhere (Duchi et al., 2008; Duchi and Singer, 2009); in this section, we include a short description of these methods for completeness.”
Phrasal: A Toolkit for New Directions in Statistical Machine Translation (2014, background): “The regularization options are L 2 , eﬃcient L 1 for feature selection (Duchi and Singer, 2009), or L 1 + L 2 (elastic net).”
Moreau-Yosida Regularization for Grouped Tree Structure Learning (2010, methodology): “We let wi j = 1,∀i, j, λ = √ 2, and v = [1, 2, 1, 1, 4, 4, 1, 1]T.”
Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity (2017, methodology): “Splitting methods and quasi-Newton methods capable of solving this problem are given in [5] and [18], respectively, which both avoid needing to assume subgradient bounds.”
How To Make the Gradients Small Stochastically (2018, background): “1a is known when ψ(x) is Lipschitz or smooth [8], but we would not like to impose such assumptions.”
Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization (2011, methodology): “For example, when the ek are independent, zero-mean, and finite-variance random variables, then proximal-gradient methods achieve the (optimal) error level of O(1/ √ k) [18, 19].”
A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces (2014, methodology): “However, it should be noted that convergence of the objective values is studied in [20] also for the non strongly convex case.”
Efficient Learning using Forward-Backward Splitting (2009, methodology): “We perform more substantial experiments in the full version of the paper [13].”