skip to main content


Search for: All records

Creators/Authors contains: "Gupta, Varun"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Free, publicly-accessible full text available October 13, 2024
  2. Abstract

    Finding outlying elementsin probability distributions can be a hard problem. Taking a real example from Voting Rights Act enforcement, we consider the problem of maximizing the number of simultaneous majority-minority districts in a political districting plan. An unbiased random walk on districting plans is unlikely to find plans that approach this maximum. A common search approach is to use abiased random walk: preferentially select districting plans with more majority-minority districts. Here, we present a third option, calledshort bursts, in which an unbiased random walk is performed for a small number of steps (called theburst length), then re-started from the most extreme plan that was encountered in the last burst. We give empirical evidence that short-burst runs outperform biased random walks for the problem of maximizing the number of majority-minority districts, and that there are many values of burst length for which we see this improvement. Abstracting from our use case, we also consider short bursts where the underlying state space is a line with various probability distributions, and then explore some features of more complicated state spaces and how these impact the effectiveness of short bursts.

     
    more » « less
  3. We consider the problem of controlling a Linear Quadratic Regulator (LQR) system over a finite horizon T with fixed and known cost matrices Q,R, but unknown and non-stationary dynamics A_t, B_t. The sequence of dynamics matrices can be arbitrary, but with a total variation, V_T, assumed to be o(T) and unknown to the controller. Under the assumption that a sequence of stabilizing, but potentially sub-optimal controllers is available for all t, we present an algorithm that achieves the optimal dynamic regret of O(V_T^2/5 T^3/5 ). With piecewise constant dynamics, our algorithm achieves the optimal regret of O(sqrtST ) where S is the number of switches. The crux of our algorithm is an adaptive non-stationarity detection strategy, which builds on an approach recently developed for contextual Multi-armed Bandit problems. We also argue that non-adaptive forgetting (e.g., restarting or using sliding window learning with a static window size) may not be regret optimal for the LQR problem, even when the window size is optimally tuned with the knowledge of $V_T$. The main technical challenge in the analysis of our algorithm is to prove that the ordinary least squares (OLS) estimator has a small bias when the parameter to be estimated is non-stationary. Our analysis also highlights that the key motif driving the regret is that the LQR problem is in spirit a bandit problem with linear feedback and locally quadratic cost. This motif is more universal than the LQR problem itself, and therefore we believe our results should find wider application. 
    more » « less
  4. We give a simple, generic conformal prediction method for sequential prediction that achieves target empirical coverage guarantees against adversarially chosen data. It is computationally lightweight -- comparable to split conformal prediction -- but does not require having a held-out validation set, and so all data can be used for training models from which to derive a conformal score. It gives stronger than marginal coverage guarantees in two ways. First, it gives threshold calibrated prediction sets that have correct empirical coverage even conditional on the threshold used to form the prediction set from the conformal score. Second, the user can specify an arbitrary collection of subsets of the feature space -- possibly intersecting -- and the coverage guarantees also hold conditional on membership in each of these subsets. We call our algorithm MVP, short for MultiValid Prediction. We give both theory and an extensive set of empirical evaluations. 
    more » « less
  5. Network planning is critical to the performance, reliability and cost of web services. This problem is typically formulated as an Integer Linear Programming (ILP) problem. Today's practice relies on hand-tuned heuristics from human experts to address the scalability challenge of ILP solvers. In this paper, we propose NeuroPlan, a deep reinforcement learning (RL) approach to solve the network planning problem. This problem involves multi-step decision making and cost minimization, which can be naturally cast as a deep RL problem. We develop two important domain-specific techniques. First, we use a graph neural network (GNN) and a novel domain-specific node-link transformation for state encoding, in order to handle the dynamic nature of the evolving network topology during planning decision making. Second, we leverage a two-stage hybrid approach that first uses deep RL to prune the search space and then uses an ILP solver to find the optimal solution. This approach resembles today's practice, but avoids human experts with an RL agent in the first stage. Evaluation on real topologies and setups from large production networks demonstrates that NeuroPlan scales to large topologies beyond the capability of ILP solvers, and reduces the cost by up to 17% compared to hand-tuned heuristics. 
    more » « less
  6. Abstract

    Achieving increased energy density under extreme operating conditions remains a major challenge in rechargeable batteries. Herein, we demonstrate an all‐fluorinated ester‐based electrolyte comprising partially fluorinated carboxylate and carbonate esters. This electrolyte exhibits temperature‐resilient physicochemical properties and moderate ion‐paired solvation, leading to a half solvent‐separated and half contact‐ion pair in a sole electrolyte. As a result, facile desolvation and preferential reduction of anions/fluorinated co‐solvents for LiF‐dominated interphases are achieved without compromising ionic conductivity (>1 mS cm−1even at −40 °C). These advantageous features were found to apply to both lithium metal and sulfur‐based electrodes even under extreme operating conditions, allowing stable cycling of Li || sulfurized polyacrylonitrile (SPAN) full cells with high SPAN loading (>3.5 mAh cm−2) and thin Li anode (50 μm) at −40, 23 and 50 °C. This work offers a promising path for designing temperature‐resilient electrolytes to support high energy density Li metal batteries operating in extreme conditions.

     
    more » « less
  7. Abstract

    Achieving increased energy density under extreme operating conditions remains a major challenge in rechargeable batteries. Herein, we demonstrate an all‐fluorinated ester‐based electrolyte comprising partially fluorinated carboxylate and carbonate esters. This electrolyte exhibits temperature‐resilient physicochemical properties and moderate ion‐paired solvation, leading to a half solvent‐separated and half contact‐ion pair in a sole electrolyte. As a result, facile desolvation and preferential reduction of anions/fluorinated co‐solvents for LiF‐dominated interphases are achieved without compromising ionic conductivity (>1 mS cm−1even at −40 °C). These advantageous features were found to apply to both lithium metal and sulfur‐based electrodes even under extreme operating conditions, allowing stable cycling of Li || sulfurized polyacrylonitrile (SPAN) full cells with high SPAN loading (>3.5 mAh cm−2) and thin Li anode (50 μm) at −40, 23 and 50 °C. This work offers a promising path for designing temperature‐resilient electrolytes to support high energy density Li metal batteries operating in extreme conditions.

     
    more » « less
  8. Cloud services are deployed in datacenters connected though high-bandwidth Wide Area Networks (WANs). We find that WAN traffic negatively impacts the performance of datacenter traffic, increasing tail latency by 2.5x, despite its small bandwidth demand. This behavior is caused by the long round-trip time (RTT) for WAN traffic, combined with limited buffering in datacenter switches. The long WAN RTT forces datacenter traffic to take the full burden of reacting to congestion. Furthermore, datacenter traffic changes on a faster time-scale than the WAN RTT, making it difficult for WAN congestion control to estimate available bandwidth accurately. We present Annulus, a congestion control scheme that relies on two control loops to address these challenges. One control loop leverages existing congestion control algorithms for bottlenecks where there is only one type of traffic (i.e., WAN or datacenter). The other loop handles bottlenecks shared between WAN and datacenter traffic near the traffic source, using direct feedback from the bottleneck. We implement Annulus on a testbed and in simulation. Compared to baselines using BBR for WAN congestion control and DCTCP or DCQCN for datacenter congestion control, Annulus increases bottleneck utilization by 10% and lowers datacenter flow completion time by 1.3-3.5x. 
    more » « less
  9. Abstract

    This paper presents the genetic algorithm (GA) and particle swarm optimization (PSO) based frequency regulation for a wind‐based microgrid (MG) using reactive power balance loop. MG, operating from squirrel cage induction generator (SCIG), is employed for exporting the electrical power from wind turbines, and it needs reactive power which may be imported from the grid. Additional reactive power is also required from the grid for the load, directly coupled with such a distributed generator (DG) plant. However, guidelines issued by electric authorities encourage MGs to arrange their own reactive power because such reactive power procurement is defined as a local area problem for power system studies. Despite the higher cost of compensation, static synchronous compensator (STATCOM) is a fast‐acting FACTs device for attending to these reactive power mismatches. Reactive power control can be achieved by controlling reactive current through the STATCOM. This can be achieved with modification in current controller scheme of STATCOM. STATCOM current controller is designed with reactive power load balance for the proposed microgrid in this paper. Further, gain values of the PI controller, required in the STATCOM model, are selected first with classical methods. In this classical method, iterative procedures which are based on integral square error (ISE), integral absolute error (IAE), and integral square of time error (ISTE) criteria are developed using MATLAB programs. System performances are further investigated with GA and PSO based control techniques and their acceptability over classical methods is diagnosed. Results in terms of converter frequency deviation show how the frequency remains under the operating boundaries as allowed by IEEE standards 1159:1995 and 1250:2011 for integrating renewable‐based microgrid with grid. Real and reactive power management and load current total harmonic distortions verify the STATCOM performance in MG. The results are further validated with the help of recent papers in which frequency regulation is investigated for almost similar power system models. The compendium for this work is as following: (i) modelling of wind generator‐based microgrid using MATLAB simulink library, (ii) designing of STATCOM current controller with PI controller, (iii) gain constants estimation using classical, GA and PSO algorithm through a developed m codes and their interfacing with proposed simulink model, (v) dynamic frequency responses for proposed grid connected microgrid during starting and load perturbations, (vi) verification of system performance with the help of obtained real and reactive power management between STATCOM and grid, and (vii) validation of results with available literature.

     
    more » « less