An official website of the United States government
Regularized learning problems in Banach spaces, which often minimize the sum of a data fidelity term in one Banach norm and a regularization term in another Banach norm, is challenging to solve. We construct a direct sum space based on the Banach spaces for the fidelity term and the regularization term and recast the objective function as the norm of a quotient space of the direct sum space. We then express the original regularized problem as an optimization problem in the dual space of the direct sum space. It is to find the maximum of a linear function on a convex polytope, which may be solved by linear programming. A solution of the original problem is then obtained by using related extremal properties of norming functionals from a solution of the dual problem. Numerical experiments demonstrate that the proposed duality approach is effective for solving the regularization learning problems.
more »
« less
Linnik's large sieve and the L1$L^{1}$ norm of exponential sums
Abstract The elementary method of Balog and Ruzsa and the large sieve of Linnik are utilized to investigate the behaviour of the norm of an exponential sum over the primes. A new proof of a lower bound due to Vaughan for the norm of an exponential sum formed with the von Mangoldt function is furnished.
more »
« less
- Award ID(s):
- 1852288
- PAR ID:
- 10383384
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Bulletin of the London Mathematical Society
- Volume:
- 55
- Issue:
- 2
- ISSN:
- 0024-6093
- Page Range / eLocation ID:
- p. 843-853
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Polynomial nonnegativity constraints can often be handled using thesum of squarescondition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822–851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and$$\ell _1$$ -norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with smaller parameters.more » « less
-
Abstract We establish pointwise convergence for nonconventional ergodic averages taken along $$\lfloor p^{c}\rfloor $$, where $$p$$ is a prime number and $$c\in (1,4/3)$$ on $$L^{r}$$, $$r\in (1,\infty )$$. In fact, we consider averages along more general sequences $$\lfloor h(p)\rfloor $$, where $$h$$ belongs in a wide class of functions, the so-called $$c$$-regularly varying functions. We also establish uniform multiparameter oscillation estimates for our ergodic averages and the corresponding multiparameter pointwise ergodic theorem in the spirit of Dunford and Zygmund. A key ingredient of our approach are certain exponential sum estimates, which we also use for establishing a Waring-type result. Assuming that the Riemann zeta function has any zero-free strip upgrades our exponential sum estimates to polynomially saving ones and this makes a conditional result regarding the behavior of our ergodic averages on $$L^{1}$$ to not seem entirely out of reach.more » « less
-
Tauman_Kalai, Yael (Ed.)In the weighted load balancing problem, the input is an n-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the 𝓁_∞- or 𝓁₂-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all 𝓁_p-norm objectives for p ≥ 1, including p = ∞, simultaneously. Our main result is a deterministic O(log n)-pass O(1)-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an O(log n)-pass O(log n)-approximation algorithm for the 𝓁_∞-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.more » « less
-
Abstract Let $$H = N^{\theta }, \theta> 2/3$$ and $$k \geq 1$$. We obtain estimates for the following exponential sum over primes in short intervals: \begin{equation*} \sum_{N < n \leq N+H} \Lambda(n) \mathrm e(g(n)), \end{equation*}where $$g$$ is a polynomial of degree $$k$$. As a consequence of this in the special case $$g(n) = \alpha n^k$$, we deduce a short interval version of the Waring–Goldbach problem.more » « less
