Proofs non-realizability of mapping class group via homeomorphisms, resolves Thurston's conjecture.
problem Non-realizability of mapping class group via homeomorphisms
method Short and elementary proof, rigidity results for actions on Euclidean spaces
result Proof of non-realizability of mapping class group via homeomorphisms
We construct non-constructible simplicial d-spheres with d+10 vertices and non-constructible, non-realizable simplicial d-balls with d+9 vertices for d≥3.
The pure braid group cannot be realized as area-preserving homeomorphisms.
problem Realizing the pure braid group inside area-preserving homeomorphisms.
method Using rotation numbers to show non-realizability.
result The pure braid group has no realization inside area-preserving homeomorphisms.
P. M. Akhmetiev used a controlled version of the stable Hopf invariant to show that any (continuous) map N -> M between stably parallelizable compact n-manifolds, n\ne 1,2,3,7, is realizable in R^{2n}, i.e. the composition of f with an embedding M\subset R^{2n} is C^0-approximable by embeddings. It has been long believ…
New algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
New active learning framework for multiclass classification beyond realizability assumption.
problem Active learning in non-realizable settings with convex model classes.
method Surrogate risk minimization, epoch-based fitting, aggregation of models.
result Achieves label and sample complexity comparable to prior work in non-realizable settings.
New method for distributional off-policy evaluation using Bellman residual minimization.
problem Learning return distribution from offline data generated by a different policy.
method Energy Bellman Residual Minimizer (EBRM) method.
result Established finite-sample error bound for EBRM estimator.
Paper solves the Hurwitz existence problem using fiber products.
problem Determining when a combinatorial map datum corresponds to a holomorphic map.
method Using fiber products of holomorphic maps between Riemann surfaces.
result Proves non-realizability of many branch data and constructs new data.
New DP algorithms achieve near-optimal regret bounds for online learning problems.
problem Online learning problems with zero-loss solutions and differential privacy constraints.
method Developed new Differentially Private algorithms with near-optimal regret bounds.
result Achieved near-optimal regret bounds for various online prediction and convex optimization problems.
The article enumerates doubly symmetric diagrams for knots up to 18 crossings.
problem Enumerating doubly symmetric diagrams for knots.
method Developed an enumeration strategy for prime knots given by doubly symmetric diagrams.
result Determined all cases of doubly symmetric diagrams up to 18 crossings.
Nielsen realization problem for the mapping class group Mod(Sg) asks whether the natural projection pg:Homeo+(Sg)→Mod(Sg) has a section. While all the previous results use torsion elements in an essential way, in this paper, we focus on the much more difficult problem of realization of…
In this paper, we will show that the projection Homeo+(Dn2)→Bn does not have a section; i.e. the braid group Bn cannot be geometrically realized as a group of homeomorphisms of a disk fixing the boundary point-wise and n marked points in the interior as a set. We also give a new proof of a result o…
Study shows certain mapping class groups cannot be realized as subgroup of homeomorphisms.
problem Proving non-realizability of specific mapping class groups.
method Analyzing compactly supported and full mapping class groups of surfaces with genus 3 or order 6 symmetries.
result Proven non-realizability of mapping class groups for surfaces with genus 3 or order 6 symmetries.
Paper tackles MLR prediction error without assuming realizable models.
problem Prediction error in mixture of linear regressions without realizable assumptions.
method Developed algorithms for list-decoding MLR predictions and minimized empirical risk.
result Alternating minimization algorithm finds best fit lines in non-realizable settings.
For every compact surface S of finite type (possibly with boundary components but without punctures), we show that when n is sufficiently large there is no lift σ of the surface braid group Bn(S) to Diff(S,n), the group of C1 diffeomorphisms preserving n marked points and restricting to t…
We present a short exposition of the following results by S. Parsa. Let L be a graph such that the join L∗{1,2,3} (i.e. the union of three cones over L along their common bases) piecewise linearly (PL) embeds into R4. Then L admits a PL embedding into R3 such that any two disjoint cycles…
We investigate active learning by pairwise similarity over the leaves of trees originating from hierarchical clustering procedures. In the realizable setting, we provide a full characterization of the number of queries needed to achieve perfect reconstruction of the tree cut. In the non-realizable setting, we rely on k…
We study a recent model of collaborative PAC learning where k players with k different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a classifier that has very small error on all tasks, there is a collaborative algorithm that finds a single classifi…
Generalizes cohomology ring result for combinatorial line arrangements.
problem Cohomology ring of boundary manifold for combinatorial line arrangements.
method Introduced boundary manifold, constructed homology cycles, computed cohomology ring.
result Cohomology ring of boundary manifold is isomorphic to double of Orlik-Solomon algebra.
The paper explores embedding Ricci flow solutions in flag manifolds.
problem Realizing Ricci flow solutions as embedded submanifolds.
method Investigation of invariant metrics in flag manifolds, proving global attractors and non-realizable collapses.
result Certain Ricci flow collapses cannot be embedded in Euclidean spaces.
New bandit algorithm works without realizability assumption.
problem Contextual bandit problems without realizability assumption.
method Computes a constrained regression problem in every epoch, ensuring similar regret guarantees as realizability-based algorithms.
result Ensures similar regret guarantees as realizability-based algorithms, up to a misspecification term.
The study provides error bounds for the generalized Lasso with sub-exponential data.
problem Analyzing the generalized Lasso under sub-exponential data distributions.
method Non-asymptotic analysis using generic chaining-based proof strategy.
result Error bounds for the generalized Lasso can be controlled by two complexity parameters.
New algorithm trains ReLU gates provably in linear time.
problem Training ReLU gates in realizable settings with mild conditions.
method Iterative stochastic algorithm with moment assumptions.
result First recovery of true labels under data-poisoning attacks.
Solves open problem on universally consistent online learning with unbounded losses.
problem Open problem on universally consistent online learning with unbounded losses.
method Constructs random measurable partitions of the instance space.
result Simple memorization rule is optimistically universal for any unbounded loss.
Algorithm learns arbitrary ReLU neurons under Gaussian inputs.
problem Learn an arbitrary ReLU activation over Gaussian marginals.
method Statistical Query (SQ) algorithm that outputs a ReLU activation achieving O(OPT)+ε loss. result First constant factor approximation for arbitrary bias in polynomial time.
This paper studies universal rates of ERM for binary classification under agnostic learning.
problem The challenge of achieving universal rates of ERM for binary classification under agnostic learning.
method The paper explores the agnostic universal rates of ERM for binary classification, revealing three possible rates: e−n, o(n−1/2), or arbitrarily slow. result The paper provides a complete characterization of which concept classes fall into each of the three categories of agnostic universal rates.
This study tightens bounds on how GD and SGD generalize in smooth convex optimization problems.
problem Understanding how GD and SGD generalize in smooth stochastic convex optimization problems.
method Provided tight excess risk lower bounds for GD and SGD under different conditions.
result Lower bounds suggest overfitting occurs and gaps remain in some cases.
To a branched cover between closed, connected and orientable surfaces one associates a "branch datum", which consists of the two surfaces, the total degree d, and the partitions of d given by the collections of local degrees over the branching points. This datum must satisfy the Riemann-Hurwitz formula. A "candidate su…
New algorithm optimizes beam and rate allocation in mmWave systems for multiple users.
problem Optimizing beam and rate allocation in mmWave systems for multiple users with limited feedback.
method Introducing SAT-CTS, a combinatorial semi-bandit policy with satisficing objective.
result SAT-CTS achieves finite-time regret bounds and reduces satisficing regret in mmWave systems.
This work characterizes the benefits of averaging schemes widely used in conjunction with stochastic gradient descent (SGD). In particular, this work provides a sharp analysis of: (1) mini-batching, a method of averaging many samples of a stochastic gradient to both reduce the variance of the stochastic gradient estima…
New learner achieves optimal agnostic error in small error regime.
problem Optimizing agnostic learning in the small error regime.
method Careful aggregations of ERM classifiers.
result Achieves error $c \cdot τ+ O \left(\sqrt{\frac{τ(d + \log(1 / δ))}{m}} + \frac{d + \log(1 / δ)}{m}
ight)$, matching lower bound when τ≈d/m.