Exploring Local Norms in Exp-concave Statistical Learning

P. 1993–2013.

Puchkin N., Zhivotovskiy N.

We consider the standard problem of stochastic convex optimization with exp-concave losses using Empirical Risk Minimization in a convex class. Answering a question raised in several prior works, we provide a 𝑂(𝑑/𝑛 + 1/𝑛 log(1/𝛿)) excess risk bound valid for a wide class of bounded exp-concave losses, where 𝑑 is the dimension of the convex reference set, 𝑛 is the sample size, and 𝛿 is the confidence level. Our result is based on a unified geometric assumption on the gradient of losses and the notion of local norms.

Keywords: Empirical risk minimization, Minimax rates of convergence, stochastic convex optimization, exp-concave losses, fast rates, стохастическая выпуклая оптимизация, минимизация эмпирического риска, экспоненциально вогнутые функции потерь, быстрые порядки, минимаксная скорость сходимости

Publication based on the results of: Structural learning and its applications (2023)

In book

Proceedings of Machine Learning Research: Volume 195: The Thirty Sixth Annual Conference on Learning Theory, 12-15 July 2023, Bangalore, India

Vol. 195: The Thirty Sixth Annual Conference on Learning Theory, 12-15 July 2023, Bangalore, India. , PMLR, 2023.