We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate (1/K) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n^1/2) in unconstrained optimization and O(n^1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.

Many problems in machine learning can be solved by rounding the solution of an appropriate linear program. We propose a scheme that is based on a quadratic program relaxation which allows us to use parallel stochastic-coordinate-descent to approximately solve large linear programs efficiently. Our software is an order of magnitude faster than Cplex (a commercial linear programming solver) and yields similar solution quality. Our results include a novel perturbation analysis of a quadratic-penalty formulation of linear programming and a convergence result, which we use to derive running time and quality guarantees.

OBJECTIVE: To describe an analytical framework for quantifying the societal savings and financial consequences of a health information exchange (HIE), and to demonstrate its use in designing pricing policies for sustainable HIEs. MATERIALS AND METHODS: We developed a linear programming model to (1) quantify the financial worth of HIE information to each of its participating institutions and (2) evaluate three HIE pricing policies: fixed-rate annual, charge per visit, and charge per look-up. We considered three desired outcomes of HIE-related emergency care (modeled as parameters): preventing unrequired hospitalizations, reducing duplicate tests, and avoiding emergency department (ED) visits. We applied this framework to 4639 ED encounters over a 12-month period in three large EDs in Milwaukee, Wisconsin, using Medicare/Medicaid claims data, public reports of hospital admissions, published payer mix data, and use data from a not-for-profit regional HIE. RESULTS: For this HIE, data accesses produced net financial gains for all providers and payers. Gains, due to HIE, were more significant for providers with more health maintenance organizations patients. Reducing unrequired hospitalizations and avoiding repeat ED visits were responsible for more than 70% of the savings. The results showed that fixed annual subscriptions can sustain this HIE, while ensuring financial gains to all participants. Sensitivity analysis revealed that the results were robust to uncertainties in modeling parameters. DISCUSSION: Our specific HIE pricing recommendations depend on the unique characteristics of this study population. However, our main contribution is the modeling approach, which is broadly applicable to other populations.