Risk and parameter convergence of logistic regression

By Ziwei Ji, Matus Telgarsky. 2018

142 citations recorded by the source corpus.

Gradient descent, when applied to the task of logistic regression, outputs iterates which are biased to follow a unique ray defined by the data. The direction of this ray is the maximum margin predictor of a maximal linearly separable subset of the data; the gradient descent iterates converge to this ray in direction at the rate $\mathcal{O}(\ln\ln t / \ln t)$. The ray does not pass through the origin in general, and its offset is the bounded global optimum of the risk over the remaining data; gradient descent recovers this offset at a rate $\mathcal{O}((\ln t)^2 / \sqrt{t})$.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “For linearly separable datasets, [55, 27, 14, 32, 33] show that first-order methods find solutions that generalize well without an explicit regularization for logistic regression.”
The Implicit Bias of Gradient Descent on Separable Data (2017, background): “Ji and Telgarsky (2018) provide an analysis of the degenerate case, establishing converges to the max margin predictor by showing that w (cid:13) (cid:13) (cid:16)q (cid:17) .”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “[2017], Telgarsky [2013], Ji and Telgarsky [2018]. We can also calculate exact rates of convergence to the asymptotic separator along the lines of Soudry et al. [2017], Nacson et al. [2018], Ji and Telgarsky [2018] showing how fast the inductive bias from optimization kicks in and why it might be be”
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019, unknown): “[12, 15] provide related results.”
On the Margin Theory of Feedforward Neural Networks (2018, background): “…works have shown that gradient descent ﬁnds the minimum norm solution ﬁtting the data for problems including logistic regression, linearized neural networks, and matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018b; Li et al., 2018; Gunasekar et al., 2018a; Ji & Telgarsky, 2018).”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “Other papers [26, 68, 46, 28, 38, 27, 38, 32] study implicit regularization towards a specific solution.”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “Note that a different reduction to mirror descent for this dynamics was also exhibited by Ji and Telgarsky (2019b) and used to derive tight convergence rates but with a much smaller step-size than in Proposition 5.”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, background): “Soudry et al. [2018], Ji and Telgarsky [2018] show that gradient descent implicitly maximizes the margin for linearly separable data, and Lyu and Li [2019] prove gradient descent converges to a stationary point of the max-margin formulation for deep homogeneous networks.”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “Previously, it was shown that SGD has other kinds of implicit bias as well [48, 27, 18].”
Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation (2019, background): “…adopted torwards explaining generalization is implicit regularization; numerous recent works have shown that the training method prefers minimum norm or maximum margin solutions (Soudry et al., 2018; Li et al., 2018; Ji & Telgarsky, 2018; Gunasekar et al., 2017, 2018a,b; Wei et al., 2018).”
Gradient descent aligns the layers of deep linear networks (2018, background): “Ji and Telgarsky (2018) further characterize such an implicit bias for general nonseparable data.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “…descent, where the data is sampled in mini-batches without replacement; [Nacson et al., 2018a] considers other losses with poly-exponential tails; [Ji and Telgarsky, 2018] characterizes the convergence of weight direction for general datasets without assuming separability; [Gunasekar et al.,…”
Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function” (2020, background): “Defining the precise complexity measure that is implicitly controlled by SGD is an open problem, except in some simple examples [14, 8, 6].”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “A bunch of papers (Gunasekar et al., 2017; Soudry et al., 2017; Ji and Telgarsky, 2018; Gunasekar et al., 2018a,b; Nacson et al., 2018; Li et al., 2018b) have studied implicit regularization/bias of GD, stochastic gradient descent (SGD) or mirror descent for matrix factorization, logistic…”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, background): “Whereas there is a growing literature in analyzing the behavior of SGD on non-convex objectives (Soudry et al., 2017; Ji and Telgarsky, 2018; Gunasekar et al., 2018; Wilson et al., 2017), we focus here on properties of the optimization problem above that are algorithm independent.”