Abstract

In this paper, we study the min-max optimization problems on Riemannian manifolds. We introduce a Riemannian Hamiltonian function, minimization of which serves as a proxy for solving the original min-max problems. Under the Riemannian Polyak--Łojasiewicz (PL) condition on the Hamiltonian function, its minimizer corresponds to the desired min-max saddle point. We also provide cases where this condition is satisfied. To minimize the Hamiltonian function, we propose Riemannian Hamiltonian methods (RHM) and present their convergence analysis. We extend RHM to include a consensus regularization and to the stochastic setting. We illustrate the efficacy of the proposed RHM in applications such as subspace robust Wasserstein distance, robust training of neural networks, and generative adversarial networks.

Abstract

We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.

Abstract

We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. One of the chief drawbacks of many of these existing constructions is the large subpacketization level, which denotes the number of times a file should be split for the schemes to provide coding gain. In this work, using a new binary matrix model, we present several novel constructions for coded caching based on the various types of combinatorial designs and their q-analogs, which are also called subspace designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement, they provide a rate that is either constant or decreasing, and moreover require competitively small levels of subpacketization, which is an extremely important feature in practical applications of coded caching. We also apply our constructions to the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. Using our binary matrix framework, we present a new simple generic coded data shuffling scheme. Employing our designs-based constructions in conjunction with this new shuffling scheme, we obtain new coded computing schemes which have low file complexity, with marginally higher communication load compared to the optimal scheme for equivalent parameters. We show that our schemes can neatly extend to the scenario with full and partial stragglers also.

Abstract

The ILSUM shared task focuses on text summarization for two major Indian languages- Hindi and Gujarati, along with English. In this task, we experiment with various pretrained sequence-to-sequence models to find out the best model for each of the languages. We present a detailed overview of the models and our approaches in this paper. We secure the first rank across all three sub-tasks (English, Hindi and Gujarati). This paper also extensively analyzes the impact of k-fold cross-validation while experimenting with limited data size, and we also perform various experiments with a combination of the original and a filtered version of the data to determine the efficacy of the pretrained models.

Abstract

The tourism industry is important for the benefits it brings and due to its role as a commercial activity that creates demand and growth for many more industries. Yet there is not much work on data science problems in tourism. Unfortunately, there is not even a standard benchmark for evaluation of tourismspecific data science tasks and models. In this paper, we propose a benchmark, TOURISMNLG, of five natural language generation (NLG) tasks for the tourism domain and release corresponding datasets with standard train, validation and test splits1 . Further, previously proposed data science solutions for tourism problems do not leverage the recent benefits of transfer learning. Hence, we also contribute the first rigorously pretrained mT5 and mBART model checkpoints for the tourism domain. The models have been pretrained on four tourism-specific datasets covering different aspects of tourism. Using these models, we present initial baseline results on the benchmark tasks. We hope that the dataset will promote active research for natural language generation for travel and tourism. Keywords: NLG for Tourism · Long QA · Blog-Title Generation · Forum-Title Generation · Paragraph Generation · Short QA

Abstract

Recent approaches to the tensor completion problem have often overlooked the nonnegative structure of the data. We consider the problem of learning a nonnegative lowrank tensor, and using duality theory, we propose a novel factorization of such tensors. The factorization decouples the nonnegative constraints from the low-rank constraints. The resulting problem is an optimization problem on manifolds, and we propose a variant of Riemannian conjugate gradients to solve it. We test the proposed algorithm across various tasks such as colour image inpainting, video completion, and hyperspectral image completion. Experimental results show that the proposed method outperforms many state-of-the-art tensor completion algorithms.

Abstract

Sparse neural networks are shown to give accurate predictions competitive to denser versions, while also minimizing the number of arithmetic operations performed. However current GPU hardware can only exploit structured sparsity patterns for better efficiency. We propose a framework for generating structured multilevel block sparse neural networks by using the theory of graph products. Our Ramanujan bipartite graph product (RBGP) framework uses products of Ramanujan graphs to obtain the best connectivity for a given level of sparsity. This essentially ensures that the i.) the networks has the structured block sparsity for which runtime efficient algorithms exists, ii.) the model gives high prediction accuracy, due to the better expressive power derived from the connectivity of the graph, iii.) the graph data structure has a succinct representation that can be stored efficiently in memory. We use our framework to design a specific connectivity pattern called RBGP4 which makes efficient use of the memory hierarchy available on GPU. We benchmark our approach on image classification and machine translation tasks with an edge (Jetson Nano 2GB) as well as server (V100) GPUs. When compared with commonly used sparsity patterns like unstructured and block, we obtain significant speedups while achieving the same level of accuracy.

Abstract

Digital multimedia tools are becoming increasingly important as the world slowly shifts to an online mode. In this work, we present a low-cost, flexible writing pad that uses a 16×16 pressure sensing matrix based on the piezoresistive thin film of velostat. The writing area is 5 cm × 5 cm with an effective pixel area of 0.06 mm2 . A read out circuit is designed to detect the change in resistance of the velostat pixel using a voltage divider. A microprocessor raster scans through the sensor pixel matrix to obtain a data frame of 256 integers. This data is processed using techniques like squaring and normalising (S&N), Gaussian blurring, and adaptive thresholding to generate a more readable output. The writing pad is able to resolve characters larger than 2 cm in length. The flexible writing pad produces legible output while flexed at bending radius of upto 4 cm. Such flexibility promises to enhance the usability and portability of the writing pad significantly. Index Terms—Flexible PCB, Flexible writing pad, Piezoresistive material, Pressure sensor, Velostat

Abstract

The particle flow Gaussian particle filter (PFGPF) uses an invertible particle flow to generate a proposal density. It approximates the predictive and posterior distributions as Gaussian densities. In this paper, we use a bank of PFGPF filters to construct a Particle flow Gaussian sum particle filter (PFGSPF), which approximates the prediction and posterior as Gaussian mixture model. This approximation is useful in complex estimation problems where a single Gaussian approximation is inadequate. We compare the performance of this proposed filter with the PFGPF and others in challenging numerical simulations. Index Terms— Gaussian mixture, invertible particle flow, Gaussian sum particle filer, Gaussian particle filter, PFGPF.

Abstract

Unde rstan din g th e relationship betwee n phys ica l characte ristics an d acti vit y to kinemati c properties of th e spin e ha s impl ication s fo r sports , occupational tasks, clin ica l diagnosi s an d prognosis. This stud y aime d to ca t egorize spin e kinema tic s from flexion, la teral -bend , an d twis t exercise s by examinin g th e co rrelation s to body -mass inde x (BMI), wais t -to -hi p rati o (WHR), an d phys ica l acti vit y le vel s in health y youn g adults . Th e data wa s co llected from a marker -base d optoelectronic motion ca pture setu p an d a marker -less motion ca pture with th e RG B ca m - er a of a standard mobile phone. Co mpa rin g th e accuracies of th e tw o techniques on th e same data se t is impo r - tant to develo p inexpe nsive (RGB ca mera) diagno stics . Sixt y -tw o pa rti c ipant s (4 0 Male , 22 female ) pa rti c ipate d in th e study. Th e angula r di splac ement of th e spin e fo r each exercise wa s extracte d by ve cto r anal ysi s usin g a si n - gl e re ference node /marker . Th e anal ysi s showed no si gni ficant co rrelation s of angula r di splac ement s va lue s fo r th e thre e movement s with BM I or WHR. Th e phys ica l acti vit y leve l of male pa rti c ipant s is si gni ficantly co rrelate d with angula r di splac ement s fo r th e flexio n (p < 0.001) an d la teral -bend (p -valu e ranges from 0.00 1 to 0.04 ) an d weakly co rrelate d (but no t si gni ficant ) fo r twis t exercises. Th e phys ica l acti vit y leve l show s a si gni ficant co rrela - tion fo r only flexio n (p < 0.001) in female pa rti c ipants. Th e findings emph asize th e crit ica l role of phys ica l acti v - it y on mu sculoskel eta l flex ibi lit y in young, health y adults . Th e angles estimate d usin g both techniques were co m - parabl e an d si gni ficantly co rrelate d across pa rti c ipant s an d exercises.