Fast Rates for Regularized Objectives

By Karthik Sridharan, Shai Shalev-Shwartz, Nati Srebro. 2008

144 citations recorded by the source corpus.

Subfields: Optimization & Training, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, background): “E.g., when strong convexity arises from regularization, as in many stochastic optimization problems, λ decreases with the overall sample size N = nm , and is typically at most 1 / √ nm (Sridharan et al. 2008; Shalev-Shwartz et al. 2009; and see also Section 4.3 below).”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, methodology): “Our proof technique closely follows that of Sridharan et al. [2008] and crucially uses the fact that Sridharan et al. [2008] only requires strong convexity of the expected loss function.”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “, see [48]) and will allow us to get rid of the extra logarithmic factor that would have otherwise shown up in the excess risk if we use the standard analysis of the exponential mechanism in [37].”
Differentially Private Empirical Risk Minimization (2009, neutral): “(96) From this we have P ( z ≥ zmin + 2 ǫp log m δ ) ≤ δ, (97) and the result follows.”
Stochastic dual coordinate ascent methods for regularized loss (2012, neutral): “t the training examples deﬁning the regularized loss minimization problem are only a ﬁnite sample from the underlying distribution. The estimation error of the primal objective behaves like 1 n (see [16, 18]). Therefore, an interesting regime is when 1 n = ( ). In that case, the bound for both Lipsc”
On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization (2008, background): “For the L2 case, Bartlett and Mendelson [2002] provides essentially the same bound. For the L1 margin case, our bound improves upon all previous bounds by removing all log n factors from Schapire et al. [1998], Langford et al. [2001], Zhang [2002]. There are also generalizations which can be stated ”
Learnability, Stability and Uniform Convergence (2010, background): “For instance, such bounds has been obtained whenever the objective function is a generalized linear function of h (Sridharan et al., 2008).”
Privacy-preserving logistic regression (2008, unknown): “Using this and [16], we can bound the second quantity in equation 1 as + O ( 1 λn ) .”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “, see [40]) and will allow us to get rid of the extra logarithmic factor that would have otherwise shown up in the excess risk if we use the standard analysis of the exponential mechanism in [31].”
Generalize Across Tasks: Efficient Algorithms for Linear Representation Learning (2019, background): “will lead to a classifier that competes against the optimal C-bounded norm classifier in terms of generalization error (Sridharan et al., 2009).”
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets (2012, background): “For example, [30] considers parameters of the form λ = C √ n in the parametric setting, while [31] considers λ = C nβ with β < 1 in a non-parametric setting.”
A Minimax Approach to Supervised Learning (2016, methodology): “ given in (19), rF (z) = E P[(Y)] for some distribution P. Therefore, krF (z)k 1Land F (z) (Y)Tz is 2L-Lipschitz in each entry z i. Then, the theorem is an immediate consequence of Theorem 1 in [20]. In the remaining of this section, we apply the described framework to the loss functions discussed a”
Improper Deep Kernels (2016, unknown): “The theorem follows Corollary 4 in [21].”