Author name cluster

Apurv Shukla

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

EWRL Workshop 2025 Workshop Paper

FraPPE: Fast and Efficient Preference-based Pure Exploration

Udvas Das
Apurv Shukla
Debabrota Basu

Preference-based Pure Exploration (PrePEx) aims to identify with a given confidence level the set of Pareto optimal arms in a vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone $\mathcal C$. Though PrePEx and its variants are well-studied, there does not exist a *computationally efficient* algorithm that can *optimally* track the existing lower bound (Shukla and Basu, 2024) for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield a computationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in $\mathcal O (KL^{2})$ time for a bandit instance with $K$ arms and $L$ dimensional reward, which is a significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, **FraPPE**, asymptotically achieves the optimal sample complexity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that **FraPPE** achieves the lowest sample complexities to identify the exact Pareto set among the existing algorithms.

PDF

NeurIPS Conference 2025 Conference Paper

FraPPE: Fast and Efficient Preference-Based Pure Exploration

Udvas Das
Apurv Shukla
Debabrota Basu

Preference-based Pure Exploration (PrePEx) aims to identify with a given confidence level the set of Pareto optimal arms in a vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone $\mathcal C$. Though PrePEx and its variants are well-studied, there does not exist a *computationally efficient* algorithm that can *optimally* track the existing lower bound (Shukla and Basu, 2024) for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield a computationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in $\mathcal O(KL^{2})$ time for a bandit instance with $K$ arms and $L$ dimensional reward, which is a significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, **FraPPE**, asymptotically achieves the optimal sample complexity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that **FraPPE** achieves the lowest sample complexities to identify the exact Pareto set among the existing algorithms.

PDF Details

EWRL Workshop 2025 Workshop Paper

Unifying (Federated) (Private) High-Dimensional Bandits via ADMM

Apurv Shukla
Debabrota Basu

We study all possible variants of the high dimensional stochastic linear contextual bandit problem in federated and private settings. We propose a unifying algorithm design and analysis framework built on ADMM. Our method achieves existing state-of-the art guarantees in either setting for the central model. For the federated model, our results are entirely new and near-optimal in either setting. We also establish a novel lower bound on privacy-utility tradeoff for the federated model in the private setting and demonstrate on suitable numerical experiments for all problem variants.

PDF

NeurIPS Conference 2024 Conference Paper

Preference-based Pure Exploration

Apurv Shukla
Debabrota Basu

We study the preference-based pure exploration problem for bandits with vector-valued rewards and a set of preferences imposed over them. Specifically, we aim to identify the most preferred policy over a set of arms according to the preferences induced on the reward vectors by an ordering cone $C$. First, to quantify the impact of preferences, we derive a novel lower bound on the sample complexity for identifying the most preferred arm with confidence level $1-\delta$. Our lower bound shows that how the geometry of the preferences and reward vectors changes the hardness of this problem. We further explicate this geometry for Gaussian distributions of rewards, and provide a convex reformulation of the lower bound solvable with linear programming. Then, we leverage this convex reformulation of the lower bound to design the Track and Stop with Preferences (TSwP) algorithm that identifies the most preferred policy. Finally, we derive a new concentration result for vector-valued rewards, and show that TSwP achieves a matching sample complexity upper bound.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

Robust Streaming PCA

Daniel Bienstock
Minchan Jeong
Apurv Shukla
Se-Young Yun

We consider streaming principal component analysis when the stochastic data-generating model is subject to perturbations. While existing models assume a fixed covariance, we adopt a robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits on any algorithm recovering principal components. We analyze the convergence of the noisy power method and Oja’s algorithm, both studied for the stationary data generating model, and argue that the noisy power method is rate-optimal in our setting. Finally, we demonstrate the validity of our analysis through numerical experiments.

PDF Details