More Like this

1. Continuous dependence on the initial data in the Kadison transitivity theorem and GNS construction

   https://doi.org/10.1142/S0129055X22500313  

   Spiegel, Daniel; Moreno, Juan; Qi, Marvin; Hermele, Michael; Beaudry, Agnès; Pflaum, Markus J. (October 2022, Reviews in Mathematical Physics)

   We consider how the outputs of the Kadison transitivity theorem and Gelfand–Naimark–Segal (GNS) construction may be obtained in families when the initial data are varied. More precisely, for the Kadison transitivity theorem, we prove that for any nonzero irreducible representation [Formula: see text] of a [Formula: see text]-algebra [Formula: see text] and [Formula: see text], there exists a continuous function [Formula: see text] such that [Formula: see text] for all [Formula: see text], where [Formula: see text] is the set of pairs of [Formula: see text]-tuples [Formula: see text] such that the components of [Formula: see text] are linearly independent. Versions of this result where [Formula: see text] maps into the self-adjoint or unitary elements of [Formula: see text] are also presented. Regarding the GNS construction, we prove that given a topological [Formula: see text]-algebra fiber bundle [Formula: see text], one may construct a topological fiber bundle [Formula: see text] whose fiber over [Formula: see text] is the space of pure states of [Formula: see text] (with the norm topology), as well as bundles [Formula: see text] and [Formula: see text] whose fibers [Formula: see text] and [Formula: see text] over [Formula: see text] are the GNS Hilbert space and closed left ideal, respectively, corresponding to [Formula: see text]. When [Formula: see text] is a smooth fiber bundle, we show that [Formula: see text] and [Formula: see text] are also smooth fiber bundles; this involves proving that the group of ∗-automorphisms of a [Formula: see text]-algebra is a Banach Lie group. In service of these results, we review the topology and geometry of the pure state space. A simple non-interacting quantum spin system is provided as an example illustrating the physical meaning of some of these results. 

   more » « less
2. Stability of Parallel Server Systems

   https://doi.org/10.1287/opre.2021.2125  

   Moyal, Pascal; Perry, Ohad (July 2022, Operations Research)

   The fundamental problem in the study of parallel-server systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most well-studied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the power-of-[Formula: see text] (PW([Formula: see text])), which assigns arrivals to the shortest among [Formula: see text] queues that are sampled from the total of [Formula: see text] queues uniformly at random; and uniform routing, under which arrivals are routed to one of the [Formula: see text] queues uniformly at random. In this paper we study the stability problem of parallel-server systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a [Formula: see text]-allocation policy, that generalizes the PW([Formula: see text]) policy, and thus also the JSQ and uniform routing, where [Formula: see text] is an [Formula: see text]-dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the [Formula: see text]-allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and [Formula: see text], is in general smaller than the set [Formula: see text]. Our analyses build on representing the queue process as a continuous-time Markov chain in an ordered space of [Formula: see text]-dimensional real-valued vectors, and using a generalized form of the Schur-convex order. 

   more » « less
3. For interpolating kernel machines, minimizing the norm of the ERM solution maximizes stability

   https://doi.org/10.1142/S0219530522400115  

   Rangamani, Akshay; Rosasco, Lorenzo; Poggio, Tomaso (January 2023, Analysis and Applications)

   In this paper, we study kernel ridge-less regression, including the case of interpolating solutions. We prove that maximizing the leave-one-out ([Formula: see text]) stability minimizes the expected error. Further, we also prove that the minimum norm solution — to which gradient algorithms are known to converge — is the most stable solution. More precisely, we show that the minimum norm interpolating solution minimizes a bound on [Formula: see text] stability, which in turn is controlled by the smallest singular value, hence the condition number, of the empirical kernel matrix. These quantities can be characterized in the asymptotic regime where both the dimension ([Formula: see text]) and cardinality ([Formula: see text]) of the data go to infinity (with [Formula: see text] as [Formula: see text]). Our results suggest that the property of [Formula: see text] stability of the learning algorithm with respect to perturbations of the training set may provide a more general framework than the classical theory of Empirical Risk Minimization (ERM). While ERM was developed to deal with the classical regime in which the architecture of the learning network is fixed and [Formula: see text], the modern regime focuses on interpolating regressors and overparameterized models, when both [Formula: see text] and [Formula: see text] go to infinity. Since the stability framework is known to be equivalent to the classical theory in the classical regime, our results here suggest that it may be interesting to extend it beyond kernel regression to other overparameterized algorithms such as deep networks. 

   more » « less
4. Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics

   https://doi.org/10.1142/S0219061323500058  

   Hirschfeldt, Denis R; Jockusch, Carl G; Schupp, Paul E (August 2024, Journal of Mathematical Logic)

   For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. 

   more » « less
5. Inhomogeneous Diophantine approximation for generic homogeneous functions

   https://doi.org/10.1142/S1793042123500628  

   Kleinbock, Dmitry; Skenderi, Mishel (July 2023, International Journal of Number Theory)

   This paper is a sequel to [Monatsh. Math. 194 (2021) 523–554] in which results of that paper are generalized so that they hold in the setting of inhomogeneous Diophantine approximation. Given any integers [Formula: see text] and [Formula: see text], any [Formula: see text], and any homogeneous function [Formula: see text] that satisfies a certain nonsingularity assumption, we obtain a biconditional criterion on the approximating function [Formula: see text] for a generic element [Formula: see text] in the [Formula: see text]-orbit of [Formula: see text] to be (respectively, not to be) [Formula: see text]-approximable at [Formula: see text]: that is, for there to exist infinitely many (respectively, only finitely many) [Formula: see text] such that [Formula: see text] for each [Formula: see text]. In this setting, we also obtain a sufficient condition for uniform approximation. We also consider some examples of [Formula: see text] that do not satisfy our nonsingularity assumptions and prove similar results for these examples. Moreover, one can replace [Formula: see text] above by any closed subgroup of [Formula: see text] that satisfies certain integrability axioms (being of Siegel and Rogers type) introduced by the authors in the aforementioned previous paper. 

   more » « less