Search

Iterative methods such as iterative closest point (ICP) for point cloud registration often suffer from bad local optimality (e.g. saddle points), due to the nature of nonconvex optimization. To address this fundamental challenge, in this paper we propose learning to form the loss landscape of a deep iterative method w.r.t. predictions at test time into a convex-like shape locally around each ground truth given data, namely Deep Loss Convexification (DLC), thanks to the overparametrization in neural networks. To this end, we formulate our learning objective based on adversarial training by manipulating the ground-truth predictions, rather than input data. In particular, we propose using star-convexity, a family of structured nonconvex functions that are unimodal on all lines that pass through a global minimizer, as our geometric constraint for reshaping loss landscapes, leading to (1) extra novel hinge losses appended to the original loss and (2) near-optimal predictions. We demonstrate the state-of-the-art performance using DLC with existing network architectures for the tasks of training recurrent neural networks (RNNs), 3D point cloud registration, and multimodel image alignment., Comment: 12 pages, 10 figures, accepted paper to Transactions on Pattern Analysis and Machine Intelligence. arXiv admin note: text overlap with arXiv:2303.11526

The Quadratic Knapsack Problem (QKP) involves selecting a subset of elements that maximizes the sum of pairwise and singleton utilities without exceeding a given budget. We introduce a Breakpoints Algorithm for QKP, named QKBP, which is based on a technique proposed in Hochbaum (2009) for efficiently generating the concave envelope of the solutions to the relaxation of the problem for all values of the budget. Our approach utilizes the fact that breakpoints in the concave envelopes are optimal solutions for their respective budgets. For budgets between breakpoints, a fast greedy procedure derives high-quality solutions from the optimal solutions of adjacent breakpoints. The algorithm is highly scalable due to an efficient parametric cut procedure used to generate the concave envelope. This efficiency is further improved by a newly developed compact problem formulation. Our extensive computational study on both existing and new benchmark instances, with up to 10,000 elements, shows that while some leading algorithms perform well on a few instances, QKBP consistently delivers high-quality solutions regardless of instance size, density, or budget. Moreover, QKBP achieves these results in significantly faster running times than all leading algorithms. The source code of the QKBP algorithm, the benchmark instances, and the detailed results are publicly available on GitHub.

The Lucas-Kanade (LK) method is a classic iterative homography estimation algorithm for image alignment, but often suffers from poor local optimality especially when image pairs have large distortions. To address this challenge, in this paper we propose a novel Deep Star-Convexified Lucas-Kanade (PRISE) method for multimodel image alignment by introducing strongly star-convex constraints into the optimization problem. Our basic idea is to enforce the neural network to approximately learn a star-convex loss landscape around the ground truth give any data to facilitate the convergence of the LK method to the ground truth through the high dimensional space defined by the network. This leads to a minimax learning problem, with contrastive (hinge) losses due to the definition of strong star-convexity that are appended to the original loss for training. We also provide an efficient sampling based algorithm to leverage the training cost, as well as some analysis on the quality of the solutions from PRISE. We further evaluate our approach on benchmark datasets such as MSCOCO, GoogleEarth, and GoogleMap, and demonstrate state-of-the-art results, especially for small pixel errors. Code can be downloaded from https://github.com/Zhang-VISLab., Comment: 8 pages, 7 figures, CVPR2023

This paper presents a novel method to generate answers for non-extraction machine reading comprehension (MRC) tasks whose answers cannot be simply extracted as one span from the given passages. Using a pointer network-style extractive decoder for such type of MRC may result in unsatisfactory performance when the ground-truth answers are given by human annotators or highly re-paraphrased from parts of the passages. On the other hand, using generative decoder cannot well guarantee the resulted answers with well-formed syntax and semantics when encountering long sentences. Therefore, to alleviate the obvious drawbacks of both sides, we propose an answer making-up method from extracted multi-spans that are learned by our model as highly confident $n$-gram candidates in the given passage. That is, the returned answers are composed of discontinuous multi-spans but not just one consecutive span in the given passages anymore. The proposed method is simple but effective: empirical experiments on MS MARCO show that the proposed method has a better performance on accurately generating long answers, and substantially outperforms two competitive typical one-span and Seq2Seq baseline decoders., Comment: Due to the policy of our institute, with the agreement of all of the author, we decide to withdraw this paper

This paper proposes a novel learning to learn method, called learning to learn iterative search algorithm (LISA), for signal detection in a multi-input multi-output (MIMO) system. The idea is to regard the signal detection problem as a decision making problem over tree. The goal is to learn the optimal decision policy. In LISA, deep neural networks are used as parameterized policy function. Through training, optimal parameters of the neural networks are learned and thus optimal policy can be approximated. Different neural network based architectures are used for fixed and varying channel models, respectively. LISA provides soft decisions and does not require any information about the additive white Gaussian noise. Simulation results show that LISA 1) obtains near maximum likelihood detection performance in both fixed and varying channel models under QPSK modulation; 2) achieves significantly better bit error rate (BER) performance than classical detectors and recently proposed deep/machine learning based detectors at various modulations and signal to noise (SNR) ratios both under i.i.d and correlated Rayleigh fading channels in the simulation experiments; 3) is robust to MIMO detection problems with imperfect channel state information; and 4) generalizes very well against channel correlation and SNRs.

Semantic role labeling (SRL) aims to discover the predicateargument structure of a sentence. End-to-end SRL without syntactic input has received great attention. However, most of them focus on either span-based or dependency-based semantic representation form and only show specific model optimization respectively. Meanwhile, handling these two SRL tasks uniformly was less successful. This paper presents an end-to-end model for both dependency and span SRL with a unified argument representation to deal with two different types of argument annotations in a uniform fashion. Furthermore, we jointly predict all predicates and arguments, especially including long-term ignored predicate identification subtask. Our single model achieves new state-of-the-art results on both span (CoNLL 2005, 2012) and dependency (CoNLL 2008, 2009) SRL benchmarks.