22 papers · 1 filter
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Vaneet Aggarwal
We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional th noise moment, . For every fixed interval …
Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization
Vaneet Aggarwal, Yiyang Lu
We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets that contain a supplied diago…
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
Vaneet Aggarwal
We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscr…
Constrained Online Learning with Noisy Constraint Values
Vaneet Aggarwal
We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under comm…
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning
Vaneet Aggarwal
We study nonnegative submodular maximization on elements subject to a general matroid of rank , when the offline algorithm is given an arbitrary controlled value oracle. Our…
Online Convex Optimization with Dueling Feedback
Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar +2
Noisy binary comparison between two candidates is a common interface between human and learning systems, especially in modern large language model (LLM) post-training alignment. We…
Online Non-Monotone DR-Submodular Maximization Matching the Offline Factor
Vaneet Aggarwal, Yiyang Lu
We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the -dimensional unit cube. The best known construct…
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Vaneet Aggarwal
We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite -th central moment, where is unknown. For a bounded…
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…
Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
Ankur Naskar, Swetha Ganesh, Vaneet Aggarwal
Many reinforcement learning (RL) problems in the infinite-horizon average-reward setting require optimizing multiple conflicting objectives while satisfying multiple safety constra…
Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal
While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited…
Lipschitz Dueling Bandits over Continuous Action Spaces
Mudit Sharma, Shweta Jain, Vaneet Aggarwal +1
We study for the first time, stochastic dueling bandits over continuous action spaces with Lipschitz structure, where feedback is purely comparative. While dueling bandits and Lips…
Oracle-Robust Online Alignment for Large Language Models
Zimeng Li, Mudit Gaur, Vaneet Aggarwal
We study online alignment of large language models under misspecified preference feedback, where the observed preference oracle deviates from an ideal but unknown ground-truth orac…
Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
Yiyang Lu, Haresh Jadav, Mohammad Pedramfar +2
We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer…
-weakly -up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions
Mohammad Pedramfar, Vaneet Aggarwal
Optimizing non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study -weakly -up-concavity, a novel first…
Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
Hareshkumar Jadav, Ranveer Singh, Vaneet Aggarwal
Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone -weakl…
A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback
Vaneet Aggarwal, Shweta Jain, Subham Pokhriyal +1
We study bi-criteria combinatorial optimization under noisy function evaluations. While resilience and black-box offline-to-online reductions have been studied in single-objective…
BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access
Yiyang Lu, Mohammad Pedramfar, Mengbo Wang +1
In adversarial Constrained Online Convex Optimization (COCO), a learner selects actions from a fixed convex set while seeking both low regret and low cumulative constraint violatio…
Stochastic -Submodular Bandits with Full Bandit Feedback
Guanyu Nie, Vaneet Aggarwal, Christopher John Quinn
In this paper, we present the first sublinear -regret bounds for online -submodular optimization problems with full-bandit feedback, where is a corresponding offline appr…
Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
Mohammad Pedramfar, Yididiya Y. Nadew, Christopher J. Quinn +1
This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (se…
Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries
Swetha Ganesh, Jiayu Chen, Gugan Thoppe +1
Federated Reinforcement Learning (FRL) allows multiple agents to collaboratively build a decision making policy without sharing raw trajectories. However, if a small fraction of th…
A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
Mohammad Pedramfar, Vaneet Aggarwal
In this paper, we analyze the problem of online convex optimization in different settings, including different feedback types (full-information/semi-bandit/bandit/etc) in either st…