Search

Reinforcement learning with multiple, potentially conflicting objectives is pervasive in real-world applications, while this problem remains theoretically under-explored. This paper tackles the multi-objective reinforcement learning (MORL) problem and introduces an innovative actor-critic algorithm named MOAC which finds a policy by iteratively making trade-offs among conflicting reward signals. Notably, we provide the first analysis of finite-time Pareto-stationary convergence and corresponding sample complexity in both discounted and average reward settings. Our approach has two salient features: (a) MOAC mitigates the cumulative estimation bias resulting from finding an optimal common gradient descent direction out of stochastic samples. This enables provable convergence rate and sample complexity guarantees independent of the number of objectives; (b) With proper momentum coefficient, MOAC initializes the weights of individual policy gradients using samples from the environment, instead of manual initialization. This enhances the practicality and robustness of our algorithm. Finally, experiments conducted on a real-world dataset validate the effectiveness of our proposed method., Comment: Accepted in ICML 2024

Many problems encountered in science and engineering can be formulated as estimating a low-rank object (e.g., matrices and tensors) from incomplete, and possibly corrupted, linear measurements. Through the lens of matrix and tensor factorization, one of the most popular approaches is to employ simple iterative algorithms such as gradient descent (GD) to recover the low-rank factors directly, which allow for small memory and computation footprints. However, the convergence rate of GD depends linearly, and sometimes even quadratically, on the condition number of the low-rank object, and therefore, GD slows down painstakingly when the problem is ill-conditioned. This chapter introduces a new algorithmic approach, dubbed scaled gradient descent (ScaledGD), that provably converges linearly at a constant rate independent of the condition number of the low-rank object, while maintaining the low per-iteration cost of gradient descent for a variety of tasks including sensing, robust principal component analysis and completion. In addition, ScaledGD continues to admit fast global convergence to the minimax-optimal solution, again almost independent of the condition number, from a small random initialization when the rank is over-specified in the presence of Gaussian noise. In total, ScaledGD highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the symmetry in low-rank factorization without hurting generalization., Comment: Book chapter for "Explorations in the Mathematics of Data Science - The Inaugural Volume of the Center for Approximation and Mathematical Data Analytics". arXiv admin note: text overlap with arXiv:2104.14526

Optical microscopy image plays an important role in scientific research through the direct visualization of the nanoworld, where the imaging mechanism is described as the convolution of the point spread function (PSF) and emitters. Based on a priori knowledge of the PSF or equivalent PSF, it is possible to achieve more precise exploration of the nanoworld. However, it is an outstanding challenge to directly extract the PSF from microscopy images. Here, with the help of self-supervised learning, we propose a physics-informed masked autoencoder (PiMAE) that enables a learnable estimation of the PSF and emitters directly from the raw microscopy images. We demonstrate our method in synthetic data and real-world experiments with significant accuracy and noise robustness. PiMAE outperforms DeepSTORM and the Richardson-Lucy algorithm in synthetic data tasks with an average improvement of 19.6\% and 50.7\% (35 tasks), respectively, as measured by the normalized root mean square error (NRMSE) metric. This is achieved without prior knowledge of the PSF, in contrast to the supervised approach used by DeepSTORM and the known PSF assumption in the Richardson-Lucy algorithm. Our method, PiMAE, provides a feasible scheme for achieving the hidden imaging mechanism in optical microscopy and has the potential to learn hidden mechanisms in many more systems.

Hydrostatic pressure has been commonly applied to tune broadband light emissions from self-trapped excitons (STE) in perovskites for producing white light and study of basic electron-phonon interactions. However, a general theory is still lacking to understand pressure-driven evolution of STE emissions. In this work we first identify a theoretical model that predicts the effect of hydrostatic pressure on STE emission spectrum, we then report the observation of extremely broadband photoluminescence emission and its wide pressure spectral tuning in 2D indirect bandgap CsPb2Br5 crystals. An excellent agreement is found between the theory and experiment on the peculiar experimental observation of STE emission with a nearly constant spectral bandwidth but linearly increasing energy with pressure below 2 GPa. Further analysis by the theory and experiment under higher pressure reveals that two types of STE are involved and respond differently to external pressure. We subsequently survey published STE emissions and discovered that most of them show a spectral blue-shift under pressure, as predicted by the theory. The identification of an appropriate theoretical model and its application to STE emission through the coordinate configuration diagram paves the way for engineering the STE emission and basic understanding of electron-phonon interaction.

An increasing number of data science and machine learning problems rely on computation with tensors, which better capture the multi-way relationships and interactions of data than matrices. When tapping into this critical advantage, a key challenge is to develop computationally efficient and provably correct algorithms for extracting useful information from tensor data that are simultaneously robust to corruptions and ill-conditioning. This paper tackles tensor robust principal component analysis (RPCA), which aims to recover a low-rank tensor from its observations contaminated by sparse corruptions, under the Tucker decomposition. To minimize the computation and memory footprints, we propose to directly recover the low-dimensional tensor factors -- starting from a tailored spectral initialization -- via scaled gradient descent (ScaledGD), coupled with an iteration-varying thresholding operation to adaptively remove the impact of corruptions. Theoretically, we establish that the proposed algorithm converges linearly to the true low-rank tensor at a constant rate that is independent with its condition number, as long as the level of corruptions is not too large. Empirically, we demonstrate that the proposed algorithm achieves better and more scalable performance than state-of-the-art matrix and tensor RPCA algorithms through synthetic experiments and real-world applications.

Despite the unsettled mechanism of electricity generation from the continuous flow of liquids on a surface, the charge-discharge theory has been widely accepted for alternating current (AC) generation from a moving droplet. It has been recently extended to rationalize direct current (DC) generation across a droplet moving between two different materials. By designing a reconfigurable contact between a metal wire and a water droplet moving on graphene, we show that the charge-discharge theory cannot explain the reversal of current when water-metal interfaces switch from dynamic to static. All experiments can be described after we distinguish a dynamic from a static interface and generalize the photovoltaic-like effect to all dynamic junctions: excited electrons and holes in a moving interface will be separated and swept under the built-in electrical field, leading to a DC response. This generalized theory will lead to an understanding and the design of efficient electricity generation based on interfacial charge transfer.

Tensors, which provide a powerful and flexible model for representing multi-attribute data and multi-way interactions, play an indispensable role in modern data science across various fields in science and engineering. A fundamental task is to faithfully recover the tensor from highly incomplete measurements in a statistically and computationally efficient manner. Harnessing the low-rank structure of tensors in the Tucker decomposition, this paper develops a scaled gradient descent (ScaledGD) algorithm to directly recover the tensor factors with tailored spectral initializations, and shows that it provably converges at a linear rate independent of the condition number of the ground truth tensor for two canonical problems -- tensor completion and tensor regression -- as soon as the sample size is above the order of $n^{3/2}$ ignoring other parameter dependencies, where $n$ is the dimension of the tensor. This leads to an extremely scalable approach to low-rank tensor estimation compared with prior art, which suffers from at least one of the following drawbacks: extreme sensitivity to ill-conditioning, high per-iteration costs in terms of memory and computation, or poor sample complexity guarantees. To the best of our knowledge, ScaledGD is the first algorithm that achieves near-optimal statistical and computational complexities simultaneously for low-rank tensor completion with the Tucker decomposition. Our algorithm highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the underlying symmetry in low-rank tensor factorization., Comment: Accepted to Journal of Machine Learning Research

It is well accepted that an outward Marangoni convection from a low surface tension region will make the surface depressed. Here, we report that this established perception is only valid for thin liquid films. Using surface laser heating, we show that in deep liquids a laser beam actually pulls up the fluid above the free surface generating fountains with different shapes. Whereas with decreasing liquid depth a transition from fountain to indentation with fountain in-indentation is observed. Further, high-speed imaging reveals a transient surface process before steady elevation is formed, and this dynamic deformation is subsequently utilized to resonantly excite giant surface waves by a modulated laser beam. Computational fluid dynamics models reveal the underlying flow patterns and quantify the depth-dependent and time-resolved surface deformations. Our discoveries and techniques have upended the century-old perception and opened up a new regime of interdisciplinary research and applications of Marangoni-induced interface phenomena and optocapillary fluidic surfaces-the control of fluids with light., Comment: 13 pages, 4 figures

Many problems in data science can be treated as estimating a low-rank matrix from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss function, such as the residual sum of squares. While tremendous progresses have been made in recent years, the natural smooth formulation suffers from two sources of ill-conditioning, where the iteration complexity of gradient descent scales poorly both with the dimension as well as the condition number of the low-rank matrix. Moreover, the smooth formulation is not robust to corruptions. In this paper, we propose scaled subgradient methods to minimize a family of nonsmooth and nonconvex formulations -- in particular, the residual sum of absolute errors -- which is guaranteed to converge at a fast rate that is almost dimension-free and independent of the condition number, even in the presence of corruptions. We illustrate the effectiveness of our approach when the observation operator satisfies certain mixed-norm restricted isometry properties, and derive state-of-the-art performance guarantees for a variety of problems such as robust low-rank matrix sensing and quadratic sampling., Comment: Accepted to IEEE Transaction on Signal Processing

Low-rank matrix estimation is a canonical problem that finds numerous applications in signal processing, machine learning and imaging science. A popular approach in practice is to factorize the matrix into two compact low-rank factors, and then optimize these factors directly via simple iterative methods such as gradient descent and alternating minimization. Despite nonconvexity, recent literatures have shown that these simple heuristics in fact achieve linear convergence when initialized properly for a growing number of problems of interest. However, upon closer examination, existing approaches can still be computationally expensive especially for ill-conditioned matrices: the convergence rate of gradient descent depends linearly on the condition number of the low-rank matrix, while the per-iteration cost of alternating minimization is often prohibitive for large matrices. The goal of this paper is to set forth a competitive algorithmic approach dubbed Scaled Gradient Descent (ScaledGD) which can be viewed as pre-conditioned or diagonally-scaled gradient descent, where the pre-conditioners are adaptive and iteration-varying with a minimal computational overhead. With tailored variants for low-rank matrix sensing, robust principal component analysis and matrix completion, we theoretically show that ScaledGD achieves the best of both worlds: it converges linearly at a rate independent of the condition number of the low-rank matrix similar as alternating minimization, while maintaining the low per-iteration cost of gradient descent. Our analysis is also applicable to general loss functions that are restricted strongly convex and smooth over low-rank matrices. To the best of our knowledge, ScaledGD is the first algorithm that provably has such properties over a wide range of low-rank matrix estimation tasks., Comment: Accepted to Journal of Machine Learning Research

Despite successful modeling of graphene as a 0.34-nm thick optical film synthesized by exfoliation or chemical vapor deposition (CVD), graphene induced shift of surface plasmon resonance (SPR) of gold films has remained controversial. Here we report the resolution of this controversy by developing a clean CVD graphene transfer method and extending Maxwell-Garnet effective medium theory (EMT) to 2D materials. A SPR shift of 0.24 is obtained and it agrees well with 2D EMT in which wrinkled graphene is treated as a 3-nm graphene/air layered composite, in agreement with the average roughness measured by atomic force microscope. Because the anisotropic built-in boundary condition of 2D EMT is compatible with graphene's optical anisotropy, graphene can be modelled as a film thicker than 0.34-nm without changing its optical property; however, its actual roughness, i.e., effective thickness will significantly alter its response to strong out-of-plane fields, leading to a larger SPR shift., Comment: 18 pages, 5 figures

In a large social network whose members harbor binary sentiments towards an issue, we investigate the asymptotic accuracy of sentiment detection. We model the user sentiments by an Ising Markov random field model and allow the user sentiments to be biased by an external influence. We consider a general supermajority sentiment detection problem and show that the detection accuracy is affected by the network structure, its parameters, as well as the external influence level., Comment: 8 pages, 6 figures, 55th Annual Allerton Conference on Communication

We analyze the problem of majority sentiment detection in Online Social Networks (OSN), and relate the detection error probability to the underlying graph of the OSN. Modeling the underlying social network as an Ising Markov random field prior based on a given graph, we show that in the case of the empty graph (independent sentiments) and the chain graph, the detection is always inaccurate, even when the number of users grow to infinity. In the case of the complete graph, the detection is inaccurate if the connection strength is below a certain critical value, while it is asymptotically accurate if the strength is above that critical value, which is analogous to the phase transition phenomenon in statistical physics.