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 algorithm designer wishes to solve a linear program (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the parameters. 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 solution to the underlying LP with high probability while drawing a small number of samples. We focus on two cases. (1) When the parameters b of the constraints are initially un-known, we propose an efficient algorithm combining 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 parameters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sample 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 algorithm designer wishes to solve a linear program (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the parameters. 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 solution to the underlying LP with high probability while drawing a small number of samples. We focus on two cases. (1) When the parameters b of the constraints are initially un-known, we propose an efficient algorithm combining 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 parameters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sample 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 algorithm designer wishes to solve a linear program (LP), max cT x s.t. Ax $\leq$b, x $\geq$0, but does not initially know some of the parameters. 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 solution to the underlying LP with high probability while drawing a small number of samples. We focus on two cases. (1) When the parameters b of the constraints are initially un-known, we propose an efficient algorithm combining 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 parameters c of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sample 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