More Like this

1. Sparse Approximation via Generating Point Sets

   https://doi.org/10.1137/1.9781611974331.ch40  

   Blum, Avrim; Har-Peled, Sariel; Raichel, Benjamin (December 2015, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016))

   For a set P of n points in the unit ball b ⊆ R d , consider the problem of finding a small subset T ⊆ P such that its convex-hull ε-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ε. We present an efficient algorithm to compute such an ε ′ -approximation of size kalg, where ε ′ is a function of ε, and kalg is a function of the minimum size kopt of such an ε-approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be ε- approximated by a convex-combination of points of T that is O(1/ε2 )-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input. 

   more » « less
2. Limit theorems for process-level Betti numbers for sparse and critical regimes

   https://doi.org/10.1017/apr.2019.50  

   Owada, Takashi; Thomas, Andrew M. (March 2020, Advances in Applied Probability)

   Abstract The objective of this study is to examine the asymptotic behavior of Betti numbers of Čech complexes treated as stochastic processes and formed from random points in the d -dimensional Euclidean space $${\mathbb{R}}^d$$ . We consider the case where the points of the Čech complex are generated by a Poisson process with intensity nf for a probability density f . We look at the cases where the behavior of the connectivity radius of the Čech complex causes simplices of dimension greater than $k+1$ to vanish in probability, the so-called sparse regime, as well when the connectivity radius is of the order of $$n^{-1/d}$$ , the critical regime. We establish limit theorems in the aforementioned regimes: central limit theorems for the sparse and critical regimes, and a Poisson limit theorem for the sparse regime. When the connectivity radius of the Čech complex is $$o(n^{-1/d})$$ , i.e. the sparse regime, we can decompose the limiting processes into a time-changed Brownian motion or a time-changed homogeneous Poisson process respectively. In the critical regime, the limiting process is a centered Gaussian process but has a much more complicated representation, because the Čech complex becomes highly connected with many topological holes of any dimension. 

   more » « less
3. Practical Data-Dependent Metric Compression with Provable Guarantees

   Indyk, Piotr; Razenshteyn, Ilya P.; Wagner, Tal (January 2017, Annual Conference on Neural Information Processing Systems)

   We introduce a new distance-preserving compact representation of multi-dimensional point-sets. Given n points in a d-dimensional space where each coordinate is represented using B bits (i.e., dB bits per point), it produces a representation of size O( d log(d B/epsilon) +log n) bits per point from which one can approximate the distances up to a factor of 1 + epsilon. Our algorithm almost matches the recent bound of Indyk et al, 2017} while being much simpler. We compare our algorithm to Product Quantization (PQ) (Jegou et al, 2011) a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT, MNIST, New York City taxi time series and a synthetic one-dimensional data set embedded in a high-dimensional space. Our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance. 

   more » « less
4. Statistical and Computational Complexities of BFGS Quasi-Newton Method for Generalized Linear Models

   Jin, Qiujiang; Ren, Tongzheng; Ho, Nhat; Mokhtari, Aryan (May 2024, Transactions on machine learning research)

   The gradient descent (GD) method has been used widely to solve parameter estimation in generalized linear models (GLMs), a generalization of linear models when the link function can be non-linear. In GLMs with a polynomial link function, it has been shown that in the high signal-to-noise ratio (SNR) regime, due to the problem's strong convexity and smoothness, GD converges linearly and reaches the final desired accuracy in a logarithmic number of iterations. In contrast, in the low SNR setting, where the problem becomes locally convex, GD converges at a slower rate and requires a polynomial number of iterations to reach the desired accuracy. Even though Newton's method can be used to resolve the flat curvature of the loss functions in the low SNR case, its computational cost is prohibitive in high-dimensional settings as it is $$\mathcal{O}(d^3)$$, where $$d$$ the is the problem dimension. To address the shortcomings of GD and Newton's method, we propose the use of the BFGS quasi-Newton method to solve parameter estimation of the GLMs, which has a per iteration cost of $$\mathcal{O}(d^2)$$. When the SNR is low, for GLMs with a polynomial link function of degree $$p$$, we demonstrate that the iterates of BFGS converge linearly to the optimal solution of the population least-square loss function, and the contraction coefficient of the BFGS algorithm is comparable to that of Newton's method. Moreover, the contraction factor of the linear rate is independent of problem parameters and only depends on the degree of the link function $$p$$. Also, for the empirical loss with $$n$$ samples, we prove that in the low SNR setting of GLMs with a polynomial link function of degree $$p$$, the iterates of BFGS reach a final statistical radius of $$\mathcal{O}((d/n)^{\frac{1}{2p+2}})$$ after at most $$\log(n/d)$$ iterations. This complexity is significantly less than the number required for GD, which scales polynomially with $(n/d)$. 

   more » « less
5. A Two-Step Fixed-Point Proximity Algorithmfor a Class of Non-differentiable Optimization Models in Machine Learning

   Zheng Li, Guohui Song (September 2019, Journal of scientific computing)

   Sparse learning models are popular in many application areas. Objective functions in sparse learning models are usually non-smooth, which makes it difficult to solve them numerically. We develop a fast and convergent two-step iteration scheme for solving a class of non-differentiable optimization models motivated from sparse learning. To overcome the difficulty of the non-differentiability of the models, we first present characterizations of their solutions as fixed-points of mappings involving the proximity operators of the functions appearing in the objective functions. We then introduce a two-step fixed-point algorithm to compute the solutions. We establish convergence results of the proposed two-step iteration scheme and compare it with the alternating direction method of multipliers (ADMM). In particular, we derive specific two-step iteration algorithms for three models in machine learning: l1-SVM classification, l1-SVM regression, and the SVM classification with the group LASSO regularizer. Numerical experiments with some synthetic datasets and some benchmark datasets show that the proposed algorithm outperforms ADMM and the linear programming method in computational time and memory storage costs. 

   more » « less