On Lipschitz Continuity and Smoothness of Loss Functions in Learning to Rank
In binary classification and regression problems, it is well understood that Lipschitz continuity and smoothness of the loss function play key roles in governing generalization error bounds for empirical risk minimization algorithms. In this paper, we show how these two properties affect generalization error bounds in the learning to rank problem. The learning to rank problem involves vector valued predictions and therefore the choice of the norm with respect to which Lipschitz continuity and smoothness are defined becomes crucial. Choosing the $\ell_\infty$ norm in our definition of Lipschitz continuity allows us to improve existing bounds. Furthermore, under smoothness assumptions, our choice enables us to prove rates that interpolate between $1/\sqrt{n}$ and $1/n$ rates. Application of our results to ListNet, a popular learning to rank method, gives state-of-the-art performance guarantees.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationLearning-To-RankSimilar Papers 제목 키워드 기반
Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning
The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization…
Coarse-Grained Smoothness for RL in Metric Spaces
Principled decision-making in continuous state--action spaces is impossible without some assumptions. A common approach is to assume Lipschitz continuity of the Q-function. We show that, unfortunately, this property fail…
Decision MakingL2C2: Locally Lipschitz Continuous Constraint towards Stable and Smooth Reinforcement Learning
This paper proposes a new regularization technique for reinforcement learning (RL) towards making policy and value functions smooth and stable. RL is known for the instability of the learning process and the sensitivity …
reinforcement-learningReinforcement Learning (RL)Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions
The performance of online convex optimization algorithms in a dynamic environment is often expressed in terms of the dynamic regret, which measures the decision maker's performance against a sequence of time-varying comp…
Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS
Theoretical analysis of the divide-and-conquer based distributed learning with least square loss in the reproducing kernel Hilbert space (RKHS) have recently been explored within the framework of learning theory. However…
Learning Theory