Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs
Linear programming (LP) is used in many machine learning applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider \emph{infeasible} IPMs for the special case where the number of variables is much larger than the number of constraints (i.e., wide), or vice-versa (i.e., tall) by taking the dual. Using tools from Randomized Linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real and synthetic data.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier
This paper explores a surprising equivalence between two seemingly-distinct convex optimization methods. We show that simulated annealing, a well-studied random walk algorithms, is directly equivalent, in a certain sense…
Distributed Primal-Dual Interior Point Framework for Analyzing Infeasible Combined Transmission and Distribution Grid Networks
The proliferation of distributed energy resources has heightened the interactions between transmission and distribution (T&D) systems, necessitating novel analyses for the reliable operation and planning of interconnecte…
GaussianFluent: Gaussian Simulation for Dynamic Scenes with Mixed Materials
3D Gaussian Splatting (3DGS) has emerged as a prominent 3D representation for high-fidelity and real-time rendering. Prior work has coupled physics simulation with Gaussians, but predominantly targets soft, deformable ma…
Worst-Case Linear Discriminant Analysis as Scalable Semidefinite Feasibility Problems
In this paper, we propose an efficient semidefinite programming (SDP) approach to worst-case linear discriminant analysis (WLDA). Compared with the traditional LDA, WLDA considers the dimensionality reduction problem fro…
Dimensionality ReductionGeneral ClassificationOptimistic Interior Point Methods for Sequential Hypothesis Testing by Betting
The technique of "testing by betting" frames nonparametric sequential hypothesis testing as a multiple-round game, where a player bets on future observations that arrive in a streaming fashion, accumulates wealth that qu…