检索结果-内蒙古大学图书馆

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Hanzhi Renmin University of China Beijing China

We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node t in an undirected graph G comprising n nodes and m edges, BackMC accurately estimates the PageRank score of node t while assuring a small relative error and a high success probability. The worst-case computational complexity of BackMC is upper bounded by (formula presented) , where dmin denotes the minimum degree of G, and dt denotes the degree of t, respectively. Compared to the previously best upper bound of (formula presented) (VLDB’23), which is derived from a significantly more complex algorithm and analysis, our BackMC improves the computational complexity for this problem by a factor of (formula presented) with a much simpler algorithm. Furthermore, we establish a matching lower bound of (formula presented) for any algorithm that attempts to solve the problem of local PageRank estimation, demonstrating the theoretical optimality of our BackMC. We conduct extensive experiments on various large-scale real-world and synthetic graphs, where BackMC consistently shows superior performance. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

HOW MANY CONTINUOUS MEASUREMENTS ARE NEEDED TO LEARN A VECTOR?

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Krieg, David Novak, Erich Ullrich, Mario University of Passau Germany Friedrich Schiller University Jena Germany Johannes Kepler University Linz Austria

One can recover vectors from Rm with arbitrary precision, using only ⌈log2(m+1)⌉+1 continuous measurements that are chosen adaptively. This surprising result is explained and discussed, and we present applications to ... 详细信息

关键词： optimization algorithms

Dynamic and Distributed Online Convex optimization for Demand Response of Commercial Buildings

学校读者我要写书评

暂无评论

IEEE CONTROL SYSTEMS LETTERS 2020年第3期4卷 632-637页

作者： Lesage-Landry, Antoine Callaway, Duncan S. Univ Calif Berkeley Energy & Resources Grp Berkeley CA 94720 USA

We extend the regret analysis of the online distributed weighted dual averaging (DWDA) algorithm from Hosseini et al. to the dynamic setting and provide the tightest dynamic regret bound known to date with respect to the time horizon for a distributed online convex optimization (OCO) algorithm. Our bound is linear in the cumulative difference between consecutive optima and does not depend explicitly on the time horizon. We use dynamic-online DWDA (D-ODWDA) and formulate a performance-guaranteed distributed online demand response approach for heating, ventilation, and air-conditioning (HVAC) systems of commercial buildings. We show the performance of our approach for fast timescale demand response in numerical simulations and obtain demand response decisions that closely reproduce the centralized optimal ones.

关键词： Heuristic algorithms Buildings Power system dynamics Fans Real-time systems Convex functions Load management optimization algorithms machine learning power systems

Exploring the Performance-Reproducibility Trade-off in Quality-Diversity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Flageat, Manon Janmohamed, Hannah Lim, Bryan Cully, Antoine Adaptive and Intelligent Robotics Lab Department of Computing Imperial College London United Kingdom

Quality-Diversity (QD) algorithms have exhibited promising results across many domains and applications. However, uncertainty in fitness and behaviour estimations of solutions remains a major challenge when QD is used in complex real-world applications. While several approaches have been proposed to improve the performance in uncertain applications, many fail to address a key challenge: determining how to prioritise solutions that perform consistently under uncertainty, in other words, solutions that are reproducible. Most prior methods improve fitness and reproducibility jointly, ignoring the possibility that they could be contradictory objectives. For example, in robotics, solutions may reliably walk at 90% of the maximum velocity in uncertain environments, while solutions that walk faster are also more prone to falling over. As this is a trade-off, neither one of these two solutions is "better" than the other. Thus, algorithms cannot intrinsically select one solution over the other, but can only enforce given preferences over these two contradictory objectives. In this paper, we formalise this problem as the performance-reproducibility trade-off for uncertain QD. We propose four new a-priori QD algorithms that find optimal solutions for given preferences over the trade-offs. We also propose an a-posteriori QD algorithm for when these preferences cannot be defined in advance. Our results show that our approaches successfully find solutions that satisfy given preferences. Importantly, by simply accounting for this trade-off, our approaches perform better than existing uncertain QD methods. This suggests that considering the performance-reproducibility trade-off unlocks important stepping stones that are usually missed when only performance is optimised. © 2024, CC BY.

关键词： optimization algorithms

(Almost) Smooth Sailing: Towards Numerical Stability of Neural Networks Through Differentiable Regularization of the Condition Number

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Nenov, Rossen Haider, Daniel Balazs, Peter Acoustics Research Institute Austrian Academy of Sciences Vienna Austria Department of Mathematics University of Vienna Vienna Austria

Maintaining numerical stability in machine learning models is crucial for their reliability and performance. One approach to maintain stability of a network layer is to integrate the condition number of the weight matrix as a regularizing term into the optimization algorithm. However, due to its discontinuous nature and lack of differentiability the condition number is not suitable for a gradient descent approach. This paper introduces a novel regularizer that is provably differentiable almost everywhere and promotes matrices with low condition numbers. In particular, we derive a formula for the gradient of this regularizer which can be easily implemented and integrated into existing optimization algorithms. We show the advantages of this approach for noisy classification and denoising of MNIST images. © 2024, CC BY.

关键词： optimization algorithms

A Full Adagrad algorithm with O(Nd) operations

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Godichon-Baggioni, Antoine Lu, Wei Portier, Bruno Sorbonne Université 4 Place Jussieu Paris75005 France Laboratoire de Mathématiques INSA Rouen Normandie BP 08 - Avenue de l’Université Saint-Etienne du Rouvray76800 France

A novel approach is given to overcome the computational challenges of the full-matrix Adaptive Gradient algorithm (Full AdaGrad) in stochastic optimization. By developing a recursive method that estimates the inverse of the square root of the covariance of the gradient, alongside a streaming variant for parameter updates, the study offers efficient and practical algorithms for large-scale applications. This innovative strategy significantly reduces the complexity and resource demands typically associated with full-matrix methods, enabling more effective optimization processes. Moreover, the convergence rates of the proposed estimators and their asymptotic efficiency are given. Their effectiveness is demonstrated through numerical studies. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Elliptical Wishart distributions: Information geometry, maximum likelihood estimator, performance analysis and statistical learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ayadi, Imen Bouchard, Florent Pascal, Frédéric Université Paris-Saclay CNRS CentraleSupélec Laboratoire des Signaux et Systèmes 3 rue Joliot-Curie Gif-sur-Yvette91190 France

This paper deals with Elliptical Wishart distributions - which generalize the Wishart distribution - in the context of signal processing and machine learning. Two algorithms to compute the maximum likelihood estimator (MLE) are proposed: a fixed point algorithm and a Riemannian optimization method based on the derived information geometry of Elliptical Wishart distributions. The existence and uniqueness of the MLE are characterized as well as the convergence of both estimation algorithms. Statistical properties of the MLE are also investigated such as consistency, asymptotic normality and an intrinsic version of Fisher efficiency. On the statistical learning side, novel classification and clustering methods are designed. For the t-Wishart distribution, the performance of the MLE and statistical learning algorithms are evaluated on both simulated and real EEG and hyperspectral data, showcasing the interest of our proposed methods. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

High-Dimensional Sparse Data Low-rank Representation via Accelerated Asynchronous Parallel Stochastic Gradient Descent

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hu, Qicong Wu, Hao College of Computer and Information Science Southwest University Chongqing China

Data characterized by high dimensionality and sparsity are commonly used to describe real-world node interactions. Low-rank representation (LR) can map high-dimensional sparse (HDS) data to low-dimensional feature spaces and infer node interactions via modeling data latent associations. Unfortunately, existing optimization algorithms for LR models are computationally inefficient and slowly convergent on large-scale datasets. To address this issue, this paper proposes an Accelerated Asynchronous Parallel Stochastic Gradient Descent (A2PSGD) for High-Dimensional Sparse Data Low-rank Representation with three fold-ideas: a) establishing a lock-free scheduler to simultaneously respond to scheduling requests from multiple threads;b) introducing a greedy algorithm-based load balancing strategy for balancing the computational load among threads;c) incorporating Nesterov's accelerated gradient into the learning scheme to accelerate model convergence. Empirical studies show that A2PSGD outperforms existing optimization algorithms for HDS data LR in both accuracy and training time. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

The Implicit Bias of Gradient Descent on Separable Multiclass Data

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ravi, Hrithik Scott, Clayton Soudry, Daniel Wang, Yutong University of Michigan United States Technion - Israel Institute of Technology Illinois Institute of Technology United States

Implicit bias describes the phenomenon where optimization-based training algorithms, without explicit regularization, show a preference for simple estimators even when more complex estimators have equal objective values. Multiple works have developed the theory of implicit bias for binary classification under the assumption that the loss satisfies an exponential tail property. However, there is a noticeable gap in analysis for multiclass classification, with only a handful of results which themselves are restricted to the cross-entropy loss. In this work, we employ the framework of Permutation Equivariant and Relative Margin-based (PERM) losses [Wang and Scott, 2024] to introduce a multiclass extension of the exponential tail property. This class of losses includes not only cross-entropy but also other losses. Using this framework, we extend the implicit bias result of Soudry et al. [2018] to multiclass classification. Furthermore, our proof techniques closely mirror those of the binary case, thus illustrating the power of the PERM framework for bridging the binary-multiclass gap. © 2024, CC BY-NC-SA.

关键词： optimization algorithms