Given the increasing scale of model sizes, efficient training strategies like gradual stacking have garnered interest. Stacking enables efficient training by gradually growing the depth of a model in stages and using layers from a smaller model in an earlier stage to initialize the next stage. Although efficient for training, the model biases induced by such growing approaches are largely unexplored. In this work, we examine this fundamental aspect of gradual stacking, going beyond its efficiency benefits. We propose a variant of gradual stacking called MIDAS that can speed up language model training by up to 40\%. Furthermore we discover an intriguing phenomenon: MIDAS is not only training-efficient but surprisingly also has an inductive bias towards improving downstream tasks, especially tasks that require reasoning abilities like reading comprehension and math problems, despite having similar or slightly worse perplexity compared to baseline training. To further analyze this inductive bias, we construct {\em reasoning primitives} – simple synthetic tasks that are building blocks for reasoning – and find that a model pretrained with stacking is significantly better than standard pretraining on these primitives, with and without fine-tuning. This provides stronger and more robust evidence for this inductive bias towards reasoning. These findings of training efficiency and inductive bias towards reasoning are verified at 1B, 2B and 8B parameter language models. Finally, we conjecture the underlying reason for this inductive bias by exploring the connection of stacking to looped models and provide strong supporting empirical analysis.

Large deep learning models have achieved state-of-the-art performance across various natural language processing (NLP) tasks and demonstrated remarkable few-shot learning performance. However, training them is often challenging and resource-intensive. In this paper, we study an efficient approach to train language models using few-shot learners. We show that, by leveraging the fast learning nature of few-shot learners, one can train language models efficiently in a stagewise manner. Our main insight is that stacking a good few-shot learner on a good small language model provides a good initializer for a larger language model. Using this insight and building upon progressive stacking approaches, we develop novel approaches for training such networks in a stagewise manner. Furthermore, we also provide a theoretical framework and accompanying empirical studies to support our insights, thereby creating a theoretical foundation for progressive stacking. Finally, we provide empirical results to demonstrate the effectiveness of our approach in reducing the training time of few-shot learners.

Batch Normalization (BN) uses mini-batch statistics to normalize the activations during training, introducing dependence between mini-batch elements. This dependency can hurt the performance if the mini-batch size is too small, or if the elements are correlated. Several alternatives, such as Batch Renormalization and Group Normalization (GN), have been proposed to address this issue. However, they either do not match the performance of BN for large batches, or still exhibit degradation in performance for smaller batches, or introduce artificial constraints on the model architecture. In this paper we propose the Filter Response Normalization (FRN) layer, a novel combination of a normalization and an activation function, that can be used as a replacement for other normalizations and activations. Our method operates on each activation channel of each batch element independently, eliminating the dependency on other batch elements. Our method outperforms BN and other alternatives in a variety of settings for all batch sizes. FRN layer performs 0.7-1.0% better than BN on top-1 validation accuracy with large mini-batch sizes for Imagenet classification using InceptionV3 and ResnetV2-50 architectures. Further, it performs >1% better than GN on the same problem in the small mini-batch size regime. For object detection problem on COCO dataset, FRN layer outperforms all other methods by at least 0.3-0.5% in all batch size regimes.

To understand the dynamics of training in deep neural networks, we study the evolution of the Hessian eigenvalue density throughout the optimization process. In non-batch normalized networks, we observe the rapid appearance of large isolated eigenvalues in the spectrum, along with a surprising concentration of the gradient in the corresponding eigenspaces. In a batch normalized network, these two effects are almost absent. We give a theoretical rationale to partially explain these phenomena. As part of this work, we adapt advanced tools from numerical linear algebra that allow scalable and accurate estimation of the entire Hessian spectrum of ImageNet-scale neural networks; this technique may be of independent interest in other applications.

In this paper, we characterize the joint coverage probability at two spatial locations in a cellular network. In particular, modeling the locations of cellular base stations (BSs) as a Poisson Point Process (PPP), we study interference correlation at two spatial locations L1and L2separated by a distance v, when user follows closest BS association policy at both spatial locations and moves from L1to L2. With this user displacement, two scenarios can occur: i) the user is handed off to a new serving BS at L2, or ii) no handoff occurs and the user is served by the same BS at both locations. After providing intermediate results such as probability of handoff and distance distributions of the serving BS at the two user locations, we derive exact expressions for the joint coverage probability for any distance separation v. The exact analysis is not straightforward and involves a careful treatment of the neighborhood of the two spatial locations and the resulting handoff scenarios. As expected, joint coverage probability decreases with the separation in the two locations.

This paper provides an analytical framework with foundations in stochastic geometry to characterize the spatiotemporal interference correlation as well as the joint coverage probability at two spatial locations in a cellular network. In particular, modeling the locations of cellular base stations (BSs) as a Poisson point process, we study interference correlation at two spatial locations ℓ1and ℓ2separated by a distance v, when the user follows the closest BS association policy at both spatial locations and moves from ℓ1to ℓ2. With this user displacement, two scenarios can occur: i) the user is handed off to a new serving BS at ℓ2, or ii) no handoff occurs and the user is served by the same BS at both locations. After providing intermediate results, such as probability of handoff and distance distributions of the serving BS at the two user locations, we use them to derive exact expressions for spatio-temporal interference correlation coefficient and joint coverage probability for any distance separation v. We also study two different handoff strategies: i) handoff skipping, and ii) conventional handoffs, and derive the expressions of joint coverage probability for both strategies. The exact analysis is not straightforward and involves a careful treatment of the neighborhood of the two spatial locations and the resulting handoff scenarios. To provide analytical insights, we also provide easy-to-use expressions for two special cases: i) static user (v = 0) and ii) highly mobile user (v → ∞). As expected, our analysis shows that the interference correlation and joint coverage probability decrease with increasing v, with v → ∞ corresponding to a completely uncorrelated scenario. Further design insights are also provided by studying the effect of few network/channel parameters, such as BS density and path loss on the interference correlation.

Traditional upsampling methods apply spatial-invariant filtering across the entire image for efficiency, but often produce unsatisfactory artifacts around the edges. We propose a novel image upsampling algorithm that preserves the image structure, particularly around the edges, better than previous techniques. Our method computes a spline approximation to the edges in the image via bitmap tracing. A scaled version of the traced image is then used as a guide for joint bilateral up-sampling to produce the final result. Our method is easy to implement and the visual fidelity and quality of our results compare favorably to state-of-the-art techniques.

We propose a method to accelerate Yang's real-timeO(1) bilateral filtering algorithm, based on the observation that in the original algorithm, some of the computation can be strategically eliminated. To identify such computation, the algorithm steps are analyzed in conjunction with its recursive Gaussian filtering component. By block partitioning the image, the procedure to isolate these unnecessary computation is simplified, and the proposed algorithm only needs to skip some of the image blocks when performing recursive linear filtering. The resultant accelerated algorithm is able to achieve 1.5~5 times speedup, depending on the image statistics and the filtering parameters. The proposed algorithm only marginally degrades the accuracy of the filtering, and the simplicity and small memory footprint of Yang's original algorithm are largely maintained.

Abstract Optimizing a stress model is a natural technique for drawing graphs: one seeks an embedding into Rd which best preserves the induced graph metric. Current approaches to solving the stress model for a graph with |𝒱| nodes and |ɛ| edges require the full all‐pairs shortest paths (APSP) matrix, which takes O(|𝒱|2 log |ɛ|+|𝒱‖ɛ|) time and O(|𝒱|2) space. We propose a novel algorithm based on a low‐rank approximation to the required matrices. The crux of our technique is an observation that it is possible to approximate the full APSP matrix, even when only a small subset of its entries are known. Our algorithm takes time O(k|𝒱|+|𝒱|log|𝒱|+|ɛ|) per iteration with a preprocessing time of O(k3+ k(|ɛ|+|𝒱| log |𝒱|) + k2|𝒱|) and memory usage of O(k|𝒱|), where a user‐defined parameter k trades off quality of approximation with running time and space. We give experimental results which show, to the best of our knowledge, the largest (albeit approximate) full stress model based layouts to date.

Multidimensional distributions are often used in data mining to describe and summarize different features of large datasets. It is natural to look for distinct classes in such datasets by clustering the data. A common approach entails the use of methods like k-means clustering. However, the k-means method inherently relies on the Euclidean metric in the embedded space and does not account for additional topology underlying the distribution.

In this paper, we describe a system for approximate shape matching and symmetry (rotation and reflection) detection of geometric shapes represented as point clouds. Rather than using the least-squares distance as a measure of similarity between shapes, we use the Hausdorff distance between point sets as the underlying shape metric. This allows us to exploit methods from geometric pattern matching to return symmetries and rigid transformation matches with guaranteed error bounds on the quality of our solution. The approximation is determined by intuitive user-specified input precision and distance threshold parameters. Another important feature of our method is that it leverages FFT-based techniques for string matching to compute all approximate symmetries simultaneously. Our algorithm is simple to implement and is efficient; we present a detailed experimental study.

In this paper, we study the problem of recovering the camera motion in a multiview setting given observation of tracked features in a three-dimensional environment. We propose a novel algorithm to simultaneously recover the pose (orientation and translation to within a scale) of every camera directly using a manifold optimization approach. Our contributions are four-fold. We present a new analytic method based on singular value decomposition that yields a closed-form solution for the multiview motion estimation problem in the noise-free case. Secondly, we use this method to derive a good initial estimate of a solution in the noisy case. This initialization step may, independently, be of use in any general iterative scheme. Thirdly, we present an iterative scheme based on Gauss-Newton's method on a product manifold that exhibits local quadratic convergence. Finally, we also present a simple linear least squares approach to recover the individual camera centers from relative translations obtained after the iteration process. Our algorithm has been implemented, and we demonstrate the efficacy of our scheme on both synthetic data and real data.

We present a simple algorithm for approximating the free configuration space of robots with low degrees of freedom (DOFs). We represent the free space as an arrangement of contact surfaces. We approximate the free space using an adaptive volumetric grid that is computed by performing simple geometric tests on the contact surfaces. We use an isosurface extraction algorithm to compute a piecewise-linear approximation to the boundary of the free space. We prove that our approximation is topologically equivalent to the exact free space boundary. We also ensure that our approximation is geometrically close to the exact free space boundary by bounding its two-sided Hausdorff error. We have applied our algorithm to compute the free configuration space for the following instances: (1) a 2D polygonal robot with translational and rotational DOFs navigating among polygonal obstacles, and (2) a 3D polyhedral robot translating among polyhedral obstacles. In practice, our algorithm works well on robots with three DOFs

In this paper, we present an algorithm that performs simplification of large geographical maps through a novel use of graphics hardware. Given a map as a collection of non‐intersecting chains and a tolerance parameter for each chain, we produce a simplified map that resembles the original map, satisfying the condition that the distance between each point on the simplified chain and the original chain is within the given tolerance parameter, and that no two chains intersect. In conjunction with this, we also present an out‐of‐core system for interactive visualization of these maps. We represent the maps hierarchically and employ different pruning strategies to accelerate the rendering. Our algorithm uses a parallel approach to do rendering as well as fetching data from the disk in a synchronous manner. We have applied our algorithm to a gigabyte sized map dataset. The memory overhead of our algorithm (the amount of main memory it requires) is output sensitive and is typically tens of megabytes, much smaller than the actual data size.

We present visibility computation and data organization algorithms that enable high-fidelity walkthroughs of large 3D geometric data sets. A novel feature of our walkthrough system is that it performs work proportional only to the required detail in visible geometry at the rendering time. To accomplish this, we use a precomputation phase that efficiently generates per cell vLOD: the geometry visible from a view-region at the right level of detail. We encode changes between neighboring cells' vLODs, which are not required to be memory resident. At the rendering time, we incrementally construct the vLOD for the current view-cell and render it. We have a small CPU and memory requirement for rendering and are able to display models with tens of millions of polygons at interactive frame rates with less than one pixel screen-space deviation and accurate visibility.

Shadow mapping is a technique for doing real-time shadowing. Recent work has shown that shadow mapping hardware can be used as a second depth test in addition to the z-test. In this paper, we explore the computational power provided by this second depth test by examining the problem of rendering objects described as CSG (Constructive Solid Geometry) expressions. We provide an algorithm that asymptotically improves the number of rendering passes required to display a CSG object by a factor of n by exploiting the two-sided depth test. Interestingly, a matching lower bound can be proved demonstrating that our algorithm is optimal.

We present improved subdivision and isosurface reconstruction algorithms for polygonizing implicit surfaces and performing accurate geometric operations. Our improved reconstruction algorithm uses directed distance fields (Kobbelt et al., 2001) to detect multiple intersections along an edge, separates them into components and reconstructs an isosurface locally within each components using the dual contouring algorithm (Ju et al., 2002). It can reconstruct thin features without creating handles and results in improved surface extraction from volumetric data. Our subdivision algorithm takes into account sharp features that arise from intersecting surfaces or Boolean operations and generates an adaptive grid such that each voxel has at most one sharp feature. The subdivision algorithm is combined with our improved reconstruction algorithm to compute accurate polygonization of Boolean combinations or offsets of complex primitives that faithfully reconstruct the sharp features. We have applied these algorithms to polygonize complex CAD models designed using thousands of Boolean operations on curved primitives.

Many geometric problems like generalized Voronoi diagrams, medial axis computations and boundary evaluation involve computation and manipulation of non-linear algebraic primitives like curves and surfaces. The algorithms designed for these problems make decisions based on signs of geometric predicates or on the roots of polynomials characterizing the problem. The reliability of the algorithm depends on the accurate evaluation of these signs and roots. In this paper, we present a {\em naive precision-driven computational model} to perform these computations reliably and demonstrate its effectiveness on a certain class of problems like sign of determinants with rational entries, boundary evaluation and curve arrangements. We also present a novel algorithm to compute all the roots of a univariate polynomial to any desired accuracy. The computational model along with the underlying number representation, precision-driven arithmetic and all the algorithms are implemented as part of a stand-alone software library, PRECISE.

In this paper, we present an algorithm and a system to perform dynamic view dependent simplification of large geographical maps through a novel use of graphics hardware. Given a map as a collection of non-intersecting chains and a tolerance parameter for each chain, we produce a simplified map that resembles the original map, satisfying the condition that the distance between each point on the simplified chain and the original chain is within the given tolerance parameter, and that no two chains intersect. We also present an interactive map visualization system which uses frame-to-frame coherence to perform dynamic view-dependent simplification. Our initial results indicate that we get a 3-4 fold increase in the frame rates using our simplification algorithm on maps with 1.5-2 million vertices on an SGI Onyx workstation.

We present a fast, memory efficient algorithm that generates a manifold triangular mesh S passing through a set of unorganized points P R 3. Nothing is assumed about the geometry, topology or presence of boundaries in the data set except that P is sampled from a real manifold surface. The speed of our algorithm is derived from a projection‐based approach we use to determine the incident faces on a point. We define our sampling criteria to sample the surface and guarantee a topologically correct mesh after surface reconstruction for such a sampled surface. We also present a new algorithm to find the normal at a vertex, when the surface is sampled according our given criteria. We also present results of our surface reconstruction using our algorithm on unorganized point clouds of various models.

We present MAPC, a library for exact representation of geometric objects-specifically points and algebraic curves in the plane.Our library makes use of several new algorithms, which we present here, including methods for fmding the sign of a determinant, fmding intersections between two curves, and breaking a curve into monotonic segments.These algorithms are used to speed up the underlying computations.The library provides C++ classes that can be used to easily instantiate, manipulate, and perform queries on points and curves in the plane.The point classes can be used to represent points known in a variety of.ways (e.g. as exact rational coordinates or algebraic numbers) in a unified manner.The curve class can be used to represent a portion of an algebraic curve.We have used MAPC for applications dealing with algebraic points and curves, including sorting points along a curve, computing arrangement of curves, medial axis computations, and boundary' evaluation on curved primitives.As compared to earlier algorithms and implementations utilizing exact arithmetic, our library is able to achieve more than an order of magnitude improvement in performance.

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree, that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre‐processing. At runtime it dynamically computes a tight fitting axis‐aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off‐line and on‐line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.

We present algorithms and systems for interactive boundary computation of Boolean combinations of sculptured solids. The algorithm is applicable to all spline solids and computes an accurate boundary representation. To speed up the computation, the algorithm exploits parallelism at all stages. It has been implemented on a multi‐processor SGI and takes one second on average per boolean operation to compute the boundary of high degree primitives. The system has also been integrated with an immersive design and manipulation environment. The resulting system is able to interactively evaluate boundaries of the models, display them for model validation and place them at appropriate position using collision detection algorithms.

We present an efficient algorithm to compute the intersection of algebraic and NURBS surfaces. Our approach is based on combining the marching methods with the algbraic formulation. In particular, we propose and matrix computations. We present algorithms to compute a start point on each component of the intersection curve (both open and closed components), detect the presence of singularities, and find all the curve branches near the singularity. We also suggest methods to compute the step size during tracing to prevent component jumping. The algorithm runs an order of magnitude faster than previously published robust algorithms. The complexity of the algorithm is output sensitive.

No abstract available.

: We present efficient algorithms based on a combination of numeric and symbolic techniques for evaluating one-dimensional algebraic sets in a subset of the real domain. Given a description of a one-dimensional algebraic set, we compute its projection using resultants. We represent the resulting plane curve as a singular set of a matrix polynomial as opposed to roots of a bivariate polynomial. Given the matrix formulation, we make use of algorithms from numerical linear algebra to compute start points on all the components, partition the domain such that each resulting region contains only one component and evaluate it accurately using marching methods. We also present techniques to handle singularities for well-conditioned inputs. The resulting algorithm is iterative and its complexity is output sensitive. It has been implemented in floating-point arithmetic and we highlight its performance in the context of computing intersection of high-degree algebraic surfaces. 1 Introduction The...