Building upon recent works on linesearch-free adaptive proximal gradient methods, this paper proposes adaPG$^{q,r}$, a framework that unifies and extends existing results by providing larger stepsize policies and improved lower bounds. Different choices of the parameters $q$ and $r$ are discussed and the efficacy of the resulting methods is demonstrated through numerical simulations. In an attempt to better understand the underlying theory, its convergence is established in a more general setting that allows for time-varying parameters. Finally, an adaptive alternating minimization algorithm is presented by exploring the dual setting. This algorithm not only incorporates additional adaptivity, but also expands its applicability beyond standard strongly convex settings.
相關內容
In a paper of 1976, Rauzy studied two complexity notions, $\underline{\beta}$ and $\overline{\beta}$, for infinite sequences over a finite alphabet. The function $\underline{\beta}$ is maximum exactly in the Borel normal sequences and $\overline{\beta}$ is minimum exactly in the sequences that, when added to any Borel normal sequence, the result is also Borel normal. Although the definition of $\underline{\beta}$ and $\overline{\beta}$ do not involve finite-state automata, we establish some connections between them and the lower $\underline{\rm dim}$ and upper $\overline{\rm dim}$ finite-state dimension (or other equivalent notions like finite-state compression ratio, aligned-entropy or cumulative log-loss of finite-state predictors). We show tight lower and upper bounds on $\underline{\rm dim}$ and $\overline{\rm dim}$ as functions of $\underline{\beta}$ and $\overline{\beta}$, respectively. In particular this implies that sequences with $\overline{\rm dim}$ zero are exactly the ones that that, when added to any Borel normal sequence, the result is also Borel normal. We also show that the finite-state dimensions $\underline{\rm dim}$ and $\overline{\rm dim}$ are essentially subadditive. We need two technical tools that are of independent interest. One is the family of local finite-state automata, which are automata whose memory consists of the last $k$ read symbols for some fixed integer $k$. We show that compressors based on local finite-state automata are as good as standard finite-state compressors. The other one is a notion of finite-state relational (non-deterministic) compressor, which can compress an input in several ways provided the input can always be recovered from any of its outputs. We show that such compressors cannot compress more than standard (deterministic) finite-state compressors.
Agent-based models describing social interactions among individuals can help to better understand emerging macroscopic patterns in societies. One of the topics which is worth tackling is the formation of different kinds of hierarchies that emerge in social spaces such as cities. Here we propose a Bonabeau-like model by adding a second class of agents. The fundamental particularity of our model is that only a pairwise interaction between agents of the opposite class is allowed. Agent fitness can thus only change by competition among the two classes, while the total fitness in the society remains constant. The main result is that for a broad range of values of the model parameters, the fitness of the agents of each class show a decay in time except for one or very few agents which capture almost all the fitness in the society. Numerical simulations also reveal a singular shift from egalitarian to hierarchical society for each class. This behaviour depends on the control parameter $\eta$, playing the role of the inverse of the temperature of the system. Results are invariant with regard to the system size, contingent solely on the quantity of agents within each class. Finally, a couple of scaling laws are provided thus showing a data collapse from different model parameters and they follow a shape which can be related to the presence of a phase transition in the model.
We consider the problem of analyzing multivariate time series collected on multiple subjects, with the goal of identifying groups of subjects exhibiting similar trends in their recorded measurements over time as well as time-varying groups of associated measurements. To this end, we propose a Bayesian model for temporal biclustering featuring nested partitions, where a time-invariant partition of subjects induces a time-varying partition of measurements. Our approach allows for data-driven determination of the number of subject and measurement clusters as well as estimation of the number and location of changepoints in measurement partitions. To efficiently perform model fitting and posterior estimation with Markov Chain Monte Carlo, we derive a blocked update of measurements' cluster-assignment sequences. We illustrate the performance of our model in two applications to functional magnetic resonance imaging data and to an electroencephalogram dataset. The results indicate that the proposed model can combine information from potentially many subjects to discover a set of interpretable, dynamic patterns. Experiments on simulated data compare the estimation performance of the proposed model against ground-truth values and other statistical methods, showing that it performs well at identifying ground-truth subject and measurement clusters even when no subject or time dependence is present.
Various methods have emerged for conducting mediation analyses with multiple correlated mediators, each with distinct strengths and limitations. However, a comparative evaluation of these methods is lacking, providing the motivation for this paper. This study examines six mediation analysis methods for multiple correlated mediators that provide insights to the contributors for health disparities. We assessed the performance of each method in identifying joint or path-specific mediation effects in the context of binary outcome variables varying mediator types and levels of residual correlation between mediators. Through comprehensive simulations, the performance of six methods in estimating joint and/or path-specific mediation effects was assessed rigorously using a variety of metrics including bias, mean squared error, coverage and width of the 95$\%$ confidence intervals. Subsequently, these methods were applied to the REasons for Geographic And Racial Differences in Stroke (REGARDS) study, where differing conclusions were obtained depending on the mediation method employed. This evaluation provides valuable guidance for researchers grappling with complex multi-mediator scenarios, enabling them to select an optimal mediation method for their research question and dataset.
We introduce an algorithm that simplifies the construction of efficient estimators, making them accessible to a broader audience. 'Dimple' takes as input computer code representing a parameter of interest and outputs an efficient estimator. Unlike standard approaches, it does not require users to derive a functional derivative known as the efficient influence function. Dimple avoids this task by applying automatic differentiation to the statistical functional of interest. Doing so requires expressing this functional as a composition of primitives satisfying a novel differentiability condition. Dimple also uses this composition to determine the nuisances it must estimate. In software, primitives can be implemented independently of one another and reused across different estimation problems. We provide a proof-of-concept Python implementation and showcase through examples how it allows users to go from parameter specification to efficient estimation with just a few lines of code.
The ability to manipulate logical-mathematical symbols (LMS), encompassing tasks such as calculation, reasoning, and programming, is a cognitive skill arguably unique to humans. Considering the relatively recent emergence of this ability in human evolutionary history, it has been suggested that LMS processing may build upon more fundamental cognitive systems, possibly through neuronal recycling. Previous studies have pinpointed two primary candidates, natural language processing and spatial cognition. Existing comparisons between these domains largely relied on task-level comparison, which may be confounded by task idiosyncrasy. The present study instead compared the neural correlates at the domain level with both automated meta-analysis and synthesized maps based on three representative LMS tasks, reasoning, calculation, and mental programming. Our results revealed a more substantial cortical overlap between LMS processing and spatial cognition, in contrast to language processing. Furthermore, in regions activated by both spatial and language processing, the multivariate activation pattern for LMS processing exhibited greater multivariate similarity to spatial cognition than to language processing. A hierarchical clustering analysis further indicated that typical LMS tasks were indistinguishable from spatial cognition tasks at the neural level, suggesting an inherent connection between these two cognitive processes. Taken together, our findings support the hypothesis that spatial cognition is likely the basis of LMS processing, which may shed light on the limitations of large language models in logical reasoning, particularly those trained exclusively on textual data without explicit emphasis on spatial content.
We present several algorithms for evaluating point containment in constructive solid geometry (CSG) trees with unbounded primitives. Three algorithms are presented based on postfix, prefix, and infix notations of the CSG binary expression tree. We show that prefix and infix notations enable short-circuiting logic, which reduces the number of primitives that must be checked during point containment. To evaluate the performance of the algorithms, each algorithm was implemented in the OpenMC Monte Carlo particle transport code, which relies on CSG to represent solid bodies through which subatomic particles travel. Two sets of tests were carried out. First, the execution time to generate a high-resolution rasterized image of a 2D slice of a detailed CSG model of the ITER tokamak was measured. Use of both prefix and infix notations offered significant speedup over the postfix notation that has traditionally been used in particle transport codes, with infix resulting in a 6$\times$ reduction in execution time relative to postfix. We then measured the execution time of neutron transport simulations of the same ITER model using each of the algorithms. The results and performance improvements reveal the same trends as for the rasterization test, with a 4.59$\times$ overall speedup using the infix notation relative to the original postfix notation in OpenMC.
PEPit is a Python package aiming at simplifying the access to worst-case analyses of a large family of first-order optimization methods possibly involving gradient, projection, proximal, or linear optimization oracles, along with their approximate, or Bregman variants. In short, PEPit is a package enabling computer-assisted worst-case analyses of first-order optimization methods. The key underlying idea is to cast the problem of performing a worst-case analysis, often referred to as a performance estimation problem (PEP), as a semidefinite program (SDP) which can be solved numerically. To do that, the package users are only required to write first-order methods nearly as they would have implemented them. The package then takes care of the SDP modeling parts, and the worst-case analysis is performed numerically via a standard solver.
We propose a novel and simple spectral method based on the semi-discrete Fourier transforms to discretize the fractional Laplacian $(-\Delta)^\frac{\alpha}{2}$. Numerical analysis and experiments are provided to study its performance. Our method has the same symbol $|\boldsymbol\xi|^\alpha$ as the fractional Laplacian $(-\Delta)^\frac{\alpha}{2}$ at the discrete level, and thus it can be viewed as the exact discrete analogue of the fractional Laplacian. This {\it unique feature} distinguishes our method from other existing methods for the fractional Laplacian. Note that our method is different from the Fourier pseudospectral methods in the literature which are usually limited to periodic boundary conditions (see Remark \ref{remark0}). Numerical analysis shows that our method can achieve a spectral accuracy. The stability and convergence of our method in solving the fractional Poisson equations were analyzed. Our scheme yields a multilevel Toeplitz stiffness matrix, and thus fast algorithms can be developed for efficient matrix-vector multiplications. The computational complexity is ${\mathcal O}(2N\log(2N))$, and the memory storage is ${\mathcal O}(N)$ with $N$ the total number of points. Extensive numerical experiments verify our analytical results and demonstrate the effectiveness of our method in solving various problems.
We study the computational problem of rigorously describing the asymptotic behaviour of topological dynamical systems up to a finite but arbitrarily small pre-specified error. More precisely, we consider the limit set of a typical orbit, both as a spatial object (attractor set) and as a statistical distribution (physical measure), and prove upper bounds on the computational resources of computing descriptions of these objects with arbitrary accuracy. We also study how these bounds are affected by different dynamical constrains and provide several examples showing that our bounds are sharp in general. In particular, we exhibit a computable interval map having a unique transitive attractor with Cantor set structure supporting a unique physical measure such that both the attractor and the measure are non computable.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191