publications | Jongha Jon Ryu

preprints

2024

arXiv

Improved Evidential Deep Learning via a Mixture of Dirichlet Distributions

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

2024

arXiv:2402.06160

Abs arXiv

This paper explores a modern predictive uncertainty estimation approach, called evidential 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 strong empirical performance, recent studies by Bengs et al. identify a fundamental pitfall of the existing methods: the learned epistemic uncertainty may not vanish even in the infinite-sample limit. We corroborate the observation by providing a unifying view of a class of widely used objectives from the literature. Our analysis reveals that the EDL methods essentially train a meta distribution by minimizing a certain divergence measure between the distribution and a sample-size-independent target distribution, resulting in spurious epistemic uncertainty. Grounded in theoretical principles, we propose learning a consistent target distribution by modeling it with a mixture of Dirichlet distributions and learning via variational inference. Afterward, a final meta distribution model distills the learned uncertainty from the target model. Experimental results across various uncertainty-based downstream tasks demonstrate the superiority of our proposed method, and illustrate the practical implications arising from the consistency and inconsistency of learned epistemic uncertainty.

2022

arXiv

One-Nearest-Neighbor Search Is All You Need for Minimax Optimal Regression and Classification

J. Jon Ryu , and Young-Han Kim

2022

arXiv:2202.02464

Abs arXiv Code

Recently, Qiao, Duan, and Cheng (2019) proposed a distributed nearest-neighbor classification method, in which a massive dataset is split into smaller groups, each processed with a k-nearest-neighbor classifier, and the final class label is predicted by a majority vote among these groupwise class labels. This paper shows that the distributed algorithm with k=1 over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions, for both regression and classification problems. Roughly speaking, distributed 1-nearest-neighbor rules with M groups has a performance comparable to standard Θ(M)-nearest-neighbor rules. In the analysis, alternative rules with a refined aggregation method are proposed and shown to attain exact minimax optimal rates.
arXiv

On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

J. Jon Ryu , and Alankrita Bhatt

2022

Submitted to IEEE Trans. Inf. Theory (minor revision).
arXiv:2207.12382

Abs arXiv 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.
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

Under revision; “Reject and resubmit” from IEEE Trans. Pattern Anal. Mach. Intell..
arXiv:1905.10945v2
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

2022

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

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

arXiv:2302.08077
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.
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) , February 2024

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

Abs arXiv 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.
ICML

Gambling-Based Confidence Sequences for Bounded Random Vectors

J. Jon Ryu , and Gregory W. Wornell

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

arXiv:2402.03683

Abs arXiv Code

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.

2023

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

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

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) , April 2022

Abs arXiv 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

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) , April 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

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) , April 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

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) , April 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.
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) , April 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.
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) , April 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

arXiv

An Information-Theoretic Proof of Kac–Bernstein Theorem

J. Jon Ryu , and Young-Han Kim

April 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

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

April 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

From Information Theory to Machine Learning Algorithms: A Few Vignettes

Jongha Jon Ryu

University of California, San Diego , September 2022

PhD thesis.

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.