Joseph Wang,
Kirill Trapeznikov,
Venkatesh Saligrama
;
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:987-995, 2014.
Abstract
We present a convex framework to learn sequential decisions and apply this to the problem of learning under a budget. We consider the structure proposed [1], where sensor measurements are acquired in a sequence. The goal after acquiring each new measurement is to make a decision whether to stop and classify or to pay the cost of using the next sensor in the sequence. We introduce a novel formulation of an empirical risk objective for the multi stage sequential decision problem. This objective naturally lends itself to a non-convex multilinear formulation. Nevertheless, we derive a novel perspective that leads to a tight convex objective. This is accomplished by expressing the empirical risk in terms of linear superposition of indicator functions. We then derive an LP formulation by utilizing hinge loss surrogates. Our LP achieves or exceeds the empirical performance as the non-convex alternating algorithm that requires a large number of random initializations. Consequently, the LP has the advantage of guaranteed convergence, global optimality, repeatability and computation efficiency.
@InProceedings{pmlr-v33-wang14b,
title = {{An LP for Sequential Learning Under Budgets}},
author = {Joseph Wang and Kirill Trapeznikov and Venkatesh Saligrama},
booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics},
pages = {987--995},
year = {2014},
editor = {Samuel Kaski and Jukka Corander},
volume = {33},
series = {Proceedings of Machine Learning Research},
address = {Reykjavik, Iceland},
month = {22--25 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v33/wang14b.pdf},
url = {http://proceedings.mlr.press/v33/wang14b.html},
abstract = {We present a convex framework to learn sequential decisions and apply this to the problem of learning under a budget. We consider the structure proposed [1], where sensor measurements are acquired in a sequence. The goal after acquiring each new measurement is to make a decision whether to stop and classify or to pay the cost of using the next sensor in the sequence. We introduce a novel formulation of an empirical risk objective for the multi stage sequential decision problem. This objective naturally lends itself to a non-convex multilinear formulation. Nevertheless, we derive a novel perspective that leads to a tight convex objective. This is accomplished by expressing the empirical risk in terms of linear superposition of indicator functions. We then derive an LP formulation by utilizing hinge loss surrogates. Our LP achieves or exceeds the empirical performance as the non-convex alternating algorithm that requires a large number of random initializations. Consequently, the LP has the advantage of guaranteed convergence, global optimality, repeatability and computation efficiency.}
}
%0 Conference Paper
%T An LP for Sequential Learning Under Budgets
%A Joseph Wang
%A Kirill Trapeznikov
%A Venkatesh Saligrama
%B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics
%C Proceedings of Machine Learning Research
%D 2014
%E Samuel Kaski
%E Jukka Corander
%F pmlr-v33-wang14b
%I PMLR
%J Proceedings of Machine Learning Research
%P 987--995
%U http://proceedings.mlr.press
%V 33
%W PMLR
%X We present a convex framework to learn sequential decisions and apply this to the problem of learning under a budget. We consider the structure proposed [1], where sensor measurements are acquired in a sequence. The goal after acquiring each new measurement is to make a decision whether to stop and classify or to pay the cost of using the next sensor in the sequence. We introduce a novel formulation of an empirical risk objective for the multi stage sequential decision problem. This objective naturally lends itself to a non-convex multilinear formulation. Nevertheless, we derive a novel perspective that leads to a tight convex objective. This is accomplished by expressing the empirical risk in terms of linear superposition of indicator functions. We then derive an LP formulation by utilizing hinge loss surrogates. Our LP achieves or exceeds the empirical performance as the non-convex alternating algorithm that requires a large number of random initializations. Consequently, the LP has the advantage of guaranteed convergence, global optimality, repeatability and computation efficiency.
TY - CPAPER
TI - An LP for Sequential Learning Under Budgets
AU - Joseph Wang
AU - Kirill Trapeznikov
AU - Venkatesh Saligrama
BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics
PY - 2014/04/02
DA - 2014/04/02
ED - Samuel Kaski
ED - Jukka Corander
ID - pmlr-v33-wang14b
PB - PMLR
SP - 987
DP - PMLR
EP - 995
L1 - http://proceedings.mlr.press/v33/wang14b.pdf
UR - http://proceedings.mlr.press/v33/wang14b.html
AB - We present a convex framework to learn sequential decisions and apply this to the problem of learning under a budget. We consider the structure proposed [1], where sensor measurements are acquired in a sequence. The goal after acquiring each new measurement is to make a decision whether to stop and classify or to pay the cost of using the next sensor in the sequence. We introduce a novel formulation of an empirical risk objective for the multi stage sequential decision problem. This objective naturally lends itself to a non-convex multilinear formulation. Nevertheless, we derive a novel perspective that leads to a tight convex objective. This is accomplished by expressing the empirical risk in terms of linear superposition of indicator functions. We then derive an LP formulation by utilizing hinge loss surrogates. Our LP achieves or exceeds the empirical performance as the non-convex alternating algorithm that requires a large number of random initializations. Consequently, the LP has the advantage of guaranteed convergence, global optimality, repeatability and computation efficiency.
ER -
Wang, J., Trapeznikov, K. & Saligrama, V.. (2014). An LP for Sequential Learning Under Budgets. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in PMLR 33:987-995
This site last compiled Mon, 16 Jul 2018 07:45:17 +0000