A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer

Tianbao Yang, Zhe Li, Lijun Zhang
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:445-453, 2018.

Abstract

In this paper, we present a simple analysis of fast rates with high probability of empirical minimization for it stochastic composite optimization over a finite-dimensional bounded convex set with exponential concave loss functions and an arbitrary convex regularization. To the best of our knowledge, this result is the first of its kind. As a byproduct, we can directly obtain the fast rate with high probability for exponential concave empirical risk minimization with and without any convex regularization, which not only extends existing results of empirical risk minimization but also provides a unified framework for analyzing exponential concave empirical risk minimization with and without any convex regularization. Our proof is very simple only exploiting the covering number of a finite-dimensional bounded set and a concentration inequality of random vectors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-yang18b, title = {A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer}, author = {Yang, Tianbao and Li, Zhe and Zhang, Lijun}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {445--453}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/yang18b/yang18b.pdf}, url = {https://proceedings.mlr.press/v84/yang18b.html}, abstract = {In this paper, we present a simple analysis of fast rates with high probability of empirical minimization for it stochastic composite optimization over a finite-dimensional bounded convex set with exponential concave loss functions and an arbitrary convex regularization. To the best of our knowledge, this result is the first of its kind. As a byproduct, we can directly obtain the fast rate with high probability for exponential concave empirical risk minimization with and without any convex regularization, which not only extends existing results of empirical risk minimization but also provides a unified framework for analyzing exponential concave empirical risk minimization with and without any convex regularization. Our proof is very simple only exploiting the covering number of a finite-dimensional bounded set and a concentration inequality of random vectors. } }
Endnote
%0 Conference Paper %T A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer %A Tianbao Yang %A Zhe Li %A Lijun Zhang %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-yang18b %I PMLR %P 445--453 %U https://proceedings.mlr.press/v84/yang18b.html %V 84 %X In this paper, we present a simple analysis of fast rates with high probability of empirical minimization for it stochastic composite optimization over a finite-dimensional bounded convex set with exponential concave loss functions and an arbitrary convex regularization. To the best of our knowledge, this result is the first of its kind. As a byproduct, we can directly obtain the fast rate with high probability for exponential concave empirical risk minimization with and without any convex regularization, which not only extends existing results of empirical risk minimization but also provides a unified framework for analyzing exponential concave empirical risk minimization with and without any convex regularization. Our proof is very simple only exploiting the covering number of a finite-dimensional bounded set and a concentration inequality of random vectors.
APA
Yang, T., Li, Z. & Zhang, L.. (2018). A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:445-453 Available from https://proceedings.mlr.press/v84/yang18b.html.

Related Material