Publications

Working papers

2024

1. working

   Lifted Residual Score Estimation

   Tejas Jayashankar*, J. Jon Ryu*, Xiangxiang Xu, and Gregory W. Wornell

   2024

   An extended abstract will be presented at ICML 2024 Workshop on Structured Probabilistic Inference & Generative Modeling.

Preprints

2024

1. arXiv

   A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation

   J. Jon Ryu, Abhin Shah, and Gregory W. Wornell

   2024

   Abs arXiv

   This paper studies a family of estimators based on noise-contrastive estimation (NCE) for learning unnormalized distributions. The main contribution of this work is to provide a unified perspective on various methods for learning unnormalized distributions, which have been independently proposed and studied in separate research communities, through the lens of NCE. This unified view offers new insights into existing estimators. Specifically, for exponential families, we establish the finite-sample convergence rates of the proposed estimators under a set of regularity assumptions, most of which are new.

2022

1. arXiv

   Minimax Optimal Algorithms with Fixed-k-Nearest Neighbors

   J. Jon Ryu, and Young-Han Kim

   2022

   Submitted.

   Abs arXiv Code

   This paper presents how to perform minimax optimal classification, regression, and density estimation based on fixed-k nearest neighbor (NN) searches. We consider a distributed learning scenario, in which a massive dataset is split into smaller groups, where the k-NNs are found for a query point with respect to each subset of data. We propose \emphoptimal rules to aggregate the fixed-k-NN information for classification, regression, and density estimation that achieve minimax optimal rates for the respective problems. We show that the distributed algorithm with a fixed k over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions. Roughly speaking, distributed k-NN rules with M groups has a performance comparable to the standard Θ(kM)-NN rules even for fixed k.

2. arXiv

   Learning with Succinct Common Representation with Wyner’s Common Information

   J. Jon Ryu, Yoojin Choi, Young-Han Kim, Mostafa El-Khamy , and Jungwon Lee

   2022

   Submitted. A preliminary version of this manuscript was presented at the Bayesian Deep Learning Workshop at NeurIPS 2018, and an abridged version of the current manuscript was presented at the Bayesian Deep Learning workshop at NeurIPS 2021.

   Abs arXiv Code

   A new bimodal generative model is proposed for generating conditional and joint samples, accompanied with a training method with learning a succinct bottleneck representation. The proposed model, dubbed as the variational Wyner model, is designed based on two classical problems in network information theory—distributed simulation and channel synthesis—in which Wyner’s common information arises as the fundamental limit on the succinctness of the common representation. The model is trained by minimizing the symmetric Kullback–Leibler divergence between variational and model distributions with regularization terms for common information, reconstruction consistency, and latent space matching terms, which is carried out via an adversarial density ratio estimation technique. The utility of the proposed approach is demonstrated through experiments for joint and conditional generation with synthetic and real-world datasets, as well as a challenging zero-shot image retrieval task.

Journal articles

2024

1. TIT

   On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

   J. Jon Ryu, and Alankrita Bhatt

   IEEE Trans. Inf. Theory, 2024

   Abs arXiv HTML Code

   This paper considers the problem of constructing a confidence sequence, which is a sequence of confidence intervals that hold uniformly over time, for estimating the mean of bounded real-valued random processes. This paper revisits the gambling-based approach established in the recent literature from a natural \emphtwo-horse race perspective, and demonstrates new properties of the resulting algorithm induced by Cover (1991)’s universal portfolio. The main result of this paper is a new algorithm based on a mixture of lower bounds, which closely approximates the performance of Cover’s universal portfolio with constant per-round time complexity. A higher-order generalization of a lower bound on a logarithmic function in (Fan et al., 2015), which is developed as a key technique for the proposed algorithm, may be of independent interest.

2022

1. TIT

   Nearest neighbor density functional estimation from inverse Laplace transform

   J. Jon Ryu*, Shouvik Ganguly*, Young-Han Kim, Yung-Kyun Noh, and Daniel D. Lee

   IEEE Trans. Inf. Theory, February 2022

   Abs arXiv HTML PDF Code

   A new approach to L_2-consistent estimation of a general density functional using k-nearest neighbor distances is proposed, where the functional under consideration is in the form of the expectation of some function f of the densities at each point. The estimator is designed to be asymptotically unbiased, using the convergence of the normalized volume of a k-nearest neighbor ball to a Gamma distribution in the large-sample limit, and naturally involves the inverse Laplace transform of a scaled version of the function f. Some instantiations of the proposed estimator recover existing k-nearest neighbor based estimators of Shannon and Rényi entropies and Kullback–Leibler and Rényi divergences, and discover new consistent estimators for many other functionals such as logarithmic entropies and divergences. The L_2-consistency of the proposed estimator is established for a broad class of densities for general functionals, and the convergence rate in mean squared error is established as a function of the sample size for smooth, bounded densities.

Conference papers

2024

1. ISIT

   Group Fairness with Uncertainty in Sensitive Attributes

   Abhin Shah, Maohao Shen, J. Jon Ryu, Subhro Das, Prasanna Sattigeri, Yuheng Bu, and Gregory W. Wornell

   In Proc. IEEE Int. Symp. Inf. Theory (ISIT) , February 2024

   A preliminary version of this manuscript was presented at ICML 2023 Workshop on Spurious Correlations, Invariance, and Stability.

   Abs arXiv

   Learning a fair predictive model is crucial to mitigate biased decisions against minority groups in high-stakes applications. A common approach to learn such a model involves solving an optimization problem that maximizes the predictive power of the model under an appropriate group fairness constraint. However, in practice, sensitive attributes are often missing or noisy resulting in uncertainty. We demonstrate that solely enforcing fairness constraints on uncertain sensitive attributes can fall significantly short in achieving the level of fairness of models trained without uncertainty. To overcome this limitation, we propose a bootstrap-based algorithm that achieves the target level of fairness despite the uncertainty in sensitive attributes. The algorithm is guided by a Gaussian analysis for the independence notion of fairness where we propose a robust quadratically constrained quadratic problem to ensure a strict fairness guarantee with uncertain sensitive attributes. Our algorithm is applicable to both discrete and continuous sensitive attributes and is effective in real-world classification and regression tasks for various group fairness notions, e.g., independence and separation.

2. ICML

   Operator SVD with Neural Networks via Nested Low-Rank Approximation

   J. Jon Ryu, Xiangxiang Xu, H. S. Melichan Erol, Yuheng Bu, Lizhong Zheng, and Gregory W. Wornell

   In Proc. Int. Conf. Mach. Learn. (ICML) , July 2024

   An extended abstract was presented at Machine Learning and the Physical Sciences Workshop, NeurIPS 2023.

   Abs arXiv HTML Code Poster

   Computing eigenvalue decomposition (EVD) of a given linear operator, or finding its leading eigenvalues and eigenfunctions, is a fundamental task in many machine learning and scientific computing problems. For high-dimensional eigenvalue problems, training neural networks to parameterize the eigenfunctions is considered as a promising alternative to the classical numerical linear algebra techniques. This paper proposes a new optimization framework based on the low-rank approximation characterization of a truncated singular value decomposition, accompanied by new techniques called nesting for learning the top-L singular values and singular functions in the correct order. The proposed method promotes the desired orthogonality in the learned functions implicitly and efficiently via an unconstrained optimization formulation, which is easy to solve with off-the-shelf gradient-based optimization algorithms. We demonstrate the effectiveness of the proposed optimization framework for use cases in computational physics and machine learning.

3. ICML

   Gambling-Based Confidence Sequences for Bounded Random Vectors

   J. Jon Ryu, and Gregory W. Wornell

   In Proc. Int. Conf. Mach. Learn. (ICML) , July 2024

   Spotlight (top 3.5%)

   Abs arXiv HTML Code Poster

   A confidence sequence (CS) is a sequence of confidence sets that contains a target parameter of an underlying stochastic process at any time step with high probability. This paper proposes a new approach to constructing CSs for means of bounded multivariate stochastic processes using a general gambling framework, extending the recently established coin toss framework for bounded random processes. The proposed gambling framework provides a general recipe for constructing CSs for categorical and probability-vector-valued observations, as well as for general bounded multidimensional observations through a simple reduction. This paper specifically explores the use of the mixture portfolio, akin to Cover’s universal portfolio, in the proposed framework and investigates the properties of the resulting CSs. Simulations demonstrate the tightness of these confidence sequences compared to existing methods. When applied to the sampling without-replacement setting for finite categorical data, it is shown that the resulting CS based on a universal gambling strategy is provably tighter than that of the posterior-prior ratio martingale proposed by Waudby-Smith and Ramdas.

4. NeurIPS

   Are Uncertainty Quantification Capabilities of Evidential Deep Learning a Mirage?

   Maohao Shen*, J. Jon Ryu*, Soumya Ghosh, Yuheng Bu, Prasanna Sattigeri, Subhro Das, and Gregory W. Wornell

   In Adv. Neural Inf. Proc. Syst. (NeurIPS) , July 2024

   Abs arXiv

   This paper questions the effectiveness of a modern predictive uncertainty quantification approach, called \emphevidential deep learning (EDL), in which a single neural network model is trained to learn a meta distribution over the predictive distribution by minimizing a specific objective function. Despite their perceived strong empirical performance on downstream tasks, a line of recent studies by Bengs et al. identify limitations of the existing methods to conclude their learned epistemic uncertainties are unreliable, e.g., in that they are non-vanishing even with infinite data. Building on and sharpening such analysis, we 1) provide a sharper understanding of the asymptotic behavior of a wide class of EDL methods by unifying various objective functions; 2) reveal that the EDL methods can be better interpreted as an out-of-distribution detection algorithm based on energy-based-models; and 3) conduct extensive ablation studies to better assess their empirical effectiveness with real-world datasets. Through all these analyses, we conclude that even when EDL methods are empirically effective on downstream tasks, this occurs despite their poor uncertainty quantification capabilities. Our investigation suggests that incorporating model uncertainty can help EDL methods faithfully quantify uncertainties and further improve performance on representative downstream tasks, albeit at the cost of additional computational complexity.

2023

1. AISTATS

   On Universal Portfolios with Continuous Side Information

   Alankrita Bhatt*, J. Jon Ryu*, and Young-Han Kim

   In Proc. Int. Conf. Artif. Int. Statist. (AISTATS) , April 2023

   Abs arXiv HTML

   A new portfolio selection strategy that adapts to a continuous side-information sequence is presented, with a universal wealth guarantee against a class of state-constant rebalanced portfolios with respect to a state function that maps each side-information symbol to a finite set of states. In particular, given that a state function belongs to a collection of functions of finite Natarajan dimension, the proposed strategy is shown to achieve, asymptotically to first order in the exponent, the same wealth as the best state-constant rebalanced portfolio with respect to the best state function, chosen in hindsight from observed market. This result can be viewed as an extension of the seminal work of Cover and Ordentlich (1996) that assumes a single state function.

2022

1. AISTATS

   Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting

   J. Jon Ryu, Alankrita Bhatt, and Young-Han Kim

   In Proc. Int. Conf. Artif. Int. Statist. (AISTATS) , March 2022

   Abs arXiv HTML PDF Code Poster

   A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and Pál (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.

2021

1. ISIT

   On the Role of Eigendecomposition in Kernel Embedding

   J. Jon Ryu, Jiun-Ting Huang, and Young-Han Kim

   In Proc. IEEE Int. Symp. Inf. Theory (ISIT) , March 2021

   Abs HTML PDF

   This paper proposes a special variant of Laplacian eigenmaps, whose solution is characterized by the underlying density and the eigenfunctions of the associated Hilbert–Schmidt operator of a similarity kernel function. In contrast to existing kernel-based spectral methods such as kernel principal component analysis and Laplacian eigenmaps, the new embedding algorithm only involves estimating density at each query point without any eigendecomposition of a matrix. A concrete example of dot-product kernels over hypersphere is provided to illustrate the applicability of the proposed framework.

2020

1. ICASSP

   Feedback Recurrent Autoencoder

   Yang Yang, Guillaume Sautière, J. Jon Ryu, and Taco S. Cohen

   In Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP) , March 2020

   Abs arXiv HTML

   In this work, we propose a new recurrent autoencoder architecture, termed Feedback Recurrent AutoEncoder (FRAE), for online compression of sequential data with temporal dependency. The recurrent structure of FRAE is designed to efficiently extract the redundancy along the time dimension and allows a compact discrete representation of the data to be learned. We demonstrate its effectiveness in speech spectrogram compression. Specifically, we show that the FRAE, paired with a powerful neural vocoder, can produce high-quality speech waveforms at a low, fixed bitrate. We further show that by adding a learned prior for the latent space and using an entropy coder, we can achieve an even lower variable bitrate.

2018

1. ICIP

   Conditional distribution learning with neural networks and its application to universal image denoising

   Jongha Ryu, and Young-Han Kim

   In Proc. IEEE Int. Conf. Image Proc. (ICIP) , March 2018

   Abs HTML PDF Poster

   A simple and scalable denoising algorithm is proposed that can be applied to a wide range of source and noise models. At the core of the proposed CUDE algorithm is symbol-by-symbol universal denoising used by the celebrated DUDE algorithm, whereby the optimal estimate of the source from an unknown distribution is computed by inverting the empirical distribution of the noisy observation sequence by a deep neural network, which naturally and implicitly aggregates multi-pie contexts of similar characteristics and estimates the conditional distribution more accurately. The performance of CUDE is evaluated for grayscale images of varying bit depths, which improves upon DUDE and its recent neural network based extension, Neural DUDE.

2. ITW

   Variations on a theme by Liu, Cuff, and Verdú: The power of posterior sampling

   Alankrita Bhatt†, Jiun-Ting Huang†, Young-Han Kim†, J. Jon Ryu†, and Pinar Sen†

   In Proc. IEEE Inf. Theory Workshop (ITW) , March 2018

   Abs HTML PDF

   The Liu–Cuff–Verdu lemma states that in estimating a source X from an observation Y, making a random guess X’ from the posterior p(x|y) can go wrong at most twice as often as the optimal answer. Several variations of this fundamental, yet rather arcane, result are explored for detection, decoding, and estimation problems.

3. Allerton

   Monte Carlo methods for randomized likelihood decoding

   Alankrita Bhatt†, Jiun-Ting Huang†, Young-Han Kim†, J. Jon Ryu†, and Pinar Sen†

   In Proc. Ann. Allerton Conf. Comm. Control Comput. (Allerton) , March 2018

   Abs HTML PDF

   A randomized decoder that generates the message estimate according to the posterior distribution is known to achieve the reliability comparable to that of the maximum a posteriori probability decoder. With a goal of practical implementations of such a randomized decoder, several Monte Carlo techniques, such as rejection sampling, Gibbs sampling, and the Metropolis algorithm, are adapted to the problem of efficient sampling from the posterior distribution. Analytical and experimental results compare the complexity and performance of these Monte Carlo decoders for simple linear codes and the binary symmetric channel.

Miscellaneous

2022

1. arXiv

   An Information-Theoretic Proof of Kac–Bernstein Theorem

   J. Jon Ryu, and Young-Han Kim

   March 2022

   Abs arXiv

   A short, information-theoretic proof of the Kac–Bernstein theorem, which is stated as follows, is presented: For any independent random variables X and Y, if X+Y and X-Y are independent, then X and Y are normally distributed.

2017

1. arXiv

   Energy-based sequence GANs for recommendation and their connection to imitation learning

   Jaeyoon Yoo, Heonseok Ha, Jihun Yi, Jongha Ryu , Chanju Kim, Jung-Woo Ha, Young-Han Kim, and Sungroh Yoon

   March 2017

   Abs arXiv

   Recommender systems aim to find an accurate and efficient mapping from historic data of user-preferred items to a new item that is to be liked by a user. Towards this goal, energy-based sequence generative adversarial nets (EB-SeqGANs) are adopted for recommendation by learning a generative model for the time series of user-preferred items. By recasting the energy function as the feature function, the proposed EB-SeqGANs is interpreted as an instance of maximum-entropy imitation learning.

Theses

2022

1. PhD thesis

   From Information Theory to Machine Learning Algorithms: A Few Vignettes

   Jongha Jon Ryu

   University of California San Diego , September 2022

   Abs HTML

   This dissertation illustrates how certain information-theoretic ideas and views on learning problems can lead to new algorithms via concrete examples.The three information-theoretic strategies taken in this dissertation are (1) to abstract out the gist of a learning problem in the infinite-sample limit; (2) to reduce a learning problem into a probability estimation problem and plugging-in a "good" probability; and (3) to adapt and apply relevant results from information theory. These are applied to three topics in machine learning, including representation learning, nearest-neighbor methods, and universal information processing, where two problems are studied from each topic.