Publications

Interactive learning with pricing for optimal and stable allocations in markets

Yigit Efe Erginbas, Soham Phade and Kannan Ramchandran
AISTATS 2023

Large-scale online recommendation systems must facilitate the allocation of a limited number of items among competing users while learning their preferences from user feedback. As a principled way of incorporating market constraints and user incentives in the design, we consider our objectives to be two-fold: maximal social welfare with minimal instability. To maximize social welfare, our proposed framework enhances the quality of recommendations by exploring allocations that optimistically maximize the rewards. To minimize instability, a measure of users’ incentives to deviate from recommended allocations, the algorithm prices the items based on a scheme derived from the Walrasian equilibria.

Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions

Yigit Efe Erginbas, Justin Singh Kang, Amirali Aghazadeh and Kannan Ramchandran
submitted to ISIT 2023

We develop a sparse Fourier transform algorithm specifically for $q$-ary functions of length $n$ sequences, dubbed $q$-SFT, which provably computes an $S$-sparse transform with vanishing error as $q^n \rightarrow \infty$ in $O(Sn)$ function evaluations and $O(S n^2 \log q)$ computations, where $S = q^{n\delta}$ for some $\delta < 1$. Under certain assumptions, we show that for fixed $q$, a robust version of $q$-SFT has a sample complexity of $O(Sn^2)$ and a computational complexity of $O(Sn^3)$ with the same asymptotic guarantees. We present numerical simulations on synthetic and real-world RNA data, demonstrating the scalability of $q$-SFT to massively high dimensional $q$-ary functions.

Interactive recommendations for optimal allocations in markets with constraints

Yigit Efe Erginbas, Soham Phade and Kannan Ramchandran
2022 INFORMS Annual Meeting

Recommendation systems when employed in markets play a dual role: they assist users in selecting their most desired items from a large pool and they help in allocating a limited number of items to the users who desire them the most. Despite the prevalence of capacity constraints on allocations in many real-world recommendation settings, a principled way of incorporating them in the design of these systems has been lacking. Motivated by this, we propose an interactive framework where the system provider can enhance the quality of recommendations to the users by opportunistically exploring allocations that maximize user rewards and respect the capacity constraints using appropriate pricing mechanisms.

Gramian-based adaptive combination policies for diffusion learning over networks

Yigit Efe Erginbas, Stefan Vlaski and Ali H. Sayed
IEEE ICASSP 2021

This paper presents an adaptive combination strategy for distributed learning over diffusion networks. We develop an adaptive combination rule that aims at optimizing the transient learning performance, while maintaining the enhanced steady-state performance obtained using policies previously developed in the literature.