Smooth minimization of non-smooth functions

By Yurii E. Nesterov. 2005

2,956 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Computational Mechanics

In Numerical Analysis

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Privacy Amplification by Iteration (2018, methodology): “While smoothing a non-smooth objective is a standard technique in optimization (e.g., see [Nes05, DBW12]) we are not aware of bounds that are stated in the form we need.”
Deep learning with Elastic Averaging SGD (2014, methodology): “It is based on the Nesterov’s momentum scheme Nesterov (2005); Lan (2012); Sutskever et al. (2013), where the update of the local worker of the form captured in Equation 4 is replaced by the following update , where δ is the momentum term.”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, background): “Recently, [10] has shown that a mini-batching distributed framework is capable of attaining asymptotically optimal speed-up in general (see also [1]).”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “…7 implies that If ∇ F ( w ⋆ ) = 0 (this is certainly the case if W is the whole space), then we have Then the expected regret bound can be simpliﬁed as To prove Theorem 7 we require the following fundamental lemma, which can be found, for example, in Nesterov (2005), Tseng (2008) and Xiao (2010).”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “Nesterov’s Second Trick: AGD After Regularization.”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “The proposed technique is a signiﬁcant improvement over simple smoothing techniques used in, e.g., Nesterov (2005); Shalev-Shwartz and Zhang (2014); and Zhang and Lin (2015) that enforce strong convexity by adding a small L 2 term to the objective.”
Best Subset Selection via a Modern Optimization Lens (2015, positive): “Observing that g1(β) = sup‖w‖∞≤1〈y − Xβ,w〉 we make use of the smoothing technique of Nesterov (2005) to obtain g1(β; τ) = sup‖w‖∞≤1(〈y − Xβ,w〉− τ2‖w‖22). g1(β; τ) is a smooth approximation of g1(β), with = λmax(X′X)/τ and our algorithmic framework applies.”
Boosting the Actor with Dual Critic (2017, positive): “We then rewrite the optimization min V max α ∈P ( S ) ,π ∈P ( A ) L r ( V, α, π ) as min V max α ∈P ( S ) ,π ∈P ( A ) L k ( V, α, π ) due to the well-known one-to-one correspondence between regularization η V and (cid:15) Nesterov (2005).”
Smoothed Dual Embedding Control (2017, methodology): “ithm is related to the reinforcement learning with entropy-regularized MDP model. Dierent from the motivation in our method where the entropy regularization is introduced in dual form for smoothing (Nesterov, 2005), the entropy-regularized MDP has been proposed for balancing exploration and exploita”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “[15, 24]), can match these lower bounds up to log factors2.”
Solving variational inequalities with Stochastic Mirror-Prox algorithm (2008, methodology): “Starting with the breakthrough paper of Nesterov [11], this phenomenon, in its general form, is utilized in the fastest known so far first order algorithms for “well-structured” nonsmooth convex programs.”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, methodology): “per, in our theoretical results, we consider non-smooth loss functions for which conditional gradient algorithms do not converge in general. One possibility is to smooth the loss function, as done by Nesterov (2005): an approximation error of ε may be obtained with a smoothness constant proportional”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, methodology): “Off-the-shelf techniques such as Nesterov’s smoothing (Nesterov, 2005) could be useful, however more thorough investigation is left for future work.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “The following theorem is a corollary of Thm. 2, and we provide a proof in Appendix A.4.”
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method (2012, methodology): “– We note that the averaging of linear approximations of f (rather than the iterates) by t + 1 is also used in the optimization strategy of Nesterov [8], which achieves an optimal O(1/t2) convergence rate for optimizing (deterministic) objectives with Lipschitz-continuous gradients (see step 3 for t”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, neutral): “Let f be convex and LLipschitz continuous.”
Fast Distributed Gradient Methods (2011, methodology): “ngly convex. Examples of f i()’s include quadratic or logistic losses regularized by a quadratic or smooth approximation to the l 1 norm–like y7! P d i=1 p y2 + 2 or y7! P d i=1 log e yi=+ 2 , [25]. We design two fast distributed gradient algorithms, a diminishing step size k = c=k;c>0, and a c”
Optimization with Sparsity-Inducing Penalties (2011, neutral): “, [25, 88, 91]).”