24 papers · 1 filter
Geometry-Dependent Approximation for Non-Monotone -Submodular Maximization
Vaneet Aggarwal
We study the maximization of a nonnegative -submodular function, not assumed monotone, in which each of elements receives one of labels or stays unselected and the s…
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…
Sharp Minimax Regret for Infinite-Memory Logistic Prediction
Vaneet Aggarwal
We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs are…
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…
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal
We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-re…
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…
Distributionally Robust Listwise Preference Optimization
Xudong Wu, Jian Qian, Pangpang Liu +2
Existing robust preference optimization for language-model alignment mainly studies pairwise supervision and places robustness at the dataset, prompt, or preference-pair level. We…
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.…
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…
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 $…
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…
Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
Subham Pokhriyal, Shweta Jain, Vaneet Aggarwal
We study the \emph{Submodular Welfare Problem} (SWP), where items are partitioned among agents with monotone submodular utilities to maximize the total welfare under \emph{bandit f…
LiSFC-Search: Lifelong Search for Network SFC Optimization under Non-stationary Drifts
Zuyuan Zhang, Vaneet Aggarwal, Tian Lan
Edge-cloud convergence is reshaping service provisioning across 5G/6G and computing power networks (CPNs). Service function chaining (SFC) requires continuously placing and schedul…
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…