Aarti Singh
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Aarti Singh has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- David Merrick
Florida State University, Tallahassee, Florida, USA
1 shared publication Dhruv Malik
1 shared publication- Hoda Heidari
Carnegie Mellon University, Pittsburgh, PA, USA
1 shared publication - Jelena Kovacevic
New York University Tandon School of Engineering, Brooklyn, NY, USA
1 shared publication - Kanad Pardeshi
Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
1 shared publication - Minjung Park
Human-Computer Interaction Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
1 shared publication
Latest Publications
- Open Access
- 25 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2055-2091
Investigating the Role of AI in Emergency Management: Use Cases, Challenges, and Opportunities
- 25 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2055-2091
Open AccessInvestigating the Role of AI in Emergency Management: Use Cases, Challenges, and Opportunities
- Open Access
Complete Policy Regret Bounds for Tallying Bandits
Policy regret is a well established notion of measuring the performance of an online learning algorithm against an adaptive adversary. We study restrictions on the adversary that enable efficient minimization of the \emph{complete policy regret}, which is the strongest possible version of policy regret. We identify a gap in the current theoretical understanding of what sorts of restrictions permit tractability in this challenging setting. To resolve this gap, we consider a generalization of the stochastic multi armed bandit, which we call the \emph{tallying bandit}. This is an online learning setting with an $m$-memory bounded adversary, where the average loss for playing an action is an unknown function of the number (or tally) of times that the action was played in the last $m$ timesteps. For tallying bandit problems with $K$ actions and time horizon $T$, we provide an algorithm that w.h.p achieves a complete policy regret guarantee of $\tilde{\mathcal{O}}(mK\sqrt{T})$, where the $\tilde{\mathcal{O}}$ notation hides only logarithmic factors. We additionally prove an $\tilde\Omega(\sqrt{m K T})$ lower bound on the expected complete policy regret of any tallying bandit algorithm, demonstrating the near optimality of our method.Open AccessComplete Policy Regret Bounds for Tallying Bandits
Policy regret is a well established notion of measuring the performance of an online learning algorithm against an adaptive adversary. We study restrictions on the adversary that enable efficient minimization of the \emph{complete policy regret}, which is the strongest possible version of policy regret. We identify a gap in the current theoretical understanding of what sorts of restrictions permit tractability in this challenging setting. To resolve this gap, we consider a generalization of the stochastic multi armed bandit, which we call the \emph{tallying bandit}. This is an online learning setting with an $m$-memory bounded adversary, where the average loss for playing an action is an unknown function of the number (or tally) of times that the action was played in the last $m$ timesteps. For tallying bandit problems with $K$ actions and time horizon $T$, we provide an algorithm that w.h.p achieves a complete policy regret guarantee of $\tilde{\mathcal{O}}(mK\sqrt{T})$, where the $\tilde{\mathcal{O}}$ notation hides only logarithmic factors. We additionally prove an $\tilde\Omega(\sqrt{m K T})$ lower bound on the expected complete policy regret of any tallying bandit algorithm, demonstrating the near optimality of our method. - 10 June 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (11) , 7350-7366
Optimization of Smooth Functions With Noisy Observations: Local Minimax Rates
We consider the problem of global optimization of an unknown non-convex smooth function with noisy zeroth-order feedback. We propose a local minimax framework to study the fundamental difficulty of optimizing smooth functions with adaptive function evaluations. We show that for functions with fast growth around their global minima, carefully designed optimization algorithms can identify a near global minimizer with many fewer queries than worst-case global minimax theory predicts. For the special case of strongly convex and smooth functions, our implied convergence rates match the ones developed for zeroth-order convex optimization problems. On the other hand, we show that in the worst case no algorithm can converge faster than the minimax rate of estimating an unknown function in the ℓ ∞ -norm. Finally, we show that non-adaptive algorithms, though optimal in a global minimax sense, do not attain the optimal local minimax rate.
- 10 June 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (11) , 7350-7366
Optimization of Smooth Functions With Noisy Observations: Local Minimax Rates
We consider the problem of global optimization of an unknown non-convex smooth function with noisy zeroth-order feedback. We propose a local minimax framework to study the fundamental difficulty of optimizing smooth functions with adaptive function evaluations. We show that for functions with fast growth around their global minima, carefully designed optimization algorithms can identify a near global minimizer with many fewer queries than worst-case global minimax theory predicts. For the special case of strongly convex and smooth functions, our implied convergence rates match the ones developed for zeroth-order convex optimization problems. On the other hand, we show that in the worst case no algorithm can converge faster than the minimax rate of estimating an unknown function in the ℓ ∞ -norm. Finally, we show that non-adaptive algorithms, though optimal in a global minimax sense, do not attain the optimal local minimax rate.
- 1 March 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 6370-6374
Representations of piecewise smooth signals on graphs
We study representations of piecewise-smooth signals on graphs. We first define classes for smooth, piecewise-constant, and piecewise-smooth graph signals, followed by a series of multiresolution local sets to analyze those signals by implementing a multiresolution analysis on graphs. Based on these local sets, we propose local-set-based piecewise-constant and piecewise-smooth dictionaries as graph signal representations that, in spirit, resemble the classical Haar wavelet basis and are naturally localized in both graph vertex and graph Fourier domains. Moreover, they promote sparsity when representing piecewise-smooth graph signals. In the experiments, we show that local-set-based dictionaries outperform graph Fourier domain based representations when approximating both simulated and real-world graph signals.
- 1 March 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 6370-6374
Representations of piecewise smooth signals on graphs
We study representations of piecewise-smooth signals on graphs. We first define classes for smooth, piecewise-constant, and piecewise-smooth graph signals, followed by a series of multiresolution local sets to analyze those signals by implementing a multiresolution analysis on graphs. Based on these local sets, we propose local-set-based piecewise-constant and piecewise-smooth dictionaries as graph signal representations that, in spirit, resemble the classical Haar wavelet basis and are naturally localized in both graph vertex and graph Fourier domains. Moreover, they promote sparsity when representing piecewise-smooth graph signals. In the experiments, we show that local-set-based dictionaries outperform graph Fourier domain based representations when approximating both simulated and real-world graph signals.