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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Backtracking Algorithm”
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.
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,…
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…
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.
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.
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.
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.
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…
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.
Backtracking gradient descent method for general functions, with applications to Deep Learningmath.OC
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…
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.
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 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.
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.
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.
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.
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.
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 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.
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.
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…
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.
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 of Graphs with the Bethe Hessiancond-mat.dis-nn
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…
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.
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…
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 -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 in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights 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.
In this study, we focus on the market clearing problem of Turkish day-ahead electricity market. We propose a mathematical model by extending the variety of bid types for different price regions. The commercial solvers may not find any feasible solution for the proposed problem in some instances within the given time li…
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.
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.
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-.
Optimization algorithms with momentum, e.g., (ADAM), have been widely used for building deep learning models due to the faster convergence rates compared with stochastic gradient descent (SGD). Momentum helps accelerate SGD in the relevant directions in parameter updating, which can minify the oscillations of parameter…
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.
VAV method optimizes learning rate for faster, stable SGD convergence.
problem Optimizing learning rate for efficient and stable machine learning models.
method Energy-based self-adaptive learning rate with auxiliary variable .
result VAV method achieves faster convergence and superior stability with larger learning rates.
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…
Optimistic method adapted for faster convex-concave min-max problems.
problem Solving convex-concave min-max optimization problems efficiently.
method Adaptive, line search-free second-order methods combining optimistic updates and second-order information.
result Achieves optimal convergence rate without line search or backtracking.
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.
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…
The paper proposes an efficient algorithm for solving Schatten- quasi-norm problems.
problem Finding low-rank solutions of linear inverse problems with Schatten- quasi-norm regularization.
method Dynamic proximal gradient algorithm using Cayley transformation and adaptive step size selection.
result The algorithm converges to a stationary point of the objective function under mild assumptions.
During recent years there has been an increased interest in stochastic adaptations of limited memory quasi-Newton methods, which compared to pure gradient-based routines can improve the convergence by incorporating second order information. In this work we propose a direct least-squares approach conceptually similar to…
We introduce the "NoBackTrack" algorithm to train the parameters of dynamical systems such as recurrent neural networks. This algorithm works in an online, memoryless setting, thus requiring no backpropagation through time, and is scalable, avoiding the large computational and memory cost of maintaining the full gradie…
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.