Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning

2019-04-25 · Wei Shen, Zhenhuan Yang, Yiming Ying, Xiaoming Yuan

In this paper we study the stability and its trade-off with optimization error for stochastic gradient descent (SGD) algorithms in the pairwise learning setting. Pairwise learning refers to a learning task which involves a loss function depending on pairs of instances among which notable examples are bipartite ranking, metric learning, area under ROC (AUC) maximization and minimum error entropy (MEE) principle. Our contribution is twofold. Firstly, we establish the stability results of SGD for pairwise learning in the convex, strongly convex and non-convex settings, from which generalization bounds can be naturally derived. Secondly, we establish the trade-off between stability and optimization error of SGD algorithms for pairwise learning. This is achieved by lower-bounding the sum of stability and optimization error by the minimax statistical error over a prescribed class of pairwise loss functions. From this fundamental trade-off, we obtain lower bounds for the optimization error of SGD algorithms and the excess expected risk over a class of pairwise losses. In addition, we illustrate our stability results by giving some specific examples of AUC maximization, metric learning and MEE.

📄 PDF Abstract BibTeX arXiv:1904.11316

Code (0)

등록된 구현이 없습니다.

Tasks

Generalization BoundsMetric Learning

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms

2023-07-07 · Ming Yang, Xiyuan Wei, Tianbao Yang, Yiming Ying

Many machine learning tasks can be formulated as a stochastic compositional optimization (SCO) problem such as reinforcement learning, AUC maximization, and meta-learning, where the objective function involves a nested c…

Learning Theory Meta-Learning

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

2026-06-05 · Jonghyun Shin, Sejun Park arxiv

We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic o…

Accelerating Stochastic Gradient Descent For Least Squares Regression

2017-04-26 · Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli 외

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their i…

regression Stochastic Optimization

Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: Application to stochastic coordinate descent

2023-09-05 · Stefano Di Giovacchino, Desmond J. Higham, Konstantinos Zygalakis

Stochastic optimization methods have been hugely successful in making large-scale optimization problems feasible when computing the full gradient is computationally prohibitive. Using the theory of modified equations for…

Stochastic Optimization

Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

2026-01-27 · Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo arxiv

The empirical evidence indicates that stochastic optimization with heavy-tailed gradient noise is more appropriate to characterize the training of machine learning models than that with standard bounded gradient variance…