1,721,223 research outputs found
Projective re-normalization for improving the behavior of a homogeneous conic linear system
Full text linkIn this paper we study the homogeneous conic system F : Ax = 0, x ∈ C \ {0}. We choose a point ¯s ∈ intC∗ that serves as a normalizer and consider computational properties of the normalized system F¯s : Ax = 0, ¯sT x = 1, x ∈ C. We show that the computational complexity of solving F via an interior-point method depends
only on the complexity value ϑ of the barrier for C and on the symmetry of the origin in the image set H¯s := {Ax :
¯sT x = 1, x ∈ C}, where the symmetry of 0 in H¯s is sym(0,H¯s) := max{α : y ∈ H¯s -->−αy ∈ H¯s} .We show that a solution of F can be computed in O(sqrtϑ ln(ϑ/sym(0,H¯s)) interior-point iterations. In order to improve the theoretical and practical computation of a solution of F, we next present a general theory for projective re-normalization of the feasible region F¯s and the image set H¯s and prove the existence of a normalizer ¯s such that sym(0,H¯s) ≥ 1/m provided that F has an interior solution. We develop a methodology for constructing a normalizer ¯s such that sym(0,H¯s) ≥ 1/m with high probability, based on sampling on a geometric random walk with associated probabilistic complexity analysis. While such a normalizer is not itself computable in strongly-polynomialtime,
the normalizer will yield a conic system that is solvable in O(sqrtϑ ln(mϑ)) iterations, which is strongly-polynomialtime.
Finally, we implement this methodology on randomly generated homogeneous linear programming feasibility
problems, constructed to be poorly behaved. Our computational results indicate that the projective re-normalization
methodology holds the promise to markedly reduce the overall computation time for conic feasibility problems; for
instance we observe a 46% decrease in average IPM iterations for 100 randomly generated poorly-behaved problem
instances of dimension 1000 × 5000.Singapore-MIT Allianc
A Geometric Analysis of Renegar's Condition Number, and its Interplay with Conic Curvature
Full text linkFor a conic linear system of the form Ax ∈ K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar's condition number C(A) is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, C(A) is a representation-dependent measure which is usually difficult to interpret and may lead to overly-conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions.
Herein we show that Renegar's condition number is bounded from above and below by certain purely geometric quantities associated with A and K, and highlights the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar's condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed
An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
No full textOur interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.United States. Air Force Office of Scientific Research (Grant No. FA9550-08-1-0350)United States. Air Force Office of Scientific Research (AFOSR Grant No. FA9550-11-1-0141)Singapore-MIT Allianc
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
New analysis and results for the Frank–Wolfe method
No full textWe present new results for the Frank–Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps and the so-called FW gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.United States. Air Force Office of Scientific Research (AFOSR Grant No. FA9550-11-1-0141)Pontifical Catholic University of Chile (MIT-Chile-Pontificia Universidad Católica de Chile Seed Fund)National Science Foundation (U.S.) (NSF Graduate Research Fellowship No. 1122374
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
A new perspective on boosting in linear regression via subgradient optimization and relatives
No full textWe analyze boosting algorithms [Ann. Statist. 29 (2001) 1189–1232; Ann. Statist. 28 (2000) 337–407; Ann. Statist. 32 (2004) 407–499] in linear regression from a new perspective: that of modern first-order methods in convex optimiz ation. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS ? ) and least squares boosting [LS-BOOST(?)], can be viewed as subgradient descent to minimize the loss function defined as the maximum absolute correlation between the features and residuals. We also propose a minor modification of FS ? that yields an algorithm for the LASSO, and that may be easily extended to an algorithm that computes the LASSO path for different values of the regularization parameter. Furthermore, we show that these new algorithms for the LASSO may also be interpreted as the same master algorithm (subgradient descent), applied to a regularized version of the maximum absolute correlation loss function. We derive novel, comprehensive computational guarantees for several boosting algorithms in linear regression (including LS-BOOST(?) and FS ? ) by using techniques of first-order methods in convex optimization. Our computational guarantees inform us about the statistical properties of boosting algorithms. In particular, they provide, for the first time, a precise theoretical description of the amount of data-fidelity and regularization imparted by running a boosting algorithm with a prespecified learning rate for a fixed but arbitrary number of iterations, for any dataset
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
