Active Information Acquisition for Linear Optimization

Shuran Zheng, Bo Waggoner, Yang Liu, Yiling Chen
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:166-175, 2018.

Abstract

We consider partially-specified optimization problems where the goal is to actively, but efficiently, acquire missing information about the problem in order to solve it. An algo- rithm designer wishes to solve a linear pro- gram (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the pa- rameters. The algorithm can iteratively choose an unknown parameter and gather information in the form of a noisy sample centered at the parameter’s (unknown) value. The goal is to find an approximately feasible and optimal so- lution to the underlying LP with high proba- bility while drawing a small number of sam- ples. We focus on two cases. (1) When the parameters b of the constraints are initially un- known, we propose an efficient algorithm com- bining techniques from the ellipsoid method for LP and confidence-bound approaches from bandit algorithms. The algorithm adaptively gathers information about constraints only as needed in order to make progress. We give sample complexity bounds for the algorithm and demonstrate its improvement over a naive approach via simulation. (2) When the param- eters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sam- ple complexity bounds, with an (inefficient) successive-elimination algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-zheng18a, title = {Active Information Acquisition for Linear Optimization}, author = {Zheng, Shuran and Waggoner, Bo and Liu, Yang and Chen, Yiling}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {166--175}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/zheng18a/zheng18a.pdf}, url = {https://proceedings.mlr.press/r16/zheng18a.html}, abstract = {We consider partially-specified optimization problems where the goal is to actively, but efficiently, acquire missing information about the problem in order to solve it. An algo- rithm designer wishes to solve a linear pro- gram (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the pa- rameters. The algorithm can iteratively choose an unknown parameter and gather information in the form of a noisy sample centered at the parameter’s (unknown) value. The goal is to find an approximately feasible and optimal so- lution to the underlying LP with high proba- bility while drawing a small number of sam- ples. We focus on two cases. (1) When the parameters b of the constraints are initially un- known, we propose an efficient algorithm com- bining techniques from the ellipsoid method for LP and confidence-bound approaches from bandit algorithms. The algorithm adaptively gathers information about constraints only as needed in order to make progress. We give sample complexity bounds for the algorithm and demonstrate its improvement over a naive approach via simulation. (2) When the param- eters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sam- ple complexity bounds, with an (inefficient) successive-elimination algorithm.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Active Information Acquisition for Linear Optimization %A Shuran Zheng %A Bo Waggoner %A Yang Liu %A Yiling Chen %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-zheng18a %I PMLR %P 166--175 %U https://proceedings.mlr.press/r16/zheng18a.html %V R16 %X We consider partially-specified optimization problems where the goal is to actively, but efficiently, acquire missing information about the problem in order to solve it. An algo- rithm designer wishes to solve a linear pro- gram (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the pa- rameters. The algorithm can iteratively choose an unknown parameter and gather information in the form of a noisy sample centered at the parameter’s (unknown) value. The goal is to find an approximately feasible and optimal so- lution to the underlying LP with high proba- bility while drawing a small number of sam- ples. We focus on two cases. (1) When the parameters b of the constraints are initially un- known, we propose an efficient algorithm com- bining techniques from the ellipsoid method for LP and confidence-bound approaches from bandit algorithms. The algorithm adaptively gathers information about constraints only as needed in order to make progress. We give sample complexity bounds for the algorithm and demonstrate its improvement over a naive approach via simulation. (2) When the param- eters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sam- ple complexity bounds, with an (inefficient) successive-elimination algorithm. %Z Reissued by PMLR on 04 October 2026.
APA
Zheng, S., Waggoner, B., Liu, Y. & Chen, Y.. (2018). Active Information Acquisition for Linear Optimization. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:166-175 Available from https://proceedings.mlr.press/r16/zheng18a.html. Reissued by PMLR on 04 October 2026.

Related Material