Composite objective mirror descent

By John C. Duchi, Shai Shalev-Shwartz, Yoram Singer, Ambuj Tewari. 2010

363 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

An Analysis of the Adaptation Speed of Causal Models (2020, background): “This is exactly the goal of the stochastic proximal gradient (Duchi et al., 2010) update”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “Extension to composite losses: Composite losses (Duchi et al., 2010; McMahan, 2011; 2017) refer to the setting where in each round, the algorithm is provided with a function ft(θ) = `(θ; dt) + rt(θ) with rt : C → R being a convex regularizer that does not depend on the data sample dt.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “, [5], [31]–[33]).”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “Several variants of SGD, that leads to sparser intermediate solutions, have been proposed (e.g. [14, 21, 27, 8, 10]).”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “We expect that this newly-found connection will also open the door for constructing more advanced reinforcement learning algorithms by borrowing further ideas from the convex optimization literature, such as Composite Objective Mirror Descent Duchi et al. (2010) and Regularized Dual Averaging (Xiao,”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “It is based on composite mirror descent (Duchi et al., 2010), which allows online optimization of many regularized problems.”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “These results can be derived from online to batch reductions yielding a O ( 1 / √ T ) convergence rate (Cesa-Bianchi et al., 2004; Duchi et al., 2010; Orabona, 2019).”
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization (2013, methodology): “[10] also presented modified mirror descent method for solving convex stochastic composite problems.”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “The framework is also particularly suitable for analyzing AdaGrad-style algorithms that adapt their regularization or norms based on the observed data, for example those of McMahan and Streeter (2010) and Duchi et al. (2010a, 2011).”
The Interplay Between Stability and Regret in Online Learning (2012, methodology): “However, [8] presents an improved analysis, that can handle non-Lipschitz continuous regularization r as well.”
Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions (2019, background): “convex setting. For generally convex objective functions, regret bounds O( √ T) were established for SGD with Titerates [15] which directly implies convergence rates O(1/ √ T) for average of iterates [16, 17]. For strongly convex objective functions, regret bounds can be improved to O(logT) [18] whi”
Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization (2011, methodology): “Previous work has shown experimentally that Dual Averaging with L 1 regularization is much more effective at introducing sparsity than FOBOS [Xiao, 2009, Duchi et al., 2010a].”
Sample size selection in optimization methods for machine learning (2012, background): “1) (see for example [32, 15, 12, 4, 33, 14, 13]) and have proven to be very effective for many online applications.”
Robust Online Multi-Task Learning with Correlative and Personalized Structures (2017, background): “We first show the regret bound of the algorithm (10) and its equivalent form in the following lemma, which is essentially the same as Theorem 2 in the paper [56]:”
Randomized Smoothing for Stochastic Optimization (2011, background): “When ψ ( X ) = X , the update (10) reduces for appropriate choice of V to min (As a side-note, it is possible to generalize this update to Schatten p -norms [10].)”
Faster Stochastic Variational Inference using Proximal-Gradient Methods with General Divergence Functions (2015, background): “…be replaced by any Bregman divergence F ( λ (cid:107) λ k ) generated from a strongly-convex function F ( λ ) (Beck & Teboulle, 2003), The convergence rate of mirror descent algorithm has been analyzed in convex (Duchi et al., 2010) and more recently in non-convex (Ghadimi et al., 2014) settings.”
Dynamical Models and tracking regret in online convex programming (2013, methodology): “Theorem 3 (Static regret for COMID (Duchi et al., 2010)).”