Despite empirical risk minimization (ERM) is widely applied in the machine learning community, its performance is limited on data with spurious correlation or subpopulation that is introduced by hidden attributes. Existing literature proposed techniques to maximize group-balanced or worst-group accuracy when such correlation presents, yet, at the cost of lower average accuracy. In addition, many existing works conduct surveys on different subpopulation methods without revealing the inherent connection between these methods, which could hinder the technology advancement in this area. In this paper, we identify important sampling as a simple yet powerful tool for solving the subpopulation problem. On the theory side, we provide a new systematic formulation of the subpopulation problem, and explicitly identify the assumptions that are not clearly stated in the existing works. This helps to uncover the cause of the dropped average accuracy. We provide the first theoretical discussion on the connections of existing methods, revealing the core components that make them different. On the application side, we demonstrate a single estimator is enough to solve the subpopulation problem. In particular, we introduce the estimator in both attribute-known and -unknown scenarios in the subpopulation setup, offering flexibility in practical use cases. And empirically, we achieve state-of-the-art performance on commonly used benchmark datasets.

Diffusion and flow matching models have recently been used to solve various linear inverse problems in image restoration, such as super-resolution and inpainting. Using a pre-trained diffusion or flow-matching model as a prior, most existing methods modify the reverse-time sampling process by incorporating the likelihood information from the measurement. However, they struggle in challenging scenarios, such as high measurement noise or severe ill-posedness. In this paper, we propose Flow with Interpolant Guidance (FIG), an algorithm where reverse-time sampling is efficiently guided with measurement interpolants through theoretically justified schemes. Experimentally, we demonstrate that FIG efficiently produces highly competitive results on a variety of linear image reconstruction tasks on natural image datasets, especially for challenging tasks. Our code is available at: https://riccizz.github.io/FIG/.

We formulate a hierarchical rectified flow to model data distributions. It hierarchically couples multiple ordinary differential equations (ODEs) and defines a time-differentiable stochastic process that generates a data distribution from a known source distribution. Each ODE resembles the ODE that is solved in a classic rectified flow, but differs in its domain, i.e., location, velocity, acceleration, etc. Unlike the classic rectified flow formulation, which formulates a single ODE in the location domain and only captures the expected velocity field (sufficient to capture a multi-modal data distribution), the hierarchical rectified flow formulation models the multi-modal random velocity field, acceleration field, etc., in their entirety. This more faithful modeling of the random velocity field enables integration paths to intersect when the underlying ODE is solved during data generation. Intersecting paths in turn lead to integration trajectories that are more straight than those obtained in the classic rectified flow formulation, where integration paths cannot intersect. This leads to modeling of data distributions with fewer neural function evaluations. We empirically verify this on synthetic 1D and 2D data as well as MNIST, CIFAR-10, and ImageNet-32 data. Our code is available at: https://riccizz.github.io/HRF/.

Model-X knockoff has garnered significant attention among various feature selection methods due to its guarantees for controlling the false discovery rate (FDR). Since its introduction in parametric design, knockoff techniques have evolved to handle arbitrary data distributions using deep learning-based generative models. However, we have observed limitations in the current implementations of the deep Model-X knockoff framework. Notably, the "swap property" that knockoffs require often faces challenges at the sample level, resulting in diminished selection power. To address these issues, we develop "Deep Dependency Regularized Knockoff (DeepDRK)," a distribution-free deep learning method that effectively balances FDR and power. In DeepDRK, we introduce a novel formulation of the knockoff model as a learning problem under multi-source adversarial attacks. By employing an innovative perturbation technique, we achieve lower FDR and higher power. Our model outperforms existing benchmarks across synthetic, semi-synthetic, and real-world datasets, particularly when sample sizes are small and data distributions are non-Gaussian.

Single particle reconstruction (SPR) in cryo-electron microscopy (cryo-EM) is a prominent imaging method that recovers the 3D shape of a biomolecule, given a large number of its noisy projections from random and unknown views. Recently, CryoGAN [1] cast SPR as an unsupervised distribution matching problem and solved it via a Wasserstein generative adversarial network (WGAN) framework. The approach bypasses the estimation of the projection parameters. The reconstruction criterion in CryoGAN is Wasserstein-1 distance. Despite the desirable properties of Wasserstein distances (WD) such as continuity and almost everywhere differentiability, they are difficult to compute and require careful tuning for a stable training. Sliced Wasserstein distance (SWD), on the other hand, has shown desirable training stability and ease to compute. Therefore, we propose to re-place Wasserstein-1 distance with SWD in the CryoGAN framework, hence the name CryoSWD. In low noise regimes, we show how CryoSWD eliminates the need to have a discriminator which is crucial in CryoGAN. However, coupling CryoSWD with a discriminator boosts its performance, especially in high noise settings. While performing as good as CryoGAN, CryoSWD does not require a gradient penalty term for stabilizing the training and imposing Lipschitz continuity of the discriminator.

Abstract. Unknown view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. A line of work starting with Kam (1980) employs the method of moments with rotation-invariant Fourier features to solve UVT in the frequency domain, assuming that the orientations are uniformly distributed. This line of work includes the recent orthogonal matrix retrieval (OMR) approaches based on matrix factorization, which, while elegant, either require side information about the density that is not available or fail to be sufficiently robust. For OMR to break free from those restrictions, we propose to jointly recover the density map and the orthogonal matrices by requiring that they be mutually consistent. We regularize the resulting nonconvex optimization problem by a denoised reference projection and a nonnegativity constraint. This is enabled by the new closed-form expressions for spatial autocorrelation features. Further, we design an easy-to-compute initial density map which effectively mitigates the nonconvexity of the reconstruction problem. Experimental results show that the proposed OMR with spatial consensus is more robust and performs significantly better than the previous state-of-the-art OMR approach in the typical low signal-to-noise-ratio scenario of 3D UVT.

The computation required for a switching Kalman Filter (SKF) increases exponentially with the number of system operation modes. In this paper, a computationally tractable graph representation is proposed for a switching linear dynamic system (SLDS) along with the solution of a minimum-sum optimization problem for clustering to reduce the switching mode cardinality offline, before collecting measurements. It is shown that upon perfect mode detection, the induced error caused by mode clustering can be quantified exactly in terms of the dissimilarity measures in the proposed graph structure. Numerical results verify that clustering based on the proposed framework effectively reduces model complexity given uncertain mode detection and that the induced error can be well approximated if the underlying assumptions are satisfied.

Aiming at convex optimization under structural constraints, this work introduces and analyzes a variant of the Frank Wolfe (FW) algorithm termed ExtraFW. The distinct feature of ExtraFW is the pair of gradients leveraged per iteration, thanks to which the decision variable is updated in a prediction-correction (PC) format. Relying on no problem dependent parameters in the step sizes, the convergence rate of ExtraFW for general convex problems is shown to be ${\cal O}(\frac{1}{k})$, which is optimal in the sense of matching the lower bound on the number of solved FW subproblems. However, the merit of ExtraFW is its faster rate ${\cal O}\big(\frac{1}{k^2} \big)$ on a class of machine learning problems. Compared with other parameter-free FW variants that have faster rates on the same problems, ExtraFW has improved rates and fine-grained analysis thanks to its PC update. Numerical tests on binary classification with different sparsity-promoting constraints demonstrate that the empirical performance of ExtraFW is significantly better than FW, and even faster than Nesterov's accelerated gradient on certain datasets. For matrix completion, ExtraFW enjoys smaller optimality gap, and lower rank than FW.

This paper studies the adversarial graphical contextual bandits, a variant of adversarial multi-armed bandits that leverage two categories of the most common side information: contexts and side observations. In this setting, a learning agent repeatedly chooses from a set of K actions after being presented with a d-dimensional context vector. The agent not only incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures, which are encoded as a series of feedback graphs. This setting models a variety of applications in social networks, where both contexts and graph-structured side observations are available. Two efficient algorithms are developed based on EXP3. Under mild conditions, our analysis shows that for undirected feedback graphs the first algorithm, EXP3-LGC-U, achieves a sub-linear regret with respect to the time horizon and the average independence number of the feedback graphs. A slightly weaker result is presented for the directed graph setting as well. The second algorithm, EXP3-LGC-IX, is developed for a special class of problems, for which the regret is the same for both directed as well as undirected feedback graphs. Numerical tests corroborate the efficiency of proposed algorithms.

Cascading bandit (CB) is a popular model for web search and online advertising. However, the stationary CB model may be too simple to cope with real-world problems, where user preferences may change over time. Considering piecewise-stationary environments, two efficient algorithms, GLRT-CascadeUCB and GLRT-CascadeKL-UCB, are developed. Comparing with existing works, the proposed algorithms: i) are free of change-point-dependent information for choosing parameters; ii) have fewer tuning parameters; iii) improve regret upper bounds. We also show that the proposed algorithms are optimal up to logarithm terms by deriving a minimax lower bound $\Omega (\sqrt {NLT} )$ for piecewise-stationary CB. The efficiency of the proposed algorithms is validated through numerical tests on a real-world benchmark dataset.

Multi-segment reconstruction (MSR) is the problem of estimating a signal given noisy partial observations. Here each observation corresponds to a randomly located segment of the signal. While previous works address this problem using template or moment-matching, in this paper we address MSR from an unsupervised adversarial learning standpoint, named MSR-GAN. We formulate MSR as a distribution matching problem where the goal is to recover the signal and the probability distribution of the segments such that the distribution of the generated measurements following a known forward model is close to the real observations. This is achieved once a min-max optimization involving a generator-discriminator pair is solved. MSR-GAN is mainly inspired by CryoGAN [1]. However, in MSR-GAN we no longer assume the probability distribution of the latent variables, i.e. segment locations, is given and seek to recover it alongside the unknown signal. For this purpose, we show that the loss at the generator side originally is non-differentiable with respect to the segment distribution. Thus, we propose to approximate it using Gumbel-Softmax reparametrization trick. Our proposed solution is generalizable to a wide range of inverse problems. Our simulation results and comparison with various baselines verify the potential of our approach in different settings.

Cryo-electron microscopy (EM) single particle reconstruction is a general technique for 3D structure determination of macromolecules. However, because the images are taken at low electron dose, it is extremely hard to visualize the individual particle with low contrast and high noise level. In this paper, we propose a novel framework for cryo-EM single particle image denoising, which incorporates the recently developed multi-frequency vector diffusion maps [1] for improving the identification and alignment of images with similar viewing directions. In addition, we propose a novel filtering scheme combining graph signal processing and truncated Fourier-Bessel expansion of the projection images. Through both simulated and publicly available real data, we demonstrate that our proposed method is efficient and robust to noise compared with the state-of-the-art cryo-EM 2D class averaging algorithms.

The recent growth of web video sharing platforms has increased the demand for systems that can efficiently browse, retrieve and summarize video content. Query-aware multi-video summarization is a promising technique that caters to this demand. In this work, we introduce a novel Query-Aware Hierarchical Pointer Network for Multi-Video Summarization, termed DeepQAMVS, that jointly optimizes multiple criteria: (1) conciseness, (2) representativeness of important query-relevant events and (3) chronological soundness. We design a hierarchical attention model that factorizes over three distributions, each collecting evidence from a different modality, followed by a pointer network that selects frames to include in the summary. DeepQAMVS is trained with reinforcement learning, incorporating rewards that capture representativeness, diversity, query-adaptability and temporal coherence. We achieve state-of-the-art results on the MVS1K dataset, with inference time scaling linearly with the number of input video frames.

Switching Kalman Filters (SKF) are well known for solving switching linear dynamic system (SLDS), i.e., piece-wise linear estimation problems. Practical SKFs are heuristic, approximate filters and require more computational resources than a single-mode Kalman filter (KF). On the other hand, applying a single-mode mismatched KF to an SLDS results in erroneous estimation. This paper quantifies the average error an SKF can eliminate compared to a mismatched, single-mode KF before collecting measurements. Derivations of the first and second moments of the estimators errors are provided and compared. One can use these derivations to quantify the average performance of filters beforehand and decide which filter to run in operation to have the best performance in terms of estimation error and computation complexity. We further provide simulation results that verify our mathematical derivations.

In this paper, we study the problem of reconstructing a 3D point source model from a set of 2D projections at unknown view angles. Our method obviates the need to recover the projection angles by extracting a set of rotation-invariant features from the noisy projection data. From the features, we reconstruct the density map through a constrained nonconvex optimization. We show that the features have geometric interpretations in the form of radial and pairwise distances of the model. We further perform an ablation study to examine the effect of various parameters on the quality of the estimated features from the projection data. Our results showcase the potential of the proposed method in reconstructing point source models in various noise regimes.

Single-particle cryo-electron microscopy (cryo-EM) reconstructs the three-dimensional (3D) structure of biomolecules from a large set of 2D projection images with random and unknown orientations. A crucial step in the single-particle cryo-EM pipeline is 3D refinement, which resolves a highresolution 3D structure from an initial approximate volume by refining the estimation of the orientation of each projection. In this work, we propose a new approach that refines the projection angles on the continuum. We formulate the optimization problem over the density map and the orientations jointly. The density map is updated using the efficient alternating-direction method of multipliers, while the orientations are updated through a semicoordinate- wise gradient descent for which we provide an explicit derivation of the gradient. Our method eliminates the requirement for a fine discretization of the orientation space and does away with the classical but computationally expensive templatematching step. Numerical results demonstrate the feasibility and performance of our approach compared to several baselines.

In photon-limited imaging, the pixel intensities are affected by photon count noise. Many applications require an accurate estimation of the covariance of the underlying 2-D clean images. For example, in X-ray free electron laser (XFEL) single molecule imaging, the covariance matrix of 2-D diffraction images is used to reconstruct the 3-D molecular structure. Accurate estimation of the covariance from low-photon-count images must take into account that pixel intensities are Poisson distributed, hence the classical sample covariance estimator is highly biased. Moreover, in single molecule imaging, including in-plane rotated copies of all images could further improve the accuracy of covariance estimation. In this paper we introduce an efficient and accurate algorithm for covariance matrix estimation of count noise 2-D images, including their uniform planar rotations and possibly reflections. Our procedure, steerable ePCA, combines in a novel way two recently introduced innovations. The first is a methodology for principal component analysis (PCA) for Poisson distributions, and more generally, exponential family distributions, called ePCA. The second is steerable PCA, a fast and accurate procedure for including all planar rotations when performing PCA. The resulting principal components are invariant to the rotation and reflection of the input images. We demonstrate the efficiency and accuracy of steerable ePCA in numerical experiments involving simulated XFEL datasets and rotated face images from Yale Face Database B.

Generative adversarial nets (GANs) and variational auto-encoders have significantly improved our distribution modeling capabilities, showing promise for dataset augmentation, image-to-image translation and feature learning. However, to model high-dimensional distributions, sequential training and stacked architectures are common, increasing the number of tunable hyper-parameters as well as the training time. Nonetheless, the sample complexity of the distance metrics remains one of the factors affecting GAN training. We first show that the recently proposed sliced Wasserstein distance has compelling sample complexity properties when compared to the Wasserstein distance. To further improve the sliced Wasserstein distance we then analyze its `projection complexity' and develop the max-sliced Wasserstein distance which enjoys compelling sample complexity while reducing projection complexity, albeit necessitating a max estimation. We finally illustrate that the proposed distance trains GANs on high-dimensional images up to a resolution of 256x256 easily.

Denoising of time domain data is a crucial task for many applications such as communication, translation, virtual assistants etc. For this task, a combination of a recurrent neural net (RNNs) with a Denoising Auto-Encoder (DAEs) has shown promising results. However, this combined model is challenged when operating with low signal-to-noise ratio (SNR) data embedded in non-Gaussian and non-stationary noise. To address this issue, we design a novel model, referred to as `Enhanced Deep Recurrent Denoising Auto-Encoder' (EDR-DAE), that incorporates a signal amplifier layer, and applies curriculum learning by first denoising high SNR signals, before gradually decreasing the SNR until the signals become noise dominated. We showcase the performance of EDR-DAE using time-series data that describes gravitational waves embedded in very noisy backgrounds. In addition, we show that EDRDAE can accurately denoise signals whose topology is significantly more complex than those used for training, demonstrating that our model generalizes to new classes of gravitational waves that are beyond the scope of established denoising algorithms.

In this paper, we study a 2D tomography problem for point source models with random unknown view angles. Rather than recovering the projection angles, we reconstruct the model through a set of rotation-invariant features that are estimated from the projection data. For a point source model, we show that these features reveal geometric information about the model such as the radial and pairwise distances. This establishes a connection between unknown view tomography and unassigned distance geometry problem (uDGP). We propose new methods to extract the distances and approximate the pairwise distance distribution of the underlying points. We then use the recovered distribution to estimate the locations of the points through constrained non-convex optimization. Our simulation results show that our point source reconstruction pipeline is robust to noise and outperforms the regularized expectation maximization (EM) baseline.

We consider a problem that recovers a 2-D object and the underlying view angle distribution from its noisy projection tilt series taken at unknown view angles. Traditional approaches rely on the estimation of the view angles of the projections, which do not scale well with the sample size and are sensitive to noise. We introduce a new approach using the moment features to simultaneously recover the underlying object and the distribution of view angles. This problem is formulated as constrained nonlinear least squares in terms of the truncated Fourier-Bessel expansion coefficients of the object and is solved by a new alternating direction method of multipliers (ADMM)-based algorithm. Our numerical experiments show that the new approach outperforms the expectation maximization (EM)-based maximum marginalized likelihood estimation in efficiency and accuracy. Furthermore, the hybrid method that uses EM to refine ADMM solution achieves the best performance.

We introduce multi-frequency vector diffusion maps (MFVDM), a new framework for organizing and analyzing high dimensional data sets. The new method is a mathematical and algorithmic generalization of vector diffusion maps (VDM) and other non-linear dimensionality reduction methods. The idea of MFVDM is to incorporates multiple unitary irreducible representations of the alignment group which introduces robustness to noise. We illustrate the efficacy of MFVDM on synthetic and cryo-EM image datasets, achieving better nearest neighbors search and alignment estimation than other baselines as VDM and diffusion maps (DM), especially on extremely noisy data.

We propose a novel formulation for phase synchronization—the statistical problem of jointly estimating alignment angles from noisy pairwise comparisons—as a nonconvex optimization problem that enforces consistency among the pairwise comparisons in multiple frequency channels. Inspired by harmonic retrieval in signal processing, we develop a simple yet efficient two-stage algorithm that leverages the multi-frequency information. We demonstrate in theory and practice that the proposed algorithm significantly outperforms state-of-the-art phase synchronization algorithms, at a mild computational costs incurred by using the extra frequency channels. We also extend our algorithmic framework to general synchronization problems over compact Lie groups.

We introduce a novel co-learning paradigm for manifolds naturally admitting an action of a transformation group $\mathcal{G}$, motivated by recent developments on learning a manifold from attached fibre bundle structures. We utilize a representation theoretic mechanism that canonically associates multiple independent vector bundles over a common base manifold, which provides multiple views for the geometry of the underlying manifold. The consistency across these fibre bundles provide a common base for performing unsupervised manifold co-learning through the redundancy created artificially across irreducible representations of the transformation group. We demonstrate the efficacy of our proposed algorithmic paradigm through drastically improved robust nearest neighbor identification in cryo-electron microscopy image analysis and the clustering accuracy in community detection.

In this paper, we address the problem of estimating a noisy, incomplete time series of a dynamical system with an unknown state evolution. The technique that we will present is transformed spiked covariance completion (TSCC), a matrix completion method for signal estimation. This method exploits the spiked covariance model of the underlying signal to develop a linear estimator that is resilient to noise. We discuss the conditions in the signal model for which this technique is applicable and compare this method against other state-of-the-art time series estimation techniques with a numerical example. Our algorithm gives estimates that are more robust to noise in comparison to the current state-of-the-art techniques that address this same estimation problem.

Multi-segment reconstruction (MSR) problem consists of recovering a signal from noisy segments with unknown positions of the observation windows. One example arises in DNA sequence assembly, which is typically solved by matching short reads to form longer sequences. Instead of trying to locate the segment within the sequence through pair-wise matching, we propose a new approach that uses shift-invariant features to estimate both the underlying signal and the distribution of the positions of the segments. Using the invariant features, we formulate the problem as a constrained nonlinear least-squares. The non-convexity of the problem leads to its sensitivity to the initialization. However, with clean data, we show empirically that for longer segment lengths, random initialization achieves exact recovery. Furthermore, we compare the performance of our approach to the results of expectation maximization and demonstrate that the new approach is robust to noise and computationally more efficient.

We focus on an alignment-free method to estimate the underlying signal from a large number of noisy randomly shifted observations. Specifically, we estimate the mean, power spectrum, and bispectrum of the signal from the observations. Since the bispectrum contains the phase information of the signal, reliable algorithms for bispectrum inversion are useful in many applications. We propose a new algorithm using spectral decomposition of the bispectrum phase matrix for this task. For clean signals, we show that the eigenvectors of the bispectrum phase matrix correspond to the true phases of the signal and its shifted copies. In addition, the spectral method is robust to noise. It can be used as a stable and efficient initialization technique for local nonconvex optimization for bispectrum inversion.

The cryo-electron microscopy (cryo-EM) reconstruction problem is to find the three-dimensional structure of a macromolecule given noisy versions of its two-dimensional projection images at unknown random directions. We introduce a new algorithm for identifying noisy cryo-EM images of nearby viewing angles. This identification is an important first step in three-dimensional structure determination of macromolecules from cryo-EM, because once identified, these images can be rotationally aligned and averaged to produce "class averages" of better quality. The main advantage of our algorithm is its extreme robustness to noise. The algorithm is also very efficient in terms of running time and memory requirements, because it is based on the computation of the top few eigenvectors of a specially designed sparse Hermitian matrix. These advantages are demonstrated in numerous numerical experiments.