A Case of Exponential Convergence Rates for SVM
Classification is often the first problem described in introductory machine learning classes. Generalization guarantees of classification have historically been offered by Vapnik-Chervonenkis theory. Yet those guarantees are based on intractable algorithms, which has led to the theory of surrogate methods in classification. Guarantees offered by surrogate methods are based on calibration inequalities, which have been shown to be highly sub-optimal under some margin conditions, failing short to capture exponential convergence phenomena. Those "super" fast rates are becoming to be well understood for smooth surrogates, but the picture remains blurry for non-smooth losses such as the hinge loss, associated with the renowned support vector machines. In this paper, we present a simple mechanism to obtain fast convergence rates and we investigate its usage for SVM. In particular, we show that SVM can exhibit exponential convergence rates even without assuming the hard Tsybakov margin condition.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Guarantees in Wasserstein Distance for the Langevin Monte Carlo Algorithm
We study the problem of sampling from a distribution $\target$ using the Langevin Monte Carlo algorithm and provide rate of convergences for this algorithm in terms of Wasserstein distance of order $2$. Our result holds …
Reinforcement Learning for Exponential Utility: Algorithms and Convergence in Discounted MDPs
Reinforcement learning (RL) for exponential-utility optimization in discounted Markov decision processes (MDPs) lacks principled value-based algorithms. We address this gap in the fixed risk-aversion setting. Building on…
Reinforcement LearningA semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
We study stability of optimizers and convergence of Sinkhorn's algorithm in the framework of entropic optimal transport. We show entropic stability for optimal plans in terms of the Wasserstein distance between their mar…
Parametrized Accelerated Methods Free of Condition Number
Analyses of accelerated (momentum-based) gradient descent usually assume bounded condition number to obtain exponential convergence rates. However, in many real problems, e.g., kernel methods or deep neural networks, the…
Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting
We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-ti…
Friction