Efficiently trains large GMMs with millions to billions of parameters.
problem Training large Gaussian Mixture Models (GMMs) is computationally expensive.
method Derives a variational approximation integrated with mixtures of factor analyzers (MFAs) to reduce complexity.
result Sublinear scaling in training GMMs, achieving significant speed-ups.
Federated learning algorithm improves with intermittent client availability.
problem Performance degradation in Federated Averaging due to client availability changes.
method Federated Latest Averaging (FedLaAvg) uses latest gradients from all clients, even when unavailable.
result FedLaAvg achieves sublinear speedup compared to classical Federated Averaging.
The paper shows how sublinear biLipschitz equivalences affect Morse boundaries of metric spaces.
problem Understanding how sublinear biLipschitz equivalences affect Morse boundaries of metric spaces.
method Defining sublinear biLipschitz equivalence and Morse boundaries, proving invariance under SBEs, using sublinear rays.
result κ-Morse boundaries of proper geodesic metric spaces are invariant under suitable sublinear biLipschitz equivalences.
Sketch-GNN reduces GNN training time and memory usage to sublinear scales.
problem Training GNNs on large graphs is computationally expensive and memory-intensive.
method Develops a sketch-based algorithm that trains GNNs on compact sketches of graph adjacency and node embeddings.
result Training time and memory usage grow sublinearly with respect to graph size.
Study online RL with mismatched dynamics, achieving sublinear regret.
problem Exploration challenges in online RL with mismatched training and deployment dynamics.
method Introduce supremal visitation ratio, propose efficient algorithm with f f f -divergence. result Achieves sublinear regret in online RMDPs with optimal dependence on supremal visitation ratio and interaction episodes.
Sublinear LSVI via LSH reduces runtime to sublinear in actions.
problem Efficiently estimating value functions in reinforcement learning with sublinear runtime.
method Formulated as approximate maximum inner product search, used LSH to solve with sublinear time complexity.
result Sublinear runtime while maintaining LSVI's regret.
The aim of this paper is to introduce the sublinear Higson corona and show that the sublinear Higson corona of Euclidean cone of P and X is decomposed into the product of P and that of X. Here P is a compact metric space and X is unbounded proper metric space. For example, the sublinear Higson corona of n-dimensional E…
New model for Knightian uncertainty with jumps.
problem Knightian uncertainty and non-linear jumps.
method Probabilistic construction of non-linear affine processes with jumps.
result Tractable model for Knightian uncertainty with sublinear expectations.
We give a proof of the sublinear tracking property for sample paths of random walks on various groups acting on spaces with hyperbolic-like properties. As an application, we prove sublinear tracking in Teichmueller distance for random walks on mapping class groups, and on Cayley graphs of a large class of finitely gene…
Two preprocessing techniques reduce neural network training cost.
problem Training over-parameterized neural networks efficiently.
method Two novel preprocessing techniques to reduce training cost.
result Training cost reduced to sublinear per iteration.
We provide a general construction of time-consistent sublinear expectations on the space of continuous paths. It yields the existence of the conditional G-expectation of a Borel-measurable (rather than quasi-continuous) random variable, a generalization of the random G-expectation, and an optional sampling theorem that…
Dividing local Gaussian processes improve real-time prediction efficiency.
problem Efficient online prediction for large data sets.
method Iterative data-driven division of input space for sublinear computational complexity.
result Sublinear computational complexity in real-time prediction.
New sublinear sketches improve ANN and KDE for massive data streams.
problem Efficiently approximate nearest neighbors and kernel density estimation in large datasets.
method Developed sublinear space and query time algorithms for ANN and A-KDE in streaming and sliding-window models.
result Achieved near-optimal trade-offs between memory size and approximation error for ANN.
Sublinear functionals of random variables are known as sublinear expectations; they are convex homogeneous functionals on infinite-dimensional linear spaces. We extend this concept for set-valued functionals defined on measurable set-valued functions (which form a nonlinear space), equivalently, on random closed sets. …
The paper develops methods for time-varying constrained online convex optimization.
problem Time-varying loss and constraint functions in online convex optimization.
method Model-based augmented Lagrangian methods (MALM) for time-varying and delayed feedback.
result Sublinear regret and constraint violation for both time-varying and delayed feedback scenarios.
Paper presents a new training method for overparametrized neural networks that reduces time per iteration.
problem Scalability issue in training overparametrized neural networks.
method Uses a new view of neural networks as binary search trees, modifying a small subset of nodes per iteration.
result Reduces amortized time per iteration to m 1 − α n d + n 3 m^{1-α} n d + n^3 m 1 − α n d + n 3 from previous m n d + n 3 mnd + n^3 mn d + n 3 . For α ∈ ( 1 , 2 ) α\in (1,2) α ∈ ( 1 , 2 ) , we present a generalized central limit theorem for α α α -stable random variables under sublinear expectation. The foundation of our proof is an interior regularity estimate for partial integro-differential equations (PIDEs). A classical generalized central limit theorem is recovered as a special case, p…
New algorithms for constrained online optimization with memory and predictions.
problem Control of constrained dynamical systems and scheduling with reconfiguration budgets.
method Proposed algorithms achieving sublinear regret and constraint violation under time-varying constraints, both with and without predictions.
result First algorithms achieving sublinear regret and constraint violation in constrained online optimization with memory.
Memory-limited learning tackles adversarial bandits with reduced storage.
problem Adversarial bandit problem with limited memory storage.
method Hierarchical learning policy with sublinear memory requirement.
result Established sublinear regret bounds for weak and shifting regrets.
Sharp Liouville theorem for minimal graphs on manifolds with nonnegative Ricci curvature.
problem Characterizing smooth solutions to minimal hypersurface equations on manifolds with nonnegative Ricci curvature.
method Gradient estimate for minimal graphs over Σ Σ Σ with small linear growth of the negative parts of graphic functions via iteration. result Every smooth solution u u u to minimal hypersurface equation on Σ Σ Σ is a constant provided u u u has sublinear growth for its negative part. New method connects CAT(0) spaces to hyperbolic spaces.
problem Injecting sublinear Morse boundaries into Gromov boundaries.
method Developed curtain machinery to characterize sublinear Morse properties.
result Continuous injection of sublinear Morse boundaries into Gromov boundaries.
Study online learning in unknown Markov games with sublinear regret.
problem Online learning in unknown Markov games with unobservable opponents.
method Introduced an algorithm achieving sublinear regret against the minimax value.
result First sublinear regret bound for unknown Markov games, independent of action spaces size.
Open problem seeks an online learning algorithm for binary classification.
problem Existence of an online learning algorithm for binary classification with sublinear mistakes.
method Assumption of sequence allowing learning algorithm's existence.
result Specific condition determines sequence's learnability.
Average signature of 2-bridge knots approximates sqrt(2c/π).
problem Estimating the average signature and 4-genus of 2-bridge knots.
method Developed a model for 2-bridge knot diagrams indexed by crossing number, and used it to derive upper bounds for the average 4-genus.
result Upper bound for the average 4-genus of a 2-bridge knot is 9.75c/log c.
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function cha…
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
Extends tracking guarantees for time-varying variational inequalities.
problem Tracking solutions of time-varying variational inequalities.
method Extends existing results to sublinear solution paths and periodic problems.
result Discrete dynamical systems of periodic time-varying VI can exhibit chaotic behavior or converge to the solution.
Geodesic loops escape from balls at a sublinear rate imply virtually abelian fundamental group.
problem Understanding fundamental groups of open manifolds with nonnegative Ricci curvature.
method Generalizing the Cheeger-Gromoll splitting theorem to sublinear escape rates.
result Fundamental groups of open manifolds with nonnegative Ricci curvature are virtually abelian if geodesic loops escape sublinearly.
Develops geometric foundations for sublinear Morse boundaries in mapping class groups and Teichmüller spaces.
problem Capturing generic directions in mapping class groups and Teichmüller spaces.
method Develops tools for modeling hulls of median rays in hierarchically hyperbolic spaces via CAT(0) cube complexes.
result Sublinear Morse boundaries are visibility spaces and admit continuous equivariant injections into the boundary of the curve graph.
LaPSRL achieves optimal regret for isoperimetric RL distributions.
problem Designing RL algorithms with sublinear regret for non-log-concave distributions.
method Posterior Sampling (PSRL) and Langevin sampling (LaPSRL) for isoperimetric distributions.
result LaPSRL achieves order-optimal regret and subquadratic complexity.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
LIBO optimizes repeated bandit tasks without prior knowledge or regret.
problem Optimizing repeated bandit tasks without prior knowledge or regret.
method LIBO sequentially meta-learns a kernel to adapt to the environment and solve tasks with the latest estimate.
result LIBO achieves sublinear lifelong regret, converging to oracle performance as more tasks are solved.
GP-UCB resolves sublinear regret for kernelized bandits.
problem Minimizing regret in kernelized bandit problems.
method Using a new regularization technique for kernel ridge estimators, improving GP-UCB's sublinear regret rate.
result GP-UCB achieves nearly optimal sublinear regret for the Matérn kernel.
New data structure identifies close match from multiple distributions.
problem Identify the closest distribution to a given sample.
method Developed a sublinear-time data structure for identifying the closest distribution.
result First data structure that identifies the closest distribution in sublinear time.
AgentNet is a graph neural network that learns to walk graphs intelligently, outperforming traditional methods.
problem Graph-level tasks, especially distinguishing and classifying graphs.
method AgentNet uses a computational model inspired by sublinear algorithms, where neural agents walk the graph and collectively decide the output.
result AgentNet can distinguish and separate graphs that are hard to distinguish, outperforming traditional graph neural networks.
Develops sublinear Morse theory in symmetric spaces.
problem Understanding sublinear Morse properties in symmetric spaces.
method Theory of sublinearly Morse boundary and lemma in higher rank symmetric spaces.
result Proves sublinear Morse lemma in higher rank symmetric spaces.
Sharp stability threshold found for deep residual architectures.
problem Ensuring stable training and inference in deep residual networks.
method Sublinear-growth principle and optimal-control analysis.
result Stable training condition: input-magnitude exponent q ≤ 1.
Paper presents a faster classical algorithm for principal component regression.
problem Efficiently solving principal component regression problems.
method Uses quantum-inspired linear algebra techniques.
result Achieves polylogarithmic runtime, significantly faster than state-of-the-art.
The paper connects discrete choice models to multi-armed bandit algorithms with sublinear regret bounds.
problem Optimizing user choices in a multi-armed bandit setting.
method Establishes connections between discrete choice models and multi-armed bandit algorithms, providing sublinear regret bounds and novel algorithms.
result Sublinear regret bounds for a family of algorithms, including the Exp3 algorithm.
New framework guides resource usage to achieve sublinear regret in adversarial settings.
problem Achieving sublinear regret in online decision making with changing reward and cost distributions.
method General primal-dual methods guided by spending plans that ensure balanced resource usage.
result Achieves sublinear regret with respect to spending plans that balance resource usage.
Two-stage mechanism designs reduce regret in recommender systems with stochastic covariates.
problem Designing effective recommender systems with user covariates sampled online.
method Two-stage algorithm integrating incentivized exploration with offline learning methods.
result Achieves sublinear regret while maintaining incentive compatibility.
The output scores of a neural network classifier are converted to probabilities via normalizing over the scores of all competing categories. Computing this partition function, Z Z Z , is then linear in the number of categories, which is problematic as real-world problem sets continue to grow in categorical types, such as …
New algorithm improves game learning with randomised optimism.
problem Learning in matrix games with unknown payoffs and bandit feedback.
method Integrates evolutionary algorithms into bandit framework for randomised optimism.
result Achieves sublinear regret, outperforming classical methods.
The paper addresses pricing interest rate derivatives in markets with volatility uncertainty.
problem Pricing interest rate derivatives under uncertainty about volatility.
method Modeling volatility uncertainty with G-Brownian motion and defining forward sublinear expectation.
result Developed robust pricing formulas for interest rate derivatives.
We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the L 1 L_1 L 1 norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fr…
Probabilistic programming languages can simplify the development of machine learning techniques, but only if inference is sufficiently scalable. Unfortunately, Bayesian parameter estimation for highly coupled models such as regressions and state-space models still scales poorly; each MCMC transition takes linear time i…
Study on scheduling jobs with unknown types, achieving sublinear excess cost.
problem Optimizing job scheduling with unknown job types and varying durations.
method Design of algorithms for non-preemptive and preemptive scenarios, proving lower bounds.
result Preemptive algorithms can significantly outperform non-preemptive ones when job types have distinct durations.
Paper proposes quantum methods for optimizing machine learning functions.
problem Machine learning optimization problem
method Average approach and Partial Swap Test Cut-off method (PSTC)
result Potential to improve PSTC to O ( ∣ Θ ∣ ⋅ s u b l i n e a r N ) O(\sqrt{|Θ|} \cdot sublinear \ N) O ( ∣Θ∣ ⋅ s u b l in e a r N )