Stochastic Convex Optimization

By Shai Shalev-Shwartz, Ohad Shamir, Nati Srebro, Karthik Sridharan. 2009

349 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 Mathematical Optimization

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “3, using the standard online-to-batch conversion (Cesa-Bianchi et al., 2002; Shalev-Shwartz et al., 2009), we obtain a population risk guarantee for DP-FTRL.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “This problem has received attention from various communities over the last fifty years in optimization, stochastic approximation, and machine learning (Polyak and Juditsky, 1992; Ruppert, 1988; Fabian, 1968; Nesterov and Vial, 2008; Nemirovski et al., 2009; Shalev-Shwartz et al., 2009; Zhang, 2004).”
Semi-Cyclic Stochastic Gradient Descent (2019, neutral): “(2) If the samples zt are chosen independently from the data distribution D, then with an appropriately chosen stepsizes ηt, SGD attains the mini-max optimal error guarantee (e.g. Shalev-Shwartz et al., 2009): E[F(w)] ≤ F(w?)”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “E.g., in regularized loss minimization and SVM-type problems (Sridharan et al., 2008), as well as more generally for stochastic convex optimization (Shalev-Shwartz et al., 2009), the regularization parameter, and hence the strong convexity parameter, decreases as 1 In practice, λ is often chosen…”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, methodology): “Recall that in general for non-strongly convex loss functions, the best excess risk one can hope for is O(1/ √ n) Shalev-Shwartz et al. [2009].”
Smoothness, Low Noise and Fast Rates (2010, methodology): “The following theorem provides a bound on excess risk similar to Corollary 3: q then for all w ⋆ ∈ W with F ( w ⋆ ) ≤ B 2 and L ( w ⋆ ) ≤ L ∗ , we have that in expectation over sample of size n : To prove Theorem 4 we use stability arguments similar to the ones used by Shalev-Shwartz et al [25], whi”
The Ideal Continual Learner: An Agent That Never Forgets (2023, positive): “These assumptions suffice to ensure uniform convergence (Shalev-Shwartz et al., 2009, Thm 5): For fixed t and δ ∈ (0, 1), with probability at least 1− δ we have (∀w ∈ W) |Lt(w;Dt)− Ed∼Dt [`t(w;d)]| ≤ ζ(mt, δ), (14) where ζ(mt, δ) := O ( MB √ n log(mt) log(n/δ)√ mt ) approaches zero as the sample…”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “The application of this framework to learning is straightforward (see for instance (Shalev-Shwartz et al., 2009)): given a hypothesis class W and a set of T i.i.d. examples, we wish to ﬁnd a predictor w whose expected loss F ( w ) is close to optimal over W .”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, background): “It is well-known that this framework can be applied to learning problems (see for instance (Shalev-Shwartz et al., 2009)): given a hypothesis class W and a set of T i.”
Parallel SGD: When does averaging help? (2016, neutral): “Although this kind of algorithm is used in practice, and some recent results Zhang and Ré [2014] suggest that more averaging is better, there are no known recipes for averaging that provide theoretical guarantees.”
Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition (2015, methodology): “So far, we have been discussed all about unconstrained probl em. In this section we extend our result to equality constraint problems under some mild conditions. Consider the equality constrained optimization problem: min w f(w) (77) s.t. ci(w) = 0, i = 1, · · · ,m Define the feasible set as the set”
Does learning require memorization? a short tale about a long tail (2019, background): “Algorithmic stability [13, 25, 28, 46] is essentially the only general approach that is known to imply generalization bounds beyond those achievable via uniform convergence [23, 46].”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “Consider the stochastic convex optimization (generalized learning) problem (Nemirovskii and Yudin, 1983; Vapnik, 1995; Shalev-Shwartz et al., 2009): min w∈Ω φ(w) := Eξ∼D [ℓ(w, ξ)] (1) where our goal is to learn a predictor w from the convex domain Ω given the convex instantaneous (loss) function…”
Private Stochastic Convex Optimization with Optimal Rates (2019, methodology): “The second approach relies on generalization properties of stability to bound the gap between the empirical and population losses [BE02, SSSSS09].”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, neutral): “• hinge loss: x ∈ Rd, y ∈ {+1,−1}, and φ(w, (x, y)) = max { 0, 1− y(wTx) } .”
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds (2020, background): “[4] propose DP gradient descent algorithms and apply uniform convergence [27] of empirical loss to population loss, i.”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “The value of λ is typically in the order of Θ(1/ √ N) = Θ(1/ √ mn) as justified by Shamir and Srebro (2014), Shamir et al.”