Theses Doctoral

Optimization and learning in dynamic environments: models and algorithms

Shukla, Apurv

This dissertation proposes new models and algorithms for optimization and learning in dynamic environments. We consider three problems: design of variance-aware optimization algorithms for the optimal power flow problem, robust streaming PCA and the contextual Pareto bandit problem. For the variance-aware optimal power flow problem, we consider the incorporation of stochastic loads and generation into the operation of power grids gives rise to an exposure to stochastic risk.

This risk has been addressed in prior work through a variety of mechanisms, such as scenario generation or chance constraints, that can be incorporated into OPF computations. We introduce a variety of convex variants of OPF that explicitly address the interplay of (power flow) variance with cost minimization, and present numerical experiments that highlight our contributions. In Robust Streaming PCA, we consider streaming principal component analysis (PCA) when the stochastic data-generating model is subject to adversarial perturbations. While existing models assume a fixed stochastic data-generating model, we instead adopt a robust perspective where the data generating model constrains the amount of allowed adversarial perturbations, and establish fundamental limits on achievable performance of any algorithm to recover appropriate principal components under this model.

Using a novel proof technique, we establish the rate-optimality for robust versions of the noisy power method, previously developed for the non-robust version of the problem. Our modeling and analysis framework provides a unique lens to study sequential stochastic optimization with a non-convex objective and sheds light on the fragility of using off-the-shelf PCA algorithms in an adversarial environment. Our claims are further corroborated on a suite of numerical experiments. The results are numerically verified for a range of parameter values governing the streaming PCA problem.

In contextual Pareto bandits, we consider a continuum-armed contextual bandit problem under vectorial rewards. For this problem, we propose a tree-based policy that maintains separate partitions for action and covariate spaces. In the presence of vectorial rewards, we evaluate the performance of the proposed policy in terms of its Contextual Pareto regret. We establish an upper bound on the performance of the proposed policy for this static policy. Finally, the efficacy of the proposed policy is described on a suite of numerical experiments.


  • thumnail for Shukla_columbia_0054D_17063.pdf Shukla_columbia_0054D_17063.pdf application/pdf 4.32 MB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Bienstock, Daniel
Iyengar, Garud N.
Ph.D., Columbia University
Published Here
March 30, 2022