An official website of the United States government
Abstract In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon–Fletcher–Powell (DFP) method and the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite–time local convergence rate is not fully investigated. In this paper, we provide a finite–time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of$$(1/k)^{k/2}$$ , wherekis the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.
more »
« less
A quantitative Hasse principle for weighted quartic forms
Abstract We derive, via the Hardy–Littlewood method, an asymptotic formula for the number of integral zeros of a particular class of weighted quartic forms under the assumption of nonsingular local solubility. Our polynomials satisfy the condition that . Our conclusions improve on those that would follow from a direct application of the methods of Birch. For example, we show that in many circumstances the expected asymptotic formula holds when and .
more »
« less
- Award ID(s):
- 2001549
- PAR ID:
- 10483339
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Mathematika
- Volume:
- 70
- Issue:
- 1
- ISSN:
- 0025-5793
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We prove novel asymptotic freeness results in tracial ultraproduct von Neumann algebras. In particular, we show that whenever$$M = M_1 \ast M_2$$is a tracial free product von Neumann algebra and$$u_1 \in \mathscr U(M_1)$$,$$u_2 \in \mathscr U(M_2)$$are Haar unitaries, the relative commutants$$\{u_1\}' \cap M^{\mathcal U}$$and$$\{u_2\}' \cap M^{\mathcal U}$$are freely independent in the ultraproduct$$M^{\mathcal U}$$. Our proof relies on Mei–Ricard’s results [MR16] regarding$$\operatorname {L}^p$$-boundedness (for all$$1 < p < +\infty $$) of certain Fourier multipliers in tracial amalgamated free products von Neumann algebras. We derive two applications. Firstly, we obtain a general absorption result in tracial amalgamated free products that recovers several previous maximal amenability/Gamma absorption results. Secondly, we prove a new lifting theorem which we combine with our asymptotic freeness results and Chifan–Ioana–Kunnawalkam Elayavalli’s recent construction [CIKE22] to provide the first example of a$$\mathrm {II_1}$$factor that does not have property Gamma and is not elementary equivalent to any free product of diffuse tracial von Neumann algebras.more » « less
-
Abstract We prove an asymptotic formula for the second moment of central values of DirichletL-functions restricted to a coset. More specifically, consider a coset of the subgroup of characters modulodinside the full group of characters moduloq. Suppose that$$\nu _p(d) \geq \nu _p(q)/2$$for all primespdividingq. In this range, we obtain an asymptotic formula with a power-saving error term; curiously, there is a secondary main term of rough size$$q^{1/2}$$here which is not predicted by the integral moments conjecture of Conrey, Farmer, Keating, Rubinstein, and Snaith. The lower-order main term does not appear in the second moment of the Riemann zeta function, so this feature is not anticipated from the analogous archimedean moment problem. We also obtain an asymptotic result for smallerd, with$$\nu _p(q)/3 \leq \nu _p(d) \leq \nu _p(q)/2$$, with a power-saving error term fordlarger than$$q^{2/5}$$. In this more difficult range, the secondary main term somewhat changes its form and may have size roughlyd, which is only slightly smaller than the diagonal main term.more » « less
-
Abstract We report that there are 49679870 Carmichael numbers less than$$10^{22}$$ which is an order of magnitude improvement on Richard Pinch’s prior work. We find Carmichael numbers of the form$$n = Pqr$$ using an algorithm bifurcated by the size ofPwith respect to the tabulation boundB. For$$P < 7 \times 10^7$$ , we found 35985331 Carmichael numbers and 1202914 of them were less than$$10^{22}$$ . When$$P > 7 \times 10^7$$ , we found 48476956 Carmichael numbers less than$$10^{22}$$ . We provide a comprehensive overview of both cases of the algorithm. For the large case, we show and implement asymptotically faster ways to tabulate compared to the prior tabulation. We also provide an asymptotic estimate of the cost of this algorithm. It is interesting that Carmichael numbers are worst case inputs to this algorithm. So, providing a more robust asymptotic analysis of the cost of the algorithm would likely require resolution of long-standing open questions regarding the asymptotic density of Carmichael numbers.more » « less
-
We consider solutions of the repulsive Vlasov–Poisson system which are a combination of a point charge and a small gas, i.e., measures of the form\delta_{(\mathcal{X}(t),\mathcal{V}(t))}+\mu^{2}d\mathbf{x}d\mathbf{v}for some(\mathcal{X}, \mathcal{V})\colon \mathbb{R}\to\mathbb{R}^{6}and a small gas distribution\mu\colon \mathbb{R}\to L^{2}_{\mathbf{x},\mathbf{v}}, and study asymptotic dynamics in the associated initial value problem. If initially suitable moments on\mu_{0}=\mu(t=0)are small, we obtain a global solution of the above form, and the electric field generated by the gas distribution \mudecays at an almost optimal rate. Assuming in addition boundedness of suitable derivatives of \mu_{0}, the electric field decays at an optimal rate, and we derive modified scattering dynamics for the motion of the point charge and the gas distribution. Our proof makes crucial use of the Hamiltonian structure. The linearized system is transport by the Kepler ODE, which we integrate exactly through an asymptotic action-angle transformation. Thanks to a precise understanding of the associated kinematics, moment and derivative control is achieved via a bootstrap analysis that relies on the decay of the electric field associated to\mu. The asymptotic behavior can then be deduced from the properties of Poisson brackets in asymptotic action coordinates.more » « less
