Applied Probability & Statistics

1. ICML 2026

   Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds

   Zedong Wang, Yuyang Wang, Ijay Narang, Felix Wang, Yuzhou Wang, and Siva Theja Maguluri

   Abs Bib arXiv

   Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency. For a fixed stepsize, the iterates typically admit a stationary distribution that is rarely tractable. Prior work shows that as the stepsize \(\alpha \downarrow 0\), the centered-and-scaled steady state converges weakly to a Gaussian random vector. However, for fixed \(\alpha\), this weak convergence offers no usable error bound for approximating the steady-state by its Gaussian limit. This paper provides explicit, non-asymptotic error bounds for fixed \(\alpha\). We first prove general-purpose theorems that bound the Wasserstein distance between the centered-scaled steady state and an appropriate Gaussian distribution, under regularity conditions for drift and moment conditions for noise. To ensure broad applicability, we cover both i.i.d. and Markovian noise models. We then instantiate these theorems for three representative SA settings: (1) stochastic gradient descent (SGD) for smooth strongly convex objectives, (2) linear SA, and (3) contractive nonlinear SA. We obtain dimension- and stepsize-dependent, explicit bounds in Wasserstein distance of order \(\alpha^{1/2}\log(1/\alpha)\) for small \(\alpha\). Building on the Wasserstein approximation error, we further derive non-uniform Berry--Esseen-type tail bounds that compare the steady-state tail probability to Gaussian tails. We achieve an explicit error term that decays in both the deviation level and stepsize \(\alpha\). We adapt the same analysis for SGD beyond strongly convexity and study general convex objectives. We identify a non-Gaussian (Gibbs) limiting law under the correct scaling, which is validated numerically, and provide a corresponding pre-limit Wasserstein error bound.

   @article{WangWangNarangWangWangMaguluri2026constantStepsize,
     title = {Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds},
     author = {Wang, Zedong and Wang, Yuyang and Narang, Ijay and Wang, Felix and Wang, Yuzhou and Maguluri, Siva Theja},
     journal = {arXiv preprint arXiv:2602.13960},
     year = {2026}
   }

2. Preprint 2026

   Optimal detection of planted stars via a random energy model

   Ijay Narang, Will Perkins, and Timothy Wee

   Abs Bib arXiv

   We study the problem of detecting a planted star in the Erdős-Rényi random graph \(G(n,m)\), formulated as a hypothesis test. We determine the scaling window for critical detection in \(m\) in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory.

   @article{NarangPerkinsWee2026plantedStar,
     title = {Optimal detection of planted stars via a random energy model},
     author = {Narang, Ijay and Perkins, Will and Wee, Timothy},
     journal = {arXiv preprint arXiv:2602.15585},
     year = {2026}
   }

Theoretical Computer Science

Undergraduate Research

1. Preprint 2025

   Sharp Inner Product Correlations for Hypercube Bijections

   Ijay Narang and Muchen Ju

   Abs Bib arXiv

   We resolve a conjecture of Rob Morris concerning bijections on the hypercube. Specifically, we show that for any bijection \(f : \{-1,1\}^n \to \{-1,1\}^n\), \(\Pr_{x,y \in \{-1,1\}^n}\big[ \langle x,y \rangle \ge 0 \;\text{and}\; \langle f(x),f(y) \rangle \ge 0 \big] \ge \tfrac{1}{4} - O(1/\sqrt{n})\), implying the same lower bound for the joint event under any two bijections. Our proof proceeds by applying the spectral decomposition of the Hamming association scheme, which allows us to reformulate the problem as a linear program over the Birkhoff polytope. This makes it possible to isolate the contribution of the nontrivial spectrum, which we show is asymptotically negligible, leaving the dominant contribution arising from the principal eigenvalue.

   @article{NarangJu2025hypercubeBijections,
     title = {Sharp Inner Product Correlations for Hypercube Bijections},
     author = {Narang, Ijay and Ju, Muchen},
     journal = {arXiv preprint arXiv:2509.00716},
     year = {2025}
   }

2. Paper

   On even-H-free Colorings

   Ijay Narang. Advised by Dr. Noga Alon

   Abs Bib PDF

   For a given graph \(H\), an edge-coloring \(C\) of the complete graph \(K_n\) is even-\(H\)-free if every copy of \(H\) intersects at least one color class with an odd number of edges. These colorings are motivated by the study of graph codes, which were introduced in earlier work. Even-\(H\)-free colorings exhibit interesting properties and are closely related to other problems in Ramsey Theory. The present short paper includes new results about the extremal properties of such colorings. Let \(g(n,H)\) be the minimum number of colors required in an even-\(H\)-free coloring of \(K_n\). Our main result is the identification of a class of graphs \(H\), namely forests of even stars satisfying appropriate size constraints, for which \(g(n,H)=\Theta(n^2)\).

   @misc{NarangEvenHFreeColorings,
     title = {On even-H-free Colorings},
     author = {Narang, Ijay},
     note = {Advised by Dr. Noga Alon}
   }

3. Thesis

   On Expansion, High-Dimensional Expanders, and Applications in Coding Theory

   Ijay Narang. Undergraduate Thesis. Advised by Dr. Pedro Paredes

   Abs Bib PDF

   Communication protocols and data storage necessitate the use of error-correcting codes, which inject redundancy into a bit-string to make it resilient against corruption. Desirable properties of such codes include distance, ensuring recoverability of the original message, and rate, capturing transmission efficiency. It is well known that expander graphs, sparse yet highly connected graphs, can be used to construct codes that achieve strong trade-offs between these parameters. Furthermore, the higher dimensional analog of expanders, high dimensional expanders, have also found useful applications in coding theory. Thus, this thesis studies this intersection of expanders, high dimensional expanders, and coding theory. Thematically, this paper can be viewed in two parts: the first is a survey of classical and recent ideas in this area, and the second presents new combinatorial constructions of expanding square and cubical complexes.

   @misc{Narang2024expandersCodingTheory,
     title = {On Expansion, High-Dimensional Expanders, and Applications in Coding Theory},
     author = {Narang, Ijay},
     note = {Undergraduate thesis, advised by Dr. Pedro Paredes}
   }