Score-based diffusion models have achieved remarkable empirical performance in the field of machine learning and artificial intelligence for their ability to generate high-quality new data instances from complex distributions. Improving our understanding of diffusion models, including mainly convergence analysis for such models, has attracted a lot of interests. Despite a lot of theoretical attempts, there still exists significant gap between theory and practice. Towards to close this gap, we establish an iteration complexity at the order of $d^{1/3}\varepsilon^{-2/3}$, which is better than $d^{5/12}\varepsilon^{-1}$, the best known complexity achieved before our work. This convergence analysis is based on a randomized midpoint method, which is first proposed for log-concave sampling (Shen & Lee, 2019), and then extended to diffusion models by Gupta et al. (2024). Our theory accommodates $\varepsilon$-accurate score estimates, and does not require log-concavity on the target distribution. Moreover, the algorithm can also be parallelized to run in only $O(\log^2(d/\varepsilon))$ parallel rounds in a similar way to prior works.

Diffusion models have emerged as a powerful framework for generative modeling, with guidance techniques playing a crucial role in enhancing sample quality. Despite their empirical success, a comprehensive theoretical understanding of the guidance effect remains limited. Existing studies only focus on case studies, where the distribution conditioned on each class is either isotropic Gaussian or supported on a one-dimensional interval with some extra conditions. How to analyze the guidance effect beyond these case studies remains an open question. Towards closing this gap, we make an attempt to analyze diffusion guidance under general data distributions. Rather than demonstrating uniform sample quality improvement, which does not hold in some distributions, we prove that guidance can improve the whole sample quality, in the sense that the ratio of bad samples (measured by the classifier probability) decreases in the presence of guidance. This aligns with the motivation of introducing guidance.

The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in a shared dynamic environment. Existing theoretical studies in this area suffer from at least two of the following obstacles: memory inefficiency, the heavy dependence of sample complexity on the long horizon and the large state space, the high computational complexity, non-Markov policy, non-Nash policy, and high burn-in cost. In this work, we take a step towards settling this problem by designing a model-free self-play algorithm \emph{Memory-Efficient Nash Q-Learning (ME-Nash-QL)} for two-player zero-sum Markov games, which is a specific setting of MARL. We prove that ME-Nash-QL can output an $\varepsilon$-approximate Nash policy with remarkable space complexity $O(SABH)$, sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, and computational complexity $O(T\mathrm{poly}(AB))$, where $S$ is the number of states, $\{A, B\}$ is the number of actions for the two players, $H$ is the horizon length, and $T$ is the number of samples. Notably, our approach outperforms in terms of space complexity compared to existing algorithms for tabular cases. It achieves the lowest computational complexity while preserving Markov policies, setting a new standard. Furthermore, our algorithm outputs a Nash policy and achieves the best sample complexity compared with the existing guarantee for long horizons, i.e. when $\min \\{ A, B \\} \ll H^2$. Our algorithm also achieves the best burn-in cost $O(SAB\,\mathrm{poly}(H))$, whereas previous algorithms need at least $O(S^3 AB\,\mathrm{poly}(H))$ to attain the same level of sample complexity with ours.

We consider the problem of distributed principal component analysis (PCA) where the data samples are dispersed across different agents. Despite the rich literature on this problem under various specific settings, there is still a lack of efficient algorithms that are amenable to decentralized and asynchronous implementations. In this paper, we extend the incremental aggregated gradient (IAG) method in convex optimization to the nonconvex PCA problems based on an Riemannian gradient-type method named IARG-PCA. The IARG-PCA method admits low per-iteration computational and communication cost and can be readily implemented in a decentralized and asynchronous manner. Moreover, we show that the IARG-PCA method converges linearly to the leading eigenvector of the sample covariance of the whole dataset with a constant step size. The iteration complexity coincides with the best-known result of the IAG method in terms of the linear dependence on the number of agents. Meanwhile, the communication complexity is much lower than the state-of-the-art decentralized PCA algorithms if the eigengap of the sample covariance is moderate. Numerical experiments on synthetic and real datasets show that our IARG-PCA method exhibits substantially lower communication cost and comparable computational cost compared with other existing algorithms.

Change-point detection (CPD) from streaming data is a fundamental problem in statistical signal processing and has wide applications in wireless sensor networks and the Internet of Things (IoT), such as environmental monitoring and physical activity detection. In various detection schemes, decentralized detection without fusion center is becoming increasingly popular for IoT applications since it enjoys the benefit of strong robustness and security. However, it faces the big challenge of high energy consumption. In this work, we propose an energy-efficient decentralized CPD algorithm called request-response and censoring-based cumulative sum. Specifically, we design a novel communication strategy based on request-response and censoring scheme, which could help the sensors extract useful information from the neighbor sets with a low amount of communication. Furthermore, to provide a guideline on selecting the parameters involved in our algorithm, we theoretically analyze the performance of the proposed algorithm under a simplification for the most interesting cases, in terms of two standard criteria average running length (ARL) and expected detection delay (EDD). Numerical simulations are conducted to verify the effectiveness of the proposed algorithm. Moreover, we test the feasibility of the proposed algorithm in the physical activity CPD task. The experimental results on the real-world data set demonstrate its high energy efficiency and small detection delay.

Detecting subspace signals is an important problem in radar and sonar signal processing, hyperspectral image processing, wireless communication, and other fields. Among these problems, a typical scenario is that one needs to detect a signal lying in a given target subspace, contaminated by interferences that also lie in some subspaces. Most classical works in this aspect treated only the cases where the interfering subspace is known a priori, but in practice the interfering subspace is often unknown. Recently, the arise of Volume Correlation Detector allows to detect subspace signals when the interfering subspace is unknown, but it does not work well in the case where the target subspace overlaps with the interfering subspace. In this paper, we propose a new detector, called Principal Angle Detector (PAD), based on principal angles between subspaces. Our new detector is robust against overlapping target subspace and interfering subspace, and against some other model mismatches. To provide a correct and reasonable theoretical result, we borrow from the literature of numerical linear algebra the tool of affine-invariant covariance estimation, which could be of potential use for related problems in signal processing.

Millimeter wave (mmWave) communication is a promising technology for future outdoor cellular systems. However, the abrupt channel change is more prone to occur over mmWave band compared to conventional frequencies, which will degrade the system performance. Hence, it is important to detect the channel change accurately for preparation of re-estimating the channel state information (CSI). In this paper, we attempt to solve the channel change problem from the perspective of change-point detection. By exploiting the low-rank characteristic of mmWave massive multiple-input multiple-output (MIMO) channel, the received signals can be viewed as data points in a subspace superimposed with noises. Then a cumulative sum (CUSUM)-based subspace change-point detection algorithm is designed to detect the mmWave channel change. The method can work without the aid of pilot signals and is of low computational complexity and memory requirement. Results are provided to validate the satisfactory of the proposed method.

Hyperspectral images (HSIs) clustering problem is a challenge and valuable task due to its inherent complexity and abundant spectral information. Sparse subspace clustering (SSC) and SSC-based methods are widely used in this problem and demonstrate excellent performance. However, considering that HSIs are usually of high dimension, these methods have expensive computing complexity because of the usage of SSC. To solve this problem, we propose a novel approach called SuperPixel and Angle-based HyperSpectral Image Clustering (SPAHSIC). It first extracts the local spectral and spatial information between pixels by superpixel segmentation, and then applies spectral clustering on the similarity matrix built based on subspace principal angles. We implement experiments on real datasets and get a high accuracy, which indicates the effectiveness of our algorithm.

Phase retrieval has been an attractive problem, and many algorithms have been proposed. Randomized Kaczmarz method is a fast iterative method with good performance in both convergence rate and computational cost with theoretical analysis. However, they all assume that the iteratively updated variables and the original data are independent, which is not true in reality. In this paper, we study for the first time the convergence analysis of this method in the real case, where only a finite number of measurements are available. Specifically, we theoretically prove the linear rate of convergence for the phase retrieval via randomized Kaczmarz algorithm without independence assumption.

In this paper, we propose using the auricle - the visible part of the ear - as a means of expressive output to extend body language to convey emotional states. With an initial exploratory study, we provide an initial set of dynamic and static auricular postures. Using these results, we examined the relationship between emotions and auricular postures, noting that dynamic postures involving stretching the top helix in fast (e.g., 2Hz) and slow speeds (1Hz) conveyed intense and mild pleasantness while static postures involving bending the side or top helix towards the center of the ear were associated with intense and mild unpleasantness. Based on the results, we developed a prototype (called Orrechio) with miniature motors, custom-made robotic arms and other electronic components. A preliminary user evaluation showed that participants feel more comfortable using expressive auricular postures with people they are familiar with, and that it is a welcome addition to the vocabulary of human body language.