From the 3 of 15 linked papers with an AI index.
15 papers
Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
Dhruv Sarkar, Vaneet Aggarwal
The paper analyzes two‑time‑scale stochastic approximation with a non‑expansive slow map, establishes sharp lower bounds on residual decay, and proposes bias‑corrected and single‑l…
Price of Fairness in Bandits: A Tight Minimax Characterization
Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury
The paper characterizes the exact regret cost of enforcing strict fairness in multi-armed bandits, proving a matching lower bound and presenting the UCB-HARE algorithm that achieve…
A Geometric Approach to Constrained Online Learning
Dhruv Sarkar, Abhishek Sinha
The paper introduces NP-OGD, a nested‑projection algorithm for online convex optimization with time‑varying constraints, achieving optimal regret and improved bounds on cumulative…
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-…
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…
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…