arXiv research

ExDAG solves DAG learning problems with low structural Hamming distance.

Unified formula for training dynamics of linear networks combining lazy and balanced regimes.

Counterfactual regret minimization (CFR) is the most popular algorithm on solving two-player zero-sum extensive games with imperfect information and achieves state-of-the-art performance in practice. However, the performance of CFR is not fully understood, since empirical results on the regret are much better than the …

New algorithm reduces regret and constraint violation in online convex optimization with predictions.

We propose a new scalable algorithm for holistic linear regression building on Bertsimas & King (2016). Specifically, we develop new theory to model significance and multicollinearity as lazy constraints rather than checking the conditions iteratively. The resulting algorithm scales with the number of samples $n$ in th…

Stochastic principal component analysis (SPCA) has become a popular dimensionality reduction strategy for large, high-dimensional datasets. We derive a simplified algorithm, called Lazy SPCA, which has reduced computational complexity and is better suited for large-scale distributed computation. We prove that SPCA and …

Lazy neural networks are vulnerable to adversarial attacks.

A new method simulates a lazy version of a Markov chain for empirical inference.

Study introduces a new investment strategy model using lazy factor and probability weights.

Gradient descent can find better tensor decompositions than lazy training in over-parameterized settings.

Lazy, perfectly informed investors trade infrequently due to costs.

New private algorithms for online learning improve regret in high privacy regimes.

Lazy Gradient Descent outperforms existing polytope algorithms in pseudo-regret.

Quantum machine learning faces 'laziness' and 'barren plateaus', but noise can mitigate the latter.

Deep networks prioritize easier examples over harder ones, leading to faster training.

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O\left(\frac{1}{\varepsilon^2}\right)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…

New method for causal discovery in high dimensions with confounder blanket assumption.

Grokking occurs when neural networks transition from lazy to rich training dynamics, fitting initial features before generalizing.

Study shows optimal model performance at critical level of feature learning.

We discuss the approximation of the value function for infinite-horizon discounted Markov Reward Processes (MRP) with nonlinear functions trained with the Temporal-Difference (TD) learning algorithm. We first consider this problem under a certain scaling of the approximating function, leading to a regime called lazy tr…

Study on network-valued processes with asynchronous updates, proving consistency in community and changepoint estimation.

New method converts and optimizes sampling schedules for generative models.

Clapping reduces memory usage in distributed optimization by reusing data samples.

We propose a framework for solving high-dimensional Bayesian inference problems using \emph{structure-exploiting} low-dimensional transport maps or flows. These maps are confined to a low-dimensional subspace (hence, lazy), and the subspace is identified by minimizing an upper bound on the Kullback--Leibler divergence …

ABC algorithms involve a large number of simulations from the model of interest, which can be very computationally costly. This paper summarises the lazy ABC algorithm of Prangle (2015), which reduces the computational demand by abandoning many unpromising simulations before completion. By using a random stopping decis…

Study allocates resources to strategic agents while balancing cost and incentives.

We explore how neural networks train to zero loss, focusing on initial scale.

A method learns common bias for multiple low-variance tasks without hyper-parameter tuning.

Study on adversarial robustness in neural networks across initialization and training phases.

Transformers learn rich in-context dependencies efficiently.

We study Bayesian optimal control of a general class of smoothly parameterized Markov decision problems. Since computing the optimal control is computationally expensive, we design an algorithm that trades off performance for computational efficiency. The algorithm is a lazy posterior sampling method that maintains a d…

Analyzes neural networks using linear models to understand their behavior.

LAZO reduces query complexity and variance in ZO methods.

LazyDINO efficiently solves high-dimensional Bayesian inverse problems with fast and scalable solutions.

Two distinct limits for deep learning have been derived as the network width $h\rightarrow \infty$, depending on how the weights of the last layer scale with $h$. In the Neural Tangent Kernel (NTK) limit, the dynamics becomes linear in the weights and is described by a frozen kernel $Θ$. By contrast, in the Mean-Field …

Study on rich regime training in deep learning, finding active parameters in bottom layers.

Auto-CEI improves LLM reasoning by balancing assertiveness and conservativeness.

Mirror flow in shallow neural networks shows similar implicit bias to gradient flow, with key differences in curvature penalties.

Use simplified layerwise linear models to understand neural dynamics.

The typical algorithmic problem in viral marketing aims to identify a set of influential users in a social network, who, when convinced to adopt a product, shall influence other users in the network and trigger a large cascade of adoptions. However, the host (the owner of an online social platform) often faces more con…

ExDBN learns dynamic Bayesian networks using mixed-integer programming.

Exact solutions reveal how unbalanced initializations promote rapid feature learning in neural networks.

Transformers capture combinatorial tasks with bounded error and logarithmic sample dependence.

Deep networks generalize well even when they fit training data perfectly, thanks to overparametrization.

Study on how adversarial training affects neural network kernels and robustness.

Functional AD for Weil algebra computations.

The need for labour intensive pixel-wise annotation is a major limitation of many fully supervised learning methods for segmenting bioimages that can contain numerous object instances with thin separations. In this paper, we introduce a deep convolutional neural network for microscopy image segmentation. Annotation iss…

New method trains shallow neural networks with subquadratic width scaling.