Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if … Read more
In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow … Read more
The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone $F$. At each iteration, the algorithm only involves a query of a separation oracle for $F$ and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a feasible point in $F$ after $\Oh(1/\tau_F^2)$ iterations, … Read more
Let $C$ be a full-dimensional pointed closed convex cone in $R^m$ obtained by taking the conic hull of a strictly convex set. Given $A \in Q^{m \times n_1}$, $B \in Q^{m \times n_2}$ and $b \in Q^m$, a simple conic mixed-integer set (SCMIS) is a set of the form $\{(x,y)\in Z^{n_1} \times R^{n_2}\,|\,\ Ax +By … Read more
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more
In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more
In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more