A new algorithm reduces online eigenvector computation time while maintaining optimal performance.
problem Online learning of top eigenvectors in both adversarial and stochastic settings.
method Follow the Compressed Leader (FTCL) framework, compressing the matrix strategy to dimensions 3 (adversarial) and 1 (stochastic).
result Achieves optimal regret without sacrificing running time, resolving open questions.
A new method detects long-range cross correlations in complex systems.
problem Detecting long-range cross correlations in complex systems.
method Joint multifractal analysis based on wavelet leaders (MF-X-WL).
result MF-X-WL detects cross correlations in synthetic and real-world data.
New clustering method for symbolic data combines leaders and agglomerative approaches.
problem Clustering of symbolic data with modal values.
method Proposed a clustering criterion function and leaders clustering method.
result Efficiently solves clustering problems with large data sets.
A new algorithm for deep learning training reduces communication costs and improves convergence.
problem Training deep learning models efficiently with limited communication.
method Leader Stochastic Gradient Descent (LSGD) combines local and global leaders' gradients to update workers.
result LSGD outperforms existing methods in distributed training of convolutional neural networks.
Characterizes preferences for decision-making under uncertainty using a leader-follower game model.
problem Decision-making under uncertainty and ambiguity aversion.
method Characterizes niveloidal preferences through a leader-follower game model, satisfying specific axioms.
result The leader's strategy space can serve as an ambiguity aversion index.
We introduce CSE for MLSF games and devise online learning algorithms for achieving no-external Stackelberg-regret.
problem Learning equilibrium in leader-follower games with noisy bandit feedback.
method Proposed Correlated Stackelberg Equilibrium (CSE) and online learning algorithms balancing exploration and exploitation.
result Achieves no-external Stackelberg-regret, converging to approximate CSE.
Investors with asymmetric information play a game to optimize their portfolios.
problem Two investors with different information levels compete in portfolio selection.
method Modelled as a Stackelberg game with entropy-regularized mean-variance objectives.
result Equilibria exist where follower's strategy depends on leader's actions.
New RL algorithms learn QSE from strategic feedbacks with sample efficiency.
problem Learning QSE in Markov games with strategic feedbacks.
method Proposes sample-efficient algorithms for online and offline settings, combining quantal response model learning and RL.
result Achieves sublinear regret bounds and quantifies model uncertainty.
Study leader-follower games with terminal state constraints using McKean-Vlasov SDEs.
problem Leader-follower games with terminal state constraints.
method Linear McKean-Vlasov forward-backward SDEs, existence and uniqueness results, convergence results.
result Existence and uniqueness of solutions for leader-follower games with constraints.
Improved theoretical guarantees for Top Two algorithms.
problem Theoretical support for best arm identification with bounded distributions.
method General analysis of Top Two methods, identifying desirable properties and replacing sampling step.
result Theoretical support for Top Two algorithms with bounded distributions.
Using a two-point correlation technique, we study emergence of market efficiency in the emergent Russian futures market by focusing on lagged correlations. The correlation strength of leader-follower effects in the lagged inter-market correlations on the hourly time frame is seen to be significant initially (2009-2011)…
Study of 2 i m e s 2 2 imes 2 2 im es 2 zero-sum games with noisy observations and commitments.
problem Analyzing 2 i m e s 2 2 imes 2 2 im es 2 zero-sum games with noisy observations and commitments. method Modeling a 2 i m e s 2 2 imes 2 2 im es 2 zero-sum game with a leader committing to a strategy and a follower observing a noisy version of the leader's action. result Observing the leader's action is either beneficial or immaterial for the follower, and the equilibrium payoff is bounded.
Transformers cluster meaningless words around leaders for sentiment analysis.
problem Capturing context in sentiment analysis using transformers.
method Characterized transformers with hardmax self-attention and normalization, showing asymptotic convergence to clustered equilibrium.
result Transformers can effectively capture context by clustering meaningless words around leader words.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of O ( n m ( d log ( d ) + m 5 / 6 ) ) \mathcal{O}(\sqrt{nm}(\sqrt{d\log(d)}+m^{5/6})) O ( nm ( d log ( d ) + m 5/6 )) in adversarial setting and logarithmic regret in stochastic setting. Neural operators approximate Stackelberg game solutions.
problem Intractability of follower's best-response operator in dynamic Stackelberg games.
method Used attention-based neural operators to approximate the best-response operator.
result Approximate best-response operator yields close game value.
Game theory approach to predicting and responding to interventions based on causal relationships.
problem Optimizing predictions and interventions in response to observational data.
method Prediction-intervention game framework, focusing on invariant subsets of covariates.
result Stable-blanket predictors are optimal for certain follower objectives and under specific conditions.
New algorithm optimizes multi-armed bandits with low computational cost.
problem Optimizing multi-armed bandits with low computational cost.
method Proposes a new FTPL algorithm with optimistic principle for ambiguity.
result Unified regret analysis and low computational costs.
Paper disproves symmetry of stars at infinity in a specific graph.
problem Symmetry of stars at infinity in a specific graph.
method Defined incidence geometry of stars at infinity; provided an example.
result Relation of one boundary point being included in a star of another is not symmetric.
FTPL policy achieves best-of-both-worlds regret in decoupled bandits with reduced computational cost.
problem Decoupled multi-armed bandit problem with observed and unobserved losses.
method Follow-the-Perturbed-Leader (FTPL) policy that avoids convex optimization and resampling.
result Achieves constant regret in stochastic regime and optimal O ( K T ) O(\sqrt{KT}) O ( K T ) regret in adversarial regime. SLHF uses sequential game theory to optimize preferences from human feedback.
problem Optimizing preferences from human feedback in sequential settings.
method SLHF frames the problem as a sequential-move game between Leader and Follower, decomposing the optimization into refinement and adversarial optimization.
result SLHF achieves strong alignment across diverse preference datasets and scales to large models.
CB-RL solves complex decision-making problems with contextual information and exogenous events.
problem Optimal policy in strategic decision-making problems that depend on environmental configuration and exogenous events.
method Contextual Bilevel Reinforcement Learning (CB-RL) with a stochastic Hyper Policy Gradient Descent (HPGD) algorithm.
result Demonstrated convergence and performance of the HPGD algorithm for reward shaping and tax design.
Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.
problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.
method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.
result BOBW guarantees for FTPL with Pareto perturbations for any α > 1 α>1 α > 1 . New algorithm reduces online learning iterations by a factor of T^2/3.
problem Efficiency in online learning with smooth cost functions.
method Follow-the-Perturbed-Leader method using online primal-dual framework.
result Guaranteed T^2/3 regret for general online convex optimization.
New mechanism designs regulate herding in financial markets.
problem Herding causes irrational market decisions and volatility.
method A trilateral game framework based on optimal control theory.
result Effective mechanisms improve social welfare.
New algorithm reduces sample complexity for Top Two method.
problem Fixed-confidence best arm identification for Top Two methods.
method UCB-based Top Two algorithm for non-asymptotic analysis.
result First non-asymptotic upper bound on expected sample complexity.
FTPL method shows near-optimal regret bounds for AMDPs with bandit feedback.
problem Minimizing regret in AMDPs with adversarial losses and bandit feedback.
method Follow-the-Perturbed-Leader (FTPL) method for AMDPs.
result FTPL achieves near-optimal regret bounds for AMDPs with bandit feedback.
Network analysis reveals changing cryptocurrency market leaders.
problem Understanding evolving cryptocurrency market leaders and their influence.
method Hourly-resolution data and Kendall's Tau correlation for network analysis.
result Pearson's correlation underestimates market dynamics; FTT and FTX were key during the 2021 bull run.
Diestel-Leader graphs are neither hyperbolic nor CAT(0), so their visual boundaries may be pathological. Indeed, we show that for d > 2 d>2 d > 2 , ∂ DL d ( q ) \partial\text{DL}_d(q) ∂ DL d ( q ) carries the indiscrete topology. On the other hand, ∂ DL 2 ( q ) \partial\text{DL}_2(q) ∂ DL 2 ( q ) , while not Hausdorff, is T 1 T_1 T 1 , totally disconnected, and compact. Since $\text{D…
LEASGD improves privacy-preserving decentralized learning with lower communication costs.
problem Achieving efficient and private decentralized learning.
method Proposes LEASGD, a Leader-Follower Elastic Averaging Stochastic Gradient Descent algorithm.
result LEASGD outperforms state-of-the-art algorithms in terms of lower loss and reduced communication costs.
Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of O ( d n ln n ) \mathcal{O}(d\sqrt{n \ln n}) O ( d n ln n ) for hypercube and ℓ 2 \ell_2 ℓ 2 ball. Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves O ( K T ) \mathcal{O}(\sqrt{KT}) O ( K T ) regrets in adversarial bandits. We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones. Our framework also captures such "unort…
Paper finds political networks reduce bond issuance costs in China.
problem The financial value of within-government political networks in China.
method Using municipal leaders' working experience to measure political networks, the study examines the effect on bond issuance yield spreads.
result Political networks reduce bond issuance yield spreads by improving issuer credit ratings, especially in less developed financial markets.
FTPL achieves optimal regret in online non-convex learning.
problem Online non-convex learning with non-convex losses.
method Follow the Perturbed Leader (FTPL) algorithm.
result FTPL achieves optimal regret rate of O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) . The Shannon theorem is extended to locally compact groups.
problem Identifying the Poisson boundary of locally compact groups.
method Random walks and Shannon-McMillan-Breiman theorem.
result Generalized criteria for identifying Poisson boundaries.
Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
Paper studies zero-sum games with noisy observations and identifies equilibrium conditions.
problem Zero-sum games with noisy observations of the leader's actions.
method Analyzes the equilibrium of games with noisy action observability, identifies necessary conditions for uniqueness, and investigates the cardinality of best responses.
result The noisy observations significantly impact the cardinality of the follower's set of best responses, and under certain conditions, this set becomes a singleton almost surely.
We fill a void in merging empirical and phenomenological characterisation of the dynamical phase transitions in complex systems by identifying three of them on real-life financial markets. We extract and interpret the empirical, numerical, and semi-analytical evidences for the existence of these phase transitions, by c…
NonSTOP predicts nonstationary time series with improved performance.
problem Handling nonstationary artifacts in time series data.
method Applying transformations to time series in the learning with experts setting.
result Improved prediction performance through transformations and follow-the-leader analysis.
Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has terrible performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We…
Two clustering algorithms optimize edge controller placement in wireless networks.
problem Optimizing edge controller placement in wireless edge networks.
method Deterministic annealing based clustering algorithms ECP-LL and ECP-LB.
result The algorithms achieve better balance between synchronization and delay costs.
Proposes a new training algorithm for zero-sum games to avoid convergence issues.
problem Gradient-based training leads to weak convergence and cyclic dynamics in zero-sum architectures.
method Follow the perturbed leader algorithm with neural mediating agent.
result Guarantees convergence to mixed Nash equilibrium without cyclic behaviors.
Paper provides faster spectral sparsification method.
problem Efficiently constructing spectral sparsifiers.
method Connecting sparsification to regret minimization via MWU.
result Linear-sized spectral sparsifiers constructed in almost-quadratic time.
Method detects phase transitions in financial markets using eigenvalue decomposition.
problem Detecting tipping points and fluctuation patterns in financial markets.
method Eigenvalue decomposition and eigen-entropy from cross-correlation matrix.
result Market events undergo phase separation and order-disorder transitions.
This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.
problem Optimizing regret in adversarial and stochastic m m m -set semi-bandit problems. method Extending FTPL with geometric resampling (GR) to m m m -set semi-bandits and analyzing its performance. result FTPL with Fréchet and Pareto distributions achieves O ( m d T ) O(\sqrt{mdT}) O ( m d T ) regret in adversarial setting and logarithmic regret in stochastic setting. New aggregation strategy handles unbounded losses with regret bounds.
problem Online optimization with unbounded loss functions.
method Follow The Regularized Leader (FTRL) with φ-divergence.
result Worst regret bound for unbounded losses with alternative divergences.
The paper explores how regularization can lead to convergence in imperfect information games.
problem Finding equilibrium in imperfect information games with imperfect information.
method Investigates Follow the Regularized Leader dynamics and how adding a regularization term can lead to strong convergence guarantees.
result The approach leads to algorithms that converge exactly to the Nash equilibrium in imperfect information games.