Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRadial Duality Part I: Foundations
102
0
0.0
(
0
)
Authors
Benjamin Grimmer
Ask ChatGPT about the research
No Arabic abstract
(Renegar, 2016) introduced a novel approach to transforming generic conic optimization problems into unconstrained, uniformly Lipschitz continuous minimization. We introduce radial transformations generalizing these ideas, equipped with an entirely new motivation and development that avoids any reliance on convex cones or functions. Perhaps of greatest practical importance, this facilitates the development of new families of projection-free first-order methods applicable even in the presence of nonconvex objectives and constraint sets. Our generalized construction of this radial transformation uncovers that it is dual (i.e., self-inverse) for a wide range of functions including all concave objectives. This gives a powerful new duality relating optimization problems to their radially dual problem. For a broad class of functions, we characterize continuity, differentiability, and convexity under the radial transformation as well as develop a calculus for it. This radial duality provides a strong foundation for designing projection-free radial optimization algorithms, which is carried out in the second part of this work.
rate research
Read More
The first part of this work established the foundations of a radial duality between nonnegative optimization problems, inspired by the work of (Renegar, 2016). Here we utilize our radial duality theory to design and analyze projection-free optimization algorithms that operate by solving a radially dual problem. In particular, we consider radial subgradient, smoothing, and accelerated methods that are capable of solving a range of constrained convex and nonconvex optimization problems and that can scale-up more efficiently than their classic counterparts. These algorithms enjoy the same benefits as their predecessors, avoiding Lipschitz continuity assumptions and costly orthogonal projections, in our newfound, broader context. Our radial duality further allows us to understand the effects and benefits of smoothness and growth conditions on the radial dual and consequently on our radial algorithms.
A geometric setup for control theory is presented. The argument is developed through the study of the extremals of action functionals defined on piecewise differentiable curves, in the presence of differentiable non-holonomic constraints. Special emphasis is put on the tensorial aspects of the theory. To start with, the kinematical foundations, culminating in the so called variational equation, are put on geometrical grounds, via the introduction of the concept of infinitesimal control . On the same basis, the usual classification of the extremals of a variational problem into normal and abnormal ones is also rationalized, showing the existence of a purely kinematical algorithm assigning to each admissible curve a corresponding abnormality index, defined in terms of a suitable linear map. The whole machinery is then applied to constrained variational calculus. The argument provides an interesting revisitation of Pontryagin maximum principle and of the Erdmann-Weierstrass corner conditions, as well as a proof of the classical Lagrange multipliers method and a local interpretation of Pontryagins equations as dynamical equations for a free (singular) Hamiltonian system. As a final, highly non-trivial topic, a sufficient condition for the existence of finite deformations with fixed endpoints is explicitly stated and proved.
Density expansions for hypoelliptic diffusions $(X^1,...,X^d)$ are revisited. In particular, we are interested in density expansions of the projection $(X_T^1,...,X_T^l)$, at time $T>0$, with $l leq d$. Global conditions are found which replace the well-known not-in-cutlocus condition known from heat-kernel asymptotics. Our small noise expansion allows for a second order exponential factor. As application, new light is shed on the Takanobu--Watanabe expansion of Brownian motion and Levys stochastic area. Further applications include tail and implied volatility asymptotics in some stochastic volatility models, discussed in a compagnion paper.
Signal processing over single-layer graphs has become a mainstream tool owing to its power in revealing obscure underlying structures within data signals. For generally, many real-life datasets and systems are characterized by more complex interactions among distinct entities. Such complex interactions may represent multiple levels of interactions that are difficult to be modeled with a single layer graph and can instead be captured by multiple layers of graph connections. Such multilayer/multi-level data structure can be more naturally modeled and captured by a high-dimensional multi-layer network (MLN). This work generalizes traditional graph signal processing (GSP) over multilayer networks for analysis of such multilayer signal features and their interactions. We propose a tensor-based framework of this multilayer network signal processing (M-GSP) in this two-part series. Specially, Part I introduces the fundamentals of M-GSP and studies spectrum properties of MLN Fourier space. We further describe its connections to traditional digital signal processing and GSP. Part II focuses on several major tools within the M-GSP framework for signal processing and data analysis. We provide results to demonstrate the efficacy and benefits of applying multilayer networks and the M-GSP in practical scenarios.
The problem of computing spectra of operators is arguably one of the most investigated areas of computational mathematics. Recent progress and the current paper reveal that, unlike the finite-dimensional case, infinite-dimensional problems yield a highly intricate infinite classification theory determining which spectral problems can be solved and with which type of algorithms. Classifying spectral problems and providing optimal algorithms is uncharted territory in the foundations of computational mathematics. This paper is the first of a two-part series establishing the foundations of computational spectral theory through the Solvability Complexity Index (SCI) hierarchy and has three purposes. First, we establish answers to many longstanding open questions on the existence of algorithms. We show that for large classes of partial differential operators on unbounded domains, spectra can be computed with error control from point sampling operator coefficients. Further results include computing spectra of operators on graphs with error control, the spectral gap problem, spectral classifications, and discrete spectra, multiplicities and eigenspaces. Second, these classifications determine which types of problems can be used in computer-assisted proofs. The theory for this is virtually non-existent, and we provide some of the first results in this infinite classification theory. Third, our proofs are constructive, yielding a library of new algorithms and techniques that handle problems that before were out of reach. We show several examples on contemporary problems in the physical sciences. Our approach is closely related to Smales program on the foundations of computational mathematics initiated in the 1980s, as many spectral problems can only be computed via several limits, a phenomenon shared with the foundations of polynomial root finding with rational maps, as proved by McMullen.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
