Convexity, Classification, and Risk Bounds

Many of the classification algorithms developed in the machine learning literature, including the support vector machine and boosting, can be viewed as minimum contrast methods that minimize a convex surrogate of the 0–1 loss function. The convexity makes these algorithms computationally efficient. The use of a surrogate, however, has statistical consequences that must be balanced against the computational virtues of convexity. To study these issues, we provide a general quantitative relationship between the risk as assessed using the 0–1 loss and the risk as assessed using any nonnegative surrogate loss function. We show that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function—that it satisfies a pointwise form of Fisher consistency for classification. The relationship is based on a simple variational transformation of the loss function that is easy to compute in many applications. We also present a refined version of this result in the case of low noise, and show that in this case, strictly convex loss functions lead to faster rates of convergence of the risk than would be implied by standard uniform convergence arguments. Finally, we present applications of our results to the estimation of convergence rates in function classes that are scaled convex hulls of a finite-dimensional base class, with a variety of commonly used loss functions.

Correction to “The Importance of Convexity in Learning With Squared Loss” [Sep 98 1974-1980]

The paper "the importance of convexity in learning with squared loss" gave a lower bound on the sample complexity of learning with quadratic loss using a nonconvex function class. The proof contains an error. We show that the lower bound is true under a stronger condition that holds for many cases of interest.

Total factor productivity growth and convergence in the petroleum industry : empirical analysis testing for convexity

While economic theory acknowledges that some features of technology (e.g., indivisibilities, economies of scale and specialization) can fundamentally violate the traditional convexity assumption, almost all empirical studies accept the convexity property on faith. In this contribution, we apply two alternative flexible production technologies to measure total factor productivity growth and test the significance of the convexity axiom using a nonparametric test of closeness between unknown distributions. Based on unique field level data on the petroleum industry, the empirical results reveal significant differences, indicating that this production technology is most likely non-convex. Furthermore, we also show the impact of convexity on answers to traditional convergence questions in the productivity growth literature.

Local polynomial convexity of the union of two totally-real surfaces at their intersection

We consider the following question: Let S (1) and S (2) be two smooth, totally-real surfaces in C-2 that contain the origin. If the union of their tangent planes is locally polynomially convex at the origin, then is S-1 boolean OR S-2 locally polynomially convex at the origin? If T (0) S (1) a (c) T (0) S (2) = {0}, then it is a folk result that the answer is yes. We discuss an obstruction to the presumed proof, and provide a different approach. When dim(R)(T0S1 boolean AND T0S2) = 1, we present a geometric condition under which no consistent answer to the above question exists. We then discuss conditions under which we can expect local polynomial convexity.

Polynomial Approximation, Local Polynomial convexity, and Degenerate CR Singularities- II

We provide some conditions for the graph of a Holder-continuous function on (D) over bar, where (D) over bar is a closed disk in C, to be polynomially convex. Almost all sufficient conditions known to date - provided the function (say F) is smooth - arise from versions of the Weierstrass Approximation Theorem on (D) over bar. These conditions often fail to yield any conclusion if rank(R)DF is not maximal on a sufficiently large subset of (D) over bar. We bypass this difficulty by introducing a technique that relies on the interplay of certain plurisubharmonic functions. This technique also allows us to make some observations on the polynomial hull of a graph in C(2) at an isolated complex tangency.

Loop transformations: convexity, pruning, and optimization

High-level loop transformations are a key instrument in mapping computational kernels to effectively exploit the resources in modern processor architectures. Nevertheless, selecting required compositions of loop transformations to achieve this remains a significantly challenging task; current compilers may be off by orders of magnitude in performance compared to hand-optimized programs. To address this fundamental challenge, we first present a convex characterization of all distinct, semantics-preserving, multidimensional affine transformations. We then bring together algebraic, algorithmic, and performance analysis results to design a tractable optimization algorithm over this highly expressive space. Our framework has been implemented and validated experimentally on a representative set of benchmarks running on state-of-the-art multi-core platforms.

Consensus under general convexity

A method is proposed to characterize contraction of a set through orthogonal projections. For discrete-time multi-agent systems, quantitative estimates of convergence (to a consensus) rate are provided by means of contracting convex sets. Required convexity for the sets that should include the values that the transition maps of agents take is considered in a more general sense than that of Euclidean geometry. © 2007 IEEE.

Curved Inertia Frames: Visual Attention and Perceptual Organization Using Convexity and Symmetry

In this paper we present an approach to perceptual organization and attention based on Curved Inertia Frames (C.I.F.), a novel definition of "curved axis of inertia'' tolerant to noisy and spurious data. The definition is useful because it can find frames that correspond to large, smooth, convex, symmetric and central parts. It is novel because it is global and can detect curved axes. We discuss briefly the relation to human perception, the recognition of non-rigid objects, shape description, and extensions to finding "features", inside/outside relations, and long- smooth ridges in arbitrary surfaces.

The level sets of the resolvent norm and convexity properties of Banach spaces

We construct a bounded linear operator on a separable, reflexive and strictly convex Banach space whose resolvent norm is constant in a neighbourhood of zero.

Calcification and ossification of the convexity of the falx cerebri and related subdural space in human cadavers

OBJECTIVE: The present work was planned to report the incidence of calcification and ossification of an isolated cranial dural fold. The form, degree of severity and range of extension of such changes will be described. Involvement of the neighboring brain tissue and blood vessels, whether meningeal or cerebral, will also be determined. The results of this study might highlight the occasional incidence of intracranial calcification and ossification in images of the head and their interpretation, by radiologists and neurologists, to be of dural or vascular origin.

METHODS: Two human formalin-fixed cadavers, one middle-aged female another older male, were investigated at the Anatomy Laboratory, College of Medicine, King Faisal University, Dammam, Kingdom of Saudi Arabia during the period from 2000 to 2003. In each cadaver, the skullcap was removed and the convexity of the cranial dura mater, as well as the individual dural folds, were carefully examined for any calcification or ossification. The meningeal and cerebral blood vessels together with the underlying brain were grossly inspected for such structural changes. Calcified or ossified tissues, when identified, were subjected to histological examination to confirm their construction.

RESULTS: The female cadaver showed a calcified parietal emissary vein piercing the skullcap and projecting into the scalp. The latter looked paler and deficient in hair on its right side. The base of the stump was surrounded by a granular patch of calcification. The upper convex border of the falx cerebri was hardened and it presented granules, plaques and a cauliflower mass, which all proved to be osseous in structure. The meningeal and right cerebral vessels were mottled with calcium granules. The underlying temporal and parietal lobes of the right cerebral hemisphere were degenerated. The male cadaver also revealed a calcified upper border of the falx cerebri and superior sagittal sinus. Osseous granules and plaques, similar to those of the first specimen, were also identified but without gross changes in the underlying brain.

CONCLUSION: Calcification or ossification of an isolated site of the cranial dura mater and the intracranial blood vessels might occur. These changes should be kept in mind while interpreting images of the skull and brain. Clinical assessment and laboratory investigations are required to determine whether these changes are idiopathic, traumatic, or as a manifestation of a generalized disease such as hyperparathyroidism, vitamin D-intoxication, or chronic renal failure.