New method uses robust estimators for Newton's method in empirical risk minimization.
problem Improving robustness in empirical risk minimization.
method Robust Newton's method with gradient and Hessian replaced by robust estimators.
result Faster convergence rates in high-dimensional settings.
New matrix reveals cluster info in sparse directed graphs.
problem Analyzing cluster information in directed graphs.
method Proposed complex non-backtracking matrix integrating Hermitian adjacency matrix and non-backtracking matrix properties.
result The complex non-backtracking matrix holds cluster information, especially for sparse directed graphs.
New approach to counterfactual reasoning in AI and psychology.
problem Challenges to conventional counterfactual reasoning in AI and psychology.
method Formalizes a backtracking approach to counterfactuals within the SCM framework.
result First general account and algorithmisation of backtracking counterfactuals.
This paper presents VEC-NBT, a variation on the unsupervised graph clustering technique VEC, which improves upon the performance of the original algorithm significantly for sparse graphs. VEC employs a novel application of the state-of-the-art word2vec model to embed a graph in Euclidean space via random walks on the n…
DeepBC method computes backtracking counterfactuals in deep causal models.
problem Computing valid counterfactuals in complex causal models.
method DeepBC method using Langevin Monte Carlo or constrained optimization.
result DeepBC provides causally compliant, versatile, and modular counterfactuals.
A new graph neural network (NBA-GNN) avoids revisiting nodes to improve accuracy.
problem Redundancy in graph neural network updates causes over-squashing and inaccurate recognition.
method Proposes non-backtracking graph neural networks (NBA-GNN) that update messages without revisiting nodes.
result The NBA-GNN alleviates over-squashing and improves performance on graph benchmarks.
A major drawback of backpropagation through time (BPTT) is the difficulty of learning long-term dependencies, coming from having to propagate credit information backwards through every single step of the forward computation. This makes BPTT both computationally impractical and biologically implausible. For this reason,…
New Q-Newton's method avoids saddle points and converges quadratically.
problem Optimizing functions with saddle points and ensuring convergence guarantees.
method Modified New Q-Newton's method with Backtracking line search.
result Theorem for Morse functions: quadratic convergence to local minima.
Spectral method detects communities in sparse hypergraphs, achieving detection threshold.
problem Community detection in sparse hypergraphs.
method Non-backtracking operator and spectral approach.
result Spectral method achieves detection threshold for sparse HSBMs.
In many environments only a tiny subset of all states yield high reward. In these cases, few of the interactions with the environment provide a relevant learning signal. Hence, we may want to preferentially train on those high-reward states and the probable trajectories leading to them. To this end, we advocate for the…
Develops active intervals for geodesics in Teichmüller space.
problem Understanding geodesics in Teichmüller space with no backtracking.
method Defines active intervals for subsurfaces along geodesics in Thurston metric.
result Active intervals represent reparametrized quasi-geodesics in curve graphs with bounded movement outside.
We propose an L-BFGS optimization algorithm on Riemannian manifolds using minibatched stochastic variance reduction techniques for fast convergence with constant step sizes, without resorting to linesearch methods designed to satisfy Wolfe conditions. We provide a new convergence proof for strongly convex functions wit…
While Standard gradient descent is one very popular optimisation method, its convergence cannot be proven beyond the class of functions whose gradient is globally Lipschitz continuous. As such, it is not actually applicable to realistic applications such as Deep Neural Networks. In this paper, we prove that its backtra…
BRACE generates efficient counterfactual explanations by integrating causal reasoning.
problem Challenges in traditional counterfactual explanations, especially neglecting causal relationships.
method Backtracking counterfactuals with causal reasoning.
result Our method provides deeper insights into model outputs and is computationally efficient.
This paper improves NAQ method for faster convergence on Tensorflow.
problem Non-convex optimization problems.
method Modified Nesterov's Accelerated Quasi-Newton (NAQ) method on Tensorflow.
result mNAQ converges better and faster than first and second order optimizers.
Backtracking Gradient Descent method converges to critical points in Banach spaces.
problem Finding convergence conditions for Backtracking Gradient Descent in Banach spaces.
method Local Backtracking GD procedure with weak topology convergence.
result Weak convergence of sequence to critical points, no saddle points for generic choices.
Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the n…
We study the problem of learning a good search policy for combinatorial search spaces. We propose retrospective imitation learning, which, after initial training by an expert, improves itself by learning from \textit{retrospective inspections} of its own roll-outs. That is, when the policy eventually reaches a feasible…
Boosting Variational Inference improves posterior approximations with adaptive step-sizes.
problem Limited resources hinder the widespread adoption of Boosting Variational Inference.
method Characterized global curvature impact, introduced local curvature, and developed an approximate backtracking algorithm.
result New theoretical convergence rates and experimental validation demonstrate improved performance.
Unified spectral clustering for sparse networks with heterogeneous degrees.
problem Efficiently detecting communities in sparse networks with varying degrees.
method Developed a parametrized regularized Laplacian matrix for spectral clustering.
result Improved parametrization accounts for network heterogeneity and community hardness.
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a…
The study proves unique path lifting properties and their implications on quotient spaces and covering maps.
problem Understanding unique path lifting properties and their implications on quotient spaces and covering maps.
method The study uses group actions on R-trees and path lifting properties to prove the main results. result Every map of manifolds with the unique path lifting property is a covering map.
Motivated by community detection, we characterise the spectrum of the non-backtracking matrix B in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on n vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights {φu}u=1n with second moment $Φ…
Local search improves GFlowNets' ability to generate high-reward samples.
problem GFlowNets struggle with over-exploration in high-reward space.
method Local search focusing on high-reward samples via backtracking and reconstruction.
result Significant performance improvement in biochemical tasks.
New method detects communities in complex hypergraphs, matching theoretical limits.
problem Detecting communities in non-uniform hypergraphs with varying hyperedge sizes.
method Developed a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs.
result Achieved the Kesten-Stigum bound for weak recovery in a general class of non-uniform HSBMs.
Researchers compute large quantum invariants for 3-manifolds.
problem Computing large values of Turaev-Viro invariants for 3-manifolds.
method Optimized backtracking algorithm, lattice point counting, preprocessing strategy, multi-precision arithmetics.
result Experimentally verified improvements over state-of-the-art implementations, supporting volume conjecture.
There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the non-backtracking matrix. However they are far from being tight when the network is sparse and displays clustering or transitivity, which is repr…
New scheme adapts batch size for faster variance-reduced algorithms.
problem Slowness of variance-reduced algorithms due to large batch size.
method Eliminates backtracking line search, adapts batch size via history stochastic gradients.
result Significantly reduces overall complexity for SVRG and SARAH/SPIDER.
New findings support a new community recovery threshold for Stochastic Block Model with many communities.
problem Recovering communities in Stochastic Block Model with more than sqrt(n) communities.
method Counting specific motifs to achieve polynomial-time community recovery above a new threshold.
result LDP fails below the new threshold, but polynomial-time recovery is possible above it.
New method quantifies network cycles to enhance community detection.
problem Challenges in detecting communities in networks, especially in sparse graphs.
method Renewal non-backtracking random walks (RNBRW) to quantify cyclic structure.
result RNBRW improves community detection algorithms, especially in sparse graphs.
This paper allows unbounded learning rates in gradient descent for better convergence.
problem Proving convergence of gradient descent with unbounded learning rates.
method Introducing a function h(t) to control the learning rates and proving convergence under Armijo's condition.
result Convergence of the sequence {x_n} is proven under specific conditions on the cost function f.
The paper develops methods for unconstrained optimization on Riemannian manifolds.
problem Optimization on Riemannian manifolds with general functions.
method Developed explicit versions of gradient descent and Newton's method for Riemannian optimization.
result The algorithms either converge to a local minimum or diverge to infinity, depending on the function and manifold properties.
Improves generative models by optimizing rewards and sample editing.
problem Efficiently generating high-reward samples with structural constraints.
method Introduces MDM-VGB, a discrete diffusion sampler that augments unmasking generation with reward-guided remasking.
result MDM-VGB achieves quadratic complexity and robustness to noise, outperforming heuristics like best-of-N. New methods solve MI problems with locally Lipschitz operators, improving solution efficiency.
problem Solving monotone inclusions with locally Lipschitz continuous operators.
method Primal-dual extrapolation methods using backtracking line search.
result Improved operation complexity for solving MI problems.
HollowFlow speeds up likelihood evaluation for large-scale models.
problem Prohibitive scaling of sample likelihood computations in flow-based models.
method Introduces HollowFlow, a flow-based generative model using a NoBGNN with a block-diagonal Jacobian structure.
result Achieves up to O(n^2) speed-up in likelihood evaluation for large systems.
We show that the driving force behind the regularizing effect of Laplacian smoothing on surface elements is the popular mean ratio quality measure. We use these insights to provide natural generalizations to polygons and polyhedra. The corresponding functions measuring the quality of meshes are easily seen to be convex…
Stochastic approximation is one of the effective approach to deal with the large-scale machine learning problems and the recent research has focused on reduction of variance, caused by the noisy approximations of the gradients. In this paper, we have proposed novel variants of SAAG-I and II (Stochastic Average Adjusted…
Paper introduces a privacy-preserving line search method for optimization.
problem Optimization performance depends on step size tuning, which is difficult and privacy-sensitive.
method Introduces a stochastic adaptive line search algorithm that satisfies differential privacy.
result The algorithm efficiently uses privacy budget and outperforms existing private optimizers.
Transformer learns to search through reinforcement learning, mimicking DFS.
problem Understanding how transformers learn search capabilities in RL.
method Two-head transformer, depth-wise curriculum, discounted returns.
result Transformer policy generalizes depth and prioritizes high-probability branches.
Paper tackles sample-efficient RL for linearly realizable MDPs with limited revisiting.
problem Sample-efficient reinforcement learning for linearly realizable MDPs with limited revisiting.
method Develops a new sampling protocol that allows for backtracking and revisiting states in a controlled manner.
result Achieves polynomial sample complexity scaling with feature dimension, horizon, and inverse sub-optimality gap.
We consider the problem of clustering partially labeled data from a minimal number of randomly chosen pairwise comparisons between the items. We introduce an efficient local algorithm based on a power iteration of the non-backtracking operator and study its performance on a simple model. For the case of two clusters, w…
We consider the problem of minimizing a difference-of-convex (DC) function, which can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous possibly nonsmooth concave function. We refine the convergence analysis in [38] for the proximal DC algorithm …
Paper uses RL and diffusion models to solve Bayesian inverse problems.
problem Bayesian inverse problems with latent biases.
method Relative Trajectory Balance (RTB) for RL, conditional diffusion models, off-policy backtracking exploration.
result RTB improves diffusion model posteriors for inverse problems.
New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
New findings on community recovery in SBM with many communities.
problem Determining community recovery conditions in SBM with more than sqrt(n) communities.
method Constructing motifs and counting them to prove community recovery above the proposed threshold.
result Proving community recovery above the proposed threshold in SBM with K >= sqrt(n) communities.
Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on th…
We say that a subset S⊆FN is \emph{spectrally rigid} if whenever T1,T2∈cvN are points of the (unprojectivized) Outer space such that ∣∣g∣∣T1=∣∣g∣∣T2 for every g∈S then T1=T2 in $\cvn$. It is well-known that FN itself is spectrally rigid; it also follows from the result of Smil…
Efficient algorithms solve joint graphical lasso problems.
problem Learning graphical models from sparse data.
method Proximal gradient procedures with ADMM backtracking option.
result Proposed algorithms achieve high accuracy and precision.