17 papers
Regret and Polylogarithmic Constraint Violation for COCO
Dhruv Sarkar, Abhishek Sinha
We study constrained online convex optimization with adversarial convex costs and constraints (). At each round , a learner selects from a -dimensi…
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
Dhruv Sarkar, Aprameyo Chakrabartty
We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained onli…
Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
Dhruv Sarkar, Vaneet Aggarwal
Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium.…
Price of Fairness in Bandits: A Tight Minimax Characterization
Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury
In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as c…
High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal
We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-t…
Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It
Dhruv Sarkar, Vaneet Aggarwal
Recent finite-time analyses of nonlinear two-time-scale stochastic approximation show that under contractive assumptions the slow iterate with stepsizes and $…
Constrained Contextual Bandits with Adversarial Contexts
Dhruv Sarkar, Abhishek Sinha
We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to…
A Geometric Approach to Constrained Online Learning
Dhruv Sarkar, Abhishek Sinha
We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared…
A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression
Dhruv Sarkar, Abhishek Sinha
We study constrained contextual bandits (CCB) with adversarially chosen contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizabi…
Improved Algorithms for Nash Welfare in Linear Bandits
Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury
Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this…
Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints
Dhruv Sarkar, Abhishek Sinha
We propose an anytime online algorithm for the problem of learning a sequence of adversarial convex cost functions while approximately satisfying another sequence of adversarial on…
Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need
Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury
Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward.…
Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
Dhruv Sarkar, Samrat Mukhopadhyay, Abhishek Sinha
We study an online learning problem with long-term budget constraints in the adversarial setting. In this problem, at each round , the learner selects an action from a convex de…
DP-NCB: Privacy Preserving Fair Bandits
Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury
Multi-armed bandit algorithms are fundamental tools for sequential decision-making under uncertainty, with widespread applications across domains such as clinical trials and person…
TAPS : Frustratingly Simple Test Time Active Learning for VLMs
Dhruv Sarkar, Aprameyo Chakrabartty, Bibhudatta Bhanja
Test-Time Optimization enables models to adapt to new data during inference by updating parameters on-the-fly. Recent advances in Vision-Language Models (VLMs) have explored learni…
Relation-Aware Slicing in Cross-Domain Alignment
Dhruv Sarkar, Aprameyo Chakrabartty, Anish Chakrabarty +1
The Sliced Gromov-Wasserstein (SGW) distance, aiming to relieve the computational cost of solving a non-convex quadratic program that is the Gromov-Wasserstein distance, utilizes p…
Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints
Dhruv Sarkar, Aprameyo Chakrabartty, Subhamon Supantha +2
We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this setting, at each round, the learner selects an action…