We present new results for online contention resolution schemes for the matching polytope of graphs, in the random-order (RCRS) and adversarial (OCRS) arrival models. Our results include improved selectability guarantees (i.e., lower bounds), as well as new impossibility results (i.e., upper bounds). By well-known reductions to the prophet (secretary) matching problem, a $c$-selectable OCRS (RCRS) implies a $c$-competitive algorithm for adversarial (random order) edge arrivals. Similar reductions are also known for the query-commit matching problem. For the adversarial arrival model, we present a new analysis of the OCRS of Ezra et al.~(EC, 2020). We show that this scheme is $0.344$-selectable for general graphs and $0.349$-selectable for bipartite graphs, improving on the previous $0.337$ selectability result for this algorithm. We also show that the selectability of this scheme cannot be greater than $0.361$ for general graphs and $0.382$ for bipartite graphs. We further show that no OCRS can achieve a selectability greater than $0.4$ for general graphs, and $0.433$ for bipartite graphs. For random-order arrivals, we present two attenuation-based schemes which use new attenuation functions. Our first RCRS is $0.474$-selectable for general graphs, and our second is $0.476$-selectable for bipartite graphs. These results improve upon the recent $0.45$ (and $0.456$) selectability results for general graphs (respectively, bipartite graphs) due to Pollner et al.~(EC, 2022). On general graphs, our 0.474-selectable RCRS provides the best known positive result even for offline contention resolution, and also for the correlation gap. We conclude by proving a fundamental upper bound of 0.5 on the selectability of RCRS, using bipartite graphs.
We introduce view birdification, the problem of recovering ground-plane movements of people in a crowd from an ego-centric video captured from an observer (e.g., a person or a vehicle) also moving in the crowd. Recovered ground-plane movements would provide a sound basis for situational understanding and benefit downstream applications in computer vision and robotics. In this paper, we formulate view birdification as a geometric trajectory reconstruction problem and derive a cascaded optimization method from a Bayesian perspective. The method first estimates the observer's movement and then localizes surrounding pedestrians for each frame while taking into account the local interactions between them. We introduce three datasets by leveraging synthetic and real trajectories of people in crowds and evaluate the effectiveness of our method. The results demonstrate the accuracy of our method and set the ground for further studies of view birdification as an important but challenging visual understanding problem.
Recent advances in camera designs and imaging pipelines allow us to capture high-quality images using smartphones. However, due to the small size and lens limitations of the smartphone cameras, we commonly find artifacts or degradation in the processed images. The most common unpleasant effects are noise artifacts, diffraction artifacts, blur, and HDR overexposure. Deep learning methods for image restoration can successfully remove these artifacts. However, most approaches are not suitable for real-time applications on mobile devices due to their heavy computation and memory requirements. In this paper, we propose LPIENet, a lightweight network for perceptual image enhancement, with the focus on deploying it on smartphones. Our experiments show that, with much fewer parameters and operations, our model can deal with the mentioned artifacts and achieve competitive performance compared with state-of-the-art methods on standard benchmarks. Moreover, to prove the efficiency and reliability of our approach, we deployed the model directly on commercial smartphones and evaluated its performance. Our model can process 2K resolution images under 1 second in mid-level commercial smartphones.
This paper is concerned with low-rank matrix optimization, which has found a wide range of applications in machine learning. This problem in the special case of matrix sensing has been studied extensively through the notion of Restricted Isometry Property (RIP), leading to a wealth of results on the geometric landscape of the problem and the convergence rate of common algorithms. However, the existing results can handle the problem in the case with a general objective function subject to noisy data only when the RIP constant is close to 0. In this paper, we develop a new mathematical framework to solve the above-mentioned problem with a far less restrictive RIP constant. We prove that as long as the RIP constant of the noiseless objective is less than $1/3$, any spurious local solution of the noisy optimization problem must be close to the ground truth solution. By working through the strict saddle property, we also show that an approximate solution can be found in polynomial time. We characterize the geometry of the spurious local minima of the problem in a local region around the ground truth in the case when the RIP constant is greater than $1/3$. Compared to the existing results in the literature, this paper offers the strongest RIP bound and provides a complete theoretical analysis on the global and local optimization landscapes of general low-rank optimization problems under random corruptions from any finite-variance family.
We develop a general method to study the Fisher information distance in central limit theorem for nonlinear statistics. We first construct completely new representations for the score function. We then use these representations to derive quantitative estimates for the Fisher information distance. To illustrate the applicability of our approach, explicit rates of Fisher information convergence for quadratic forms and the functions of sample means are provided. For the sums of independent random variables, we obtain the Fisher information bounds without requiring the finiteness of Poincar\'e constant. Our method can also be used to bound the Fisher information distance in non-central limit theorems.
We study a class of nonlinear eigenvalue problems of Schr\"{o}dinger type, where the potential is singular on a set of points. Such problems are widely present in physics and chemistry, and their analysis is of both theoretical and practical interest. In particular, we study the regularity of the eigenfunctions of the operators considered, and we propose and analyze the approximation of the solution via an isotropically refined $hp$ discontinuous Galerkin (dG) method. We show that, for weighted analytic potentials and for up-to-quartic polynomial nonlinearities, the eigenfunctions belong to analytic-type non homogeneous weighted Sobolev spaces. We also prove quasi optimal a priori estimates on the error of the dG finite element method; when using an isotropically refined $hp$ space the numerical solution is shown to converge with exponential rate towards the exact eigenfunction. We conclude with a series of numerical tests to validate the theoretical results.
The exact computation of the matching distance for multi-parameter persistence modules is an active area of research in computational topology. Achieving an easily obtainable exact computation of this distance would allow multi-parameter persistent homology to be a viable option for data analysis. In this paper, we provide theoretical results for the computation of the matching distance in two dimensions along with a geometric interpretation of the lines through parameter space realizing this distance. The crucial point of the method we propose is that it can be easily implemented.
We propose and analyze exact and inexact regularized Newton-type methods for finding a global saddle point of a \textit{convex-concave} unconstrained min-max optimization problem. Compared to their first-order counterparts, investigations of second-order methods for min-max optimization are relatively limited, as obtaining global rates of convergence with second-order information is much more involved. In this paper, we highlight how second-order information can be used to speed up the dynamics of dual extrapolation methods {despite inexactness}. Specifically, we show that the proposed algorithms generate iterates that remain within a bounded set and the averaged iterates converge to an $\epsilon$-saddle point within $O(\epsilon^{-2/3})$ iterations in terms of a gap function. Our algorithms match the theoretically established lower bound in this context and our analysis provides a simple and intuitive convergence analysis for second-order methods without requiring any compactness assumptions. Finally, we present a series of numerical experiments on synthetic and real data that demonstrate the efficiency of the proposed algorithms.
In domains where sample sizes are limited, efficient learning algorithms are critical. Learning using privileged information (LuPI) offers increased sample efficiency by allowing prediction models access to auxiliary information at training time which is unavailable when the models are used. In recent work, it was shown that for prediction in linear-Gaussian dynamical systems, a LuPI learner with access to intermediate time series data is never worse and often better in expectation than any unbiased classical learner. We provide new insights into this analysis and generalize it to nonlinear prediction tasks in latent dynamical systems, extending theoretical guarantees to the case where the map connecting latent variables and observations is known up to a linear transform. In addition, we propose algorithms based on random features and representation learning for the case when this map is unknown. A suite of empirical results confirm theoretical findings and show the potential of using privileged time-series information in nonlinear prediction.
The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by [Hassidim et al., 2017]. For a cardinality constraint, we propose an algorithm achieving a near-optimal $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation guarantee (for arbitrary $\varepsilon > 0$) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of [Singer et al., 2018]. For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.
A variety of deep neural networks have been applied in medical image segmentation and achieve good performance. Unlike natural images, medical images of the same imaging modality are characterized by the same pattern, which indicates that same normal organs or tissues locate at similar positions in the images. Thus, in this paper we try to incorporate the prior knowledge of medical images into the structure of neural networks such that the prior knowledge can be utilized for accurate segmentation. Based on this idea, we propose a novel deep network called knowledge-based fully convolutional network (KFCN) for medical image segmentation. The segmentation function and corresponding error is analyzed. We show the existence of an asymptotically stable region for KFCN which traditional FCN doesn't possess. Experiments validate our knowledge assumption about the incorporation of prior knowledge into the convolution kernels of KFCN and show that KFCN can achieve a reasonable segmentation and a satisfactory accuracy.